From: Adam Shostack <adam@lighthouse.homeport.org>
Date: Sun, 3 Mar 1996 04:20:06 +0800
To: PADGETT@hobbes.orl.mmc.com (A. Padgett Peterson P.E. Information Security)
Subject: Re: Truelly Random Numbers
In-Reply-To: <960302142608.202017b7@hobbes.orl.mmc.com>
Message-ID: <199603022011.PAA16975@homeport.org>
MIME-Version: 1.0
Content-Type: text


A. Padgett Peterson P.E. Information Security wrote:

| >The number of randomly selected 768 bit primes that you would need for a
| >reasonable chance of a birthday collision is 1.708E104
| 
| True however the current mechanism of generating PGP keys which consists 
| primarily of pseudo-randomly pounding on a keyboard is hardly "truely random.
| 
| Have no idea of the true number but expect it to be significantly less than
| that quoted above, even for a 1024 bit key like mine.

	Accroding to Stephan Neuhaus's 'Statistical Properties of IDEA
session keys in PGP,' the session keys are very well distributed, when
tested for equidistribution and serial correlation.

	This does not demonstrate that the RSA keys are as well
distributed, but it does generate some confidence that the key
generation methods of PGP are not very broken.  Testing for RSA
generation would be more difficult, since there are some practical
difficulties in getting a large sample of RSA private keys.

Stephan Neuhaus is neuhaus@informatik.uni-kl.de.  He has a long (24
page), and short (8? page) version of the paper available.


Adam

-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume