Key Pair Agreement?

[Jack Lloyd]

On Mon, 20 Jan 2003, Jeroen C. van Gelderen wrote:

> It would seem that the DSA key structure facilitates this:
>
> 1. Scott sends SEED1 to Alice.
> 2. Alice picks a random number SEED2.
> 3. Alice sets SEED=SHA1(SEED1 || SEED2).
> 4. Alice generates a set of DSA parameters P, Q, G using the
>     algorithm in Appendix 2, FIP-186-2.
> 5. Alice generates a key pair (x,y) using the parameters from (4).
> 6. Alice sends SEED2, counter, P, Q, G, y to Scott.
> 7. Scott generates P', Q', G' based on SEED=SHA1(SEED1 || SEED2),
>     counter, and compares them to P, Q, G.

A minor nit: G can be any random thing. While the generation of P and Q is
controlled entirely by the seed, G is not (though of course, IF you use the
method in FIPS 186, it will depend on P and Q, but will not be
deterministic). The value of H (see the FIPS) can be entirely random. Of
course you can mandate that in this protocol H be the smallest integer that
generates a working G, or something like that.

Another nit: Alice could, if she wanted, choose the same x every time.
Since P and Q would (presumably) change, this would change the public key
of course.

Actually, that makes me wonder. Given:
   y_i = (g_i^x) mod p_i for i 0...n

can you find x easier than you would with just y=g^x mod p? Obviously it
couldn't be any harder, but I wonder if there is any practical advantage
for an attacker there.

> 2) does anybody know of more efficient algorithms?

Are you asking this question because you want do actually do this, or
because you are interested in the problem? Practically speaking, having
Scott choose among a pool of N primes and sending one to Alice (who
generates a key pair using that prime) seems 'good enough', but doesn't
quite meet the requirements you specify.

The only idea that occurs to me for speeding this up is that maybe using
ECC would lead to a faster key generation step.

-Jack


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