La criptografía asimétrica, es por definición, aquella que utiliza dos claves diferentes para cada usuario, una para cifrar que se le llama clave pública y otra para descifrar que es la clave privada. El nacimiento de la criptografía asimétrica se dio al estar buscando un modo más práctico de intercambiar las llaves simétricas. Diffie y Hellman, proponen una forma para hacer esto, sin embargo no fue hasta que el popular método de Rivest Shamir y Adleman RSA publicado en 1978, cuando toma forma la criptografía asimétrica, su funcionamiento esta basado en la imposibilidad computacional de factorizar números enteros grandes.
Actualmente la criptografía asimétrica es muy usada, sus dos principales aplicaciones son el intercambio de claves privadas y la firma digital, una firma digital se puede definir como una cadena de caracteres que se agrega a un archivo digital que hace el mismo papel que la firma convencional que se escribe en un documento de papel ordinario. Los fundamentos de la criptografía asimétrica pertenecen a la teoría de números.
En la actualidad la criptografía asimétrica o de clave pública se divide en tres familias según el problema matemático del cual basan su seguridad. La primera familia es la que basa su seguridad en el Problema de Factorización Entera PFE , los sistemas que pertenecen a esta familia son, el sistema RSA, y el de Rabin Williams RW . La segunda familia es la que basa su seguridad en el Problema del Logaritmo Discreto PLD, a esta familia pertenece el sistema de Diffie Hellman DH de intercambio de claves y el sistema DSA de firma digital. La tercera familia es la que basa su seguridad en el Problema del Logaritmo Discreto Elíptico PLDE, en este caso hay varios esquemas tanto de intercambio de claves como de firma digital que existen como el DHE (Diffie Hellman Elíptico), DSAE, (Nyberg-Rueppel) NRE, (Menezes, Qu, Vanstone) MQV , etc.
Aunque los sistemas asimétricos más conocidos pertenecen a las familias anteriores, existen otro tipo de sistemas que basan su seguridad en problemas diferentes como por ejemplo, en el Problema del Logaritmo Discreto Hiperelíptico, sobre problemas de retículas y sobre subconjuntos de clases de campos numéricos reales y complejos.
RSA En el caso de RSA el problema matemático es el de la factorización de un número entero n grande (1024 bits), este número entero se sabe es producto de dos números primos p,q de la misma longitud, entonces la clave pública es el número n y la privada es p,q. El razonamiento del funcionamiento de RSA es el siguiente:
- a cada usuario se le asigna un número entero n, que funciona como su clave pública
-
solo el usuario respectivo conoce la factorización de n (o sea p,q), que mantiene en secreto y es la clave privada
-
existe un directorio de claves públicas
-
si alguien quiere mandar un mensaje m a algún usuario entonces elige su clave pública n y con información adicional también pública puede mandar el mensaje cifrado c, que solo podrá descifrar el usuario correspondiente, el mensaje m convertido a número (codificación) se somete a la siguiente operación (donde e es constante y público)
-
Entonces el mensaje c puede viajar sin problema por cualquier canal inseguro
-
cuando la información cifrada llega a su destino el receptor procede a descifrar el mensaje con la siguiente fórmula
- Se puede mostrar que estas formulas son inversas y por lo tanto dan el resultado deseado, (n,e) son la clave pública, la clave privada es la pareja (p,q) o equivalentemente el número d. La relación que existe entre d y e es que uno es el inverso multiplicativo del otro módulo l (n) donde l (n) es el mínimo común múltiplo de p-1 y q-1, o también puede usarse j (n)=(p-1)(q-1) esto significa que la clave privada o el la pareja p,q o es el número d.
En términos muy generales es así como funciona el sistema RSA. Sin embargo en la realidad existen dos formas que son las más comunes, estas formas depende de la aplicación y se llaman el esquema de firma y el esquema de cifrado, cada una de estas dos diferentes aplicaciones consiste en una serie de pasos que a continuación se describen
Esquema de cifrado RSA
Uso: este esquema se usa principalmente en cifrar claves de sistemas simétricos (claves de 128 bits aprox.)
- Se toma el mensaje M (por ejemplo una clave simétrica de 128 bits), como en la practica actual es recomendable usar bloques de longitud de 1024 bits, los complementa esos 128 bits con una serie de técnicas para obtener uno de 1024 bits, después se aplica un proceso de codificación para que el ordenador entienda al mensaje como un número entero m.
- Se le aplica la formula de cifrado de RSA al entero m
- Se envía el número entero c
- Al recibir este número se aplica la formula de descifrado al entero c para obtener el entero m
- Se decodifica m para obtener el mensaje M
Ejemplo simple:
Generación de parámetros
- p = 3, q = 5 (se eligen dos números primos como clave privada)
- n = 15 ( se calcula el producto, es la clave pública)
- j (n)=(3-1)(5-1)=8
- Sea e=3, entonces d=3, ya que e*d = 3*3 =9 mod 8 =1 (como este caso solo es para mostrar el funcionamiento no importa que d sea igual a e, sin embargo en la práctica e es pequeño y d es muy grande)
- Si el mensaje es m=2
Proceso de cifrado
- El mensaje cifrado es c= me mod n, es decir, c=23 mod 15, o sea c=8
Proceso de descifrado
- Para descifrar el mensaje m=83 mod 15, es decir, m=512 mod 15, asi m=2 (ya que 512/15=2 mod 15 = m)
Por lo tanto es correcto el funcionamiento.
FACTORIZACIÓN Y LOGARITMOS DISCRETOS
Curiosamente, la inmensa mayoría de los algoritmos asimétricos que se usan en la actualidad -por no decir todos- se apoyan en problemas como el de la factorización o el de los logaritmos discretos. En realidad existen otros algoritmos que se basan en teorías diferentes, pero hoy por hoy no están suficientemente estudiados como para ser considerados seguros de forma general, por lo que no se suelen emplear en la práctica. Sistemas como RSA, Diffie-Hellman, e incluso la criptografía de curva elíptica depositan su seguridad en estos dos problemas. Todos ellos descansan en la supuesta imposibilidad de resolverlos de forma algorítmicamente eficiente, y se dice "supuesta" porque nadie ha demostrado que no pueda existir un algoritmo capaz de hacerlo de forma satisfactoria.
El problema de la factorización es justo el inverso a la multiplicación. Si para multiplicar se parte de la existencia de dos números y se trata de hallar su producto (para lo cual existen algoritmos claramente definidos), en el caso de la factorización se parte de un número y se trata de hallar sus factores primos. Por ejemplo, si se tiene el 342, se llega a que 342=2*3*3*19. Desgraciadamente (o afortunadamente, según se mire) no se conoce ningún algoritmo capaz de hacer esto de forma rápida y eficiente cuando el número a factorizar es muy grande.
El problema del logaritmo discreto es algo más complejo. Se define sobre aritmética modular y consiste en averiguar cuántas veces que hay que multiplicar un número consigo mismo para que nos dé otro concreto. Por ejemplo, el logaritmo base 4 de 12 módulo 13 es el número de veces que hay que multiplicar el 4 por sí mismo para que nos dé 12 módulo 13. El resultado es 3, ya que 4*4*4=64 =12 mod 13. (lo de "módulo 13" significa tomar el resto de la división por 13). De todas formas, existe una íntima relación entre este problema y el anterior, hasta tal punto que basta con tener resuelto uno de ellos para deducir una solución al otro.
Llegados a este punto parece claro cómo funcionaría la misteriosa "caja negra". Ésta analizaría el tráfico de la red, rescatando tantas claves públicas como pudiera. Esas claves serían clasificadas según el tipo de algoritmo asimétrico sobre el que estuvieran definidas (RSA, Diffie-Hellman...), para luego resolver el problema particular de factorización que plantea cada una, lo cual nos conduce a las claves privadas correspondientes. Ahora ya sólo quedaría capturar las claves de sesión e ir decodificando las comunicaciones en tiempo real.
COMPLEJIDAD ALGORITMICA
Pero, ¿qué es un algoritmo "eficiente"? Alguien podría decir que cuando haya ordenadores más y más rápidos, problemas que ahora son difíciles se podrán resolver, y eso es radicalmente falso. En Teoría de Algoritmos, se define el orden de complejidad de un algoritmo como una función "O(n)" de la entrada "n". Esta medida nos dice cómo crece el tiempo de computación a medida que aumenta el tamaño de la entrada. Por ejemplo, si un algoritmo fuera cuadrático, es decir, O(n^2), se tiene que el tiempo de ejecución es proporcional al cuadrado de la entrada. Eso quiere decir que si sobre la entrada dos tarda cuatro minutos, sobre la entrada 10 debe tardar cien, sobre 1000 un millón de minutos, etc.
Según esto, si se desea factorizar un número, se puede tratar de dividirlo por todos los números menores que él, uno por uno. Suponiendo que la prueba de divisibilidad se ejecutara en un tiempo constante x -simplificación que en realidad no es cierta-, el algoritmo necesitaría aproximadamente n pasos para tratar de el número n. Eso quiere decir que el programa podrá factorizar sin problemas números pequeños, pero si al ejecutarlo sobre un número de 1024 bits (el módulo de una clave típica RSA), se precisan llevar a cabo una cantidad de pasos elementales enorme. Por desgracia, es imposible construir una máquina capaz de llevar a cabo semejante computación.
Si por el contrario se pudiera encontrar un algoritmo capaz de resolver el problema anterior en un número de pasos proporcional, por ejemplo, al logaritmo de n, se podría factorizar un número de 1024 bits con sólo cien veces más pasos que los que necesitaríamos para hacerlo con un número de tan sólo 10 bits. No se trata, pues, de tener máquinas más rápidas -que por supuesto ayuda- sino de investigar en algoritmos con órdenes de complejidad menores, capaces de resolver los mismos problemas en menos pasos.
EL ALGORITMO RSA Y LA FACTORIZACION
Para finalizar, se comenta brevemente la forma concreta en la que RSA explota el problema de la factorización. Este algoritmo está definido de tal forma que tanto la codificación como la decodificación se llevan a cabo mediante una exponenciación en aritmética modular, así:
C=M^e (mod n)
M=C^d (mod n)
siendo C el mensaje cifrado, M el mensaje original, e la clave pública (para codificar) y d la clave privada (para decodificar). Cifrar el mensaje consistirá, pues, en elevarlo a la clave pública y luego quedarse con el resto que sale al dividir por n.
Para que se cumpla esta relación, debe darse la siguiente propiedad:
e*d=1 (mod Ø(n))
donde Ø(n) es la llamada función Totient de Euler. Curiosamente, esta función es muy fácil de calcular si se conocen los factores de n, y muy difícil en el caso contrario. De hecho, si n=p*q, Ø(n)=(p-1)*(q-1). Puesto que la clave pública ha de estar constituida por el par (n,e) para que alguien pueda cifrar un mensaje, si fuera posible factorizar n, el algoritmo RSA estaría sencillamente perdido.
UN MENSAJE TRANQUILIZADOR
Afortunadamente, los matemáticos cada vez están más seguros de que los problemas en los que descansa casi toda la criptografía asimétrica conocida (y ciertamente toda la que se usa en la práctica) son computacionalmente intratables, por lo que no es posible llevarse ninguna desagradable sorpresa al respecto en los próximos años. De todas formas, hay que mantenerse en guardia y seguir investigando, porque siempre será mejor que un descubrimiento en este campo se haga en la comunidad científica y de cara al público, que en el departamento de investigación y desarrollo de una oscura agencia al servicio de algún gobierno.
