Diffie-Hellman Key Exchange

First we pick a random prime and a primitive root.

r:=random(10^20)

math

p:=nextprime(r())

math

 

alpha:=numlib::primroot(p)

math

Now Alice selects random x and Bob selects random y.

r1:=random(0..p-2);

math

 

x:=r1()

math

 

y:=r1()

math

 

alice:=powermod(alpha,x,p)

math

 

bob:=powermod(alpha,y,p)

math

 

K:=powermod(alice,y,p)

math

 

K-powermod(bob,x,p)

math

One way to break the system is to recover x, the discrete log of Alice's number.

The Pohlig-Hellman algorithm

ifactor(p-1)

math

We can find x mod 2 easily:

numlib::legendre(alice,p)

math

Since this is -1, i.e., αx is not a perfect square mod p, x is odd.

Similarly, we can find x mod 3:

c:=powermod(alice, (p-1)/3, p)

math

 

So x is 0 mod 3.  Say we want to find x mod 4271.

_mod(x, 4271)

math

c:=powermod(alice, (p-1)/4271, p)

math

We run through integers j mod 4271 until we find a match.

for j from 1 to 4270 do

  t:=powermod(alpha, j*(p-1)/4271, p);

  if t=c then print(j, t); break end_if;

end_for

math

4271*6

math

So x is 64 mod 4271. And mod 4271*6=25626, x is

xmod17104:=numlib::ichrem([1,0,64],[2,3,4271])

math

Say we want to find x mod the large prime factor q of p-1.

q:=(p-1)/25626

math

isprime(q)

math

c:=powermod(alice, (p-1)/q, p)

math

We run through integers j mod q until we find a match.

for j from 1 to q-1 do

  t:=powermod(alpha, j*(p-1)/q, p);

  if t=c then print(j, t); break end_if;

end_for

Error: Computation aborted;

during evaluation of 'powermod'

 

Didn't work so well; q is too big.  However, since we've cut the calculation down to only q possibilities, we can try the baby step, giant step method.

 

N:=ceil(sqrt(q))

math

c1:=powermod(alpha, (p-1)/q, p);

firstlist:=matrix(1,N);

for j from 1 to N do

   firstlist[1,j]:=powermod(c1, j, p);

end_for;

 

c2:=powermod(alpha, -N*(p-1)/q, p);

for k from 1 to N do

    t:=alice*powermod(c2, k, p);

    for j from 1 to N do if t=firstlist[1,j]

    then print(j, k, t); break; break end_if;

end_for; end_for

math

Error: Computation aborted;

during evaluation of '(Dom::Matrix(Dom::ExpressionField()))::_index_intern'

 

Also took too much time, but with smaller prime factors of p-1 this method would work.