From: Bill Stewart <stewarts@ix.netcom.com>
Date: Tue, 10 Jun 1997 16:26:18 +0800
To: "Robert A. Costner" <pooh@efga.org>
Subject: Re: PGP Key generation
In-Reply-To: <199706082051.VAA05211@server.test.net>
Message-ID: <3.0.1.32.19970610011235.0068f800@popd.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



At 07:05 PM 6/8/97 -0400, Robert A. Costner wrote:
>If I generate a personal PGP keypair on some machine it takes a specific 
>period of time to do the intensive calculations, let's assume ten minutes
for 
>this example.  If I needed 10,000 such individual keyspairs for a
unspecified 
>authentication attack, does this have to take 10,000 times 10 minutes (over 
>two months with this CPU), or is there a faster way to generate a large 
>number of keypairs to appear to be a large number of people.
>
>The larger question is since 10,000 unique written signatures seems to 
>indicate that 10,000 unique individuals exist, would 10,000 unique PGP 
>signatures also seem to indicate that these are not from the same person?

If you're concerned about legitimacy, independence of keys, etc.,
then doing them one at a time is the way to go.  However, if you're
just trying to gen up a bunch of keys to fake your way through an
authentication system that wants "different" keys, and you don't mind
a bit of coding or code-borrowing, you can do far better.

First of all, you can generate 10,000 different RSA keys by generating
~142 prime numbers and using combinations of two of them.
Furthermore, you don't need to generate good random numbers to seed
the prime number searcher, so you've gone from 10,000 randoms plus
10,000/P(prime) prime searches to 1 random plus 142/P(prime) prime searches.

However, your RSA keys may not even need to be that good,
depending on the authentication system you're trying to weasel into.
RSA uses n=pq, p and q prime, and ed==1 mod (p-1)(q-1),
where e and d are relatively prime to n (usually e is a small prime.)
So you could pick _one_ pair of primes and 10,000 values of e,
if the test doesn't mind that all the (e,n) pairs have the same n,
and the e's can be a table of the first 10,000 primes.
A cheap test might or might not notice, depending on whether it's
using PGP KeyID or fingerprint or some other hash.
(Since the keyID is "just the bottom few bits of the modulus",
a test using the KeyID would notice -- so you've got to social-engineer
them into using a "better" test with the length and fingerprint :-)

#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
#   (If this is a mailing list or news, please Cc: me on replies.  Thanks.)