In this case we will determine if a generator value (\(g\)) is safe to be used with an order of a prime number \(p\). If it is, every value of \(g^x \pmod p\) will produce a unique output value in the range 1 to \((p-1)\). The typical values used for \(g\) are 2 and 5:
Picking g value within 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.
But, in order to demonstrate the principle, I have done this is a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well here’s a nice simple method in Python that I created to test up to p):
import sys def issafe(g,p): exp=1 rand=g next = rand % p while (next != 1 ): next = (next*rand) % p exp = exp+1 if (exp==p-1): return True else: return False p=11 g=4 if (len(sys.argv)>1): p=int(sys.argv[1]) if (len(sys.argv)>2): g=int(sys.argv[2]) print ("Is g={0} safe for p={1}? {2}".format(g,p,issafe(g,p))) print ("x\tg^x\tg^x (mod p)") for x in range(0,10): print ("{0}\t{1}\t{2}".format(x,pow(g,x),pow(g,x,p)))
A sample run with an unsafe value is:
Is g=3 safe for p=13? False x g^x g^x (mod p) 0 1 1 1 3 3 2 9 9 3 27 1 4 81 3 5 243 9 6 729 1 7 2187 3 8 6561 9 9 19683 1
and where the only output value is 1, 3 and 9. For a safe value we get:
Is g=3 safe for p=17? True x g^x g^x (mod p) 0 1 1 1 3 3 2 9 9 3 27 10 4 81 13 5 243 5 6 729 15 7 2187 11 8 6561 16 9 19683 14
Presentation
The following is an outline: