Re: Golden Key Campaign

At  3:27 PM 4/25/96 -0400, Perry E. Metzger wrote:
>Bill Frantz writes:
>> I will add to Bill's list:
>> 
>> 7) RSA is the best known and vetted of the Public Key algorithms.
>
>Nota at all, Mr. Frantz. There are no proofs of security associated
>with RSA. Rabin has excellent proofs that breaking a message is
>strictly equivalent to factoring.

I do not equate good vetting with proofs of security.  Given the Verona
intercepts, I don't think there are any valid proofs of the security of
complete crypto-systems.  While anyone who can factor RSA keys can break
RSA, factoring has been intensively studied since RSA was published.  The
public information says that in spite of improvements, factoring is still a
hard problem.  If people in Maryland can factor big RSA keys, they're Not
Saying Anything.

So far, I'll stand by my two contentions:

7a) RSA is the best known public key algorithm.
7b) RSA is the best vetted public key algorithm.

Do you have any counter examples to help me change my mind?


------------------------------------------------------------------------
Bill Frantz       | The CDA means  | Periwinkle  --  Computer Consulting
(408)356-8506     | lost jobs and  | 16345 Englewood Ave.
frantz@netcom.com | dead teenagers | Los Gatos, CA 95032, USA

Bill Frantz writes:
> At  3:27 PM 4/25/96 -0400, Perry E. Metzger wrote:
> >Bill Frantz writes:
> >> I will add to Bill's list:
> >> 
> >> 7) RSA is the best known and vetted of the Public Key algorithms.
> >
> >Not at all, Mr. Frantz. There are no proofs of security associated
> >with RSA. Rabin has excellent proofs that breaking a message is
> >strictly equivalent to factoring.
> 
> I do not equate good vetting with proofs of security.  Given the Verona
> intercepts, I don't think there are any valid proofs of the security of
> complete crypto-systems.

In that case, why do you think that an RSA system would be better
implemented as a matter of necessity than a Rabin system?

> While anyone who can factor RSA keys can break
> RSA, factoring has been intensively studied since RSA was published.  The
> public information says that in spite of improvements, factoring is still a
> hard problem.  If people in Maryland can factor big RSA keys, they're Not
> Saying Anything.

You didn't hear what I said.

There is no proof that RSA is equivalent to factoring -- only a strong
belief. There may exist ways to break RSA that do not involve
factoring. Rabin, however, is provably equivalent to factoring.

> So far, I'll stand by my two contentions:
> 
> 7a) RSA is the best known public key algorithm.

Meaningless and unimportant.

> 7b) RSA is the best vetted public key algorithm.

Again, false. RSA has no proofs of security, and other systems have
far better proofs. RSA also leaks small bits of information like
parity that other systems do not leak. This is not to say that RSA is
bad, but its choice over, say, Rabin, at least for encryption, is
fairly abitrary.

Perry