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…
