Baby-Step, Giant-Step: Solving Discrete Logarithms and Why It’s A Hard Problem To Solve

Within normal logarithms we define:

Baby-Step, Giant-Step: Solving Discrete Logarithms and Why It’s A Hard Problem To Solve

Within normal logarithms we define:

h = aˣ

So if we want to find the value of x, we use:

x = logₐ (h)

So 10⁴ is 10,000, and the inverse log is log10(10,000) is 4.

Within discrete logarithms we introduce a finite field with a prime number. For this we have:

h = gˣ (mod p)

and where p is the prime number. It is thus a difficult task to find the value of x which has been used, even if we know h, g and p. We use discrete logarithms with the Diffie-Hellman key exchange method and in ElGamal encryption.

Let’s start with an example:

20 = 5ˣ (mod 53)

In this case we have g= 5, h= 20 and p= 53, and want to find x. We first determine the square root of p-1, and we will round it up to the nearest integer. In this case it will be:

N =Ceiling(√(p-1)) = Ceiling(√(52)) = 7

Next we will pre-compute from 1 to N with the baby table. These will store gⁱ (mod p) and then store them in the form of {gⁱ (mod p), i}:

{1: 0, 3: 7, 5: 1, 51: 5, 42: 4, 43: 6, 19: 3, 25: 2}

For example:

If i=0, we get 5⁰ mod 7 gives 1 {1:0}.

For i=1 we get 5¹ mod 7 gives 5 {5:1}

For i=2 we get 5² mod 7 gives 5 {25:2}

We now have a list of pairs from 0 to the square root of p-1.

We now compute g⁻ᴺ to give c:

c = pow(g, N * (p-2), p)

We then search through values of:

h cˣ (mod p)

until we find a match in the table. We then take this value and multiply it by N and add the value we have found:

for j in range(N):
 y = (h * pow(c, j, p)) % p
 if y in t: 
   return j * N + t[y]

The completed code is:

def solve(g, h, p):
N = int(math.ceil(math.sqrt(p — 1))) 
 print “N=”,N
 t = {}
# Baby step.
 for i in range(N):
 t[pow(g, i, p)]=i
print “Baby step”,t
# Fermat’s Little Theorem
 c = pow(g, N * (p — 2), p)
 
 for j in range(N):
 y = (h * pow(c, j, p)) % p
 if y in t: 
 return j * N + t[y]
return None

Now let’s try and example. If we try 22 = 5ˣ (mod 53) we get [Try]:

g= 5
h= 22
p= 53
22 = 5 ^x (mod 53 )
==============
N= 8
Baby step {1: 0, 3: 7, 5: 1, 51: 5, 42: 4, 43: 6, 19: 3, 25: 2}
x= 9
Checking for h= 22

This gives a solution of x=9, and when we try it back in 5⁹ (mod 53), we get a result of 22.

Here are a few examples:

  • 5=2ˣ (mod 41) Try!
  • 22=5ˣ (mod 53) Try!
  • 15=7ˣ (mod 131) Try!
  • 50=11ˣ (mod 997) Try!
  • 777=7ˣ (mod 14947) Try!

And there you go.

In real-life examples our prime numbers are likely to be extremely large, so we will need to store the square root of the number of values. For a 128-bit prime number we will need to store:

>>> p=2**128–1
>>> int(math.ceil(math.sqrt(p — 1)))
18446744073709551616L

In ElGamal the recommended prime number size is 2,048 bits which would fill all the memory on the planet and much more. For just 512 bit prime numbers we get:

>>> p=2**512–1
>>> int(math.ceil(math.sqrt(p — 1)))
115792089237316195423570985008687907853269984665640564039457584007913129639936L

Which is a vast amount of memory.

Conclusions

We reduce the complexity of the problem by storing a square root of the prime number used. So for a prime number of 14,947, we now only need to 123 values. Unfortunately as our prime numbers get larger the amount of memory we need becomes vast.

And so discrete logarithms continue to be a hard task for a computer. If someone uses a 512-bit prime number, we will need to store 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 values in our baby table. This would be much more than all the memory on the planet. For 2,048 bit prime numbers we would need vastly more memory. Unfortunately quantum computers do not struggle as much with discrete logarithms, and will be able to crack them in a reasonable amount of time.

Using Python, can you solve these?

1849836 = 11ˣ (mod 2097151)

711087309 = 9ˣ (mod 1073741823)