In this blog post, we will explore a step-by-step example of partially homomorphic encryption using ElGamal in Python. While many existing resources provide high-level overviews of the ElGamal encryption algorithm, in this post we will delve into the underlying mathematics and demonstrate how the algorithm actually works. We will cover key generation, encryption, and decryption, explaining the mathematical principles behind each step. Additionally, we will focus specifically on the math behind ElGamal’s partially homomorphic features, which allow for certain computations to be performed on encrypted data. We will explore how ElGamal enables both addition and multiplication of encrypted values, providing a detailed explanation of the math behind each operation. Finally, we will implement its homomorphic features in Python for both addition and multiplication. Whether you are a cryptography enthusiast or simply curious about the inner workings of encryption algorithms, this post will provide you with a comprehensive understanding of partially homomorphic encryption using ElGamal in Python. So, let’s dive into the math behind this powerful encryption scheme!
Vlog
You can either continue to read this tutorial or watch the following video. They both cover the partially homomorphic encryption example with ElGamal in python while giving a kindly proof of the algorithm with modular arithmetic.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
🐍 Python Library
In this post, we will mostly focus on the math behind the cryptosystem and implement it from scratch. If you are interested in how to use the algorithm easy and fast instead of its mathematical foundation, then you may consider to use LightPHE.
LightPHE is a lightweight partially homomorphic encryption library for python. It wraps many partially homomorphic algorithms such as RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, Okamoto–Uchiyama, Benaloh, Naccache–Stern, Goldwasser–Micali. With LightPHE, you can build homomorphic crypto systems with a couple of lines of code, encrypt & decrypt your data and perform homomorphic operations such as homomorphic addition, homomorphic multiplication, homomorphic xor, regenerate cipher texts, multiplying your cipher text with a known plain constant according to the built algorithm.
# pip install lightphe from lightphe import LightPHE # exponential elgamal is additively homomorphic cs = LightPHE(algorithm_name = 'Exponential-ElGamal') # define plaintexts m1 = 17 m2 = 23 # calculate ciphertexts c1 = cs.encrypt(m1) c2 = cs.encrypt(m2) # performing homomorphic addition on ciphertexts assert cs.decrypt(c1 + c2) == m1 + m2 # scalar multiplication (increase its value 5%) k = 1.05 assert cs.decrypt(k * c1) == k * m1 # standard elgamal is multiplicatively homomorphic cs2 = LightPHE(algorithm_name = 'ElGamal') # multiplicatively homomorphic operation assert cs2.decrypt(c1 * c2) == m1 * m2
You may consider to watch the LightPHE demo video.
Now, let’s turn back to understand and implement the crypto system from scratch!
ElGamal vs RSA
ElGamal is an important algorithm in public key cryptography but its reputation comes after RSA. ElGamal algorithm depends on the difficulty of computing logarithms over finite fields whereas RSA counts on the difficulty of factoring large integers. The both RSA and ElGamal are multiplicative homomorphic but ElGamal can be transformed to additively homomorphic while it losing its multiplicative homomorphic feature.
Generating Keys
Let’s describe the algorithm first.
We are expected to pick a generator g and a prime number modulus p.
g = 7 # generator p = 2083 # prime
To test the primeness of the modulus, we should have a validation step here.
def is_prime(n):
for i in range(2, n): # [2, n-1]
if n % i == 0:
return False
return True
assert is_prime(p)
Thereafter, we will pick an integer x for private key. Then, public key y will be x-th power of generator g in modulus p.
x = 17 #private key y = pow(g, x, p) # public
Generator g and modulus p are also shared as a public key. So, my private and public key pair are shown below for this configuration set.
private key is 17
public key is 2083, 7, 739
One will use my public key to encrypt messages and I will use my private key to decrypt messages.
Encryption and decryption
Encryption requires to generate a random integer r. Then, a tuple c1, c2 will be produced for encrypted message.
def encrypt(m, r):
c1 = pow(g, r, p)
c2 = (m * pow(y, r, p)) % p
return c1, c2
def decrypt(c1, c2):
return (c2 * pow(c1, -1*x, p)) % p
Suppose that the message I want to decrypt is 100. For each cycle, I need to create a random integer as well.
m = 100 r = random.randint(1, p-1)
Now, we can encrypt the message with pre-written functions. Notice that random integer was 1726 in my experiment.
c1, c2 = encrypt(m, r)
This returns (883, 1857) tuple in my experiment. You will have a different tuple because you might generate a different random key.
Thereafter, we can decrypt the message with the pre-designed function.
p = decrypt(c1, c2)
I can successfully restore the message 100 in that way!
Math behind ElGamal
We just implemented ElGamal encryption algorithm and it is working successfully. Let’s explain why it is working. We are using this c1 and c2 tuple to decrypt messages.
p = c2 x (c1)-x mod p
Let’s remember the c1 and c2 tuple calculations.
c1 = gr mod p
c2 = m x yr mod p
Replace c1 and c2 tuple in the decryption calculation p.
p = (m x yr) x (gr)-x mod p
And public key y was calculated with the x-th power of g where x is the private key.
p = (m x (gx)r) x (gr)-x mod p
As you can see, this multiplication includes gxr and g-xr as a multiplier. Multiplication of these two terms is 1. Then, p is equal to message itself.
p = m
This proof shows how ElGamal algorithm is working.
Math behind multiplicative homomorphic ElGamal
Let’s encrypt two different messages with ElGamal algorithm. Each encrypted message consists of c1 and c2 tuples. Notice that we are using different random integers while encrypting messages.
E(m1, r1): c1=(gr1 mod p) , c2=(m1 x yr1 mod p)
E(m2, r2): c1=(gr2 mod p) , c2=(m2 x yr2 mod p)
If we multiply the encrypted m1 and encrypted m2, then we will multiply c1 and c2 tuples eachother.
E(m1, r1).E(m2, r2): c1=(gr1gr2 mod p), c2=(m1m2yr1yr2 mod p)
Tuples have common base values. That is why, we can represent this multiplication as:
E(m1, r1).E(m2, r2): c1=(gr1+r2 mod p), c2=(m1m2yr1+r2 mod p)
On the other hand, if I multiply m1 and m2 and encrypt this multiplication with r1+r2 random integer, then I will have the same result.
E(m1m2, r1+r2): c1=(gr1+r2 mod p), c2=(m1m2yr1+r2 mod p)
That is why, ElGamal is homomorphic with respect to the multiplication.
Implementation of multiplicative homomorphic ElGamal
We will firstly decide numbers we want to encrypt and generate random integers for each of them.
m1 = 9 r1 = random.randint(1, p-1) m1_encrypted = encrypt(m1, r1) m2 = 11 r2 = random.randint(1, p-1) m2_encrypted = encrypt(m2, r2)
Thereafter, we must have same values when we multiply the encrypted values and encrypting the multiplication of plain numbers. Notice that 0-th index value is c1, and 1-st index value is c2.
h1 = encrypt(m1*m2, r1+r2) h2 = m1_encrypted[0]*m2_encrypted[0] % p , m1_encrypted[1]*m2_encrypted[1] % p assert h1 == h2
Neutral element and re-encryption
We shown that ElGamal is multiplicative homomorphic. What if we encrypted the message 1 and multiply it to any ciphertext? We expect not to break anything, right?
m1 = 9 r1 = random.randint(1, p-1) m1_encrypted = encrypt(m1, r1) m2 = 1 r2 = random.randint(1, p-1) m2_encrypted = encrypt(m2, r2)
In this case, you will have a different ciphertext than ciphertext of m1 itself. However, if you decrypt those different ciphertexts, then you will have same plaintext.
m1_times_1_encrypted = encrypt(m1*m2, r1+r2) assert m1_encrypted != m1_times_1_encrypted assert decrypt(m1_encrypted[0], m1_encrypted[1]) == decrypt(m1_times_1_encrypted[0], m1_times_1_encrypted[1])
This feature of ElGamal is currently being used in e-voting applications. You can change the ciphertext with re-encrypting it but actually plaintext remains same.
Math behind additive homomorphic exponential ElGamal
We have shown that ElGamal is homomorphic with respect to the multiplication. On the other hand, it is unfortunately not homomorphic with respect to the addition. Still, we are able make it additive homomorphic with small modification. However, it will lose its multiplicative homomorphic feature this time.
Remember the encryption calculations in ElGamal
E(m1, r1): c1=(gr1 mod p) , c2=(m1 x yr1 mod p)
E(m2, r2): c1=(gr2 mod p) , c2=(m2 x yr2 mod p)
Here, what if we will use m-th power of generator g instead of message itself in c2 calculations. I called this new function E’.
E'(m1, r1): c1=(gr1 mod p) , c2=(gm1 x yr1 mod p)
E'(m2, r2): c1=(gr2 mod p) , c2=(gm2 x yr2 mod p)
Now, let’s multipy them.
E'(m1, r1).E'(m2, r2): c1=(gr1gr2 mod p) , c2=(gm1gm2 x yr1yr2 mod p)
Combine the powers of same bases.
E'(m1, r1).E'(m2, r2): c1=(gr1+r2 mod p) , c2=(gm1+m2 x yr1+r2 mod p)
I will have the same result if find the addition of messages m1 and m2 while using r1+r2 random key.
E'(m1+m2, r1+r2): c1=(gr1+r2 mod p) , c2=(gm1+m2 x yr1+r2 mod p)
So, exponential ElGamal is homomorphic with respect to the addition. However, it loses its multiplicative homomorphic feature.
Implementation of additive homomorphic exponential ElGamal
I am going to modify the encrypt function to serve both standard ElGamal and exponential ElGamal. I added a 3rd optional exponential argument and its default value is False. It will behave same with standard ElGamal if we will not mention this argument or set this to False. However, if we set this argument to True, then it becomes exponential ElGamal.
def encrypt(m, r, exponential = False):
c1 = pow(g, r, p)
if exponential is True:
c2 = (pow(g, m, p) * pow(y, r, p)) % p
else:
c2 = (m * pow(y, r, p)) % p
return c1, c2
def decrypt(c1, c2):
return (c2 * pow(c1, -1*x, p)) % p
Now, let’s encrypt our message pair with exponential ElGamal.
m1 = 9 r1 = random.randint(1, p-1) m1_encrypted = encrypt(m1, r1, exponential = True) m2 = 11 r2 = random.randint(1, p-1) m2_encrypted = encrypt(m2, r2, exponential = True)
Then, we must have same results if we add the message pair and encrypt, or multiply encrypted message pair. Notice that 0-th index value is c1 and 1st index value is c2.
h1 = encrypt(m1+m2, r1+r2, exponential = True)
h2 = m1_encrypted[0]*m2_encrypted[0] % p , m1_encrypted[1]*m2_encrypted[1] % p
assert h1 == h2
Conclusion
In conclusion, we have explored a step-by-step example of partially homomorphic encryption using ElGamal in Python. Through our detailed examination of the underlying mathematical principles behind the ElGamal encryption algorithm, we have provided a comprehensive understanding of how this powerful encryption scheme works. We have also focused on the math behind its partially homomorphic features, demonstrating how ElGamal enables both addition and multiplication of encrypted values. By following our step-by-step guide, readers should now have a solid foundation for implementing partially homomorphic encryption using ElGamal in Python. Whether you are interested in the field of cryptography or simply looking to expand your knowledge of encryption algorithms, we hope that this blog post has provided you with valuable insights and inspiration.
In constrast to RSA, ElGamal is either multiplicatively or additively homomorphic algorithm. However, this does not mean that it is fully homomorphic. It loses its multiplicative homomorphic feature if it becomes additively homomorphic. We are currently seeing the usage of homomorphic ElGamal algorithm in e-voting systems.
I pushed the source code of this study to GitHub. You can support this work if you star its repo.
Like this blog? Support me on Patreon
