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.


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?


1 Answer 1


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$).

  • $\begingroup$ 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. $\endgroup$
    – sefiks
    Nov 21, 2023 at 11:34
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Nov 21, 2023 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.