Month: April 2011

Desde el principio de los tiempos, los humanos han deseado en ocasiones mantener la privacidad de sus comunicaciones. En tiempos de los romanos ya se utilizaban técnicas de criptografía como el cifrado César para las comunicaciones militares.

El cifrado César consiste en la sustitución simple de unas letras por otras, por ejemplo, sustituir la “a” por “c”, “b” por “d”, “c” por “e”, etc. Con lo que por ejemplo, “cifrado cesar” se convertiría en “ekhtcfq eguct”. Este sistema (y muchos otros) se basa en el secreto del sistema- sólo el emisor y receptor del mensaje conocen el método de cifrado y la manera en la que se realiza- en este caso, que cada letra se sustituye por la letra que existe a dos posiciones en el orden alfabético; lo que se conoce como clave secreta.

A pesar de que el cifrado César no ofrece prácticamente ninguna seguridad (una persona que intercepte un mensaje puede fácilmente deducir el sistema usado y desencriptarlo), sí que existen mecanismos de encriptación muy potentes basados en el secreto de la clave (básicamente, un sistema de clave secreta fuerte es aquel en el que podemos hacer que los mensajes sean más difícilmente desencriptables escogiendo claves más complejas).

Sin embargo, en muchas situaciones, los sistemas de claves secretas no son muy útiles. Para hacerlos funcionar, el emisor y el receptor deben poder compartir la clave de una manera segura antes de poder utilizarla.

Pongamos por ejemplo el caso de que queramos realizar transacciones seguras por internet, por ejemplo compras online. Como internet no es un canal de comunicación seguro (es razonablemente sencillo espiar, interceptar y alterar comunicaciones), antes de realizar cualquier compra a un vendedor online, deberíamos poder quedar con el vendedor y acordar una clave secreta por un canal seguro- por ejemplo, quedando presencialmente e intercambiando la clave, algo que no parece nada práctico.

Un investigador de una agencia de inteligencia británica dio en 1973 con un sistema tremendamente sencillo para resolver este problema. Lamentablemente, no lo pudo implementar ni publicar- ya que en ese momento no disponían de los sistemas informáticos suficientemente potentes como para hacerlo funcionar, y al formar parte de una agencia de inteligencia, se consideró un secreto de estado. En 1978, un trío de matemáticos- Rivest, Shamir y Adleman redescubrieron independientemente este sistema y lo publicaron con un nombre tomado de sus iniciales: RSA.

El sistema se basa en un concepto sencillo. En los esquemas de clave secreta, se utiliza una única clave y dos funciones matemáticas de codificación y decodificación. Formalmente, sea un mensaje m, una clave k, y dos funciones E(m,k) y D(m,k), se cumple que D(E(m,k),k)=m; es decir, que las codificar y decodificar un mensaje con la misma clave, se obtiene de nuevo el mensaje original.

El nuevo esquema RSA se basa en que las claves de codificación y decodificación son diferentes, y a pesar de que están íntimamente relacionadas, conocer una no implica conocer la otra. Con esto, yo puedo crear un par de claves; a una la llamaré clave pública y a la otra privada- siguiendo sus nombres, difundiré mi clave pública pero conservaré en secreto mi clave privada.

Así, cualquiera que quiera enviarme un mensaje, podrá coger mi clave pública y codificar el mensaje con ella. Sólo yo, con mi clave privada, podré descifrarlo.

Es decir, si pub es mi clave pública y prv mi clave privada, C la función de codificación y D la de decodificación, D(C(m,pub), prv)=m

Una propiedad interesante de este sistema es que si las funciones se escogen de manera que este proceso funciona a la inversa (puedo “decodificar” con la clave privada primero y al “recodificar” con la clave pública recupero el mensaje original también), yo puedo coger un mensaje y codificarlo con mi clave privada. Si publico el mensaje y la versión codificada, cualquiera que conozca mi clave pública podrá decodificar el mensaje que he codificado y verificar que coincide con el mensaje original. Poder codificar el mensaje de esta manera para que la gente lo pueda verificar sólo lo puede hacer el conocedor de la clave privada- así pues esta operación permite demostrar que el mensaje proviene del propietario de la clave privada. A esta operación se la denomina firma digital y tiene todas las utilidades de una firma en papel tradicional (con la ventaja que es más difícil de falsificar).

¿Cómo funciona este sistema? Pues tanto el investigador inglés como los señores RSA, tuvieron la brillante idea de realizar este esquema al ver el pequeño teorema de Fermat y/o el teorema de Euler. Estos teoremas sobre exponenciación, números primos y cocientes nos permiten encontrar una función de codificación y decodificación (exponenciación y cociente) usando como exponentes y cocientes unos números concretos basados en números primos que permiten que funcione todo esto. Las operaciones de codificación y decodificación son opuestas, y a pesar de que los números (claves) privados y públicos están profundamente relacionados, su relación no es fácilmente descubrible- para descubrirla hemos de factorizar en primos los números que lo componen, lo cuál es un problema complejo.

Lo mejor de todo es que obtener claves muy muy grandes (que hacen que la descomposición sea lenta), es muy sencillo. Podemos generar números primos gigantescos con relativa facilidad, y al componerlos, obtener un número enorme cuya descomposición es infinitamente más costosa.

El sistema RSA lo tiene todo: es muy, muy sencillo, podemos hacerlo tan difícilmente de romper como queramos (buscando primos mayores)… lo único que falla es que es relativamente lento; las operaciones de codificación son lentas. La solución aquí es sencilla- los esquemas de clave privada tienen a ser extremadamente veloces, así que normalmente lo que haremos es usar el sistema de criptografía asimétrica para intercambiar una clave para una codificación de clave privada; así el sistema de clave pública nos resuelve el problema de compartir la clave privada por un canal seguro: usamos la criptografía de clave pública para hacerlo, y a partir de entonces usamos los veloces algoritmos de clave privada para realizar el resto de comunicaciones.

Este sistema es usado hoy en día en la mayoría de aplicaciones de seguridad informática. El criptosistema RSA basado en números primos sigue siendo la implementación más popular- existe un sistema alternativo basado en “curvas elípticas” que se considera más seguro, pero es mucho más complejo y, sobre todo, que algunas de estas curvas elípticas están patentadas y no está claro si se pueden realizar implementaciones de este sistema sin pagar a sus inventores (mientras que el sistema RSA es “libre”).