On Mon, Jan 20, 2003 at 09:08:31PM -0500, Radia Perlman wrote: > [...] I was going to suggest something similar to what David Wagner > suggested, but with Scott telling Alice the modulus size and the > *high* order 64 bits (with the top bit constrained to be 1). I can > see how Alice can easily generate two primes whose product will have > that *high* order part, but it seems hard to generate an RSA modulus > with a specific *low* order 64 bits.
One cheap way the low order 64 bits can be set is to set the low order bits of p to the target bitset and the low order bits of q to ...00001 (63 0s and one 1 in binary), and then to increase the stride of candidate values in the prime sieve to be eg 2^64. This was the method used in the deadbeef attack on pgp 2.x keyids. pgp 2.x uses the least significant 64 bits as a keyid, and being able to easily generate keys with the same keyids can be a nuisance for keyservers and databases and could possibly confuse a user who incorrectly though they unique. (The intended unique id value is the pgp fingerprint, but in 2.x this had problems, see: http://216.239.53.100/search?q=cache:BcFAtn404nAC:cypherpunks.venona.com/date/1997/06/msg00523.html+dead+fingerprint+%22adam+back%22&hl=en&ie=UTF-8 ). Adam > As for Jack Lloyd's solution...I was also thinking > of something based on Diffie-Hellman, and was going > to suggest that Scott supply the prime p. I'd have > had Scott generate p (as with PDM). If Alice also > needs assurance that p isn't funny somehow, then she > could specify the high order bits of p to Scott, or > Scott could provide the seed to Alice from which he > generated p. But that would force Alice to do a lot > of work. I sort of like making it cheap for Alice, > and making Scott, who is making Alice jump > through hoops for no discernible reason, do a lot > of work. > > Radia > > > "David Wagner" <[EMAIL PROTECTED]> wrote: > >Jeroen C. van Gelderen wrote: > >>Here is a scenario: Scott wants Alice to generate a key pair after > >>which he will receive Alice's public key. At the same time, Scott wants > >>to make sure that this key pair is newly generated (has not been used > >>before). > > > >You might be able to have Scott specify a 64-bit string, and then ask > >Alice to come up with a RSA public key that has this string as its low > >64 bits. I believe it is straightforward to modify the RSA key generation > >algorithm to generate keypairs of the desired form. > > > >If you're worried about the security of allowing Scott to choose the > >low bits of Alice's public key, you could have Scott and Alice perform > >a joint coin-flipping protocol to select a random 64-bit string that > >neither can control, then proceed as before. > > > >I haven't worked out all the details, but something like this might > >be workable. > > > >In practice, you might also want to confirm that Alice knows her private > >key (i.e., has ability to decrypt messages encrypted under her public > >key). > > > >--------------------------------------------------------------------- > >The Cryptography Mailing List > >Unsubscribe by sending "unsubscribe cryptography" to > >[EMAIL PROTECTED] > > > > --------------------------------------------------------------------- > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]