Índice:

Introducción: Breve historia de la criptografía

1-Nociones matemáticas previas

2-Inicio de la criptografía de llave pública: algoritmo de Diffie-Hellman

2.1- Ataques al Diffie-Hellman

3-Algoritmo RSA

3.1- El Algoritmo RSA

3.2- Vulnerabilidades y ataques al RSA

4-Otros algoritmos de cifrado de llave pública

4.1- Cifrado de Rabin

4.2- Cifrado de El Gamal

5-Aplicaciones de la criptografía de llave pública

Introducción: Breve historia de la criptografía

Se suele definir criptografía como el conjunto de procedimientos (aunque sería más correcto hablar de una disciplina) que permiten transformar una información de manera que quede oculta a observadores no autorizados.

En tiempos remotos se estableció ya la necesidad de ocultar la información a observadores no deseados. Probablemente esta preocupación sea tan antigua como la propia escritura, ya que cualquiera que supiera leer podía tener acceso a una información que podía desearse mantener oculta.

Existen pruebas de que en tiempos del antiguo Egipto, o la Roma clásica ya se usaban métodos criptográficos. Algunos de ellos, como el método César, o el algoritmo de cifrado de Augusto, se siguieron usando durante la edad media, y fueron perfeccionados en el renacimiento (método Vigénere).

Durante un tiempo se tendió a abandonar la criptografía por otros métodos de ocultación (como el uso de una jerga particular), pero en la edad moderna, con la llegada de los nuevos medios de comunicación, como el telégrafo, la criptografía volvió a cobrar importancia, y se empezó abuscar nuevos métodos criptográficos.

Sin embargo, ha sido durante el S. XX cuando la criptografía ha experimentado un mayor crecimiento. Basta recordar la importancia que llegó a tener durante la II Guerra Mundial, cuando numerosos matemáticos trabajaron, tanto en el bando aliado como en el bando del eje, dedicándose casi en exclusiva a tratar de romper los cifrados del enemigo.

Durante todo ese tiempo, se estuvo empleando la criptografía de llave privada como medio de protección de la información. En ella, toda la seguridad depende de la capacidad del método y de la capacidad de cada uno de los usuarios de mantener su clave privada en secreto. Pero para descifrar la información se necesita dicha llave, y eso vuelve vulnerable todo el sistema.

Así, en la década de los 70 apareció un nuevo concepto en criptografía: la criptografía de llave pública. En este tipo de criptografía, cada uno de los usuarios tiene dos claves, una clave pública y una clave privada, y sólo una de ellas es necesaria para descifrar la información que se cifra con la otra. Así, la seguridad del sistema se ve incrementada.

Así, utilizando lo mejor de la criptografía de llave pública y privada, se consigue dar respuesta a las siguientes necesidades:

a)Garantizar la autenticidad del origen de la información

b)Garantizar la autenticidad del contenido e integridad del mismo

c)Incorporación de protocolos que dificulten en repudio interesado

d)Verificar la identidad de los comunicantes.

En la actualidad, ambos tipos de criptografía se emplean, utilizándose la criptografía de llave pública como complemento de la de llave privada, permitiendo aumentar la seguridad de los métodos criptográficos empleados y cubriendo las lagunas que la criptografía de llave privada deja.

1- Nociones matemáticas previas

Números relativamente primos: Se definen los números relativamente primos (o números primos entre sí) como aquellos pares de números tales que su máximo común divisor sea uno. Es decir, dados dos números a, n ÎN

Función de Euler: Se define la función de Euler de un determinado número N como el número de valores enteros positivos menores que N y relativamente primos con N. Es decir, teniendo en cuenta la factorización de N de la forma:

Se calcula la función de Euler como:

Números primos fuertes: se dice que dos números primos, P y Q son números primos fuertes si son números grandes (» 200 dígitos) y de la forma:

Donde p’ y q’ son a su vez números primos fuertes.

2- Inicio de la criptografía de llave pública: algoritmo de Diffie-Hellman

En los algoritmos de llave secreta, se hacía necesario guardar la llave privadapara evitar que toda posterior comunicación fuese fácilmente vulnerable. Esta condición hacía sumamente difícil el intercambio de las claves, que se tenía que hacer mediante protocolos jerárquicos rígidos.

En 1976 W. Diffie y M. E. Hellman inventaron un método de intercambio de llaves secretas a través de un canal abierto. Con ello nacía la criptografía de llave pública.

El algoritmo básico de Diffie-Hellman es bastante sencillo de entender:

Sea p un número primo grande (@ 200 dígitos en adelante), y sea g un número entero. Los valores de p y g son públicos. Sean k_a y k_b las claves privadas que dos comunicantes, A y B desean intercambiar. Para ello, A genera un valor (aleatorio) entero x_a / 1< x_a < p-1, y de la misma manera, B genera un valor x_b / 1 < x_b < p-1.

A continuación, A envía a B el valor público :

Y análogamente, B envía a A el valor (también público):

Así, B calcula el valor secreto:

Y de la misma forma, A calcula:

Y como se puede fácilmente deducir, z_ab=z_ba, y puede ser utilizado como clave secreta compartida por ambos comunicantes.

2.1- Ataques al Diffie-Hellman

Se pueden clasificar en dos grupos: ataque pasivos y ataques activos.

Un ataque pasivo es aquel en el que el “espía” trata de descifrar algo a partir de información cifrada interceptada. Un ataque activo es aquel en el atacante desea no sólo espiar información interceptada, sino también poder manipularla a su conveniencia.

Sería un típico ataque pasivo intentar obtener a partir de p, g, y_a, y_b la clave secreta z_ab. No obstante, es difícil que este ataque pueda ser llevado a término, ya que para ello se necesitaría obtener x_a o x_b, y para ello debería resolverse alguna de las operaciones:

lo que es inviable para números grandes, así, bastaría elegir p y g lo suficientemente grandes para evitar este ataque.

Así las cosas, para realizar un ataque activo un buen método sería que el atacante (sea llamado C) interviniese de forma activa en el intercambio. Supóngase que C genera un entero aleatorio x_c / 1<x_c<p-1. Así, cuando A envíe a B y_a, C intercepta la comunicación y envía a B y_cºg^xc(mod p).

B recibe y_c , creyendo que procede de A, y responde enviando y_b. Nuevamente, C intercepta la comunicación, y ahora envía y_c a A.

Así, A calcula:

Y B calcula:

claves ambas que también pueden ser calculadas por el atacante. Así, cuando A envíe una información a B cifrada con z_ca, el atacante la intercepta, decodifica, manipula a su antojo, la encripta con z_cb y la envía a B. De igual forma cuando B envía información cifrada a A.

Este ataque es difícil de evitar y de descubrir, pero requiere la continua intervención del atacante para no ser descubierto.

3-Algoritmo RSA

En 1977 R. L. Rivest, A. Shamir y L. Adleman propusieron un algoritmode cifrado asimétrico de clave pública, que bautizaron como RSA, y que fue posteriormente patentado por el MIT (Massachussets Institute of Technology).

Los algoritmos de cifrado asimétrico son aquellos en los que cada comunicante tiene dos claves diferentes, una pública y una privada, siendo el/los algoritmo/s de cifrado públicos. Además, deben cumplir:

·Ambos comunicantes calculan sus claves en tiempo polinómico

·El emisor A puede, si conoce la clave pública de B, enviarle en tiempo polinómico un mensaje cifrado con la clave pública de B

·El receptor B debe poder descifrar el mensaje cifrado de A en tiempo polinómico con su clave secreta

·Un atacante deberá enfrentarse a costes cuya complejidad computacional los haga inviables cuando trate de calcular, bien las claves secretas, bien los mensajes en claro a partir de los mensajes cifrados.

3.1- El Algoritmo RSA

Sean p y q dos números primos grandes (@ 100-200 dígitos), y sea N=pq su producto, con F(N)=(p-1)(q-1).

Sea e/ 1<e<N un número aleatorio relativamente primo con F(N), y d un entero que verifica que edº1 (mod F(N)). Así dispuesto, se verifica que para un cierto mensaje M, resulta que M^edºM(mod N), y por tanto, si CºM^e(mod N), resulta que MºC^d(mod N).

El algoritmo RSA utiliza estas propiedades para establecer un sistema criptográfico de cifrado asimétrico, en el que N,e corresponderían a la clave pública, y d a la clave privada.

3.2- Vulnerabilidades y ataques al RSA

Nótese que en un sistema RSA existirá un conjunto de mensajes que no pueden ser cifrados. Se dice que un mensaje M no puede ser cifrado si M^eºM(mod N). Esto se puede rescribir, de forma que M no podrá ser cifrado si:

M^eºM(mod p)

M^eºM(mod q)

Así, se puede calcular que el número de mensajes no cifrables de un sistema RSA viene definido por la expresión:

y los mensajes no cifrables serán de la forma:

Donde:

Se han propuesto multitud de ataques al algoritmo RSA, aunque hasta la fecha ninguno de ellos ha demostrado ser efectivo:

El Ataque por factorización de la clave pública

La forma más evidente de romper la seguridad de un sistema RSA pasa por factorizar su clave. Ello no obstante constituye la forma más difícil de lograrlo, ya que si los factores primos p y qson números lo suficientemente grandes la complejidad computacional de los algoritmos de factorización hace inviable la factorización de N en un tiempo finito.

El Ataque Cíclico

El ataque cíclico se basa en la idea de que los sistemas RSA son grupos multiplicativos con un número finito de elementos. Así, para descifrar CºM^e(mod N) no sería necesario conocer la llave privada d, sino que bastaría con realizar cifrados sucesivos con la clave pública e hasta obtener el mensaje cifrado C (recordemos que RSA se basa en la aritmética modular). Si C_i es el i-ésimo cifrado realizado con la llave pública e, y C_iºC(mod N), entonces resulta obvio que C_i-1 debe corresponder a M.

Este ataque puede ser evitado si los valores primos p y q que forman la factorización de N son números primos fuertes, ya que entonces la complejidad computacional aumenta hasta convertir el problema en irresoluble.

Ataque de Merkle-Hellman

Este ataque, propuesto por R. Merkle y M. Hellman en 1981, se basa en la idea de que se puede romper el cifrado de un sistema conociendo un mensaje cifrado y su correspondiente texto en claro (algo que en el RSA es, evidentemente, posible).

La justificación matemática del ataque es muy compleja, pero su modo de funcionamiento es relativamente simple de describir:se basa en realizar pruebas de encriptación con un mensaje M, hasta obtener una coincidencia que permita obtener la clave privada pareja de la clave pública (conocida) e. Se puede demostrar que este método de criptoanálisis es mejor que los métodos de fuerza bruta. No obstante, también se demuestra que la probabilidad de hallar una clave válida disminuye cuando los factores p y q son números primos fuertes. Si los números p y q están bien elegidos este ataque se vuelve impracticable.

Ataque por control de tiempos

Este ataque se basa en la idea de medir el tiempo invertido por el dispositivo cifrante en realizar el cifrado de los mensajes, y a partir de esos tiempos medidos tratar de extraer información acerca de la clave usada. No obstante es complicado y existen ciertas sencillas técnicas algorítmicas que permiten evitar este ataque.

Ataque por introducción de faltas

La idea de este ataque pasa por la introducción de alteraciones en el mensaje que se va a cifrar con la clave privada, y observar después la diferencia entre el mensaje cifrado con los valores erróneos y el mensaje que se hubiera cifrado de no haber introducido errores. Tiene el evidente inconveniente de que resulta necesario que el atacante tenga cierto control sobre el dispositivo a atacar.

Así pues, parece bastante evidente que a pesar de la multitud de ataques propuestos contra el algoritmo RSA, no hay ninguno de ellos que tenga la suficiente efectividad como para comprometer seriamente la credibilidad de dicho algoritmo.

4-Otros algoritmos de cifrado de llave pública

RSA no es el único algoritmo de cifrado de llave pública que existe, aunque sí es seguramente el más popular, no obstante, en la bibliografía se pueden hallar algunos otros interesantes ejemplos

4.1- Cifrado de Rabin

Este método de cifrado fue descrito en el año 1979. Se basa en la existencia de dos números primos grandes, p y q / pºqº3(mod 4), siendo N=pq la clave pública, y el par (p,q) la llave privada. Así, el cifrado de un cierto mensaje M se obtendría:

Así, para descifrar el mensaje C sería necesario calcular su raíz cuadrada (mod N), y esto sólo es posible si se conocen los factores primos p y q, ya que en otro caso la complejidad de los algoritmos lo hace inviable. Aún así, existe el problema de que existen cuatro posibles soluciones para dicha raíz cuadrada, y de ahí el problema de elegir una, ya que si el mensaje M debe tener sentido en alguna lengua humana, entonces un operador humano podrá decidir, pero si el mensaje M es aleatorio o no tiene sentido para un operador humano, o no puede establecerse una relación con un diccionario, entonces este método de cifrado resulta inviable.

Existe una modificación a este método de cifrado introducida por H. C. Williams en el año 1980, orientada a eliminar el inconveniente de la multiplicidad de las raíces cuadradas (mod N).

4.2- Cifrado de El Gamal

Este sistema de cifrado fue propuesto por T. El Gamal en 1985. Se basa en la dificultad del cálculo de los logaritmos discretos con números enteros grandes.

Sea p un número primo grande, y sea g un número entero (grande). Ambos valores son públicos. Sea x/ 1<x<p-1 un valor aleatorio secreto, con una clave pública asociada y, definida por yºg^x(mod p).

Así, el cifrado de un cierto mensaje M se realizará eligiendo un valor aleatorio k/1<k<p-1, siendo k relativamente primo con (p-1). Así, el mensaje cifrado vendrá dado por la pareja de valores:

La recuperación del mensaje en claro a partir del cifrado se calcula como:

Ya que Mº(s/r^x)(mod p) => Mº(My^k/y^k)(mod p)ºM(mod p).

Este método de cifrado tiene la particularidad de que dado un mismo mensaje en claro puede tener varios cifrados diferentes. No obstante, tiene el problema de que el cifrado tiene una longitud doble del mensaje original, lo que puede resultar en problemas de espacio y de manejo de cifrado.

5-Aplicaciones de la criptografía de llave pública

Después de examinar los algoritmos de clave pública y comprobar su efectividad, cabe preguntarse por sus aplicaciones. Ya se ha explicado cómo cumplen estos algoritmos con su principal aplicación, que es la de cifrar (ocultar) la información. A continuación se intenta dar una visión somera de las otras aplicaciones que tiene la criptografía de llave pública.

Recordemos que al principio planteábamos las siguientes necesidades:

·Garantizar la autenticidad del origen de la información

·Garantizar la autenticidad del contenido e integridad del mismo

·Incorporación de protocolos que dificulten en repudio interesado

·Verificar la identidad de los comunicantes.

La autenticación pretende obtener constancia de que la información que se recibe procede de un emisor esperado y no de un atacante. En la criptografía de llave pública la solución a este punto es trivial, ya que resulta evidente que cualquier información que se descifre con la clave pública del emisor tiene forzosamente que haber sido cifrada con su llave privada. No obstante, la criptografía de llave pública suele presentar el inconveniente de que resulta más lenta en el cifrado y descifrado que la de llave privada. Por ello, una posible solución puede ser la utilización de una llave de sesión para cifrar la información mediante un algoritmo de llave privada (p. Ej. El DES), que permita ocultar convenientemente la información, y a continuación la encriptación de la llave de sesión mediante nuestra llave privada. El posterior descifrado del mensaje se realizará mediante el descifrado de la llave de sesión, que al ser de menor longitud que el mensaje, resulta más rápida.

Al respecto de la identificación de los comunicantes, existen protocolos establecidos para permitir la identificación electrónica, el más conocido y extendido de los cuales es la utilización de certificados. En este protocolo, una autoridad certificadora se encarga de dar constancia de que la clave pública contenida en el certificado procede del comunicante que realiza la afirmación, y no de otro individuo. Así, posteriormente toda comunicación contará con las garantías propias de la criptografía de llave pública.

Sobre la garantía de integridad del contenido se ha establecido un protocolo de firma digital que soluciona tanto los problemas de integridad como parte de los problemas de autenticación de la fuente y del repudio interesado. Este protocolo se basa en la existencia de funciones resumen (hash) tales que, dada una información, el resultado de la función resumen es único, y cualquier modificación introducida en la información producirá un resultado distinto de la función resumen (la probabilidad de que exista una información similar a la original con un resumen de igual valor es ínfima). Así, se realizaría un resumen del texto a firmar, y el resultado se cifraría con la clave privada y se colocaría anexo al texto original. Cualquier alteración de la información sería detectada de inmediato sólo con desencriptar el resumen, y además el hecho de estar encriptado éste con la llave privada de firmante, permite autenticar la identidad del mismo.

Acerca del resto de problemas del repudio interesado, se han descrito algunos protocolos basados también en autoridad certificadora, que tratan de verificar los documentos mediante la incorporación de marcas de tiempo y similares. Estas marcas de tiempo serán distintas según el momento y el documento a marcar, de tal forma que la autoridad certifica el “tiempo de vida” de tal documento.

Conclusión

Hemos visto que la criptografía de clave pública es, hoy por hoy, la forma más segura de preservar la privacidad de nuestra información. Tal y como se ha podido comprobar, la criptografía de llave pública constituye una tecnología criptográfica relativamente nueva (no más de 26 años), que permite dar solución a muchos de los problemas que la criptografía clásica, de clave privada, no resolvía. Ciertamente, la criptografía de llave pública no es la panacea contra todos los problemas de la sociedad de la información, pero puede resultar una ayuda muy valiosa en la obtención de técnicas que solventen algunos de estos problemas, aunque eso no hace que la criptografía no pase de ser una herramienta, y sólo un uso inteligente de ella dará los frutos esperados.

Bibliografía

Criptografía digital, fundamentos y aplicaciones, José Pastor Franco y Miguel Ángel Sarasa López, Prensas Universitarias de Zaragoza, 1998

Criptografía y seguridad en computadores, Manuel Lucena López- José L. Peláez- Antonio M. Sánchez, Universidad de Jaén, 1996

Técnicas criptográficas de protección de datos, Amparo Fuster Sabater et. Al, RA-MA Editorial, 1997