At 03:16 PM 4/19/96 -0700, Hal <hfinney@shell.portal.com> wrote:

Choose x bits of good random numbers (x defined below), calling it X. Seed an MD5 iteration or some other crypto RNG with X and generate random starting points for p and q. Search for the next primes after these starting points to get p and q, multiply to get n, and choose the first exponent >= 3 or 17 or 65537 (choose by taste) as e. Burn p and q but memorize the random seed X.

An interesting approach; given enough spare computing, the passphrase is the key. Remember to transform the passphrase space into some wide-enough space that it will include a bunch of primes, to avoid having multiple passphrases generating the same prime. Primes density is approximately log n (ln n?), e.g. 1/512 for a 512-bit number, so a crude approach like using a 128-bit hash as the most significant bits should do fine.

The main question is, can x be both long enough that it is not the weakest length in factoring, say, a 1024 bit key, while being short enough that it can be memorized? My guess is that x must be 80-120 bits, somewhere in there. This would be 6 to 9 words chosen from a 16K word list: marginaly doable.

Almost by definition, you want at least 128 bits, since you'll probably be using the public key crypto to protect a 128-bit session key. (Keys for signatures may need a bit less slack, though I'd still be wary of <90 bits.) Also, if you're starting by taking an MD5 of the passphrase (after looking up the words in the dictionary or whatever), you're limited to 128 bits of entropy; it's probably worth using SHA, or at least picking p from the MD5 and q from the MD5 of the reverse of the passphrase. # Thanks; Bill # Bill Stewart, stewarts@ix.netcom.com, +1-415-442-2215