# Decryption of Naccache–Stern cryptosystem is not guaranteed for large keys

Naccache-Stern cryptosystem is mainly based on Chinese Remainder Theorem. According to its wiki page and Partially Homomorphic encryption book, I generated following keys.

1- Picked a family of k small distinct primes. I set k to 6 and primes are

pi = {3, 5, 7, 11, 13, 17}


2- Divide the set in half and find the multiplication of primes as

u = 3x5x7 = 105
v = 11x13x17 = 2431


3- Find sigma as multiplication of u and v

σ = u x v = 105 x 2431 = 255255


4- Choose large primes a and b such that both p = 2au+1 and q=2bv+1 are prime as well

a = 19903238899171
b = 5031940459031

p = 2au + 1 = 2x19903238899171x105+1 = 4179680168825911
q = 2bv + 1 = 2x5031940459031x2431+1 = 24465294511808723


5- Set n to p x q

n = pq = 4179680168825911 x 24465294511808723 = 102257106295492317188047918221653
ϕ(n) = (p-1)(q-1) = 102257106295492288543073237587020


6- Generate a generator g that satisfies g^(ϕ(n)/pi) != 1.

g=28805426433623101967928508095048


7- My plaintext is 17. I will encrypt this as

c = g^m mod n = 28805426433623101967928508095048 ^ 17 mod 102257106295492317188047918221653
c = 56869948461238576264190303866429


8- Decryption requires following steps

ci = c ^(ϕ(n) / pi) mod n
ci = 56869948461238576264190303866429 ^ (102257106295492288543073237587020 / 3) mod 102257106295492317188047918221653
ci = 55506363668208546317381600107672


Then we need to solve DLP from

ci == g^(j x ϕ(n) / pi) mod n for j = 1 to pi


However, there is no j satisfying the following equation.

55506363668208546317381600107672 == 28805426433623101967928508095048^(j*102257106295492288543073237587020/3) mod 102257106295492317188047918221653


I also added the guaranteeing decryption step in Benaloh which is not mentioned in wiki or book. This resolves decryption issues for small keys (35 bit for a and b) but it becomes problematic for larger keys.

Am I skipping some important steps in key generation or this cryptosystem does not guarantee decryption always? If decryption is not guaranteed, then is there a way to check out decryption is guaranteed while generating keys?

The question's $$g$$ is not suitable. Try e.g. $$g=30359963453720570073793540267704$$.

I read the question's condition 6 as: $$\forall p_i\in\mathcal S,\quad g^{\varphi(n)/i}\bmod n\ne1$$, with $$\mathcal S$$ the set $$\{3,5,7,11,13,17\}$$. This condition is met, and necessary, but it's not sufficient.

That's because in the Naccache–Stern cryptosystem, the order of $$g$$ modulo $$n$$ must be $$\varphi(n)/4$$ per the key generation procedure of the wiki reference.

Thus we also need $$g^{(p-1)(q-1)/4}\bmod n=1$$, and that's what's missing. As an aside, we also want to include $$a$$ and $$b$$ in the set $$\mathcal S$$, since they also are odd divisors of $$\varphi(n)$$; however that addition is unlikely to change the outcome.

In order to minimize trial and error in generating $$g$$, we can generate $$g_p\in[1,p)$$ of order $$(p-1)/2$$ modulo $$p$$ separately from $$g_q\in[1,q)$$ of order $$(q-1)/2$$ modulo $$q$$, and then compute $$g$$ per the Chinese Remainder Theorem as $$g=\bigl((g_p-g_q)(q^{-1}\bmod p)\bmod p\bigr)\,q+g_q$$.

To generate $$g_p$$, we can pick a random $$h_p\in[1,p)$$, compute $$g_p=h_p^{\,2}\bmod p$$, until $$g_p^{\,(p-1)/i}\bmod p\ne1$$ for each odd $$i$$ dividing $$p-1$$ (there are four $$i$$ in the question: $$3$$, $$5$$, $$7$$, $$19903238899171$$). Generation of $$g_q$$ is similar.

Another issue is that the question makes encryption per $$c=g^m\bmod n$$ rather than $$c=x^\sigma\,g^m\bmod n$$ for random $$x$$ as it's supposed to do. That compromises security (in particular by allowing to test a guess of $$m$$).

• I see I need to check g^(phi/4) mod n = 1 but generating numbers satisfying this condition is hard. When I make the calculations you recommended in the 2nd section order of g modulo n is not phi/4. Would you please make more details for the fast key generation. Nov 21, 2023 at 11:34
• @sefiks: with the question's parameters, more than one random $g$ out of 12 matches all the conditions. That's not very hard (though my procedure is faster). Short of adding code, I do not see what to add to my procedure: we generate $g_p$ iteratively as detailed, generate $g_q$ similarly (except for different modulus $q$ and different set of odd $i$ dividing $q-1$), then apply the formula given above to get $g$. By construction, $g^{\varphi(n)/4}\bmod n=1$ and all other required conditions hold.
– fgrieu
Nov 21, 2023 at 15:54