In the field of cryptography, homomorphic encryption is a powerful technique that enables computations to be performed on encrypted data without the need to decrypt it. This is achieved through a variety of mathematical operations and algorithms, with one of the most popular being RSA encryption. In this blog post, we will explore a step-by-step example of partially homomorphic encryption using RSA in Python. We will cover the basics of RSA encryption, including key generation, encryption and decryption. We will then delve into the concept of partially homomorphic encryption, and demonstrate how it can be applied to perform simple computations on encrypted data. Whether you are a beginner in cryptography or a seasoned practitioner, this blog post will provide you with a comprehensive overview of partially homomorphic encryption using RSA in Python.
Vlog
You can continue to read this tutorial or watch the following video. They both cover the partially homomorphic encryption with RSA in Python.
🙋♂️ 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 # build a cryptosystem cs = LightPHE(algorithm_name = 'RSA') # define plaintexts m1 = 17 m2 = 23 # calculate ciphertexts c1 = cs.encrypt(m1) c2 = cs.encrypt(m2) # performing homomorphic multiplication on ciphertexts assert cs.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!
Generating RSA keys
The algorithm expects to pick two prime numbers first. In a practical application, these should be large primes but we will use small ones in this example.
p = 11; q = 13
To have a safety net, we should check the primeness of this p and q pair. A prime number must not be divided by another number less than it without remainder. If you set a non-prime number to p or q, then this program will raise an error.
def is_prime(n):
for i in range(2, n): # [2, n)
if n % i == 0:
return False
return True
assert is_prime(p)
assert is_prime(q)
Fermat-Euler Theorem
Then, we will find the module n and totient n (or shortly phi) variables from p and q.
n = p * q
phi = (p-1)*(q-1)
print(f"totient({n}) = {phi}")
These variables are coming from the Euler’s generalization of Fermat’s Little Theorem.
aφ(n) = 1 mod n
Totient function of n counts the positive integer numbers that co-prime to n. We know that if n is a prime number, then positive integer number that co-prime to it should be (n-1). However, we picked the n as the multiplication of two prime numbers. Even though, n is a prime number, it is the multiplication of two prime numbers. Herein, totient function is a multiplicative function. Instead of counting positive integer numbers that co-prime to it, we can find the multiplication of its multipliers’s totient function results.
phi(n) = phi(p*q) = phi(p)*phi(q) = (p-1)*(q-1)
In that way, we can find the phi with O(1) complexity. Otherwise, we can build a for loop to find positive integer numbers that co-prime to it but this requires O(n) complexity. Remember that n should be multiplication of two large primes. We do not want to spend that time!
Private Public Key Pair
Thereafter, we should pick a random integer that co-prime to phi. We can check the co-primeness of two integer with math module of python. It comes with a greatest common divisor function.
import math # private key e = 7 assert math.gcd(e, phi) == 1
After then, we need to find the multiplicative inverse of our private key for module phi. Normally, we can use extended Euclidean algorithm to find the multiplicative inverse. However, this is much easier after Python 3.8. We will use Python’s power function directly. It expects base, exponent and modulus arguments respectively. Base will be the private key, exponent will be -1 and finally modulus will be phi. Notice that we set the exponent to -1 to find the multiplicative inverse. E.g. multiplicative inverse of 3 is 3-1 and multiplication of a number with its multiplicative inverse must be 1.
d = pow(e, -1, phi) assert (e * d) % phi == 1
So, public key will be 103 while private key was 7 for n = 143 and phi = 120.
Encryption
We are ready to encrypt and decrypt messages when we have private and public key. Suppose that the message we would like to encrypt is 99.
m = 99
To encrypt a message, we will find its e-th power for modulus n. We can use python pow function for encryption purposes.
c = pow(m, e, n)
Then, ciphertext c will be 44.
Decryption
We are going to apply same procedure of encryption in decryption. We will just use public key (d) instead of private key (e). Then, message must be restored.
p = pow(c, d, n) assert p == m
Partially Homomorphic Encryption
We have shown how to encrypt and decrypt messages with RSA. Now, let’s encrypt a message pair.
m1 = 9; m2 = 11
Now, I will encrypt these message pair with the private key (e).
m1_encrypted = pow(m1, e, n) # 44 m2_encrypted = pow(m2, e, n) # 132
Multiplication of encrypted m1 and encrypted m2 pair in module n should be equal to the encryption of multiplication of plain m1 and m2 pairs if RSA is multiplicative homomorphic.
# validates that RSA is partially homomorphic assert (m1_encrypted * m2_encrypted) % n == pow(m1*m2, e, n) % n
Encrypted m1 is 44 and encrypted m2 is 132. Multiplication of these numbers in module 143 is 44. Really, I will get the same number if I encrypt 99 (9×11) directly.
Proof of RSA homomorphic feature
While encrypting messages in RSA, we are finding the e-th power of messages.
E(m1) = (m1)e mod n
E(m2) = (m2)e mod n
If we multiply these two statement, we will have a general statement as shown below.
E(m1)E(m2) = (m1)e . (m2)e mod n
The both m1 and m2 bases have common power e. We can put these bases into a parenthesis with same power.
E(m1)E(m2) = (m1m2)e mod n
On the other hand, if we multiply m1 and m2 first and encrypt this multiplication second, then we will have same result.
E(m1m2) = (m1m2)e mod n
So, this shows that RSA encryption algorithm is homomorphic with respect to the multiplication.
Use case
Imagine that your salary is encrypted on a database with RSA algorithm. Then, your salary can be updated with your yearly wage increase without having the private key. For example, if you have 20% wage increase, firstly 1.2 should be encrypted with RSA algorithm and secondly this should be multiplied with your encrypted salary. That is all! Then, you will see the encrypted version 20% added your new salary. On the other hand, RSA is not additive homomorphic. So, we will not be able to add a constant amount of bonus such as 500 USD with this approach. Similarly, standard ElGamal is a multiplicative homomorphic algorithm but its exponential extension is just additive homomorphic. Adding constant bonus case can be done with exponential ElGamal but it cannot apply yearly wage increasement.
Conclusion
In conclusion, we have explored a step-by-step example of partially homomorphic encryption using RSA in Python. We covered the basics of RSA encryption, including key generation, encryption, and decryption, and demonstrated how to implement them in Python. Furthermore, we delved into the concept of partially homomorphic encryption, which allows for certain types of computations to be performed on encrypted data. We showed how RSA can be partially homomorphic, allowing for multiplication of encrypted values. While RSA is not fully homomorphic, it is still a powerful encryption scheme that can be used in a variety of applications. By following our guide, readers should now have a solid understanding of how to implement partially homomorphic encryption using RSA in Python, and how it can be used to perform computations on encrypted data.
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
