Discrete Logarithm problem, Diffie Helman key exchange and El-Gamal.
A group $(G, \cdot)$ is a set together with a binary operation $\cdot: G\times G \rightarrow G$ such that
Furthermore if for any $a,b\in G$ one has $a \cdot b = b\cdot a$ then we say that the group $(G,\cdot)$ is commutative.
We can figure out some quick properties from these,
where $$ \lambda = \begin{cases}\frac{y_2 - y_1}{x_2-x_1} &\text{ if } x_1 \neq x_2\\ \frac{3x^2 + a}{2y} &\text{ if } x_1 = x_2 = x \end{cases}$$ This is called the modulo $p$ points of an Elliptic curve.
For some group $(G,\cdot)$ given $g$ and $A$ such that $g^a = A$ in $G$ for some integer $a$, find the integer $a$ in an expedient manner.
In other words, is it easy to find, $a$ such that $$ \underbrace{g \cdot g \cdot \ldots g}_{a \text{ times }} = A.$$
The Diffie Helman problem is actually weaker than that (or is it?). The problem is given $g^a$ and $g^b$ is there an efficient algorithm to find $g^{ab}$. It is clear that if one can solve the Discrete Logarithm Problem (DLP) for the group $((\mathbb{Z}/p\mathbb{Z})^\times , *)$ efficiently, then one can solve the Diffie Helman Problem (DHP). It is not known if an efficient solution of the DHP implies an efficient solution for DLP.
def fastexp(x,n,m):
z = 1
while n!=0:
if n%2==1:
z = (z*x)%m
x = (x*x)%m
n = n//2
return z
import matplotlib.pyplot as plt
x = range(0,640)
y = [fastexp(7,i,641) for i in x]
s = [5 for i in x]
plt.scatter(x,y,s)
plt.show()
def DLPslowsolver(A,g,p):
#Finds a such that g^a = A mod p.
result = 1
for a in range(p):
result = (result*g)%p
if result == A:
return a
print("no solution")
return None
DLPslowsolver(15,8,100000001)
no solution
For the additive group $G = (\mathbb{Z}/m\mathbb{Z}, +)$ the question is to find the a such that $$ \underbrace{g + g + \cdots + g}_{a \text{ times}} = A$$ i.e. $ag \equiv A\pmod m$. Firstly, if $g$ and $m$ contain any common divisors, we can cancel them out, so let's assume they are relatively prime. Then if $g^{-1}$ is the multiplicative inverse of $g$ modulo $m$, we get that $$a \equiv Ag^{-1} \pmod m.$$
Efficiently finding the multiplicative inverse is done via Bezout's lemma.
Given two integers $n$ and $m$ and $d = \operatorname{gcd}(n,m)$ there existstwo integers $u$ and $v$ such that $$nu + mv = d.$$
Proof: Consider the set $L = \{an + bm >0: a,b\in \mathbb{Z}\}$ and consider $\min(L)= d = nu + mv$. If $e$ is any common divisor of $n$ and $m$, it divides any integer linear combination, and so any element in $L$, in particular $e | d$. Now we show that $d$ is a common divisor of $n$ and $m$. If we had $$n = dq + r$$ with $0\leq r <d$, then substituting the expression for $d$, we have $$r = n - dq = n - (nu + mv)q = n(1-uq) + m(-vq)\in L,$$ and since $d$ is the smallest positive linear combination in this set, $r = 0$, i.e. $d | n$. Similarly $d | m$, i.e. $d$ is a common divisor, and it is a multiple of any other common divisor, it is the greatest common divisor.
Keeping track of quotients in the Euclidean algorithm gives us the $u$ and $v$: Let $n= 152$ and $m= 96$
g | u | v |
---|---|---|
152 | 1 | 0 |
96 | 0 | 1 |
56 | 1 | -1 |
40 | -1 | 2 |
16 | 2 | -3 |
8 | -5 | 8 |
Indeed,
152*(-5)+ 96*(8)
8
def bezout(n,m):
(g,u,v) = (n,1,0)
(e,s,t) = (m,0,1)
r = g%e
while r != 0:
q = g//e
(eprime, sprime,tprime) = (e,s,t)
(e,s,t) = (r,u - q*s,v - t*q)
(g,u,v) = (eprime,sprime,tprime)
r = g%e
return (e,s,t)
def gcd(n,m):
(g,u,v) = bezout(n,m)
return g
n = 92384723423809809809876765854865333333456423498478768768768768768768768767657657555555555555555555555555555555555765765765765765765666666666666666666666666666666999999999999999999999990000000000
m = 192384792342341234132489876987687687687687687609879870987098709879872222222222222222222222222222222222222222222222222222254324324324325432222222222222222222221123432143215321765487659876098709879
(g,u,v) = bezout(n,m)
print("gcd(n,m) = ", g, )
print(" and ")
print("nu + mv =",n,"*",u,"+" ,m,"*",v, "=", n*u + m*v)
gcd(n,m) = 1 and nu + mv = 92384723423809809809876765854865333333456423498478768768768768768768768767657657555555555555555555555555555555555765765765765765765666666666666666666666666666666999999999999999999999990000000000 * 34962490539652007893012977698932523559185037154005385504416688787328013077993733415444025845790909163459199062325419570130875165508790630953715587151102210810121463627724789599628008404088921063 + 192384792342341234132489876987687687687687687609879870987098709879872222222222222222222222222222222222222222222222222222254324324324325432222222222222222222221123432143215321765487659876098709879 * -16789268940580597879996190160725729044999335596250103947689468249399840063895633754339260368355215988603757059041576091040949343150477315616528797448395373510318568345353286372536920128086756281 = 1
Consider all the residue classes modulo $m$, under multiplication. The operation is associative, and identity element is $1$. But are there inverses? Not necessarily, for example consider the set of residue classes modulo $10$.
$\times$ | - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
1 | - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
2 | - | 0 | 2 | 4 | 6 | 8 | 0 | 2 | 4 | 6 | 8 | ||
3 | - | 0 | 3 | 6 | 9 | 2 | 5 | 8 | 1 | 4 | 7 | ||
4 | - | 0 | 4 | 8 | 2 | 6 | 0 | 4 | 8 | 2 | 6 | ||
5 | - | 0 | 5 | 0 | 5 | 0 | 5 | 0 | 5 | 0 | 5 | ||
6 | - | 0 | 6 | 2 | 8 | 4 | 0 | 6 | 2 | 8 | 4 | ||
7 | - | 0 | 7 | 4 | 1 | 8 | 5 | 2 | 9 | 6 | 3 | ||
8 | - | 0 | 8 | 6 | 4 | 2 | 0 | 8 | 6 | 4 | 2 | ||
9 | - | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Notice that those elements which are relatively prime to $10$ actually do have inverses. The multiplicative group we are interested in is $$(\mathbb{Z}/10\mathbb{Z})^\times =\{1,3,7,9\} $$ and it has $4$ elements, which we denote by $\phi(10) = 4$.
Now given $x$ and $m$ with $\operatorname{gcd}(x,m) = 1$ we can find $u$ such that $$xu \equiv 1 \pmod{m},$$ afterall the g.c.d. condition states by Bezout's lemma that there are integers $u$ and $v$ such that $$xu + mv = 1.$$
Now reducing both sides modulo $m$ we get that $xu \equiv 1 \pmod m$.
This calculation is efficient as well, because finding the $u$ and $v$ in Bezout's lemma is as efficient as the Euclidean algorithm.
def inverse(x,n):
(g,u,v) = bezout(x,n)
if g!=1:
return None
else:
return u
x = 2938472847
m = 109987987987987489
a = inverse(x,m)
print(a)
28056777069990099
x*a
82444077594498124470341853
(x*a)%m
1
The ElGamal method of public key encryption which came after the RSA (1978 vs 1985) but is logically more close to the Diffie Helman (1976).
Alice agrees on a prime p and an element of large prime order $g$. Also choses a private key $a$. Alice computes $A = g^a \pmod{p}$, publishes $A$.
Bob has a message $m$ which is recorded as a number less than p and greater than 2. Bob choses an ephemeral key $k$ to be used only once and computes $c_1 = g^k\pmod p$ and $c_2 = mA^k \pmod p$, then sends $c = (c_1,c_2)$. This is his ciphertext, which he sends to Alice.
Then Alice, who doesn't know the ephemeral key $k$ can get rid of the $A^k$ factor next to the message by computing $x \equiv c_1^a \pmod p$ which is equivalent to $A^k$ and then computes $x^{-1} c_2 \equiv m \pmod p$.
import random
def ElGamalKeyGenerator(a,g,p):
A = fastexp(g,a,p)
return A
def ElGamalEncryptor(A,g,p,m):
#encrypts a message using the ElGamal encryption technique
k = random.randint(p//2,p-2)
c1 = fastexp(g,k,p)
c2 = (m*fastexp(A,k,p))%p
return (c1,c2)
def ElGamalDecryptor(c, a, p):
#The ciphertext should be in the form (c1,c2)
(c1,c2) = c
x = fastexp(c1,a,p)
m = (c2*inverse(x,p))%p
return m
from sympy import isprime, factorint
p = 1234567891
g = 2
k = random.randint(p//4, 3*p//4)
print("p is Prime:", isprime(p))
A = ElGamalKeyGenerator(k,g,p)
plaintext = "yes"
m = int.from_bytes(plaintext.encode(), 'big')
print("message is:", m)
c = ElGamalEncryptor(A,g,p,m)
print("ciphered is:", c)
p is Prime: True message is: 7955827 ciphered is: (392864368, 363130765)
m = ElGamalDecryptor(c,a,p)
print("decryption gives", m)
decryption gives 11362729
Let us have access to a Diffie-Helman oracle, meaning that there is a function (whose inner workings we do not know), such that $$\operatorname{DHO}(g,p,A= g^a,B=g^b) = g^{ab} \pmod p.$$
With access to such an oracle we can crack the ElGamal problem, if we intercept $c = (c_1,c_2)$ and also the integers $A, g,p$ which were public information to begin with. Note that $c_1 \equiv g^k \pmod p$ and $A \equiv g^a \pmod p$ so that we get, $$\operatorname{DHO}(g,p, c_1 = g^k, A = g^a) = g^{ak} \equiv A^k \pmod{p}$$ And so we can then find the multiplicative inverse of $A^k$, multiply it by $c_2$ in order to obtain $m$.
Conversely now assume that we have an ElGamal Oracle, such that $$\operatorname{EGO}(g,p,A = g^a,c = (c_1 = g^k, c_2 = mA^k)) \equiv (c_1^a)^{-1} c_2 \equiv m \pmod p,$$ i.e. somehow the oracle decrypts the ciphertext efficiently. Now we want to solve the DHP, and so given $A = g^a$ and $B = g^b$, we input $$\operatorname{EGO}(g,p, A = g^a, c = (B = g^b, 1)) = g^{-ab}\pmod p.$$ Taking the inverse modulo $p$ of the output gives us the solution to the Diffie Helman Problem.
There is a method to solve the Discrete Logarithm Problem for any group $G$ in $O(\sqrt{N} \log(N) )$ many steps, where $N = |G|$. We are trying to solve the problem $$g^x \equiv h \text{ in } G.$$
Let $n = \lfloor\sqrt{N}\rfloor + 1$. Note that $n > \sqrt{N}$. Make two lists, both of length about $n$.
Find a match between these two lists (which exists). Then we have $$g^i = h*g^{-jn}$$ for some $0\leq i < n$ and $0\leq j \leq n$. This means that $$h \equiv g^{i + nj} \text{ in } G.$$
If three is a solution to $g^x \equiv h$, then there is a match between these sets. To see this, first divide $x$ by $n$ with remainder. Since $x < N$, we have that $x = nq + r$ with $q \leq N/n < n$, and $0\leq i < n$. In that case $h = g^{q n + j}$, or in other words $$h*g^{-qn} = g^r$$
#Solves g^x = h in Z/mZ
from math import sqrt
from math import floor
from sympy.ntheory.factor_ import totient as phi
def BabyStepGiantStep(g,h,m,N =None):
#solves the Discrete logarithm problem if g has order
#$N$ in the group Z/mZ
if N == None:
N = phi(m)
n = floor(sqrt(N)) + 1
G = fastexp(g,n,m)
L1 = [fastexp(g,i,m) for i in range(n)]
L2 = [(h*inverse(fastexp(G,j,m),m))%m for j in range(n)]
common = set(L1) & set(L2)
if common==set():
print("There is no solution")
return None
else:
c = common.pop()
i = L1.index(c)
j = L2.index(c)
return (i + n*j)%N
BabyStepGiantStep(16,fastexp(17,4,101),101,N= 25)
5
fastexp(16,5,101)
95
BabyStepGiantStep(2,17,101)
30
fastexp(2,30,101)
17
fastexp(17,25,101)
100
There is a way to attack the Discrete Logarithm Problem. This depends on whether $p-1$ has a lot of small prime factors. The method requires the so-called Chinese Remainder Theorem.
Let $m = m_1m_2$ with $\operatorname{gcd}(m_1,m_2) = 1$. Then there is an isomorphism of rings: $$ \begin{align*}\mathbb{Z}/m_1m_2 \mathbb{Z} &\longrightarrow (\mathbb{Z}/m_1\mathbb{Z} ) \times (\mathbb{Z}/m_2\mathbb{Z})\\ x \pmod {m_1m_2} &\longmapsto (x \pmod {m_1}, x\pmod {m_2})\end{align*}$$ which does also translate to an isomorphism of their group of invertible elements: $$ (\mathbb{Z}/m_1m_2 \mathbb{Z})^* \longrightarrow (\mathbb{Z}/m_1\mathbb{Z} )^* \times (\mathbb{Z}/m_2\mathbb{Z})^*$$
The inverse of the above map is given as, $$ \begin{align*}(\mathbb{Z}/m_1\mathbb{Z} ) \times (\mathbb{Z}/m_2\mathbb{Z}) &\longrightarrow \mathbb{Z}/m_1m_2 \mathbb{Z}\\ (x_1 \pmod {m_1}, x_2\pmod {m_2}) &\longmapsto x_2 m_1\overline{m_1} + x_1 m_2 \overline{m_2} \end{align*}$$ where $\overline{m_1}$ is an integer such that $m_1\overline{m_1} \equiv 1 \pmod {m_2}$ and $\overline{m_2}$ is such that $m_2 \overline{m_2} \equiv 1 \pmod{m_1}$.
m1 = 18
m2 = 21
m1inv = inverse(m1,m2)
m2inv = inverse(m2,m1)
from mpl_toolkits.mplot3d import Axes3D
r = range(0,m1*m2)
x = [x%m1 for x in r]
y = [y%m2 for y in r]
s = [5 for i in r]
plt.scatter(x,y,c = r, s=s)
plt.show()
def CRT(xs, ms):
#The input ms =[m1,m2,...,m_k] is a sequence of pairwise relatively prime moduli. xs =[x1,x2,... x_k] are integers
#modulo m's. The output is an integer x that is congurent to x_i modulo m_i for all the elements in the list.
x = 0
m = 1
for (y,n) in zip(xs,ms):
x = SimpleCRT(x,y,m,n)
m = n*m
return x
def SimpleCRT(x,y,m,n):
#outputs an integer modulo mn that is congruent to x modulo m and y modulo n
if gcd(m,n)!=1:
print("Moduli are not relatively prime")
return None
minv = inverse(m,n)
ninv = inverse(n,m)
return (x*n*ninv + y*m*minv)%(m*n)
(x1,x2,x3) = (5,2,3)
(m1,m2,m3) = (25,4,7)
x = CRT([x1,x2,x3],[m1,m2,m3])
print("x =", x,'\n x mod ', m1,' =', x%m1, '\n x mod ', m2, ' =', x%m2,'\n x mod ',m3, ' =', x%m3)
x = 430 x mod 25 = 5 x mod 4 = 2 x mod 7 = 3
The Algorithm is as follows. Assume that the group $G$ is of order $N$ which factors as $$N = q_1^{k_1} \ldots q_r^{k_r}.$$ For each prime factor $q_i^{k_i}$ raise both sides of the equation to the power of $N/q_i^{k_i}$.
As an example take the multiplicative group $(\mathbb{Z}/101 \mathbb{Z})$ which has order $100 = 4 \times 25$. Consider an equation of the form, $$g^x \equiv A \pmod{101}$$ The solution to this equation is determined as $x \mod 100$, since $g^{100} = 1$ (note that $(\mathbb{Z}/101\mathbb{Z})^*$ has $\phi(101)= 100$ elements. Now we exponentiate both sides to $4$-th and $25$-th powers: $$(g^{4x} \equiv A^{4} \pmod{101}$$ is solvable quickly becasue $g^4$ has order at most $25$ not $100$. Also $$g^{25x} \equiv A^{25}$$ is solvable quickly because the $g^{25}$ has order $4$. This gives two conditions on $x \equiv x_1 \pmod{4}$ and $x \equiv x_2 \pmod{25}$ and we solve them using Chinese remainder theorem to get a solution $x \pmod{100}$.
import sympy
p = 1234567811
sympy.isprime(p)
True
sympy.factorint(p-1)
{2: 1, 5: 1, 7: 1, 41: 1, 149: 1, 2887: 1}
from sympy.ntheory.factor_ import totient as phi
def PohligHelman(g,A,p,N = None):
if N == None:
N = phi(p)
fac = sympy.factorint(N)
powerlist = [pr**fac[pr] for pr in fac]
allbut = [N/x for x in powerlist]
bases = [fastexp(g,a,p) for a in allbut]
expos = [fastexp(A,a,p) for a in allbut]
results = [BabyStepGiantStep(bases[i],expos[i],p, N = powerlist[i]) for i in range(len(powerlist))]
return CRT(results, powerlist)
PohligHelman(2,43,101)
42
PohligHelman(7,47,p)
577740778
BabyStepGiantStep(7,47,p, N = p-1)
577740778
fastexp(7,577740778,p)
47