The Beauty of the ElGamal Method: A Sage Implementation

The Beauty of the ElGamal Method: A Sage Implementation

One of the highlights of my academic year will be talking with Taher ElGamal:

Within the interview, he talks about how Len Adleman gave him a number of problems that needed to be solved, and where Taher just went ahead and tried lots of methods, and finally ended up with this mighty paper [here]:

It is a beautiful method, especially since it can now be used in homomorphic operations. So, let’s go ahead and implement it in Sage.

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 (mod 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 (mod p)

b=y^k.M (mod p)

Bob then receives these (a and b), and then uses his private key (x) to decrypt the values and discover the message:

M=b/(a^x) (mod p)

With the divide by (a^x) we basically take the inverse of (a^x) mod p, and then multiply. The operation works because:

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 × 2 × 2 × 2 × 2 × 3. The prime factors of this are thus 2 and 3. We then check that g^x (mod p) for all these prime factors and make sure the result is not 1. So for 96, all the factors are:

2, 3, 6 (2x3), 12 (2x2x3), 24 (2x2x2x3), 48 (2x2x2x2x3).

If we select g=3, we get:

3² (mod 97) = 9

3² (mod 97) = 27

3⁶ (mod 97) = 50

3¹² (mod 97) = 75

3²⁴ (mod 97) = 96

3⁴⁸ (mod 97) = 1 (not safe!!!)

Let’s see if 5 is safe:

5² (mod 97) = 25

5³ (mod 97) = 28

5⁶ (mod 97) = 8

5¹² (mod 97) = 64

5²⁴ (mod 97) = 22

5⁴⁸ (mod 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^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

A write-up is here:

https://asecuritysite.com/sage/sage05

Conclusions

ElGamal is a public key method that supports homomorphic operations and is being extensively used in privacy applications. Basically, now is the time for the method to shine.