Key Pair Agreement?

[Joseph Ashwood]

----- Original Message -----
From: "Jeroen C. van Gelderen" <jeroen at vangelderen.org>
> 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).
[snip]
> 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.
>
> This is a very expensive key generation operation but it would
> seem to work.
>
> My questions are:
> 0) who has invented this before?
> 1) does it achieve what I think it achieves?
> 2) does anybody know of more efficient algorithms?

I can think of a more efficient algorithm off the top of my head.
1. Scott creates P,Q,G
2. Scott sends P,Q,G
3. Alice verifies P,Q,G and creates (x,y)
4. Alice sends (x,y)

Scott can be certain that, within bounds, P,Q,G have never been found
before, and it vastly reduces the computations (since there was no stated
requirement that Alice believe the pair had never been used before).

Now on to Jack's question:
> Actually, that makes me wonder. Given:
>   y_i = (g_i^x) mod p_i for i 0...n

> An 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.

I believe it is unfortunately so, depending on how strong P is. If (P-1)/2Q
is always prime, then I believe there is little erosion (but some remains).
The foundation of this thus.
X can be determined from Y if the attacker can find inverses in all the sub
groups, by the CRT.
I believe there is a way to extend this such that provided you have enough
sub-groups to uniquely identify a number > Y, X can be determined.
If this is the case then having a large number of (Y,P,G,Q) around can erode
the security of the DLP.
I also believe that it is the case that each of the factors must be unique,
otherwise it is simply a collision in the CRT context (although a change of
G may correct this)
If this is the case then it would be important that Alice generate a new X
for each pair in existence, which is simply good policy to begin with.
                Joe


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