Baby-Step-Giant-Step solves for x in \(h = g^x \pmod p\). This solves for discrete logarithm problems:
Baby-Step-Giant-Step |
Outline
Within normal logarithms we define:
\(h = a^x\)
So if we want to find the value of x, we use:
\(x = log_a (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^x \pmod 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^x \pmod {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^i \pmod p\) and then store them in the form of {\(g^i \pmod 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^0 \pmod {53}\) gives 1 {1:0}.
For i=1 we get \(5^1 \pmod {53}\) gives 5 {5:1}
For i=2 we get \(5^2 \pmod {53}\) gives 5 {25:2}
We now have a list of pairs from 0 to the square root of p-1.
We now compute \( g^{-N} \) to give \(c\):
\(c = g^{N (p-2)} \pmod p\)
We then search through values of:
\(h c^x \pmod 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^x \pmod {53}\) we get:
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^9 \pmod {53}\), we get a result of 22.
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 plant and much more. For just 512 bit prime numbers we get:
>>> p=2**512–1 >>> int(math.ceil(math.sqrt(p — 1))) 115792089237316195423570985008 687907853269984665640564039457584007913129639936L
Which is a vast amount of memory.
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^x \pmod {2097151}\)
\(711087309 = 9^x \pmod {1073741823}\)
Presentation
An outline presentation is here [slides]: