Sage and ElGamal
[ElGamal Home][Home]
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\).
TheoryInitially 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 SageWe 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^256) 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 b = Y^k*m a_x = a^x inv_a =Integer(a_x).inverse_mod(p) mrec=b*inv_a print (f"Private key: x={x}") print (f"Public Key: g={g}, Y={Y}") print (f"Message={m}") print(f"Encrypted: a={a}, b={b}") print (f"Decrypted m={mrec}") A sample run 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]. |