If we have \(g^x \pmod p\) and where \(p\) is a prime number, can we find a value of \(g\) that makes sure that we get a unique output from 1 to \(p-1\), for every value of \(x\) from 0 to \(p-1\). This is known as the primitive root under modulo \(p\). In this case, we will discover the first 10 safe generators for a given prime number.
Creating a safe generator (\(g\)): Primitive root of a prime number p modulo p in Python |
Theory
Our online security is fundamentally dependent on hard problems. Unfortunately, most of the methods used cannot be proven to be hard problems, and where the RSA method, discrete logs and elliptic curve methods will generally not be hard problems in a post-quantum computer world. But, for just now:
\(Y=g^x \pmod p\)
is generally a hard problem to find \(x\), if we know \(Y\), \(g\) and \(p\) (as long the prime number — \(p\) - is large enough). These days, p needs to have at least 1,024 bits to be secure, and in many cases much more than that. But, can we pick any value of \(g\) and \(p\)? Well, normally we randomly generate a number of a given size, and then increment the value until we find that it is a prime number. Next, we must find a value of the generator \(g\), that will work with this prime number.
If we have \(g^x \pmod p\) and where \(p\) is a prime number, can we find a value of \(g\) that makes sure that we get a unique output from 1 to \(p-1\), for every value of \(x\) from 0 to \(p-2\)? This is known as the primitive root under modulo \(p\).
First, we need the Euler Totient Function (\(\varphi(p)\)) and, when \(p\) is a prime number this is:
\(\varphi(p) = p-1\)
Next, we find all the prime factors of \(\varphi(p)\). All powers are then computed as \(\varphi(p)\) divided by each prime factor. After this, all the powers from \(i\)=2 to \(p-1\) are tested for:
\(i^{powers} \pmod p\)
If this is 1, then \(i\) is not a primitive root of \(p\). If it is never 1, we return \(i\). The basic form is:
\(Y = g^x \pmod p\)
where we have a generator value (\(g\)) and a prime number \(p\). If select a prime number of 7, and then select \(g\) values of 2, 3, 4 … 9, and then calculate the results we get:
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^1 \pmod 7\)), 2 (\(3^2 \pmod 7\)), 6 (\(3^3 \pmod 7\)), 4 (\(3^4 \pmod 7\)), 5 (\(3^5 \pmod 7\)), and 1 (\(3^6 \pmod 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.
Example
Let's say we have a prime number of \(p=41\). First we determine that:
\(\varphi=40 \)
The factors of \( \varphi\) are then:
\(40 = 4 \times 10 = 2 \times 2 \times 2 \times 5\)
with this we would try \(g^{2} \pmod {41}\), \(g^{4} \pmod {41}\), \(g^{8} \pmod {41}\), \(g^{10} \pmod {41}\), and \(g^{20} \pmod {41}\) to see if any of these give a value of 1 for our generator value. So, let's test \(g=2\):
\(2^{2} \pmod {41} = 4\)
\(2^{4} \pmod {41} = 16\)
\(2^{8} \pmod {41} = 10\)
\(2^{10} \pmod {41} = 40 \)
\(2^{20} \pmod {41} = 1\)
So, we can see that \(2^{20} \pmod {41} = 1\)1, so it fails. Now, let's test \(g=3\):
\(3^{2} \pmod {41} = 9\)
\(3^{4} \pmod {41} = 40\)
\(3^{8} \pmod {41} = 1\)
\(3^{10} \pmod {41} = 9 \)
\(3^{20} \pmod {41} = 40\)
We can see that \(3^{8} \pmod {41} = 1\), and so \(g=3\) is not a safe generator for \(p=41\). Now, let's test \(g=5\):
\(5^{2} \pmod {41} = 25\)
\(5^{4} \pmod {41} = 10\)
\(5^{8} \pmod {41} = 18\)
\(5^{10} \pmod {41} = 40\)
\(5^{20} \pmod {41} = 1\)
We can see that \(5^{20} \pmod {41} = 1\), and so \(g=5\) is not a safe generator for \(p=41\). Now, let's test \(g=6\):
\(6^{2} \pmod {41} = 36\)
\(6^{4} \pmod {41} = 25\)
\(6^{8} \pmod {41} = 10\)
\(6^{10} \pmod {41} = 32\)
\(6^{20} \pmod {41} = 40\)
As none of these result in a value of 1, \(g=6\) is a safe generator for \(p=41\).
Coding
For the coding we can generate all the values from \(1\) to \(p-1\) for \(Y=g^x \pmod p\) and then determine is the values created are from \(1\) to \(p-1\), and where there are no repeated values:
import sys def getG(p): r = set(range(1, p)) res = [] for i in r: gen = set() for x in r: gen.add(pow(i,x,p)) if gen == r: res.append(i) if (len(res)>10): break return res p=997 if (len(sys.argv)>1): p=int(sys.argv[1]) print("Computing the first 10 generators") g=getG(p) print(f"p={p}") print(f"g={g}") print(f"\nNow trying the first 20 values for {g[0]} (there should be no repeated values):") print(f"x\tg^x (mod p)") print(f"===================") for i in range(0,p): print(f"{i}\t{pow(g[0],i,p)}") if (i>20): break
A sample run for \(p=41\) is:
Computing the first 10 generators p=41 g=[6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26] Now trying the first 20 values for 6: x g^x (mod p) 0 1 1 6 2 36 3 11 4 25 5 27 6 39 7 29 8 10 9 19
In this case we see that \(g=6\) is the first generator for \(p=41\).
Generating a safe generator in OpenSSL
In OpenSSL we can generate a random prime number of a given size, and it will create a safe generator for us. For example to generate a 512-bit prime number:
% openssl dhparam -text -out dhparams.pem 512 Generating DH parameters, 512 bit long safe prime ...............+..............+.........................+...++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++* % cat dhparams.pem DH Parameters: (512 bit) P: 00:b9:2e:60:17:90:5d:2e:dc:ef:4d:ba:33:61:13: a5:78:09:da:e5:85:f4:ee:49:ed:4d:6f:a1:93:51: 4f:f6:39:64:ff:52:67:9f:d8:21:ea:bb:3d:d3:61: fb:33:a1:70:ea:ee:4f:8e:b1:a1:f9:e1:ed:a3:f4: 83:7f:03:be:77 G: 2 (0x2) -----BEGIN DH PARAMETERS----- MEYCQQC5LmAXkF0u3O9NujNhE6V4CdrlhfTuSe1Nb6GTUU/2OWT/Umef2CHquz3T YfszoXDq7k+OsaH54e2j9IN/A753AgEC -----END DH PARAMETERS-----
and for a 1,024 bit random prime:
% openssl dhparam -text -out dhparams.pem 1024 Generating DH parameters, 1024 bit long safe prime ....................................................+.......................................................................................................................+......................+........................................................................++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*++*
and which gives:
DH Parameters: (1024 bit) P: 00:87:2b:31:4c:06:95:06:f4:70:66:8b:d4:95:b9: fb:cb:86:f9:45:4a:8d:2e:29:c9:f2:0f:bb:9e:c1: 37:cf:e8:a4:b2:0f:93:a0:d7:9a:ed:10:81:d9:60: 60:f7:8f:e3:eb:2a:1c:80:92:45:3d:28:2b:15:85: c5:a5:47:8e:be:38:61:a6:48:29:54:bc:bc:61:b5: 07:68:76:2b:7c:9d:ce:d6:a9:cf:87:8c:86:41:b3: 2a:1a:36:28:57:ab:d0:db:cf:82:0c:ac:0e:36:44: 5c:90:c0:b8:85:32:27:b9:07:67:6f:5d:08:0e:d1: ee:a5:ea:42:1f:2e:76:96:67 G: 2 (0x2) -----BEGIN DH PARAMETERS----- MIGHAoGBAIcrMUwGlQb0cGaL1JW5+8uG+UVKjS4pyfIPu57BN8/opLIPk6DXmu0Q gdlgYPeP4+sqHICSRT0oKxWFxaVHjr44YaZIKVS8vGG1B2h2K3ydztapz4eMhkGz Kho2KFer0NvPggysDjZEXJDAuIUyJ7kHZ29dCA7R7qXqQh8udpZnAgEC -----END DH PARAMETERS-----
In both cases, \(g=2\) is a safe generator for the parameters used. Overall, we use these parameters within the Diffie-Hellman key exchange method.