Diffie-Hellman Key Exchange
First we pick a random prime and a primitive root.
r:=random(10^20)
p:=nextprime(r())
alpha:=numlib::primroot(p)
Now Alice selects random x and Bob selects random y.
r1:=random(0..p-2);
x:=r1()
y:=r1()
alice:=powermod(alpha,x,p)
bob:=powermod(alpha,y,p)
K:=powermod(alice,y,p)
K-powermod(bob,x,p)
One way to break the system is to recover x, the discrete log of Alice's number.
The Pohlig-Hellman algorithm
ifactor(p-1)
We can find x mod 2 easily:
numlib::legendre(alice,p)
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)
So x is 0 mod 3. Say we want to find x mod 4271.
_mod(x, 4271)
c:=powermod(alice, (p-1)/4271, p)
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
4271*6
So x is 64 mod 4271. And mod 4271*6=25626, x is
xmod17104:=numlib::ichrem([1,0,64],[2,3,4271])
Say we want to find x mod the large prime factor q of p-1.
q:=(p-1)/25626
isprime(q)
c:=powermod(alice, (p-1)/q, p)
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))
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
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.