414: Diffie-Hellman

846 days ago by wstein

Math 414: Jan 29, 2009:  Diffie-Hellman -- The World's First (Public) Public-Key Cryptosystem
 
       

Additive Diffie-Hellman: Not good.
digits = 3 set_random_seed(0) # so everybody can recreate this p = next_probable_prime(ZZ.random_element(10^digits)) g = Mod(ZZ.random_element(2,p), p) print "p = ", p print "g = ", g n = ZZ.random_element(1,p); print "n = ", n m = ZZ.random_element(1,p); print "m = ", m 
        
p =  337
g =  227
n =  100
m =  55
p =  337
g =  227
n =  100
m =  55

Nikita sends ng and Michael sends mg:
print "n*g = ", n*g print "m*g = ", m*g 
        
n*g =  121
m*g =  16
n*g =  121
m*g =  16

The "secret" key is nmg = n\cdot (mg) = m\cdot (ng):

n*m*g 
        
252
252

However, anybody can instantly compute nmg, given what was sent over the wire (which was mg, ng, and g):
time ss = (m*g) * ((n * g) / g) ss 
        
Time: CPU 0.00 s, Wall: 0.00 s
468738878288630638333358888551939639945207222683730397638051244680545455\
777888529310307256529162138999494148015688505639157400137730563812590764\
913935653800123896188353517549614438265333812008584504780941160691082437\
618146393002310529125415544153229608069065803026175300082278212392339175\
8153522866
Time: CPU 0.00 s, Wall: 0.00 s
4687388782886306383333588885519396399452072226837303976380512446805454557778885293103072565291621389994941480156885056391574001377305638125907649139356538001238961883535175496144382653338120085845047809411606910824376181463930023105291254155441532296080690658030261753000822782123923391758153522866
 
       

Multiplicative Diffie-Hellman: Much better!
%time digits = 3 set_random_seed(0) # so everybody can recreate this p = next_probable_prime(ZZ.random_element(10^digits)) g = Mod(ZZ.random_element(2,p), p) print "p = ", p print "g = ", g n = ZZ.random_element(1,p); print "n = ", n m = ZZ.random_element(1,p); print "m = ", m 
        
p =  337
g =  227
n =  100
m =  55
CPU time: 0.01 s,  Wall time: 0.01 s
p =  337
g =  227
n =  100
m =  55
CPU time: 0.01 s,  Wall time: 0.01 s

Nikita and Michael agree on g and p in public, then Nikita sends g^n and Michael sends g^m, where we view g as a number mod p:
print "g^n = ", g^n print "g^m = ", g^m 
        
g^n =  253
g^m =  41
g^n =  253
g^m =  41

The "secret" key is g^{nm} = (g^m)^n = (g^n)^m:

print "Michael computes secret: ", (g^n)^m 
        
Michael computes secret:  158
Michael computes secret:  158
print "Nikita computes secret: ", (g^m)^n 
        
Nikita computes secret:  158
Nikita computes secret:  158

And it appears that nobody else can easily compute g^{nm}, given what was sent over the wire, since finding n from g^n and g seems very, very hard in general.  This hard problem is called the discrete log problem.
 
       

Naive Algorithm to Solve the Discrete Log Problem
@interact def _(p=(37,primes(1000)), g=(2..999), gn=(2..999)): g = Mod(g,p) h = g for n in [1..p]: if h == gn: print "Answer = ", n return h *= g print "No solution" 
       

Click to the left again to hide and once more to show the dynamic interactive window
 
       
 
       

Plotting the Exponentiation Function Modulo p
@interact def _(p=(37,primes(150)), g=(2..50), modp=True): #g = Mod(primitive_root(p), p) print "p = ", p print "g = ", g if modp: g = Mod(g,p) try: print "Multiplicative order =", g.multiplicative_order() except: pass v = [(n, ZZ(g^n)) for n in [1..p-1]] show(line(v,color='gray',thickness=0.5) + points(v,pointsize=20)) 
       

Click to the left again to hide and once more to show the dynamic interactive window