criptosistema Naccache-Stern

• Elija una familia de k primos pequeños y distintos p ₁ ,..., p _k .
• Divide el conjunto por la mitad y coloca${\displaystyle u=\prod _{i=1}^{k/2}p_{i}}$y${\displaystyle v=\prod _ {k/2+1}^{k}p_ {i}}$.
• Colocar${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}$
• Elija primos grandes a y b tales que tanto p = 2 au +1 como q =2 bv +1 sean primos.
• Establecer n = pq .
• Elija un valor aleatorio g módulo n tal que g tenga orden φ( n )/4.

La clave pública son los números (σ, n , g ) y la clave privada es el par ( p , q ).

Los números primos (p ₁ , ..., p _k ) también son efectivamente públicos, ya que pueden recuperarse eficientemente a partir del valor público σ = Π pi, dado que son pequeños. Estos primos son necesarios durante el descifrado, donde se realizan cálculos módulo cada p _i para recuperar el mensaje.

Cuando k = 1, esto es esencialmente el criptosistema de Benaloh .

Este sistema permite el cifrado de un mensaje m en el grupo.${\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }$.

• Elige uno al azar${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$.
• Calcular${\displaystyle E(m)=x^{\sigma }g^{m}\mod n}$

Entonces E(m) es un cifrado del mensaje m .

Para descifrar, primero encontramos m mod p _i para cada i , y luego aplicamos el teorema chino del resto para calcular m mod${\displaystyle \sigma }$.

Dado un texto cifrado c , para descifrarlo, calculamos

• ${\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}$. De este modo

${\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}$

dónde${\displaystyle m_{i}\equiv m\mod p_{i}}$.

• Dado que p _i se elige pequeño, m _i se puede recuperar mediante una búsqueda exhaustiva, es decir, comparando${\displaystyle c_{i}}$a${\displaystyle g^{j\phi (n)/p_{i}}}$para j desde 1 hasta p _i -1.
• Una vez que se conoce m _i para cada i , m se puede recuperar mediante una aplicación directa del teorema chino del resto.