Date: Thu, 17 Apr 1997 18:21:24 +0100 From: Adam Back To: coderpunks@toad.com Subject: non-interactive forward secrecy Some time ago I posed the problem of creating a non-interactive forward secrecy protocol. Lewis McCarthy commented on the original post recently. I think I found a working (though inefficient) solution. X_0, g, and p are Alice's public key x_0 is Alice's private key X_0 = g ^ x_0 (mod p) Diffie-Hellman key exchange proceeds as normal: Bob chooses a random y, and calculates and sends Alice Y: Y = g ^ y (mod p) The generated key k_0 can be calculated by Bob (with X_0 and y): k_0 = X_0 ^ y (mod p) And independently by Alice (with Y and x_0): k_0 = Y ^ x_0 (mod p) This works because: X_0 ^ y = (g ^ x_0) ^ y (mod p) = g ^ (x_0 . y) (mod p) = g ^ (y . x_0) (mod p) (commutivity multiplication) = (g ^ y) ^ x_0 (mod p) => X_0 ^ y = Y ^ x_0 (mod p) (So far this is standard Diffie-Hellman). After each time period, Bob uses a new public parameter X_t, and Alice uses a new private parameter x_t. Alice calculates her new private parameter x_{t+1} from her current private parameter x_t: [1] x_{t+1} = x_t . X_t Bob Calculates Alice's next public parameter X_{t+1}from her previous public parameter X_t: [2] X_{t+1} = X_t ^ X_t (mod p) The normal relation that: [3] X_t = g ^ x_t (mod p) still holds, for any t. To see why, consider: X_{t+1} = X_t ^ X_t (mod p) using [2] = (g ^ x_t) ^ X_t (mod p) using [3] = g ^ (x_t . X_t) (mod p) => x_{t+1} = x_t . X_t However x_t increases in size by approx log2( p ) for each new time period, and: log2( x_t ) ~ t . log2( p ) Encryption time is not affected, but decryption time increases logarithmically with t. For a 4096 bit DH prime p, one time period per day, and a public key with a years expiration date, on the last time period, log2( x_t ) ~ 365 x 4096 = 1,495,040 ~ 1.5 Mbits = 183 Kbytes. Key generation is: Y_0 ^ x_365 mod p with lengths log2( Y_0 ) = 4096 bits, x_365 = 1.5 Mbits, p = 4096 bits. Is there any way to reduce the size of x_t while keeping the result? Is there any way to improve the efficiency of calculating K_i = Y_i ^ x_i mod p where x_i is large? A related question, does knowledge of p & q where n is an RSA modulus, n = p.q, provide any short cuts in calculating discrete logarithms mod n? Adam -- Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/ print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<> )]}\EsMsKsN0[lN*1lK[d2%Sa2/d0