In the ever-evolving landscape of cybersecurity, encryption plays a pivotal role in safeguarding sensitive information. One intriguing facet of encryption is its ability to perform computations on encrypted data without revealing the underlying information, a property known as homomorphic encryption. One such encryption scheme that showcases this fascinating feature is the Naccache-Stern cryptosystem. However, delving into the world of partially homomorphic encryption can be a complex journey, especially when you factor in the requirement to solve the Chinese Remainder Problem for decrypting messages. In this blog post, we’ll take you on a step-by-step exploration of the Naccache-Stern encryption system, demonstrating how it can be employed to perform additively homomorphic encryption in Python, all while unraveling the intricacies of the Chinese Remainder Problem along the way. Join us as we unlock the secrets behind this powerful encryption technique and provide you with a comprehensive understanding of its practical application.
🐍 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.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
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 = 'Naccache-Stern') # 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
You may consider to watch the LightPHE demo video.
Now, let’s turn back to understand and implement the crypto system from scratch!
Key Generation
We are going to k different small prime numbers.
prime_set = [3,5,7,11,13,17] k = len(prime_set) import sympy assert all(sympy.isprime(prime) is True for prime in prime_set) is True
Then, we will divide this prime set in half, and calculate the product of these two prime sets u and v:
# divide the set in half and find products of primes
u = 1; v = 1
for i, prime in enumerate(prime_set):
if i < len(prime_set)/2:
u = u * prime
else:
v = v * prime
Thereafter, calculate the product of all items in the prime set, and store this into sigma
sigma = u*v
Next, we will pick two large prime numbers a and b such that 2au+1 and 2bv+1 are also prime.
while True:
# pick large prime numbers
a = sympy.randprime(100, 200)
b = sympy.randprime(100, 200)
assert sympy.isprime(a)
assert sympy.isprime(b)
# calculate two primes from chosen ones
p = (2*a*u)+1
q = (2*b*v)+1
if sympy.isprime(p) and sympy.isprime(q):
break
After, we will calculate modulo n and ϕ similar to RSA.
n = p*q phi = (p-1)*(q-1)
Finally, we are going to pick a generator g. Its order must be phi(n)/4.
g = 131 assert g < n
So, sigma, n and g will be our public keys whereas p and q will be private keys.
print(f'public keys: {sigma}, {n}, {g}')
print(f'private keys: {p}, {q}')
Encryption
Cryptosystem allows us to encrypt messages less than sigma
m = 202 assert m < sigma
Basically, to encrypt messages, we are going to perform the calculation as:
c = gm mod n
def encrypt(m):
return pow(g, m, n)
c = encrypt(m)
Decryption
To decrypt a ciphertext c, we will basically perform the calculation
ci = cϕ(n)/pi mod n
for each prime number in our prime set.
Then, do the following brute force attack to find mi values for each pi.
for j from 1 to pi-1, if ci == gjϕ(n)/pi then mi = j
Once, mi is known for each i, m can be found with Chinese Remainder Theorem. Magical sympy comes with out-of-the-box implementation for Chinese remainder theorem.
def decrypt(c):
# find mi values for each i
mi_set = []
for i, prime in enumerate(prime_set):
ci = pow(c, int(phi/prime), n)
for j in range(1, prime):
if ci == pow(g, int((j*phi)/prime), n):
mi_set.append(j)
# find equations such that m = mi mod pi
congruences = []
for i in range(0, k):
print(f'm mod {prime_set[i]} = {remainders[i]}')
congruences.append((remainders[i], prime_set[i]))
# chinese remainder theorem
from sympy.ntheory.modular import solve_congruence
ms = solve_congruence(*congruences)
ms = [i for i in ms if i > sigma]
m = ms[0]
return m
So, we restored the plaintext from ciphertext!
Homomorphic Features
Naccache-Stern cryptosystem comes with additively homomorphic features. Multiplying the encryption of two messages is equivalent to encryption of their sum.
m1 = 100 m2 = 200 c1 = encrypt(m1) c2 = encrypt(m2) assert (c1*c2) % n == encrypt(m1+m2) assert decrypt((c1*c2) % n) == m1+m2
Proof of Homomorphic Features
To encrypt a message m, we are performing the calculation:
E(m) = gm mod n
So, encrypting m1 and m2 pair will give these ciphertexts.
E(m1) = gm1 mod n
E(m2) = gm2 mod n
Multiply two ciphertexts
E(m1).E(m2) = gm1gm2 mod n
According to the product rule of exponent rules, when multiplying two exponential terms with the same base, you can combine their exponents by addition.
E(m1).E(m2) = gm1+m2 mod n
On the other hand, if we encrypt m1+m2, then we will have same ciphertext, too.
E(m1+m2) = gm1+m2 mod n
So, this proves the additively homomorphic feature of Naccache-Stern cryptosystem because multiplying the encryption of two messages is equivalent to encryption of their sum.
E(m1+m2) = E(m1).E(m2)
Proof of Decryption
To decrypt a ciphertext c, we basically performed the calculation
ci = cϕ(n)/pi mod n
for each prime number in our prime set.
Ciphertext was calculated as gm mod n
ci = (gm)ϕ(n)/pi mod n
ci = gmϕ(n)/pi mod n
Here, we are going to make a magic. Instead of using plaintext m in the decryption, let’s use a variable mi such that dependent to plaintext m and current prime pi.
yi = (m – mi)/pi
yipi = (m – mi)
m = yipi + mi
Replace the m’s equivalent to
ci = gmϕ(n)/pi mod n
ci = g(yipi + mi)ϕ(n)/pi mod n
ci = g(yipi + mi)ϕ(n)/pi mod n
ci = gyipiϕ(n)/pi + miϕ(n)/pi mod n
pi terms can be simplified because it is available in both dividend and divisor
ci = gyiϕ(n) + miϕ(n)/pi mod n
According to product rule of exponent rules, this can be represented as
ci = gyiϕ(n)gmiϕ(n)/pi mod n
The term gyiϕ(n) mod n will vanish because yiϕ(n) is being multiple of ϕ(n).
ci = gmiϕ(n)/pi mod n
Here, we are going to solve this discrete logarithm problem with brute force
for j from 1 to pi-1, if ci == gjϕ(n)/pi then mi = j
Once mi is known for each i, m can be restored with Chinese Remainder Theorem.
Conclusion
In this journey through the world of partially homomorphic encryption with the Naccache-Stern cryptosystem, we’ve not only explored the fascinating concept of additively homomorphic encryption but also delved into the intriguing intricacies of the Chinese Remainder Problem. We’ve witnessed how this combination of mathematical principles can be harnessed to protect and process sensitive data, offering a powerful tool for privacy preservation. As we wrap up this exploration, it’s essential to acknowledge the significance of understanding and applying encryption techniques like Naccache-Stern, especially in a world where data security is paramount. Whether you’re an aspiring cryptographer or a cybersecurity enthusiast, the knowledge gained from this journey empowers you to contribute to the ongoing evolution of secure data management. As technology advances, so does the need for robust encryption solutions, and we hope this blog post has equipped you with the insights and skills to be at the forefront of this critical domain, helping to ensure the confidentiality and integrity of data for years to come.
I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo.
Like this blog? Support me on Patreon
