The Pohlig Hellman method attacks groups which do not have an order of a group which is prime.
Pohlig Hellman attack |
What is an order?
In cryptographic systems, we typically implement within a group with a prime order of ℓ. But what does this mean? Well, let’s say we have a simple cipher and where we modular multiply by \(h\), and then to decipher, we modulo divide by \(h\). The cipher would then be:
\(c=h.x \pmod p\)
If we select \(p\) as 7 and \(h\) as 2, we then map:
x=0 -> c=0 x=1 -> c=3 x=2 -> c=6 x=3 -> c=2 x=4 -> c=5 x=5 -> c=1 x=6 -> c=4
And now we repeat:
x=7 -> c=0 x=8 -> c=3 and so on.
This is a ring which has outputs from 0 ... 6, and thus the number of valid outputs is 7. This is known as the order of the group, and in this case is a prime number. In this case number of possible outputs is equal to the prime number, but the order can differ from this as not all the outputs might be valid.
If we now have \(g^x \pmod p\), and with \(g=3\) and \(p=11\), we get:
x=0 -> c=1 x=1 -> c=3 x=2 -> c=2 x=3 -> c=6 x=4 -> c=4 x=5 -> c=5
And now we repeat:
x=6 -> c=1 x=7 -> c=3 and so on.
The order is 6. In discrete log problems the order is \(p-1\) and which will not be a prime number. This provides us with a problem: the Pohlig Hellman attack. So let's analyse.
Every composite number can be defined as product of prime powers, such that:
\(m={p_1}^{n_1}.{p_2}^{n_2}...\)
For example, if \(m=102\), we get:
\(102= 2 \times 3 \times 17\)
and where the three prime numbers are 2, 3 and 17.
For \(m=39883\), we get:
\(39883= 2 \times 3 \times 17 \times 17 \times 23 = 2 \times 3 \times 17^2 \times 23\)
If we have \(g^x \pmod p\) we can then factorize the order as:
\(order= p-1={p_1}^{n_1}.{p_2}^{n_2}...\)
This gives us a number of subgroups which are defined by the prime number factors.
The coding is:
import libnum import sys p=21 if (len(sys.argv)>1): p=int(sys.argv[1]) p_1=p-1 a=libnum.factorize(p_1) count=0 print(f"If we have g^x (mod p)") print(f"With: p={p}") print(f"Order: {p_1}") print(f"\nThe prime powers will be: ",end='') for key in a: for i in range(0,a[key]): if (count==0): print (f"{key}",end='') else: print (f"x{key}",end='') count=count+1
and a sample run is:
If we have g^x (mod p) With: p=7919 Order: 7918 The prime powers will be: 2x37x107
After we find the subgroups, we can determine:
\(x_1 = x \pmod {{p_1}^{n_1}}\)
...
\(x_k = x \pmod {{p_k}^{n_k}}\)
and where \(k\) is the number of prime numbers that make up the order. With this we can then use Chinese Remainder Theory to determine \(x \pmod p\):
\(x = x_1 \pmod {{p_1}^{n_1}}\)
...
\(x = x_k \pmod {{p_k}^{n_k}}\)