(* 
  Discrete Logarithm. A Mathematica implementation of an algorithm of Pollard 
  and the 100 Dollar problem of McCurley,

         O. Knill,  3. Dec. 1991

Other algorithms beside the Pollard algorithm are 

-- Shanks  Baby step-Giant step algorithm  (1971).
   (Can be used if the order of the group is not known. About same 
   running-time then Pollards algorithm.)  
-- Pohlig-Hellman-Silver algorithm (1978). Good if the order of the 
   group generated by the element x is smooth.
-- Index Calculus Method (Kraitchik 1922, Adlemann 1979). Quickest algorithm 
   in GF(p). Recent implementation by LaMacchia and Odlyzko.

The Pollard algorithm: 

The Pollard algorithm in a group G of order k has a running time believed to be   
O(k^(1/2) log(k)). To calculate the value n such that  g^n= b in G, one first 
wants to find an identity g^t=b^s. To do so, one performs a random walk in the
group G: Divide the group into three sets  G1,G2,G3 and calculate
after initialisation x(0)=1,s(0)=0,t(0)=0 recursively the sequences x_n,s_n,t_n 

x(n) -> b * x(n ),       x in G1, s  ->  s+1
x(n) -> x(n ) * x(n ),   x in G2 ,t  ->  2 t,  s -> 2 s
x(n) -> g *x(n),         x in G3 ,t  ->  t+1

If x(n)=x(2n) in G, one obtains with t= t(2n)-t(n), s=s(n)-s(2n)
the identity  g^t=b^s from which the value of n satisfying g^n=b can be determined. 

Literature :

K. S.McCurley, "The discrete Logarithm Problem",  in Cryptology and
Computational Number Theory, Proc. of Symposia in Applied Mathematics,  90
E. Bach, "Intractable Problems in Number Theory", Adv. Cryptology, CRYPTO 88
C. Pomerance, Cryptology and Copmutational Number Theory-An Introduction.
in Cryptology and Computational Number Theory, Proc. of Symp. in App. Math.,90

Note added in April 2001 (almost 10 years after this file had been written): 
The 100 Dollar McCurley problem had been solved in 1998,
(9 years after it had been posed by McCurley) by Damian Weber and Thomas Denny. 

*)

DisLogPollard::usage= "DisLogPollard[g,a,p] computes with a method of
Pollard the discrete logarithm x of the nonzero number a with
respect to the basis g modulo p. That is: g^x=a mod p."

DisLogPollard[g_Integer,a_Integer,p_Integer]:= Module[
  {x1=1,x2=1,s1=0,s2=0,t1=0,t2=0,u,h,d,k,l,r,i,j=1,q,n=EulerPhi[p]},
   If[a==g,r=1,
     While[x1!=x2 || j==1,
       If[x1<p/3,x1=Mod[a*x1,p];s1=Mod[s1+1,n]];
       If[x1>=p/3 && x1<2p/3,
          x1=Mod[x1*x1,p];s1=Mod[2*s1,n];t1=Mod[2*t1,n]];
       If[x1>=2*p/3,x1=Mod[g*x1,p];t1=Mod[t1+1,n]];
       Do[
         If[x2<p/3,x2=Mod[a*x2,p];s2=Mod[s2+1,n]];
         If[x2>=p/3 && x2<2p/3,
            x2=Mod[x2*x2,p];s2=Mod[2*s2,n];t2=Mod[2*t2,n]];
         If[x2>=2*p/3,x2=Mod[g*x2,p];t2=Mod[t2+1,n] ],{i,2}];
         j=j+1;
     ];
     s=Mod[s2-s1,n];t=Mod[t1-t2,n];
     h=ExtendedGCD[s,n];
     d=h[[1]];u=h[[2,1]];
     If[d==1,r=Mod[PowerMod[s,-1,n]*t,n],
        k=(u*t)/d;l=n/d;i=1;q=PowerMod[g,k+l,p];
        o=PowerMod[g,l,p];
        While[a!=Mod[q,p] && i<=d,q=Mod[q*o,p];i=i+1];
        r=Mod[k+i*l,n];
     ];
   ];
   Return[r];
];

(*
The 100 Dollar problem  of  McCurley  (1990).  Given is a Diffie-Helleman 
problem: Given a prime number p and two numbers  7^x=a (mod p)  und  
7^y=b (mod p). For the determination of the number  7^(xy) (mod p) together 
with a proof that it is the right number, McCurley promised 100 Dollars. 
The difficulty of this attack allows key exchange: Bob chooses x and sends 
7^x to Alice, Alice chooses y and sends 7^y to Bob. Both know p and both can 
determine 7^(xy), the secret key. An eavesdropper can see 7^x and 7^y, know 
the base 7 and p but is unable to determine the secret key  which Bob and 
Alice have agreed on. 

*)

DiffieHelleman::usage= "DiffieHelleman[g,a,b,p] determines the 
discrete logs x,y satisfying g^x=a (mod p), g^y=b (mod p) as well as
g^(xy) (mod p). Determining DiffieHelleman[g,a,b,p] is an attempt to 
eavesdrop the secret key g^(xy) Alice and Bob have agreed on. They have 
sent each other a and b over a public channel and made g and p public too." 


DiffieHelleman[g_,a_,b_,p_]:=Module[{x,y}, 
  x=DisLogPollard[g,a,p];
  y=DisLogPollard[g,b,p];
Return[ {x,y,PowerMod[g,x*y,p]} ]
]

(*
 
Here comes a test with very small numbers

 g^x=5^6  = 15625       =  2=a (mod 17)   
 g^y=5^15 = 30517578125 =  7=b (mod 17) 

 g^(x*y)  =807793566946316088741610050849573099185363389551639556884765625
          = 9                  (mod 17)  

*)

TestDiffieHelleman:=Module[{},
 g=5; 
 p=17;
 a=2; 
 b=7;
 Return[DiffieHelleman[g,a,b,p]];
] 

(* 

Don't hope that the Curley problem can be solved so easily. Nevertheless. 
Let's try! To run the program, just run in a terminal

math<curley.m  &

If you are lucky, you will get it (after a few thousend years
maybe, maybe sooner, who knows). 

*)

Curley:=Module[{},
g=7;
q=(Power[7,149]-1)/6;
p=2*739*q+1;

TimeEstimate = N[Sqrt[p]*Log[p]/10^17];
Print["Message from the procedure Curley: expeced number of steps:  ", TimeEstimate,
       " times the age of the universe in seconds" ]; 
Print["But you might be lucky..."]; 

a =127402180119973946824269244334322849749382042586931621\
   654557735290322914679095998681860978813046595166455458\
   144280588076766033781;
b =1801622852874531024447828348367998501596704669534669731\
   3025121734059953772058475958176910625380692101651848662\
   362137934026803049;
Return[DiffieHelleman[g,a,b,p]];
]; 


Print[" Hi, Spy!  "];
res=TestDiffieHelleman;
Print[" Alice and Bob have exchanged a key on the Diffie-Helleman "];
Print[" key exchange basis. You know the prime p = ", p,"."];  
Print[" You know the base g = ", g, " ."];  
Print[" Alice knows x, you successfully got Alice message a=g^x ",a, " sent to Bob"  ];  
Print[" Bob knows y, you successfully got Bobs message b=g^y ",b, " sent to Alice" ];
Print[" You try to find the secret key g^(x y) (mod p) which Alice and Bob know."];   
Print[""]

x=res[[1]]; y=res[[2]]; 

Print["Your cracking program obtained x= ",x];
Print["Your cracking program obtained y= ",y];
Print["Check whether g^x -a (mod p) = 0  ", Mod[PowerMod[g,x,p]-a,p] ==0 ];
Print["Check whether g^y -b (mod p) = 0  ", Mod[PowerMod[g,y,p]-b,p] ==0 ];
Print["Success! The secret key g^(xy) (mod p) is  ",Mod[PowerMod[g,x*y,p],p]     ];

Print[""]; 
Print[" Now, we try to attack the Curley 100 Dollar problem" ];
Print[" It is the same problem as before. Only that the numbers are much bigger "]; 
Print[" Don't expect to finish this soon .....   By, Spy. Nice try! " ];
res=Curley;
g0=res[[1]]; x0=res[[2]]; y0=res[[3]]; p0=res[[4]];
Print["We obtained x= ",x];
Print["We obtained y= ",y];
Print["Check whether g^x (mod p)-a = 0  ", Mod[PowerMod[g,x,p]-a,p] ==0 ];
Print["Check whether g^y (mod p)-b = 0  ", Mod[PowerMod[g,y,p]-b,p] ==0 ];
Print["The secret key g^(xy) (mod p) is  ",Mod[PowerMod[g,x*y,p],p]     ];