David Naccache and Jacques Stern — And The Uncracked Method With Homomorphic Addition
RSA has survived nearly five decades and is still going strong. However, there have been other methods for public key encryption that have not quite scaled the levels of RSA. And, so, in 1997, David Naccache and Jacques Stern produced a knapsack method for public key encryption, and which has still to be broken [1][here]:
Before we cover the Naccache-Stern Knapsack cryptosystem, we will first cover the method created by Ralph Merkle and Marty Hellman [2]:
Knapsack encryption provides a good approach to creating public and private keys, where the private key is easy to use, while the public key is difficult to compute. Within five years of the paper being published, Adi Shamir [3] cracked it, and so RSA was clear to become the de facto method:
The Knapsack problem
The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight. In general, the problem is:
- Given a set of numbers A and a number b.
- Find a subset of A which sums to b (or gets nearest to it).
So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).
So our code would become 11011 (represented by ‘1’, ‘4’, no ‘6’, ‘8’ and ‘15’).
Then, if our plain text is 11011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15, which gives us 28.
A plain text of 00001 will give us a cipher text of 15.
With public key cryptography, we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).
Creating a public and a private key
We can now create a superincreasing sequence with our weights where the current value is greater than the sum of the preceding ones, such as {1, 2, 4, 9, 20, 38}. Superincreasing sequences make it easy to solve the knapsack problem, where we take the total weight, and compare it with the largest weight, if it is greater than the weight, it is in it, otherwise, it is not.
For example, with weights of {1,2,4,9,20,38} with a value of 54, we get:
Check 54 for 38? Yes (smaller than 54). [1] We now have a balance of 16.
Check 16 for 20? No. [0].
Check 16 for 9? Yes. [1]. We now have a balance of 5.
Check 5 for 4? Yes. [1]. We now have a balance of 1.
Check 1 for 2? No. [0].
Check 1 for 1? Yes [1].
Our result is 101101.
If we have a non-superincreasing knapsack such as {1,3,4,6,10,12,41}, and have to make 54, it is much more difficult. So a non-superincreasing knapsack can be the public key, and the superincreasing one is the private key.
Making the Public Key
We first start with our superincreasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus (m) of a value which is greater than the total (m — such as 120). For n we make sure that there are no common factors with any of the numbers. Let’s select an n value of 53, so we get:
1×53 mod(120) = 53
2×53 mod(120) = 106
4×53 mod(120) = 92
10×53 mod(120) = 50
20×53 mod(120) = 100
40×53 mod(120) = 80
So the public key is: {53,106,92,50,100,80} and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy.
Let’s try to send a message that is in binary code:
111010 101101 111001
We have six weights so we split into three groups of six weights:
111010=53 + 106 + 92 + 100 = 351
101101 = 53+92+50+80 = 275
111001 = 53 + 106 + 92 + 80 = 331
Our cipher text is thus 351 275 331.
The two numbers known by the receiver is thus 120 (m — modulus) and 53 (n multiplier).
We need n^(−1), which is a multiplicative inverse of n mod m, i.e. n(n−1) = 1 mod m. For this we find the inverse of n (_n):
_n = 53^(-1) mod 120
(53 x _n) mod 120 = 1
So we try values of _n in (53 x _n mod 120) in order to get a result of 1:
So the inverse is 77 [Calculator].
The coded message is 351 275 331 and is now easy to calculate the plain text:
351×77 mod(120) = 27 = 111010 (1+2+4+20)
275×77 mod(120) = 55 = 101101
331×77 mod(120) = 47 = 111001
The decoded message is thus:
111010 101101 110001
which is the same as our original message:
111010 101101 111001
The decoding was so easy, the only thing we had was to find the inverse which is not too difficult.
Try this example here.
On this Wiki page [Here], the private key is {2, 7, 11, 21, 42, 89, 180, 354}, n=792, m=881, with data of “01100001” which gives a public key of {295, 592, 301, 14, 28, 353, 120, 236} and gives a cipher of “1129”. Try example here.
So, now let’s look at an improved method, and which has not been cracked …
Naccache-Stern Knapsack Cryptosystem
Initially, we select a large prime number (p). We then select a value (n) and for i from 0 to n, we select the first n prime numbers (p_0…p_{n−1} of which p_0 is 2. We must make sure that:
For our secret key (s) we make sure that:
and where gcd(a,b) is the greatest common denominator between a and b. To compute the public key (v_i), we calculate:
To cipher, we take a message of m and then determine the message bits of m_i. We can then cipher with the public key:
We then to decrypt:
Some simple code to implement this is [here]:
import sympy
import random
import math
import sys
from sympy.ntheory.modular import solve_congruence
# Code derived from https://github.com/serengil/LightPHE/blob/master/lightphe/cryptosystems/NaccacheStern.py
def generate_keys(key_size: int) -> dict:
private = {}
public = {}
prime_set = [3, 5, 7, 11, 13, 17]
k = len(prime_set)
if all(sympy.isprime(prime) is True for prime in prime_set) is False:
raise ValueError("All items of prime set must be prime!")
# 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
# product of all primes
sigma = u * v
# pick large prime numbers
while True:
a = sympy.randprime(200, 2 ** int(key_size / 2) - 1)
b = sympy.randprime(100, a)
# calculate two primes from chosen ones
p = (2 * a * u) + 1
q = (2 * b * v) + 1
# recommended n is 768 bits
n = p * q
phi = (p - 1) * (q - 1)
if phi % sigma != 0:
continue
if math.gcd(sigma, int(phi // sigma)) != 1:
continue
p_conditions = []
for i in range(0, int(k / 2)):
pi = prime_set[i]
if (
(p - 1) % pi == 0
and math.gcd(pi, int((p - 1) / pi)) == 1
and math.gcd(pi, q - 1) == 1
):
p_conditions.append(1)
else:
p_conditions.append(0)
p_satisfied = True if len(p_conditions) == sum(p_conditions) else False
if p_satisfied is False:
continue
q_conditions = []
for i in range(int(k / 2), k):
pi = prime_set[i]
if (
(q - 1) % pi == 0
and math.gcd(pi, int((q - 1) / pi)) == 1
and math.gcd(pi, p - 1)
):
q_conditions.append(1)
else:
q_conditions.append(0)
q_satisfied = True if len(q_conditions) == sum(q_conditions) else False
if q_satisfied is False:
continue
# p and q must be primes
if not (sympy.isprime(p) and sympy.isprime(q)):
continue
# choose a generator g
g = random.randint(2, n)
# it must be co-prime to n
if math.gcd(g, n) != 1:
continue
# guarantee it is not pi-th power.
for pi in prime_set:
if pow(g, int(phi / pi), n) == 1:
continue
# the order of g modulo n must be phi/4
if pow(g, int(phi / 4), n) != 1:
continue
is_decryption_guaranteed = True
for pi in prime_set:
prime_factors = sympy.factorint(pi).keys()
for prime_factor in prime_factors:
if pow(g, int(phi / prime_factor), n) == 1:
is_decryption_guaranteed = False
if is_decryption_guaranteed is True:
break
print(f"n bits is {len(bin(n)[2:])}")
public["g"] = g
public["n"] = n
# sigma can optionally be secret in deterministic version
public["sigma"] = sigma
private["p"] = p
private["q"] = q
private["phi"] = phi
private["prime_set"] = prime_set
return public,private
def generate_random_key(public) -> int:
n = public["n"]
return random.randint(1, n - 1)
def encrypt(plaintext: int, public) -> int:
g = public["g"]
n = public["n"]
r =generate_random_key(public)
sigma = public["sigma"]
return (pow(r, sigma, n) * pow(g, plaintext, n)) % n
def decrypt(ciphertext: int, private):
phi = private["phi"]
n = public["n"]
g = public["g"]
prime_set = private["prime_set"]
remainders = []
for i, prime in enumerate(prime_set):
ci = pow(ciphertext, int(phi / prime), n)
j = 0
while True:
if ci == pow(g, int((j * phi) / prime), n):
remainders.append(j)
break
j = j + 1
if j > prime**2:
raise ValueError(
f"c_{i} cannot be restored from {ci} = {g}^(j*{phi}/{prime}) mod {n}"
)
congruences = []
for i in range(0, len(prime_set)):
congruences.append((remainders[i], prime_set[i]))
# chinese remainder problem
ms = solve_congruence(*congruences)
if not ms:
raise ValueError("message cannot be restored with Chinese Remainder!")
return ms[0]
m=17
size=37
if (len(sys.argv)>1):
m=int(sys.argv[1])
if (len(sys.argv)>2):
size=int(sys.argv[2])
public,private=generate_keys(size)
print(f"Private key: {private}")
print(f"Public key: {public}")
c=encrypt(m,public)
dec=decrypt(c,private)
print(f"\nMessage: {m}")
print(f"\nCipher: {c}")
print(f"Decrypted: {dec}")and a sample run [here]:
n bits is 55
Private key: {'p': 59241211, 'q': 381185663, 'phi': 22581899851531020, 'prime_set': [3, 5, 7, 11, 13, 17]}
Public key: {'g': 9230441627496043, 'n': 22581900291957893, 'sigma': 255255}
Message: 50
Cipher: 3517812328284789
Decrypted: 50The implementation of homomorphic addition is:
Conclusion
And so Shamir cracked the Merkle knapsack public key method, but Naccache and Stern produced a knapsack version that has not yet been cracked. But, it doesn’t have proof of security, so it has not been adopted that much. If you are a researcher, please consider the method, as some papers are still using it:
- Hemlathadhevi, A. (2024). An Authentication Data Security in Cloud Medical Server (CMS) Using Homomorphic Encryption Process Based Naccache-Stern Cryptogram. International Journal of Scientific and Research in Engineering (IJSRE), 1(1), 17–24.
- Abdel-Basset, M., Mohamed, R., & ELkomy, O. M. (2022). Knapsack Cipher-based metaheuristic optimization algorithms for cryptanalysis in blockchain-enabled internet of things systems. Ad Hoc Networks, 128, 102798.
- Brier, É., Géraud, R., & Naccache, D. (2017, June). Exploring Naccache-Stern Knapsack Encryption. In International Conference for Information Technology and Communications (pp. 67–82). Springer, Cham.
- Micheli, G., Rosenthal, J., & Schnyder, R. (2016). An information rate improvement for a polynomial variant of the Naccache-Stern knapsack cryptosystem. In Physical and Data-Link Security Techniques for Future Communication Systems (pp. 173–180). Springer, Cham.
- Budiman, M. A., & Sitepu, R. (2018, March). File text security using hybrid cryptosystem with playfair cipher algorithm and Knapsack Naccache-Stern algorithm. In Journal of Physics: Conference Series (Vol. 978, №1, p. 012114). IOP Publishing.
References
[1] Naccache, D., & Stern, J. (1997, May). A new public-key cryptosystem. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 27–36). Springer, Berlin, Heidelberg.
[2] Merkle, Ralph; Hellman, Martin (1978). “Hiding information and signatures in trapdoor knapsacks”. Information Theory, IEEE Transactions on 24 (5): 525–530. doi:10.1109/TIT.1978.1055927.
[3] Shamir, Adi (1984). “A polynomial-time algorithm for breaking the basic Merkle — Hellman cryptosystem”. Information Theory, IEEE Transactions on 30 (5): 699–704. doi:10.1109/SFCS.1982.5.
