Criptosistemas de clave pública basados en el problema de las mochilas

Abstract

Un criptosistema de clave pública es un sistema de transmisión de mensajes entre un emisor y un receptor a través de una función de una vía, es decir, una función cuya inversa es muy difícil de calcular sin una información complementaria de la que sólo dispone el receptor legítimo. Una de estas funciones es el problema de las mochilas, que consiste en, dado un conjunto de pesos A y un número grande S, encontrar, si existe, un subconjunto de A tal que la suma de sus elementos sea S. Tanto los pesos como S son números naturales. El trabajo consistirá en una explicación y ejemplos del criptosistema de Merkle-Hellmann (1978), el posterior de Shamir (1982) y un resumen de las variantes surgidas hasta la fecha, dado que el sistema de Merkle-Hellmann ya no es útil.