[566] in cryptography@c2.net mail archive
non-interactive forward secrecy
daemon@ATHENA.MIT.EDU (Adam Back)
Thu Apr 17 19:39:15 1997
Date: Thu, 17 Apr 1997 22:33:16 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cryptography@c2.net
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<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
