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 [EMAIL PROTECTED]
