Key Pair Agreement?

[Radia Perlman - Boston Center for Networking]

Mostly, I'm mystified as to the application for
this. Scott can force Alice to generate a public key
pair, but he can't force her never to use it for
another purpose, or even ensure that she doesn't
use it for some other purpose between the time
she generates it at Scott's demand and uses it for
Scott's application. And Scott can't discover
whether Alice is using a bad random number generator,
which depending on the application might be another
way to cheat or be insecure.

But not worrying about that for now (despite my
anecdote about how one should know what problem
you're solving before trying to come up with a solution),
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.

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" <daw at mozart.cs.berkeley.edu> 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
>majordomo at wasabisystems.com



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com