Picking a Safe Generator For Discrete Logs

Picking a Safe Generator For Discrete Logs

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:

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, to find a large prime number, we normally randomly generate a number of a given size, and then increment the value until we find that it is a prime. Next, we must find a value of the generator g, that will work with this prime number.

If we have g^x (modp) 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 (φ(p)) and, when p is a prime number this is:

φ(p)=p−1

This basically defines that we have p-1 possible values in input and output. Next, we find all the prime factors of φ(p). All the powers are then computed as φ(p) divided by each prime factor. After this, all the powers from i=2 to p−1 are tested for:

If this is 1, then i is not a primitive root of p. If it is never 1, we return i. The following is then the basic method using Python. For this, we will generate all the possible outputs for a given value of i and that it contains all the values from 0 to p−1.

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¹(mod7)), 2 (3² (mod7)), 6 (3³(mod7)), 4 (3⁴(mod7)), 5 (3⁵(mod7)), and 1 (3⁶(mod7)), 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:

φ=40

The factors of φ are then:

40=4×10=2×2×2×5

with this we would try g²(mod41), g⁴(mod41), g⁸(mod41), g¹⁰ (mod41), and g²⁰ (mod41) to see if any of these give a value of 1 for our generator value. So, let’s test g=2:

2² (mod41)=4

2⁴ (mod41)=16

2⁸ (mod41)=10

2¹⁰ (mod41)=40

2²⁰ (mod41)=1

So, let’s test g=3

3²(mod41)=9

3⁴(mod41)=40

3⁸(mod41)=1

3¹⁰(mod41)=9

3²⁰(mod41)=40

We can see that 38(mod41)=1, and so g=3 is not a safe generator for p=41.

So, let’s test g=5

5²(mod41)=25

5⁴(mod41)=10

5⁸(mod41)=18

5¹⁰(mod41)=40

5²⁰(mod41)=1

We can see that 5²⁰(mod41)=1, and so g=5 is not a safe generator for p=41 .

So, let’s test g=6:

6²(mod41)=36

6⁴(mod41)=25

6⁸(mod41)=10

6¹⁰(mod41)=32

6²⁰(mod41)=40

As none of these result in a value of 1, g=6 is a safe generator for p=41 [here].

Coding

For the coding we can generate all the values from 1 to p−1 for Y=g^x (mod p) and then determine is the values created are from 1 to p−1 , and where there are no repeated values [here]:

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 [here]:

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.

Conclusions

Discrete logs are cool, but watch out, they can trip you up! So, if you want the Diffie-Hellman key exchange method in your organisation, hopefully you will be using a safe generator value.