From: mccoy@ccwf.cc.utexas.edu (Jim McCoy)
Date: Sun, 28 Mar 93 19:49:13 PST
To: uni@acs.bu.edu (Shaen Bernhardt)
Subject: Re: PGP Secure?
In-Reply-To: <9303290550.AA41108@acs.bu.edu>
Message-ID: <9303290632.AA21124@tigger.cc.utexas.edu>
MIME-Version: 1.0
Content-Type: text


> 
> Forgive my slow math mind, but I pose the following question, knowing
> in advance that it's a FAQ, but I can't find an answer anywhere....
> 
> Given a brute force attack on ciphertext encrypted with PGP2.2
> using the 1024 bit key, how many operations are required to
> hit on the session key...?
> (The session key being used with the IDEA cipher)

This has been recently hashed over in sci.crypt.  Here are a few
generalities, read the articles in sci.crypt for the real numbers.

	-If you did 1000 attempts to break a 1024 bit RSA key every second
	and started your calculations at the beginning of the universe, you
	would still have several trillion years to go.
	-If you stored every attempted key in a single atom, you would run
	out of atoms in the universe long before you ran out of keys.

If I remeber correctly there are something like 10^152 primes possible with
a 512 bit key.  That is what most people refer to as a BIG number...  :)

> The real meat of this question boils down to: What are the capabilities
> currently, and what is required to brute force the various stages of PGP?

What it boils down to is that anyone who tried a brute-force attack on your
RSA key is either very stupid or hopes to be very lucky.  (very, very, very
lucky)  It would be easier for the person to track you down, put a gun to
your face and force you to disclose the message.  Barring any mathematical
miracle with regards to factoring large numbers, RSA using large keys is
safe from brute-force attack.


> Also:  What does 1024 bit refer to?  The IDEA session key? or the RSA key?

The RSA key.  It would probably be easier for someone to try to brute-force
your IDEA session key than your RSA key; but this would only give them one
message, while cracking a RSA key gives you all messages that have the
session key wrapped with that RSA keypair.

jim