With ElGamal encryption [1], Bob selects his public key by selecting a \(g\) value and a prime number (\(p\)) and then selecting a private key (\(x\)). He then computes \(Y\) which is: \(Y=g^x \pmod p\). His public key is \((Y, g, p)\) and he will send this to Alice. Alice then creates a message (\(M\)) and selects a random value (\(k\)). She then computes \(a\) and \(b\) so that \(a=g^k \pmod p\) and \(b=y^k M \pmod p\). Bob then receives these (\(a\) and \(b\)), and then uses his private key (\(x\)) to decrypt the values and discover the message: \(M=\frac{b}{a^x} \pmod p\). In this case, we will use a 128-bit prime number.
ElGamal and Sage with parameter |
Theory
Initially Bob creates his public key by selecting a \(g\) value and a prime number (\(p\)) and then selecting a private key (\(x\)). He then computes \(Y\) which is:
\(Y=g^x \pmod p\)
His public key is \((Y, g, p)\) and he will send this to Alice. Alice then creates a message (\(M\)) and selects a random value (\(k\)). She then computes \(a\) and \(b\):
\(a=g^k \pmod p\)
\(b=y^k M \pmod p\)
Bob then receives these (\(a\) and \(b\)), and then uses his private key (\(x\)) to decrypt the values and discover the message:
\(M=\frac{b}{a^x} \pmod p\)
Finding a safe generator (\(g\))
Now, we can't just use any base generator value of \(g\), and which 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)
Performing the ElGamal method in Sage
We can now generate a 256-bit random prime (p) and create a ring of numbers that go between 0 and p-1:
p = random_prime(2^256) ZZn = IntegerModRing(p)
Then we can find a value of g:
g=getG(p) g= ZZn (getG(p))
After this, we can compute the private key (x), and determine the public key (Y=g^x).
x = ZZn.random_element() k =ZZn.random_element() Y=g^x
If we then take a message (m), we can compute a and b:
a=g^k m=10 b = Y^k*m
Finally, we can decrypt with:
inv_a =Integer(a_x).inverse_mod(p) mrec=b*inv_a
The following defines the Sage code:
def getG(p): eTotient=p-1 g=3 e = eTotient/2 while (pow(g,e,p) !=eTotient): g=g+2 return(g) p = random_prime(2^128) ZZn = IntegerModRing(p) g=getG(p) g= ZZn (getG(p)) x = ZZn.random_element() k =ZZn.random_element() Y=g^x a=g^k m=10 str=sys.argv[1] m=int((str.split(";")[2]).replace(' ','')) b = Y^k*m a_x = a^x inv_a =Integer(a_x).inverse_mod(p) mrec=b*inv_a print (f"Private key:\nx={x}") print (f"\nPublic Key:\ng={g}\nY={Y}") print (f"\nMessage={m}") print(f"\nEncrypted: a={a}, b={b}") print (f"\nDecrypted m={mrec}")
A sample run is:
Private key: x=145989233190079244265598934367942210919 Public Key: g=5 Y=75736309579797081070896540172675055863 Message=100 Encrypted: a=23690150745699249008190470176472676965, b=134375371174769694230275224585319299547 Decrypted m=100
A sample run for a 256-bit prime number is:
Private key: x=5942060865465722774251983418118158365573262612768369196783988907335679740801 Public Key: g=3, Y=17234537431601839150379222183472286711211971411631153323383474368142376197660, p=26655532238364405728941235765122483592945012327485834468904083420451536409177 Message=10 Encrypted: a=25841696002926180348621136961158037851754154139840158945214997223330270042386, b=22799100849065094938649255302628019554623677569420002613910334737322207320692 Decrypted m=10
and again:
Private key: x=54232371423611932786737806573515879707286942381232417234251153801536553632090 Public Key: g=3, Y=66937885410437483431628247779123630521140326563995222715275366240935679310957, p=75819111097303633994598969976347208452361961036472977046990087268491824950567 Message=10 Encrypted: a=43593149293960090079448928339242762702469443863767036670288860089343280668594, b=13327600927493535327619616637138780552472880638066005810423803884308315002157 Decrypted m=10424064914411059368083007784170927300795552769227681297490258480 Decrypted m=10
and:
Private key: x=93471090300816244471563501263240199033022969178204034587158272989892017548 Public Key: g=13, Y=120945070115388125726509610754238384492088350536591918015681817139367481656, p=361236282528310698797965278097185872976185879597403088039216712182109903711 Message=10 Encrypted: a=77762843553707369750527355535165510389845486610026203147182003685888828081, b=218300343547037764671843191060174481784314035242539109385935486019764143493 Decrypted m=10
A talk with Taher ElGamal:
References
[1] ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4), 469-472 [here].