From: collins@newton.apple.com (Scott Collins)
Date: Sat, 28 Aug 93 21:18:49 PDT
To: Network Demon <demon@aql.gatech.edu>
Subject: Re: Total RSA in PGP
Message-ID: <9308290413.AA21961@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


  >Am I mistaken in believing RSA is more secure than the present hybrid?

.....SHORT ANSWER.....

You are mistaken.


.....MEDIUM ANSWER.....

You are mistaken not because the statement 'RSA is more secure than the
present hybrid' is false, but because it is a mistake to put your belief in
this statement, which has not been proved true.  RSA alone would represent
a great increase in computational effort, without risk of a decrease in
security, after which you couldn't prove you were any better off (though,
in practice, against currently known attacks, and with a large key, you
might be).


.....LONG ANSWER.....

RSA alone is no _less_ secure than the PGP's combination of RSA and IDEA:
if you can break RSA, you can extract the IDEA key and decipher the
message; if you can break IDEA, you don't need the key.

I am guessing that you share a widely echoed predjudice that public-key
ciphers are better than secret-key ciphers (I apologize if I have
mis-labeled you :).  Public-key ciphers have gained a reputation for being
more secure, as a class, than secret-key ciphers.  Perhaps because
public-key ciphers afford 'better' key management, the world at large has
gotten the impression that they provide 'better' security.  Public-key
ciphers as a class are _not_ more secure than secret-key ciphers.  One
counter example, which periodically rears its ugly head here, is the (truly
random) one-time-pad.  This secret-key cipher offers perfect security in
the Shannon sense.  No public-key cipher can make that claim.

To prove RSA _more_ secure than the hybrid, RSA must be proved more secure
than IDEA.  Unfortunately, we don't really know how secure the RSA
algorithm is (or IDEA, for that matter).  It is known that RSA is no _more_
secure than factoring a component of the public key (readily available to
an attacker).  To my knowledge, it has not been proved that either a) RSA
is at least this secure; or b) factoring is hard.

Despite a paucity of formal proof, I know of know better attack on a
message enciphered with well chosen keys than factoring, which both man and
machine currently find taxing.  RSA with well chosen keys is 'empirically'
computationally secure.

While IDEA has been designed specifically to resist differential
cryptanalysis (thanks to those who pointed me to the IDEA papers explaining
this), more formal proof of its security awaits further understanding of
the information theory aspects of its foundation: mixing operations from
incompatible groups.  In the end, IDEA is also 'empirically'
computationally secure.

I know of no comparisons of the security offered by RSA and IDEA against
practical attacks.


.....FINAL ANSWER.....

In theory: theory is as good as practice; but in practice... it isn't.


Hope this helps,

Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   1 Infinite Loop, MS 301-2C   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024/669687   catalyst@netcom.com