Los criptosistemas de mochila son criptosistemas cuya seguridad se basa en la dureza de resolver el problema de la mochila . Siguen siendo bastante impopulares porque las versiones simples de estos algoritmos se han roto durante varias décadas. [1] Sin embargo, ese tipo de criptosistema es un buen candidato para la criptografía post-cuántica . [ cita requerida ]
El criptosistema de mochila más famoso es el criptosistema de clave pública Merkle-Hellman , uno de los primeros criptosistemas de clave pública , publicado el mismo año que el criptosistema RSA . Sin embargo, este sistema se ha roto por varios ataques: uno de Shamir , [2] uno de Adleman, [3] y el ataque de baja densidad .
Sin embargo, existen criptosistemas de mochila modernos que se consideran seguros hasta ahora: entre ellos se encuentra Nasako-Murakami 2006. [4]
Se cree que los criptosistemas de mochila, cuando no están sujetos al criptoanálisis clásico, son difíciles incluso para las computadoras cuánticas. Ese no es el caso de los sistemas que se basan en factorizar números enteros grandes, como RSA , o calcular logaritmos discretos , como ECDSA , problemas resueltos en tiempo polinómico con el algoritmo de Shor . [5]
Referencias
- ^ Schneier, Bruce (2004). Secretos y mentiras . Wiley Publishing, Inc. pág. 95 . ISBN 978-0-471-25311-2.
- ^ Shamir, 1982 .
- ^ Adleman, 1982 .
- ^ Nasako y Murikami 2006 .
- ^ Shor, Peter (1997). "Algoritmos de polinomio-tiempo para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación . 26 (5): 1484–1509. arXiv : quant-ph / 9508027 . doi : 10.1137 / s0097539795293172 . S2CID 2337707 .
Bibliografía
- Leonard Adleman (1982), "Sobre la ruptura del criptosistema de clave pública titulado Merkle-Hellman", Crypto'82 , Springer: 303–308, doi : 10.1007 / 978-1-4757-0602-4_29 , ISBN 978-1-4757-0604-8
- Adi Shamir (1982), "Un algoritmo de tiempo polinomial para romper los criptosistemas básicos de Merkle-Hellman", Focs'82 : 145-152, doi : 10.1109 / SFCS.1982.5
- T. Nasako; Y. Murakami (2006), "Un criptosistema de mochila de alta densidad con trampilla combinada" , Sociedad Japonesa de Matemáticas Industriales y Aplicadas , 16 (4): 519–605, doi : 10.11540 / jsiamt.16.4_591