Criptosistema de mochila Naccache-Stern

El criptosistema de mochila Naccache-Stern es un criptosistema de clave pública atípico desarrollado por David Naccache y Jacques Stern en 1997. Este criptosistema es determinista y, por lo tanto, no es semánticamente seguro . Si bien hasta la fecha no ha sufrido fallas, este sistema también carece de seguridad demostrable .

Descripción general del sistema

Este sistema se basa en un tipo de problema de mochila . En concreto, el problema subyacente es el siguiente: dados los números enteros c , n , p y v ₀ ,..., v _n , hallar un vector tal que ${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle c\equiv \prod _{i=0}^{n}v_{i}^{x_{i}}\mod p}$

La idea aquí es que cuando los v _i son primos entre sí y mucho menores que el módulo p, este problema se puede resolver fácilmente. Es esta observación la que permite descifrarlo.

Generación de claves

Para generar un par de claves pública/privada

• Elija un módulo primo p grande .
• Elija un entero positivo n y para i desde 0 hasta n , establezca p _i como el i ésimo primo, comenzando con p ₀ = 2 y tal que No se pudo analizar (SVG (MathML se puede habilitar a través del complemento del navegador): Respuesta no válida ("La extensión Math no puede conectarse a Restbase") del servidor "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \prod_{i=0}^np_i < p} .
• Elija un entero secreto s < p -1, tal que mcd( p -1, s ) = 1.
• Colocar . ${\displaystyle v_{i}={\sqrt[{s}]{p_{i}}}\mod p}$

La clave pública es entonces p , n y v ₀ ,..., v _n . La clave privada es s .

Encriptación

Para cifrar un mensaje de n bits de longitud m , calcule

${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}\mod p}$

donde m _i es el i- ésimo bit del mensaje m .

Descifrado

Para descifrar un mensaje c , calcule

${\displaystyle m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\times \left(\gcd(p_{i},c^{s}\mod p)-1\right)}$

Esto funciona porque la fracción

${\displaystyle {\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}}$

es 0 o 1 dependiendo de si p _i divide c ^s mod p .

Seguridad

La seguridad de la función de trampilla se basa en la dificultad del siguiente problema multiplicativo de la mochila : dado que se recupera el . A diferencia de los criptosistemas aditivos basados ​​en la mochila, como Merkle-Hellman , las técnicas como la reducción reticular euclidiana no se aplican a este problema. $${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\pmod {p}},}$$ ${\displaystyle m_{i}}$

El ataque genérico más conocido consiste en resolver el problema del logaritmo discreto para recuperarse de , lo que se considera difícil para un computador clásico. Sin embargo, el algoritmo cuántico de Shor resuelve eficientemente este problema. Además, actualmente (2023), no hay ninguna prueba de que la mochila de Naccache-Stern se reduzca al problema del logaritmo discreto. ${\displaystyle s}$ ${\displaystyle p,p_{i},v_{i}}$

El ataque específico más conocido (en 2018) utiliza el teorema del cumpleaños para invertir parcialmente la función sin conocer la trampilla, asumiendo que el mensaje tiene un peso de Hamming muy bajo . ^[1]

Referencias

1. Anastasiadis, M.; Chatzis, N.; Draziotis, KA (octubre de 2018). "Ataques de tipo cumpleaños al criptosistema de mochila Naccache-Stern". Cartas de procesamiento de la información . 138 : 39–43. doi :10.1016/j.ipl.2018.06.002.

• Documento original
• Mejora reciente del ancho de banda

Véase también

• Criptosistema de mochila Merkle-Hellman
• Sistema criptográfico de mochila Graham-Shamir