2.3 Algoritmos de clave pública o asimétricos

La criptografía de clave pública fue inventada en 1975 por Whitfield Diffie y Matin Hellman. Se basa en emplear un par de claves distintas, una pública y otra privada. La idea fundamental es que las claves están ligadas matemáticamente pero es computacionalmente imposible obtener una a partir de la otra.

Fundamentos matemáticos

Las funciones de una sola dirección son aquellas en las que obtener el resultado en una dirección es fácil, pero en la otra es casi imposible. Los algoritmos criptográficos de clave pública se basan en funciones de una sola dirección con puerta trasera, que son aquellos en los que el problema es resoluble en la dirección opuesta (la que antes era muy difícil) empleando una ayuda (la puerta trasera).

Los siguientes problemas matemáticos son considerados como funciones de una sola dirección con puerta trasera y son la base de la mayoría de algoritmos de clave pública actuales:

• Factorización de enteros. Un número entero siempre se puede representar como un producto de números primos denominados factores primos. La factorización de enteros consiste en encontrar los factores primos de un número. Los algoritmos criptográficos basados en este problema aprovechan el hecho de que la multiplicación de números primos grandes es computacionalmente sencilla pero la factorización un número grande en sus factores primos es muy cara computacionalmente.
• Logaritmos discretos. En aritmética módulo n dos enteros son equivalentes si tienen el mismo resto cuando son divididos por n. El resto de la división m / n es el menor entero no negativo que difiere de m por un múltiplo de n. La exponenciación discreta (a^x  mod  n) es la exponenciación en aritmética módulo n. Por ejemplo, 3⁴  mod  10 es 81  mod  10, que es equivalente a 1  mod  10. El logaritmo discreto es la operación inversa a la exponenciación discreta, el problema es encontrar la x tal que a^x = b  mod  n. Por ejemplo, si 11^x = 1  mod  10, entonces x = 2. Los algoritmos que emplean este tipo de problema se basan en que la exponenciación módulo n es un problema fácil y hallar el logaritmo discreto es un problema difícil.
• Logaritmos discretos de curva elíptica. Es una variación del problema anterior más cara computacionalmente, lo que permite usar claves más pequeñas que mejoran las prestaciones de los algoritmos y reducen el tamaño de los textos cifrados.

Tipos de algoritmo

En función de su relación matemática distinguimos varios tipos de algoritmo:

• Reversible. Es aquel en el que un mensaje encriptado con la clave privada puede ser desencriptado usando la clave pública y viceversa (uno encriptado usando la clave pública puede ser desencriptado usando la privada).
• Irreversible. Es aquel en el que un mensaje encriptado usando la clave privada puede ser desencriptado con la clave pública pero la clave privada no desencripta los mensajes cifrados usando la clave pública.
• De intercambio de claves. Sólo permiten negociar de forma segura una clave secreta entre dos partes. Hay que indicar que los algoritmos reversibles también se pueden emplear para esta función, pero los irreversibles no.

Aplicaciones

Este tipo de algoritmos tienen dos aplicaciones fundamentales:

1. Encriptación. Si un usuario A quiere mandar un mensaje a otro usuario B, lo encripta usando la clave pública de B. Cuando B lo recibe lo desencripta usando su clave privada. Si alguien intercepta el mensaje no puede descifrarlo, ya que no conoce la clave privada de B (de hecho, ni tan siquiera A es capaz de desencriptar el mensaje).
2. Firmas digitales. Si B encripta un mensaje usando su clave privada cualquiera que tenga su clave pública podrá obtener el texto en claro correspondiente; si alguien quiere hacerse pasar por B tendrá que cifrar el mensaje usando la misma clave privada o no se descifrará correctamente con la clave pública de B. Lo que B ha hecho es firmar digitalmente el mensaje. El proceso de desencriptar con una clave pública un mensaje firmado se denomina verificación de firma.

Estos algoritmos son mucho más caros que los de clave secreta, por lo que no se usan para encriptar mucha información. Su principal aplicación está en la fase inicial de una comunicación, ya que permiten que los dos extremos se autentifiquen e intercambien claves secretas para encriptar con un algoritmo simétrico.

El problema fundamental de este tipo de algoritmos es la distribución de las claves; aunque la clave pública se puede distribuir libremente (A la puede enviar por correo o decírsela a B por teléfono), nos queda el problema de la suplantación (C le puede dar su clave pública a B haciéndose pasar por A). Para solventar estos problemas se emplean autoridades certificadoras y certificados digitales, que discutiremos más adelante.