El sistema RSA

El sistema de cifrado de clave pública más conocido y utilizado es probablemente el RSA, inventado en 1978 por Ronald Riverst, Adi Shamir y Leonard Adelman, del MIT (Massachusetts Institute of Technology).[1]

El método se basa en las dos constataciones siguientes:

• Es relativamente fácil encontrar dos números primos grandes y multiplicarlos para dar un número N = p x q que sirva para una clave de cifrado. 
• El proceso inverso, esto es, la determinación de p y q a partir de un número grande N es imposible de realizar en un tiempo aceptable. Esta imposibilidad garantiza que un eventual espía no podrá descifrar el mensaje aunque conozca el número N. 

Un ejemplo simplificado de este planteamiento:

Para que Alicia pueda enviar un mensaje a Bernardo con toda seguridad, Bernardo elige dos números primos grandes p y q cuya división por 3 de cómo resto 2 (hay otra posibilidad además de estos valores 3 y 2), calcula N = p x q y transmite a Alicia el valor de N. Para enviar su mensaje, Alicia lo transforma en una sucesión de cifras y luego lo divide en segmentos de longitud aproximadamente igual a N.

Alicia envía cada fragmento por separado del modo siguiente. Supongamos que un fragmento es un número x: Alicia calcula el resto y de la división de x3 por N y el segmento cifrado es simplemente el numero y.

Para descifrar el segmento recibido, Bernardo utiliza el número ultrasecreto e = (2 (p - 1) (q – 1) + 1/3, el cual debido a la elección de p y q, es entero.

Se puede demostrar, efectivamente, que si y es un fragmento codificado siguiendo el método anterior, el fragmento original x es igual al resto de la división de ye por N. El cálculo puede realizarse muy rápidamente. Como se ve, para descifrar el mensaje en clave ni siquiera es necesario acordarse de p y q, basta acordarse de e. Es muy importante que este entero e no caiga en poder de un eventual espía, pero como Bernardo es el único que lo conoce, los riesgos de indiscreción son muy reducidos.

La importancia de la teoría de números en criptografía es tal que los matemáticos se ven confrontados a problemas deontológicos. Por ejemplo, si uno de ellos descubre un método de factorización numérica mucho más eficaz que los precedentes, ¿qué debe hacer? ¿Comunicarlo al presidente, exponerlo públicamente en una conferencia internacional para que nadie pueda aprovecharse de él a expensas de otros o venderlo al mejor postor? Afortunadamente, hasta dónde se sabe, las mejoras encontradas por los matemáticos no son lo bastante revolucionarias como para que el problema se plantee en toda su acuidad.

(H. Cohen, Mundo Científico/54; extracto - adaptado)

[1] R. L. Rivest et al, Communications of the ACM, 21, 120, 1978.

 Ver ejemplo y más