For \(Y=g^x \pmod p\), we can't just use any base generator value of \(g\), as we need to make sure that all of the values of \(x\) between 0 and \(p-1\) to produce values of \(Y\) between 0 and \(p-1\). To enable this the generator value must be a primitive root of \(p\). For this, we start with our prime (\(p\)), and then the order of the group will be \(p-1\). We can then factorize \(p-1\) into prime factors.
Picking g value in discrete logs |
Outline
In reading about cryptography, have you ever come across the term of a cyclic group \(G\) of order \(p\) and with a generator \(g\)? This article will hopefully explain what this means. The world of public key encryption is currently dominated by two things: discrete logarithms and elliptic curve methods. RSA is becoming a thing of the past for new applications, but it is only hanging on as it has such a monopoly in digital certificates. And so with discrete logarithms and the Diffie-Hellman method we end up with:
\(Y = g^x \pmod p\)
where we have a generator value (\(g\)) and a prime number \(p\). The challenge is that even though we know \(Y\), \(g\) and \(p\), it is extremely difficult to determine the \(x\) value if we use a large prime number.
So can we use any value of \(g\), and should it be as large as possible? The answer to both of these questions is no. If select a prime number of 7, and then select g values of 2, 3, 4 …9, and then calculate the results we get [spreadsheet]:
Now look at g=2, we get an output of 2, 4, 1, 2, 4 … for the sequence values of 1, 2, … This means that we do not get a unique output for the values from 1 to 6(where the maximum value will be six as we take the modulus of 7). But look at g=3, we get 3 (3¹ mod 7), 2 (3² mod 7), 6 (3³ mod 7), 4 (3⁴ mod 7), 5 (3⁵ mod 7), and 1 (3⁶ mod 7), which means that we get a unique value for all the possible outputs from 1 to 6, and which then repeats. For a prime number of 7, the valid values of g are 3 and 5.
Computing g
For \(Y=g^x \pmod p\), we can't just use any base generator value of \(g\), as we need to make sure that all of the values of \(x\) between 0 and \(p-1\) to produce values of \(Y\) between 0 and \(p-1\). To enables this the generator value must be a primitive root of \(p\). For this, we start with our prime (\(p\)), and then the order of the group will be \(p-1\). We can then factorize \(p-1\) into prime factors. For example, if \(p=97\), we have \(p-1=96\), and which can be factorized with \(2\times 2 \times 2 \times 2 \times 2 \times 3\). The prime factors of this are thus 2 and 3. We then check that \(g^x \pmod p\) for all these prime factors and make sure the result is not 1. So for 96, the factors we check are:
\(2, 3, 6 (2\times3), 12 (2\times2\times3), 24 (2\times2\times2\times3), 48 (2\times2\times2\times2\times3)\)
If we select \(g=3\), we get:
\(3^2 \pmod {97}= 9\)
\(3^3 \pmod {97}= 27\)
\(3^6 \pmod {97}= 50\)
\(3^{12} \pmod {97}= 75\)
\(3^{24} \pmod {97}= 96\)
\(3^{48} \pmod {97}= 1\) (not safe!!!)
Let’s see if 5 is safe:
\(5^2 \pmod {97}= 25\)
\(5^3 \pmod {97}= 28\)
\(5^6 \pmod {97}= 8\)
\(5^{12} \pmod {97}= 64\)
\(5^{24} \pmod {97}= 22\)
\(5^{48} \pmod {97}= 96\)
and so \(g=5\) is thus safe. An efficient way to compute this is:
def getG(p): eTotient=p-1 g=3 e = eTotient/2 while (pow(g,e,p) !=eTotient): g=g+2 return(g)
The final code is:
import sys def getG(p): eTotient=p-1 g=3 e = eTotient//2 while (pow(g,e,p) !=eTotient): g=g+2 return(g) p=997 if (len(sys.argv)>1): p=int(sys.argv[1]) g=getG(p) print(f"p={p}") print(f"g={g}")