Picking g value in discrete logs from random prime numberFor \(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. |
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)
Coding
The coding is:
import sys import Crypto.Util.number def getG(p): eTotient=p-1 g=3 e = eTotient//2 while (pow(g,e,p) !=eTotient): g=g+2 return(g) bits=16 if (len(sys.argv)>1): bits=int(sys.argv[1]) p=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) print ("\nRandom n-bit Prime (p): ",p) g=getG(p) print(f"p={p}") print(f"g={g}")
An example with 16-bit primes:
Number of bits in prime is 16 Random 16-bit Prime (p)=51749 g=3
An example with 32-bit primes:
Number of bits in prime is 32 Random 32-bit Prime (p)=3391475587 g=3
An example with 64-bit primes:
Number of bits in prime is 64 Random 64-bit Prime (p)=18041698990511379517 g=5
An example with 128-bit primes:
Number of bits in prime is 128 Random 128-bit Prime (p)=278502388752072551854523704008712344571 g=3
An example with 128-bit primes:
Number of bits in prime is 128 Random 128-bit Prime (p)=278502388752072551854523704008712344571 g=3
An example with 256-bit primes:
Number of bits in prime is 256 Random 256-bit Prime (p)=70697469854278733436184483511259501469680432396505511211311794451246366637283 g=3
An example with 512-bit primes:
Number of bits in prime is 512 Random 512-bit Prime (p)=9295983158396816302773696017447501160778105101816318493571401865857289652763219481245748583387088151487793267056347152352724427343141665720028122191054647 g=5
An example with 1024-bit primes:
Number of bits in prime is 1024 Random 1024-bit Prime (p)=125675696246570471066497492640874419388383144532026250352965316482120823283974094646464286162721225013663329902150488028642336462849932896940567552948995121843267291905520638385423357938549533302620789058946402525532410889492647926735445574441827834125557774168208133377146636426279499478751505794295587327921 g=11