Los sistemas de encriptación de datos por clave publica han revolucionado el mundo de la criptografía y se han impuesto ampliamente en el mercado de las comunicaciones, la idea aunque sencilla recién surgió en la década del '70, los expertos en criptografía no logran ponerse de acuerdo en cual fue el motivo que demorara tanto el surgimiento de este tipo de sistema de encriptación.
La idea de los sistemas de clave publica es sencilla: cada usuario genera 2 (dos) claves: una publica y una privada, el usuario debe conservar su clave privada a salvo mientras que la clave publica es distribuida en forma masiva.
El juego de claves funciona de la siguiente forma: los mensajes que son encriptados con la clave publica de un usuario solo pueden ser desencriptados con la clave privada del mismo.
El algoritmo de encriptación es publico, de forma tal que cualquiera pueda encriptar un mensaje, el algoritmo de desencriptación debe de forma tal que sin la clave privada sea muy difícil desencriptar el código mientras que con la clave privada esto es una tarea sencilla. Todos los algoritmos de encriptación por clave publica se basan en algún problema en general de tipo matemático de cuyo tiempo de resolución no pueda establecerse una cota inferior.
KNAPSACKS.
El primer ejemplo sobre el cual presentaremos a los sistemas de clave publica esta basado en un problema de ingenio denominado 'el problema de la mochila'
'El problema de la mochila'
Se tiene una mochila con capacidad para "K" kilos. Además se cuenta con una lista de "n" objetos cuyos pesos se conocen y son (A1,A2,A3,...,AN). El problema consiste en seleccionar una cierta cantidad de objetos de la lista de forma tal que la mochila quede completamente llena.
Para resolver este problema no se conoce ningún método mejor que el ir probando las distintas combinaciones de objetos y ver si en alguna de ellas la mochila queda completamente llena. Si los pesos de los objetos están en un vector (A1,A2,A3,...,AN) una combinación puede escribirse como un numero binario de N bits en el cual un uno en la posición "i" indica que el elemento "i" debe estar en la mochila, un cero indica lo contrario.
Ej:
A=(3,45,6,7,21,12,9,90)
C1=(00000001)=90
C2=(10101010)=3+6+21+9=39
etc...
De esta forma se puede ver claramente que la cantidad de combinaciones a probar es 2^N siendo N el numero de elementos del vector, a este tipo de vectores lo denominaremos 'Knapsack'. Si N es un numero lo suficientemente grande (por ejemplo 300) la cantidad de combinaciones a probar es tan grande que resultaría imposible probarlas todas antes de que se termine el universo!.
Veamos como podemos construir un sistema de clave publica utilizando Knapsacks.
Empecemos por inventar un sistema de clave privada que utilice 'Knapsacks'
Dado un mensaje lo pasamos a binario y tomamos bloques de "N" bits de acuerdo al tamaño del Knapsack, sumamos los elementos del Knapsack que corresponden a los bits en 1 y el numero resultante es la codificación del bloque.
Ej: Con bloques de 8 bits y usando el código Ascii si el vector es: (3,45,6,7,21,12,9,90)
'H' = 01001000 = 45 + 21 = 66
'o' = 01101111 = 45 + 6 + 21 + 12 + 9 + 90 = 183
'l' = 01101100 = 45 + 6 + 21 + 12 = 84
'a' = 01100001 = 45 + 6 + 90 = 141
'Hola' = 66,183,84,141
Hasta ahora tenemos un método para encriptar un mensaje, la clave privada por el momento es el Knapsack, sin embargo este sistema tiene un problema: el receptor 'legal' del mensaje pese a poseer el Knapsack aun tiene que resolver el problema de la mochila para poder descifrar el mensaje, esto obviamente dista mucho de ser lo deseado. La solución consiste en simplificar el problema de la mochila utilizando un vector super-incrementante (super increasing, tradúzcanlo mejor si pueden). Un vector super-incrementante es aquel en el cual el elemento Ak es mayor a la sumatoria de todos los elementos con subíndice menor que él.
Ej: (1,3,5,11,21,44,87,175,349,701) es super-incrementante.
Con un vector super-incrementante resolver el problema de la mochila es fácil, para un cierto numero lo que hay que hacer es tomar el primer elemento del vector menor o igual al numero y poner su bit en 1, luego al número restarle el elemento y con el resultado repetir el procedimiento hasta que el número se hace cero.
Supongamos que tenemos el numero 734.
Para 734: Como 734 > 701 => el bit numero 10 es 1
734-701 = 33
Para 33: 33 > 21 => el bit 5 es 1
33-21 = 12
Para 12 : 12 > 11 => el bit 4 es 1
12-11 = 1
Para 1 : El bit 1 es 1
Luego 734=(1001100001) = 1+11+21+701
El algoritmo de desencriptado, como puede verse, es ahora muy sencillo. El problema es que el sistema sigue siendo de clave privada, conociendo el Knapsack se puede tanto encriptar como desencriptar cualquier mensaje.
Convirtiendo los Knapsacks en un sistema de clave pública
Lo que debemos lograr es identificar cual va a ser la clave privada y cual va a ser la clave publica, para ello una vez que tenemos un vector super-incrementante lo que se hace es elegir dos números t y m forma tal que t y m no tengan factores en común.
Al numero t lo denominamos multiplicador.
Al numero m lo denominamos modulo.
Además debemos encontrar un numero t' que sea el inverso multiplicativo de t usando aritmética modulo m.
Ejemplo: Sea m=1590 Verificar que 1590 y 43 no tienen factores en común
t=43 (43 es primo y 1590 no es divisible por 43)
1590 y 43 son relativamente primos.
Para el inverso de t hacemos 1591/43 = 37 luego t'=37
(37 * 43 = 1591, 1591 mod 1590 = 1)
Ahora lo que hacemos es aplicarle a cada elemento Ai del Knapsack la función
Ai'= Ai*t mod m
(1,3,5,11,21,44,87,175,349,701)=>(43,129,215,473,903,302,561,1165,697,1523)
Al vector que obtenemos una vez aplicada la función lo utilizaremos como clave publica (notar que el vector obtenido no es super-incrementante). Es decir que para encriptar un mensaje utilizaremos el método que ya hemos descripto utilizando la clave publica. Si el mensaje cifrado es interceptado el interceptor tiene que resolver el problema de la mochila para poder desencriptar el mensaje, y como sabemos este problema le va a llevar mucho mas que toda su vida.
La clave privada esta formada por t' y m, el receptor legal del mensaje primero convierte todos los números haciendo c*t' mod m y luego convierte el Knapsack de la misma forma, lo único que le resta hacer es resolver el problema de la mochila con un vector super-incrementante, lo cual es fácil.
Ejemplo:
Para el Knapsack ejemplo anterior la clave publica es (tomando solo 8 elementos para no hacer tantas cuentas, obviamente cuanto mayor es el vector mas seguro es el sistema)
P = (43,129,215,473,903,302,561,1165)
Supongamos que queremos encriptar 'Hola'
'H' = 01001000 = 129 + 903 = 1032
'o' = 01101111 = 129 + 215 + 903 + 302 + 561 + 1165 = 3275
'l' = 01101100 = 129 + 215 + 903 + 302 = 1549
'a' = 01100001 = 129 + 215 + 1165 = 1509
'Hola' = 1032,3275,1549,1509
Si este código es interceptado y sabiendo la clave publica no puede hacerse nada para desencriptar el mensaje pues la clave publica no es super-incrementante (aquí reside la gracia del asunto).
La clave privada es t'=37 m=1590
Para desencriptar usamos la clave privada:
1032 * 37 mod 1590 = 24
3275 * 37 mod 1590 = 335
1549 * 37 mod 1590 = 73
1509 * 37 mod 1590 = 183
A continuación se convierte el vector publico en un vector super-incrementante utilizando la misma transformación.
Luego con los números (24,335,73,183) y el vector super-incrementante se puede desencriptar fácilmente el mensaje.
RSA.
El algoritmo de clave publica más probado y utilizado en todo el mundo es el algoritmo RSA, denominado así debido a sus autores: Rivest, Shamir y Adleman.
Está basado en una idea asombrosamente sencilla de la teoría de números y hasta la fecha ha resistido todo tipo de ataques criptoanalíticos.
La idea es simple: dados dos números primos p y q muy grandes es sencillo a partir de p y q hallar su producto (p*q) pero es un problema muy complejo a partir del producto hallar los números p y q en cuestión. Si bien hasta el momento no se ha podido demostrar que la factorización prima de un numero es un problema NP-complejo, todos los intentos realizados para factorizar un número en forma veloz han fracasado.
Sean dos números p y q primos de aproximadamente 100 dígitos cada uno.
n = p*q y §(n) = (p-1) * (q-1)
Además se elige un número random d de muchos dígitos tal que d y §(n) son relativamente primos. Y un número e, 1<e<§(n) tal que e*d=1 usando aritmética módulo §(n).
n = módulo.
e = exponente de encriptación.
d = exponente de desencriptación.
La clave pública estará formada por n y e.
La clave privada estará formada por p,q,§(n) y d.
Para encriptar se pasa el mensaje a binario y se lo divide en bloques de un cierto tamaño, cada bloque se encripta elevando el numero a la potencia e y reduciéndolo modulo n. Para desencriptar se eleva el código a la potencia d y se lo reduce modulo n.
El tamaño de los bloques es i tal que 10(i--1) < n < 10i
Ejemplo (chiquito para poder seguir las cuentas) :
Sea p=5 , q=11, n=p*q=55,§(n)=40.
Elegimos d=23 pues 23 y 40 son relativamente primos.
Luego e=7 pues 7*23=161 (161 mod 40) = 1.
Si encriptamos números comprendidos en el rango (0..15) (tenemos 4 bits)
| Número |
Encriptado |
|
| 0 |
0 |
(0^ 7 mod 55) |
| 1 |
1 |
(1^ 7 mod 55) |
| 2 |
18 |
(2^ 7 mod 55) |
| 3 |
42 |
(3^ 7 mod 55) |
| 4 |
49 |
(4^ 7 mod 55) |
| 5 |
25 |
(5^ 7 mod 55) |
| 6 |
41 |
(6^ 7 mod 55) |
| 7 |
28 |
(7^ 7 mod 55) |
| 8 |
2 |
(8^ 7 mod 55) |
| 9 |
4 |
(9^ 7 mod 55) |
| 10 |
10 |
(10^ 7 mod 55) |
| 11 |
11 |
(11^ 7 mod 55) |
| 12 |
23 |
(12^ 7 mod 55) |
| 13 |
7 |
(13^ 7 mod 55) |
| 14 |
9 |
(14^ 7 mod 55) |
| 15 |
5 |
(15^ 7 mod 55) |
Probar que el desencriptado funciona correctamente, por ejemplo para desencriptar el 42 debemos hacer 42^23, esta operación puede hacerse fácilmente sin usar números 'super enormes' ya que por cada producto aplicamos un modulo n.
42^2=4 42^4=16 42^8=36 42^16=31 42^17=37 42^18=14 42^19=38
42^20=1 42^21=42 42^22=4 42^23=3
Luego 3 mod 55 = 3 y queda desencriptado.
Notar que para calcular las potencias trabajamos siempre con aritmética modulo n.
El ejemplo presentado tiene algunas falencias que pueden ser descubiertas fácilmente por el lector (lo dejamos como ejercicio), estas fallas se reducen automáticamente a valores casi nulos cuando los números p y q son lo suficientemente grandes.
Criptoanálisis:
Las técnicas criptoanalíticas más utilizadas contra el RSA, aunque sin éxito, consisten en intentar factorizar el numero "n" que se distribuye en la clave publica averiguando de esta forma los números p y q. Debido a que no existen algoritmos eficientes para factorizar un número, el problema de descomponer un numero muy grande insume un tiempo tan elevado que los ataques mas sofisticados contra el RSA han fallado (o casi...)
El algoritmo RSA sin embargo presenta una vulnerabilidad: hay una leyenda que indicaría que el algoritmo es vulnerable. Y la clave de todo se la ha llevado a la tumba (una vez más) el misterioso Fermat.
La leyenda:
Allá por el siglo 17, Cataldi, un matemático de renombre de la época, trabajaba intentando descubrir nuevos números primos. Cataldi había encontrado tres números de unos 200 dígitos de los cuales sospechaba que eran primos, como no podía probarlo, le envío los tres números al ilustre Fermat.
Fermat: Fermat fue un matemático sumamente misterioso, su teorema más famoso denominado “el último teorema de Fermat” era aquel que decía que para n>2 no existían enteros a,b,c tales que a^n = b^n + c^n. Fermat anotó en su cuaderno que había encontrado una demostración muy elegante para este teorema pero que lamentablemente no entraba en el margen del cuaderno. Nunca más se supo de otro manuscrito de Fermat sobre el tema y el teorema permaneció inconcluso hasta 1995, año en el cual dos científicos ingleses presentaron un mamotreto de 200 paginas con una supuesta demostración, la cual está aún en estudio!!.
La cuestión es que el misterioso Fermat le envía a Cataldi dos meses más tarde una carta en la cual le decía que los dos primeros números si eran primos (felicitaciones Cataldi !) pero el tercero no lo era pues era divisible por dos números, los cuales sí eran primos (Fermat le envió los números a Cataldi). Hasta el día de hoy no hay algoritmo ni computadora que sea capaz de factorizar un numero de 200 dígitos en dos meses. Y Fermat no tenía computadoras!!!!!
Como puede observarse el ataque mas devastador contra el RSA ocurrió en el siglo XVII y hasta el día de la fecha no se ha vuelto a repetir. Se supone que el misterioso Fermat se ha llevado a la tumba un método para factorizar números que hasta el día de hoy nadie ha descubierto. Mientras no aparezca otro Fermat el RSA permanece tranquilo.
PGP : Pretty Good Privacy.
En esta sección analizamos el programa más utilizado para encriptar y desencriptar datos mediante algoritmos de clave publica. El PGP se utiliza en internet y en casi todas las redes de mensajería cada vez que quiere transmitirse información privada.
PGP es un producto de distribución libre, es distribuido con sus fuentes y su distribución le ha causado a su autor Philip Zimmerman más de un problema como veremos más adelante.
PGP trabaja con el algoritmo RSA utilizando claves de 256,512 o 1024 bytes según el nivel de seguridad que se necesite, las claves de 1024 bytes superan ampliamente los mas estrictos requisitos militares sobre seguridad criptográfica.
PGP genera las claves públicas y privadas del usuario utilizando un algoritmo muy avanzado de pseudoaleatorización que mide los tiempos transcurridos entre lo que se tipea en un teclado. (PGP solicita al usuario que tipee durante un cierto tiempo en la pantalla) o los movimientos del mouse (se solicita al usuario que lo mueva aleatoriamente durante cierto tiempo).
La clave publica queda grabada en el disco y lista para ser distribuida, la clave privada se almacena también en el disco, PGP en sus manuales destaca que el acceso a la computadora donde se almacena la clave privada debe restringirse en forma drástica pues el conseguir la clave privada anula todo el sistema, el autor recomienda el uso de dispositivos que distorsionen las señales de radio en el ambiente donde reside la computadora pues existen dispositivos ultra-avanzados de las agencias gubernamentales que permiten leer la información de un disco a distancia mediante ondas de radio (!!).
Las claves publicas que nos envían otros usuarios son almacenadas en un conjunto de claves publicas (Public-key-ring) sobre el cual se pueden realizar altas, bajas y modificaciones.
Cuando un usuario le envía a otro su clave pública, por ejemplo a través de internet, el usuario que recibe la clave suele querer chequear que la clave publica recibida sea la del usuario que el quiere y no cualquier otra. Para ello PGP permite extraer de cada clave publica un numero conocido como 'FINGERPRINT' el Fingerprint puede ser chequeado telefónicamente o personalmente, y si coincide puede certificarse que la clave publica es de quien dice ser. (Cualquier cambio en la clave publica modifica el Fingerprint). El fingerprint se calcula hasheando la clave publica.
PGP dispone de varias opciones interesantes:
Envío de mensajes en forma clásica:
Este esquema sigue el mecanismo clásico de la encriptación por clave publica, el mensaje es encriptado usando la clave publica de un determinado usuario de forma tal que solo pueda ser desencriptado por la clave privada del mismo.
Certificación de mensajes:
Esta es una utilidad muy recomendable, y sirve para que un usuario firme un mensaje de forma tal que se pueda autenticar su autoría. Lo que hace el PGP es primero extraer un 'concentrado' del mensaje sometiéndolo a una función de hashing, luego el concentrado es encriptado con la clave privada del usuario y agregado al final del mensaje. Cuando el mensaje es recibido por un usuario la firma digital es desencriptada usando la clave pública del usuario y luego el mensaje es sometido a la función de hashing, si el concentrado coincide con el concentrado desencriptado del mensaje entonces el mensaje fue escrito por quien dice ser, de lo contrario o bien fue escrito por otra persona o bien fue modificado el texto del mensaje.
Los mensajes certificados a su vez pueden ser encriptados para que solo puedan ser leídos por una cierta persona.
Notar que la certificación utiliza el juego de claves en forma inversa al uso normal de las mismas.
Mensajes solo para sus ojos:
Esta opción del PGP permite encriptar un mensaje para una cierta persona de forma tal que cuando esta lo desencripte usando su clave privada el texto del mensaje solo se pueda ver en pantalla y no pueda ser grabado en un archivo, esta opción otorga una seguridad extra a quien envía el mensaje y tiene miedo que el usuario que lo recibe lo trate en forma descuidada dejándolo por allí.
Borrado especial del archivo a encriptar:
Cuando se quiere encriptar un mensaje muy critico que esta escrito en un archivo, PGP dispone de la opción de eliminar el archivo original del disco una vez encriptado. PGP no utiliza un borrado común del archivo sino que sobreescribe el área del disco con sucesivas pasadas de unos, ceros y unos y ceros alternados en forma random, esto lo hace varias veces. El algoritmo de borrado del PGP asegura que la información no podrá ser recuperada del disco. (Si el algoritmo no es lo suficientemente seguro el análisis de trazas magnéticas del disco puede permitir recuperar la información).
PGP es un programa sumamente seguro y es utilizado en todo el mundo para el envío de e-mail en forma segura y la certificación de mensajes de importancia.