Criptosistema Nakasha-Stern

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de octubre de 2019; las comprobaciones requieren 4 ediciones .

El criptosistema Nakasha- Stern es un algoritmo criptográfico de clave pública basado en la complejidad computacional del problema del logaritmo discreto . A diferencia de RSA , es homomórfico con respecto a la suma y la resta, no a la multiplicación .

Desarrollado por David Nakache y Jacques Stern en 1998 [1] en dos versiones: determinista y probabilística. Es una mejora del esquema Benalo [2] : los autores pudieron construir un criptosistema homomórfico probabilístico con seguridad semántica y reducir significativamente la relación entre el tamaño del texto cifrado y el tamaño del texto sin formato .

Hay una implementación (python3) de algoritmos de generación de claves, cifrado y descifrado [3] .

Comparación con RSA

Similitudes

Uso de números RSA [1]

Diferencias

Uso de varias funciones unidireccionales con una entrada secreta . Como enfatizan los autores de [1] , este punto es de gran interés teórico, ya que, en su opinión, en este momento solo existe una pequeña variedad de funciones unidireccionales con entrada secreta, y esto afecta directamente la velocidad de creación. nuevos criptosistemas de clave pública [1] .
La solidez de este algoritmo no está directamente relacionada con la solidez del algoritmo de cifrado del criptosistema RSA . Es decir, la seguridad de RSA está relacionada con la complejidad del problema de factorización de enteros , y la seguridad del criptosistema Nakas-Stern está relacionada con la complejidad del problema del logaritmo discreto [4] .
El criptosistema RSA es homomórfico con respecto a la multiplicación, mientras que el criptosistema Nakas-Stern es homomórfico con respecto a la suma [1] .

Descripción de la variante determinista del criptosistema

En general, una versión determinista del criptosistema Nakasha-Stern se puede describir de la siguiente manera: sea un B-smooth (B es pequeño, generalmente un número de 10 bits), un número impar, sin cuadrados , y sea un RSA número (generalmente se piensa que es al menos un número de 768 bits) tal que divide y es coprimo con , donde es la función de Euler . A continuación, vamos a ordenar . Entonces el triple de números forma una clave privada. Un mensaje menor que se cifra como . El descifrado se basa en el uso de divisores primos del número [1] . $\sigma$ $n=pq$ $norte$ $\sigma$ $\phi(n)$ ${\ estilo de visualización \ phi (n)/\ sigma}$ $\phi(n)$ $g\en \mathbb {Z} /n\mathbb {Z}$ $\phi(n)/4$ ${\ estilo de visualización p, \ q, \ \ sigma}$ $metro$ $\sigma$ $g^{m}mod\ n$ $\sigma$

Generación de claves

Elija "pequeños primos " donde es par. Aquí, la frase "pequeños números primos" significa que el primero de los números primos (1, 3, 5, ...) se toma o se genera de alguna otra manera que no sea usando algoritmos para generar números primos grandes. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Dejar , y $u=\prod_{i=1}^{k/2}p_{i}$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\ estilo de visualización \ sigma = uv = \ prod _ {i = 1} ^ {k} p_ {i}}$
Elige 2 "primos grandes" tales que , sean primos. Aquí, la frase "primos grandes" se usa en el sentido en que se usa en algoritmos para generar números primos grandes. $un, \ b$ $p=2au+1$ $q=2b\upsilon +1$
deja _ En la literatura, el número , el producto de "primos grandes", se denomina número RSA. $n=pq$ $norte$
Elija un número aleatorio tal que y sea el orden ${\ estilo de visualización g \ mod \ n}$ $gramo$ $\phi(n)/4$

Entonces la clave pública está formada por un triple de números . Y cerrado - [1] ${\ estilo de visualización \ sigma, \ norte, \ g}$ ${\ estilo de visualización p, \ q}$

A medida que el número crece, la generación de claves se convierte en una operación que requiere mucho tiempo, ya que el número a debe estar en un rango adecuado y, además, satisfacer las pruebas de primalidad junto con el número . Para sortear esta dificultad, los autores proponen generar primero números primos y luego, mediante la selección de números primos auxiliares , lograr la igualdad y , donde son primos [1] . $norte$ $p=2au+1$ ${\ estilo de visualización a, \ b, \ u, \ upsilon}$ ${\ estilo de visualización p', q'}$ $p=2aup'+1$ $q=2b\upsilon q'+1$ ${\ estilo de visualización p, \ q}$

Cifrado

El cifrado consta de una sola operación de exponenciación módulo : un mensaje menor que , se cifra como . Y aquí no se usan de ninguna manera . [una] $norte$ $metro$ $\sigma$ $E(m)=g^{m}mod\ n$ $\sigma$

Descifrado

El descifrado se basa en el teorema del resto chino . Sean divisores primos . El algoritmo calcula y luego descifra el mensaje m utilizando el teorema chino del resto [1] . $p_{i},\ 1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\mod\ p_{i))$

Para encontrar mi dado el texto cifrado , el algoritmo calcula , que es exactamente . Esto se deduce de los siguientes cálculos, aquí : . Al comparar este resultado con todas las potencias posibles de , se puede encontrar el valor de . Más formalmente, la función de descifrado está representada por un pseudocódigo [1] : $c=g^{m}mod\ n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$ $g^{m_{i}\phi(n)/p_{i))\mod\n$ ${\displaystyle y_{i}=(m-m_{i})/p_{i))$ ${\textstyle c_{i}\ =\ c^{\phi (n)/p_{i))\ =\ g^{m\phi (n)/p_{i))\ =\ g^{(m_ {i}+y_{i}p_{i})\phi (n)/p_{i}}\ =\ g^{m_{i}\phi (n)/p_{i}}g^{y_{ i}\phi (n)}\ =\ g^{m_{i}\phi (n)/p_{i}}\ mod\ n}$ $g^{j\phi(n)/p_{i))$ $mi}}$

para = 1 a : $i$ $k$
$c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$

para = 0 a - 1: $j$ $Pi}$

si : $c_{i}==g^{j\phi (n)/p_{i))\ mod\ n$

${\ estilo de visualización m_ {i} = j}$

$X$ = Recordatorio Chino( , ) $mi$ $Pi}$

Ejemplo

Generación de claves para $k = 6$

[cm. "Descripción de una variante determinista de un criptosistema"]

${\ estilo de visualización p = 21211 = 2 * 101 * 3 * 5 * 7 + 1}$

${\ estilo de visualización q = 928643 = 2 * 191 * 11 * 13 * 17 + 1}$

${\ estilo de visualización n = 21211 * 928643 = 19697446673}$

${\ estilo de visualización g = 131}$

${\ estilo de visualización \ sigma = 3*5*7*11*13*17}$

$p_{1}=3,...,p_{6}=17$

{\ estilo de visualización \ {i, j \}}

contiene

g^{j\phi (n)/p_{i}}\ mod\ n\ mod\ 10000

	yo=1	yo=2	yo=3	yo=4	yo=5	yo=6
j = 0	una	una	una	una	una	una
j = 1	1966	6544	1967	6273	6043	372
j = 2	9560	3339	4968	7876	4792	7757
j = 3		9400	1765	8720	262	3397
j = 4			6488	8651	6291	702
j = 5			2782	4691	677	4586
j = 6				9489	1890	8135
j = 7				8537	6878	3902
j = 8				2312	2571	5930
j = 9				7701	7180	6399
j = 10					8291	9771
j = 11					678	9771
j = 12						609
j = 13						7337
j = 14						6892
j = 15						3370
j = 16						3489

Cifrado ${\ estilo de visualización m = 202}$

$c=g^{m}mod\ n=131202\ mod\ 19697446673$

Descifrado

$c^{\phi(n)/p_{1}}\mod\nmod\10000=1996$

$c^{\phi(n)/p_{2}}\ mod\ n\ mod\ 10000=3339$

$c^{\phi(n)/p_{3}}\ mod\ n\ mod\ 10000=2782$

$c^{\phi(n)/p_{4}}\ mod\ n\ mod\ 10000=7994$

$c^{\phi(n)/p_{5}}\ mod\ n\ mod\ 10000=1890$

$c^{\phi (n)/\ p_{6))\ mod\ n\ mod\ 10000=3370$

A continuación, utilizando la tabla anterior:

$m_{1}=m\ mod\ 3=tabla(1996)=1$

$m_{2}=m\ mod\ 5=tabla(3339)=2$

$m_{3}=m\ mod\ 7=tabla(2782)=1996$

$m_{4}=m\ mod\ 11=tabla(7994)=4$

$m_{5}=m\ mod\ 13=tabla(1890)=7$

$m_{6}=m\ mod\ 17=tabla(3370)=15$

y por el teorema del resto chino obtenemos: [1] ${\ estilo de visualización m = 202}$

Descripción de la variante probabilística del criptosistema

Una variante probabilística de un criptosistema es una mejora de los criptosistemas probabilísticos anteriores (por ejemplo, el criptosistema Benalo).

Los criptosistemas anteriores tenían un inconveniente muy importante: para cifrar un pequeño conjunto de datos (por ejemplo, los votos 0, 1 en la votación electrónica), los criptosistemas deterministas, como RSA, no son adecuados [1] , porque para el descifrado bastará con compare el texto cifrado con los elementos cifrados del conjunto . Esta propiedad de los criptosistemas, la incapacidad de distinguir textos cifrados de diferentes elementos del conjunto S, se denomina seguridad semántica [5] . Pero con una combinación de homomorfismo y fuerza semántica, los criptosistemas anteriores comenzaron a generar alrededor de un kilobyte de texto cifrado para cifrar el texto sin formato en unos pocos bits [1] . En el criptosistema Nakasha-Stern, además de tener las propiedades de homomorfismo, fuerza semántica, la relación entre el tamaño del texto cifrado y el tamaño del texto plano es exactamente igual a . Los autores afirman que es seguro tomar [1] . $S$ $S$ ${\ estilo de visualización n/\ sigma}$ ${\ estilo de visualización \ sigma / n <{\ frac {1} {4}}}$

Generación de claves

Elija "primos pequeños" donde sea par. Aquí, la frase "pequeños números primos" significa que el primero de los números primos (1, 3, 5, ...) se toma o se genera de alguna otra manera que no sea usando algoritmos para generar números primos grandes. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Dejar , y $u=\prod_{i=1}^{k/2}p_{i}$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\ estilo de visualización \ sigma = uv = \ prod _ {i = 1} ^ {k} p_ {i}}$
Elige 2 "primos grandes" tales que , sean primos. Aquí, la frase "primos grandes" se usa en el sentido en que se usa en algoritmos para generar números primos grandes. $un, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Sea un número RSA. $n=pq$
Elija un número aleatorio tal que y sea el orden ${\ estilo de visualización g \ mod \ n}$ $gramo$ $\phi(n)/4$

Entonces la clave pública está formada por un triple de números . Y cerrado - [1] ${\ estilo de visualización \ sigma, \ norte, \ g}$ ${\ estilo de visualización p, \ q}$

Cifrado

El cifrado probabilístico es muy similar al cifrado determinista . "Descripción de una variante determinista de un criptosistema"] . Es decir, sea un número positivo elegido al azar del anillo de residuos módulo : . Entonces el algoritmo se escribe como [1] $X$ $norte$ $x\in \mathbb {Z} /n\mathbb {Z}$ $E(m)=x^{\sigma }g^{m}mod\ n$

Descifrado

El descifrado en la versión probabilística del algoritmo de D. Nakache y J. Stern permanece sin cambios en comparación con la versión determinista [ver. "Descripción de una variante determinista de un criptosistema"] . El efecto de multiplicar por en el cifrado se tiene en cuenta cuando elevamos el texto cifrado a la potencia de . Hagamos algunos cálculos para verificar esto. ${\ estilo de visualización x ^ {\ sigma}}$ ${\ estilo de visualización \ phi (n) / p_ {i))$

Sean divisores primos . El algoritmo calcula y luego descifra el mensaje usando el Teorema del Resto Chino. $p_{i},1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\mod\ p_{i))$ $metro$

Para encontrar , dado el texto cifrado , el algoritmo calcula , que es exactamente . Esto se deduce de los siguientes cálculos: $mi$ $c=x^{\sigma }g^{m}mod\ n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$ $g^{m_{i}\phi(n)/p_{i))\mod\n$

{\begin{matriz}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{matriz}}

Comparando este resultado con todas las potencias posibles de , se puede encontrar el valor [1] $g^{j\phi(n)/p_{i))$ $mi}}$

Aplicación

En la mayoría predominante de las áreas de aplicación del criptosistema Nakasha-Stern, se utiliza la propiedad de homomorfismo de este criptosistema con respecto a la suma y la resta [6] [2] :

Supongamos que un cliente tiene una cuenta bancaria y quiere retirar una pequeña cantidad . También asumimos que el saldo se almacena en forma encriptada , y el representante del banco, al realizar la operación de retirar el monto de la cuenta del cliente , no tiene acceso para descifrar los datos de la cuenta. Con la ayuda del criptosistema Nakasha-Stern, se propone una solución simple a este problema a través de la operación : este es el valor del nuevo saldo de cuenta en forma encriptada: . Más formalmente: sean los algoritmos de cifrado de la cuenta , luego la cuenta es igual a la suma y se calcula mediante la siguiente fórmula: [1] . $metro$ $tu$ $metro$ ${\ estilo de visualización E (m)}$ $tu$ ${\ estilo de visualización E (m) / E (u) \ mod \ n}$ ${\ estilo de visualización mu}$ $E(m_{1})=g^{m_{1}}mod\ n,\ E(m_{2})=g^{m_{2}}mod\ n$ $m_{1},\ m_{2}$ $m_1$ $m_2$ $E(m_{1})E(m_{2})=g^{m_{1}}g^{m_{2}}mod\ n=g^{m_{1}+m_{2} }mod\n$
Seguridad informática en la nube . Suponga que la nube contiene muchos usuarios (clientes) . El usuario tiene datos sensibles almacenados en la nube. Este servicio en la nube se llama Storage aaS (almacenamiento como servicio). El usuario puede aplicar a la nube con una solicitud para calcular el valor de alguna función en función de datos confidenciales. La solicitud debe consistir en una descripción de la función , la identificación del usuario y la clave pública del usuario . La nube debe comprobar la autoridad informática del usuario . Dicha verificación se puede implementar utilizando el procedimiento estándar de firma digital electrónica . Si el usuario ha validado sus derechos para calcular la función , la nube debe calcular el valor y enviárselo al usuario. Como se puede tomar la función de cifrado de cualquier criptosistema homomórfico de clave pública, como, por ejemplo, el criptosistema Nakache-Stern. Un usuario que almacena sus datos confidenciales y envía una solicitud para evaluar la función no confía en la nube y debe tomar las medidas y requisitos adecuados para garantizar su seguridad. Evidentemente, sería mucho más seguro transferir datos de forma que durante las operaciones que se realicen sobre ellos no se divulgue de ninguna forma información sobre estos datos. Por lo tanto, en primer lugar, los datos deben estar encriptados y deben llegar al servidor ya en forma encriptada. Esto significa que el usuario aún debe realizar el cifrado. En segundo lugar, es necesario procesar estos datos sin descifrarlos, ya que se deben seguir ciertos procedimientos para transmitir y almacenar la clave secreta , especialmente complejos si la información se procesa en un entorno no confiable. Los criptosistemas con encriptación homomórfica solo ayudan a resolver estos problemas [7] [2] . $S$ ${\displaystyle p_{1},...,p_{i},...,p_{l))$ $Pi}$ $x_{yo}$ $Pi}$ $F$ $F$ ${\displaystyle pk_{i))$ $Pi}$ ${\ Displaystyle F (x_ {i})}$ $F$ $E(pk_{i},\ F(x_{i}))$ $mi$ $F$

Ofuscación para proteger los productos de software. Por primera vez, el uso de ofuscación en criptografía fue mencionado en el trabajo de Diffie y Hellman [8] . En él, para construir un criptosistema asimétrico, se propone utilizar la complejidad de la tarea, que consiste en analizar programas en un lenguaje de programación de bajo nivel (ensamblador, bytecode). El objetivo principal de la ofuscación es dificultar la comprensión del funcionamiento del programa. Dado que todas las arquitecturas informáticas tradicionales utilizan cadenas binarias, al aplicar un cifrado completamente homomórfico sobre bits, se puede calcular cualquier función. Por lo tanto, es posible cifrar homomórficamente todo el programa para que conserve su funcionalidad [9] .
Voto electrónico. Es decir, que haya candidatos y la dirección, que dispone de este criptosistema, reparte entre los participantes una boleta-vector , donde figura el apellido del enésimo candidato. Y cada participante tiene una clave pública . Como resultado, obtenemos: cada votante regresa a la dirección un vector , donde está el vector de preferencias. El ganador de la elección es el candidato que recibió la mayor cantidad de votos en total; este número, la suma de los votos, se calcula sobre vectores cifrados de votantes. Esto es posible gracias al homomorfismo. Y el beneficio de este enfoque es que no hay necesidad de descifrar los datos de los votantes para contar los votos: aumenta la seguridad de las elecciones para los votantes [10] . $norte$ ${\ estilo de visualización (p_{1},...,\ p_{n})}$ $Pi}$ $i$ $paquete$ ${\ estilo de visualización (\ nu _ {1},..., \ nu _ {n})}$ ${\ estilo de visualización \ nu _ {i} \ en \ {0,1 \}}$
Área de marca de agua [11] . El homomorfismo del criptosistema le permite aplicar una marca de agua a los datos cifrados [12] .
Prueba de conocimiento cero . Los sistemas homomórficos se utilizan cuando se hace necesario confirmar la posesión de cualquier información que pueda verificarse sin revelar la información misma [13] [14] .

Ataques

Los ataques ampliamente conocidos a este criptosistema no están documentados. Los propios autores alientan el trabajo para romper el criptosistema. El artículo original ofrecía [1] $768 a alguien que pudiera descifrar el texto cifrado y publicar el método de criptoanálisis . A continuación se muestran los datos para esta tarea. $C$

$C$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a 16

$gramo$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743 16

$norte$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d 16

Aquí ( — se forman a partir de los primeros números primos, excepto 2) [1] . ${\ estilo de visualización k = 30}$ $Pi}$ $i$

Enlaces

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Jacques, Stern. Un nuevo criptosistema de clave pública basado en residuos superiores // ACM . - 1998. - P. 59–66 . Archivado desde el original el 6 de diciembre de 2006.
↑ 1 2 3 IA Troubey. Cifrado homomórfico: seguridad informática en la nube y otras aplicaciones (revisión) (ruso) // Informática. - 2015. - Enero. Archivado desde el original el 26 de noviembre de 2018.
↑ Implementación de algoritmos de cifrado, descifrado y generación de claves en el criptosistema Nakashe-Stern . Consultado el 16 de diciembre de 2018. Archivado desde el original el 28 de diciembre de 2020. (indefinido)
↑ Thomas W. Cusick. Una comparación de RSA y el criptosistema de clave pública Naccache-Stern // Protocolos de seguridad. — Berlín, Heidelberg: Springer Berlin Heidelberg, 1997. — P. 111–116 . — ISBN 9783540624943 , 9783540680475 . -doi : 10.1007/ 3-540-62494-5_10 . Archivado desde el original el 2 de diciembre de 2018.
↑ S. Goldwasser, S. Micali. Cifrado probabilístico (inglés) // JCSS. - 1984. - Abril. - pág. 270-299 .
↑ Una breve descripción del criptosistema homomórfico y sus aplicaciones // Revista internacional de aplicaciones informáticas. — 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. Sobre bancos de datos y homomorfismos de privacidad // Fundamentos de computación segura.
↑ W. Diffie, M. Hellman. Nuevas direcciones en criptografía // IEEE Trans. inf. teoría.
↑ J. Alwen [et al.] Sobre la relación entre el cifrado funcional, la ofuscación y el cifrado completamente homomórfico // Criptografía y codificación: 14.º pasante de IMA. Conf., IMACC-2013..
↑ JD Cohen Benaloh. Elecciones con voto secreto verificable (inglés) // Universidad de Yale: tesis doctoral. — 1988.
↑ B. Pfitzmann, M. Schunter. Toma de huellas dactilares asimétricas (inglés) // Spinger-Verlag. - 1996. - P. 84-95 .
↑ Construcción de un esquema de marca de agua dependiente del contenido seguro mediante el cifrado homomórfico.
↑ O. Goldreich, S. Micali, A. Wigderson. Pruebas que no arrojan nada más que su validez y una metodología de diseño de protocolos criptográficos . - 1986. - P. 174-187 .
↑ G. Brassard, D. Chaum, C. Crepeau. Discusión mínima Pruebas de conocimiento // JCSS. - 1988. Archivado el 27 de septiembre de 2011.

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP