From: frantz@netcom.com (Bill Frantz)
Date: Thu, 25 Apr 1996 15:46:11 -0700 (PDT)
To: perry@piermont.com
Subject: Re: Golden Key Campaign
Message-ID: <199604252245.PAA14156@netcom9.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At  5:18 PM 4/25/96 -0400, Perry E. Metzger wrote:
>Bill Frantz writes:
>> 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?

I don't imply that.  I do think that the use of proof is of limited
applicability in demonstrating security.  Complex proofs can be as much in
doubt as complex computer programs.  Used within its limitations, proof is
very valuable, but too often its value is asserted beyond those
limitations.  The Varona case applies because of the common statement that
one time pads are the only provably secure crypto-system.


>> 7a) RSA is the best known public key algorithm.
>
>Meaningless and unimportant.

Not in terms of why people use RSA rather than some other algorithm.


>> 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.

Thanks for the information.  Schneier (V2) says that while Rabin and
Williams are provably as secure as factoring.  They, like RSA, are
completely insecure against a chosen cyphertext attack.  Correcting this
problem by using a one-way hashing function makes them no longer provably
as secure as factoring, although adding a random string does not have this
defect.

Rabin also has the problem, which Williams corrects, that each message has
four possible decypherments, and the user must select the correct one.

While these systems have a small theoretical advantage over RSA (their
provability), how much effort has been expended in examining them compared
with RSA?  Level of effort is important in determining "best vetted".  (I
realize that some efforts, such as research into factoring, apply to both
systems.)

Regards - Bill


------------------------------------------------------------------------
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