MAESTRÍA EN CIENCIAS DE LA INFORMACIÓN Y LAS COMUNICACIONES

MEMORIAS DE SEMINARIO EL ALGORTIMO DE ELGAMAL

LUIS ALBERTO PERALTA AMAYA

UNIVERSIDAD DISTRITAL “FRANCISCO JOSÉ DE CALDAS” MARZO 2004

“A pocos podremos convencer de que no es nada fácil inventar un método de escritura secreta que resista investigación cuidadosa. No obstante, puede afirmarse rotundamente que el ingenio humano es incapaz de preparar una clave que el ingenio humano no pueda resolver” Edgar Allan Poe. Introducción La información en la era de los computadores se ha convertido paulatinamente en una fuente de poder invaluable, desde tiempos remotos los secretos más importantes se guardaban y transmitían con el mayor celo, especialmente los secretos militares permitieron un auge sin precedentes de las técnicas criptográficas. El aumento en el poder de cómputo de los computadores actuales ha obligado a manejar la información confidencial de manera cada vez más segura, implicando el uso de algoritmos de cifrado cada vez más complejos. Aquí trataré de exponer de la manera más sencilla posible uno de los algoritmos de clave pública más conocidos, el algoritmo de ElGamal, basado en el algoritmo de cambio de clave de los profesores W. Diffie y M. Hellman. PRELIMINARES Qué es la Criptografía? La humanidad desde tiempos remotos ha tratado de proteger sus secretos, guardándolos celosamente en sus escritos, según referencia David Khan en su libro The Codebreakers, se conoce el uso de cifras para ocultar información desde 1900 A.C. en Egipto, 1500 A.C en Mesopotamia y 500 A.C. en la Biblia. Uno de las cifras antiguas más conocidas es la atribuida a Julio César, que se basa en la rotación fija de las letras del alfabeto. Según el Diccionario de la Real Academia de la Lengua, la palabra Criptografía proviene de las raices griegas kriptos que significa oculto, y graphos, que significa escritura, que al unirse traducirían algo como escritura oculta y que en nuestros días puede traducirse como el arte de escribir mensajes en clave o secretos, sin embargo cabe anotar que actualmente con los grandes avances tecnológicos y teóricos impulsados inicialmente por Shannon y posteriormente por Diffie-Hellman, el concepto fue revaluado, y se pasó de una criptografía vista como arte, a considerarse como una ciencia aplicada donde convergen varias ciencias como la estadística, las matemáticas, la teoría de la información, etc.

Actualmente puede definirse como el estudio de los protocolos y algoritmos que permiten proteger de “intrusos” los mensajes durante su transmisión y almacenamiento, y es aplicable también a los archivos, los objetos serializados o a cualquier secuencia de bytes. Adicionalmente existen otros usos para la criptografía como son: conservar la integridad de los datos, probar la identidad de alguien y demostrar que un mensaje proviene de una fuente con una identidad determinada. Cita de un artículo de Martin Gardner cuando se presentó en 1977 el criptosistema RSA: “Los computadores y la teoría de complejidad están llevando a la criptografía a una etapa excitante, que quizás adquiera tintes tristes. Repartidos por todo el mundo se encuentran hombres y mujeres de gran inteligencia, algunos de ellos geniales, que han dedicado sus vidas al dominio del análisis criptográfico moderno. A partir de la Segunda Guerra Mundial, incluso aquellas claves gubernamentales y militares que no son de uso único se han hecho tan difíciles de descifrar que el talento de estos expertos va siendo cada vez menos útil. Estas personas se encuentran ahora encima de trampillas a punto de abrirse y sumirlos en las profundidades del olvido." Qué es el Criptoanálisis? Si se requiere que la comunicación sea secreta, es porque se teme que un enemigo intercepte y descifre el mensaje transmitido. Si este enemigo realmente existe, utilizará todos los medios que tenga a su alcance para descifrar esos mensajes secretos, utilizando un conjunto de técnicas y métodos, al que llamaremos criptoanálisis. En pocas palabras, criptoanálisis es el estudio de las revelaciones de los protocolos y algoritmos criptográficos. Qué es la Criptología? Es la ciencia que reune la criptografía y el criptoanálisis, en otras palabras estudia tanto las claves (criptografía) como sus debilidades (criptoanálisis) . “En toda comunicación secreta se presenta una lucha entre criptógrafos y criptoanalistas. Un éxito de unos es el fracaso de los otros”.[PIN96]

El Concepto de Cifra El texto plano se convierte a texto en clave por medio de algoritmos criptográficos, llamados cifras(ciphers). Encriptación y Desencriptación La encriptación es el proceso de transformar texto plano a texto clave, mientras que la desencriptación es el proceso inverso, es decir tomar texto en clave y transformarlo en el texto plano original. Ambos procesos están controlados por claves, que son los valores que hacen variar la representación de texto plano a texto clave. En la criptografía basada en claves, los algoritmos de encriptación y desencriptación podrían ser bien conocidos. Sin embargo, la clave de desencriptación, y a veces, la clave de encriptación están muy bien protegidas. Una vez que se crea el texto plano con una determinada clave, el texto cifrado que se crea sólo puede ser desencriptado con la clve de desencriptación que esté asociada a la clave de encriptación. A continuación expondremos las ideas principales de los dos sistemas criptográficos más comunes, a saber: Criptografia de clave secreta y Criptografia de clave pública. Criptografía de Clave Secreta (Simétrica) En algunos algoritmos de encriptación, las claves de encriptación y desencriptación son las mismas, o la clave de desencriptación se puede calcular a través de la clave de encriptación en una unidad de tiempo útil. Estos algoritmos se conocen como algoritmo de clave secreta, algoritmo de clave privada o algoritmo simétricos y se caracterizan por ser altamente eficientes ( en relación al tamaño de su clave) y robustos. Estos algoritmos exigen que la clave se mantenga en secreto, como también que el remitente y el destinatario coordinen el uso de las claves secretas. En otras palabras: Llamemos M al conjunto de todos los mensajes que pueden enviarse dos usuarios, A y B; C , al conjunto de todos los textos encriptados, y K a de todas las posibles claves que pueden utilizar. Un criptosistema de clave secreta es una familia de pares de funciones (Ek, Dk ) (Ek, Dk ) para cada clave k de K definidas como sigue:

Ek: M
C y Dk: C
M, de modo que para cada mensaje m de M se verifique que: Dk (Ek (m)) = m. Para utilizar este criptosistema, los usuarios A y B se ponen de acuerdo y eligen secretamente un clave k de K. Si A desea enviar un mensaje m de M a B, encripta el mensaje por medio de la función Ek, Ek(m) = c, y envia el resultado c a B. Para recuperar el mensaje original, B desencripta el texto encripatado que ha recibido, c,por medio de la función Dk (c) = Dk (Ek(m)) = m. Los pares de funciones (Ek, Dk ) deben ser “fáciles” de computar para los usuarios, y deberian se “difíciles” de computar para un escucha que conociera c, de modo que no pudiera recuperar ni m ni k. En criptografia se suele utilizar el término “fácil” para indicar que el cómputo se puede llevar a cabo en un corto espacio de tiempo, mientra que el témino “difícil” o “intratable” se utiliza para indicar que no puede computarse en un tiempo aceptable utilizando el mejor algoritmo conocido ni la mejor tecnología disponible. Estos son algunos de los criptosistemas de clave secreta más conocidos y sus vulnerabilidades: DES(Data Encription Standard) es un algoritmo diseñado por IBM y utilizado habitualmente desde los años 70. Es un método de cifrado altamente resistente frente a ataques criptoanalíticos diferenciales. Por desgracia, su tamaño de clave (56 bits) la hace vulnerable a ataques de fuerza bruta. Un reciente ataque, "patrocinado" por la empresa de seguridad RSA Data Security Inc. contra un mensaje con cifrado DES requirió el uso de cientos de ordenadores durante 140 días. Sin embargo, hay diseños de máquinas que, con un costo de un millón de dólares, podrían descifrar mensajes DES en cuestión de minutos. Quizá por eso el gobierno de EEUU lo utiliza solamente para cifrar datos no clasificados. En la actualidad ofrece protección contra el pirata informático habitual, pero no contra un esfuerzo masivo por parte de un usuario con grandes recursos. Tiene varios modos de funcionamiento, ECB (Electronic Codebook), CBC (Cipher Block Chaining), CFB (Cipher Feedback), OFB (Output Feedback), DESede. Blowfish fue creado por Bruce Schneier, autor del libro Applied Criptography (considerado por muchos como la "biblia" en cuestiones de criptografía). Utiliza claves de hasta 448 bits y, hasta el momento, ha resistido con éxito todos los ataques. Por ello y por su estructura se le considera uno de los algoritmos más seguros, a pesar de lo cual no se utiliza

masivamente. Tal vez se deba a su relativa juventud (la del algoritmo, no la de Schneier). Su autor no ha patentado el método para que pueda ser empleado sin limitaciones. CAST (Carlisle Adams y Stafford Tavares) tiene estructura similar a la de Blowfish. Parece ser un buen algoritmo, aunque tampoco lleva el tiempo suficiente como para haber sido atacado hasta la saciedad. De momento, sus posibilidades son buenas. Se conocen ataques criptoanalíticos contra la versión de clave 64 bits, aunque distan mucho de ser eficaces (requieren 2^17 textos sin cifrar y 2^48 cálculos diferentes). No se conocen ataques contra la versión de 128 bits. Ha sido patentado por Entrust Technologies, quienes permiten el uso libre de este algoritmo. IDEA (International Data Encription Algorithm) ha sido desarrollado por Xuejia Lay y James Massey. A pesar de que solamente lleva unos años en uso, es probablemente el mejor algoritmo de bloques existente. Utiliza clave de 128 bits y se cree que es resistente al criptoanálisis. Se encuentra bajo patente de Ascom-Tech, aunque se permite su uso gratuito para aplicaciones no comerciales. RC2 es un cógido protegido bajo secreto comercial (aunque no patentado) por RSA Data Security Inc. Existen ataques criptoanalíticos que, aunque requieren de gran cantidad de texto cifrado, muestran las vulnerabilidades de RC-2. Existen versiones mejoradas, y hoy día RC2 tiende a utilizarse cada vez menos en el beneficio de su “hermano mayor” RC4. RC4 es un intento de reemplazar RC2 por un algoritmo más sólido. También es un secreto comercial, aunque (al igual que RC2) su código fuente ha sido publicado en grupos de discusión. No se conocen ataques contra él. Forma una parte vital del sistema de cifrado en capas SSL, ampliamente utilizado en navegadores de Internet tales como Netscape Navigator y Microsoft Internet Explorer. Por desgracia, la versión exportable de RC4 tiene una clave de solamente 40 bits, lo que lo hace altamente vulnerable a ataques de fuerza bruta. La versión EEUU, con clave de 128 bits. RC5 fue diseñado por Ron Rivest y se encuentra bajo patente de RSA Data Security Inc. Es relativamente nuevo, y se conocen ciertos tipos de ataques contra él. Asimismo existe un cierto número (pequeño) de claves débiles que no deben utilizarse.A pesar de ello, se le considera un sistema seguro.

SAFER es un algoritmo diseñado por Robert Massey (uno de los creadores de IDEA). Tiene claves de hasta 128 bits y, a pesar de algunas debilidades en la primera versión y de ciertos ataques, parece un algoritmo seguro. Este programa fue desarrollado para la empresa Cylink, que algunos ligan a la no muy querida Agencia de Seguridad Nacional norteamericana (NSA); por ello, hay quien no se fía. Inconvenientes en la Criptografía de Clave Secreta 1. Distribución de claves Dos usuarios tienen que seleccionar un clave en secreto antes de empesar a comunicarse, lo que deberán hacer bien personalmente o por medio de un canal inseguro. 2. Manejo de claves En una red de n usuarios, cada pareja debe tener su clave secreta particular, lo que hace un total de n(n-1)/2 claves para esa red. 3. Sin firma digital Una firma digital es lo análogo a una firma manual o rubrica, pero en un red de comunicaciones. En los criptosistemas de clave secreta, no hay posibilidad, en general, de firmar digitalmente los mensajes, con lo que el receptor del mismo no puede estar seguro de que quien dice que le envia el mensaje sea realmente quien lo ha hecho. Cambio de Clave de Diffie-Hellman Con objeto de evitar los tres problemas que se acaban de mensionar, DiffieHellman describieron un protocolo por medio del cual dos personas pueden intercambiarse pequeñas informaciones secretas por un canal inseguro. Este protocolo se conoce como el cambio de clave de Diffie-Hellman, y es el siguiente: 1. Los dos usuarios, A y B, seleccionan públicamente un grupo multiplicativo finito, G de ordenn y un elemento α de G.

2. A genera un número aleatorio a, calcula αa en G y transmite este elemento a B. 3. B genera un número aleatorio b, calcula αb en G y transmite este elemento a A. 4. A recibe αb y calcula (αb )a en G. 5. B recibe αa y calcula (αa )b en G. Ahora A y B poseen un elemento común y secreto del grupo G αab . Un escucha(espía), S, podría conocer G, n, αa y αb y debería poder calcular el elemento αab , lo que hasta ahora es un problema intratable. Criptografía de Clave Pública (Asimétrica) De acuerdo a lo anteriormente expuesto, la criptografía de clave pública o asimétrica, contrasta con la de clave privada en el sentido que usa dos claves distintas una para el encriptado y otra para el desencriptado, eliminando de paso uno de los inconvenientes de la clave secreta: como hacer llegar al remitente la clave de desencriptado. En los algoritmos utilizados en este tipo de criptografía se usa una clave pública para encriptar y una clave privada para desencriptar, de hecho el conocimiento de la clave pública no es suficiente para descifrar el mensaje. Este sistema tiene un precio, las claves tienden a tener un mayor tamaño que las de los sistemas simétricos, son más lentos y los mensajes cifrados son de mayor extensión. De esta forma todo lo que se requiere para iniciar una conversación secreta es que el remitente consiga una copia de la clave pública del destinatario, que puede ser usada por cualquier persona que desee comunicarse con su propietario, necesitándose solo n pares de claves por cada n personas que deseen comunicarse entre sí. Actualmente la criptografía asimétrica tiene dos aplicaciones principales, el intercambio de claves privadas y la firma digital que acompaña a un archivo digital. Bases de la Criptografía de clave pública Los sistemas de cifrado de clave pública se basan en funciones-trampa de un sólo sentido que aprovechan propiedades particulares, por ejemplo de los números primos. Una función de un sólo sentido es aquélla cuya computación es fácil,

mientras que el cálculo de su inversa resulta extremádamente difícil (es computacionalmente intratable). Por ejemplo, es fácil multiplicar dos números primos juntos para obtener uno compuesto, pero es difícil factorizar uno compuesto en sus componentes primos. Una función-trampa de un sentido es algo parecido, pero tiene una "trampa". Esto quiere decir que si se conociera alguna pieza de la información, sería fácil computar el inverso. Por ejemplo, si tenemos un

número compuesto por dos factores primarios y conocemos uno de los factores, es fácil computar el segundo. Teniendo en cuenta lo anterior pueden identificarse tres familias según el problema matemático en que se basa la seguridad el criptosistema. La primera familia basa su seguridad en el Problema de Factorización Entera PFE, siendo los más conocidos, RSA, y el de Rabin-Williams. La segunda familia basa su seguridad en el Problema del Logaritmo Discreto PLD, a esta pertenecen el sistema de DiffieHellman de intercambio de claves, el sistema DSA de firma digital y el sistema de ElGamal. La tercera familia basa su seguridad en el Problema del Logaritmo Discreto Elíptico PLDE, pertenecen a esta DHE (Diffie-Hellman Elíptico), DSAE, NRE(Nyberg-Rueppel), ElGamal Elíptico, etc. Logaritmo Discreto Dado un elemento b Є Zn, N un natural positivo, y otro entero x, es “fácil” calcular bx = a mod N. Pero dado a y b, el recuperar x, es un problema difícil, o sea, no existen métodos rápidos que sirvan en cualquier caso, tales que recuperen x. Este es el problema del logaritmo discreto o del índice. El énfasis puesto en la frase “que sirvan en cualquier caso” se debe a que en algunas circunstancias es posible resolver con rapidez el problema del logaritmo discreto. Si se cumple que bx = a diremos que x es un logaritmo discreto de a en la base b y lo escribiremos x = ld ba Planteamos el ejemplo en Zn, pero en realidad los sistemas criptográficos basados en el logaritmo discreto utilizan cuerpos finitos como base, en particular, Zn es un cuerpo si y solo si N es un número primo. Recordamos que en un cuerpo F esta definida una suma, +, y un producto,*, al igual que ocurre en Zn, pero exigimos que para cada elemento a Є F, a ≠ 0 exista un elemento a−1, llamado el inverso de a, tal que a * (a−1) = (a−1) * a = 1, donde 1 es el neutro de la multiplicación, o sea el elemento que cumple a * 1 = 1 * a = a para todo a Є F.

Criptosistema de ElGamal En 1984 Taher ElGamal propuso un esquema de clave pública basado en la exponenciación discreta sobre el grupo multiplicativo de un cuerpo finito Zp . No obstante, aquí presentaremos un protocolo más general al propuesto por ElGamal sobre un cuerpo finito G. Suponemos, en primer lugar que los mensajes son elementos de G y que el usuario A desea enviar un mensaje m al usuario B. El protocolo a seguir es el siguiente: 1. Se selecciona un grupo finito G y un elemento α de G. 2. Cada usuario A elige un núemro aleatorio a, que será su clave privada, y calcula αa en G, que será su clave pública. Para que un usuario A envíe un mensaje m, a otro usuario B, suponiendo que los mensajes son elementos de G, realiza las siguientes operaciones: 1. A genera un número aleatorio v y calcula αv en G. 2. A mira la clave pública de B, αb , y calcula (αb)v y m * αbv en G. 3. A envía la pareja (αv , m*αbv) a B. Para recuperar el mensaje original: 1. B calcula (αv)b en G. 2. B obtiene m solo con calcular m*αvb / αvb Por seguridad y eficacia, el grupo G y el elemento α deberían elegirse de modo que verificaran las siguientes condiciones: • Por eficacia, la operación en G debería ser “fácil” de aplicar. •

Por seguridad, el problema del logaritmo discreto en el subgrupo cíclico de G generado por α, , debería ser “difícil”.

Para simplificar el protocolo anterior, podemos suponer, tal y como fue descrito por ElGamal, que el grupo sobre el que se llevan a cabo las operaciones mencionadas en el protocolo anterior es el grupo multiplicativo del cuerpo Zp ; de esta forma, las potencias y productos anteriores se efectúan módulo un número primo p.

Ejemplo. Consideremos el grupo Z*15485863, con p=15485863 primo y un generador α =7.

A y B eligen las siguientes claves: a=28236, b=21702. αa=728236≅12506884(mod 15485863) y αb=721702≅8890431(mod 15485863), que son las claves privadas y públicas de A y B, respectivamente. Supongamos que A quiere mandar a B el mensaje m=”HIJO”. Entonces, codificamos m: m = “HIJO” = 7.263+8.262+9.26+14 = 128688 A elige el número v = 480 y calcula αv= 7480=12001315(mod 154885863). A continuación A calcula (αv)b = 8890431480 ≅ 9846598(mod 15485863), el de m*αvb=128688*9846598 ≅ 8263449(mod 15485863) y decodifica el par formado por: (αv, m*αvb) = (12001315,8263449), que es el mensaje encriptado:

αv= 12001315 = 1.265+0.264+6.233+21.262+11.26+1=BAGVLB m*αvb = 8263449 = 18.264+2.263+4.262+0.26+1= SCEAZ Por tanto el mensaje a enviar a B, es (BAGVLB,SCEAZ). Veamos como recupera B el mensaje recibido. En primer lugar, B codifica en base 26 la pareja recibida: BAGVLB = 1.265+0.264+6.233+21.262+11.26+1=12001315= α SCEAZ = 18.264+2.263+4.262+0.26+25 = 8263449 = m*αvb A continuación B calcula (αv)b = 1200131521702= 9846598(mod 154885863) y luego tiene que calcular m*αvb / αvb Para ello debe determinar el inverso de αvb mod 15485863. La determinación de este inverso se lleva a cabo por medio del algoritmo de Euclides Extendido, es decir, como - 662582 * αvb + 421299 * p = 1 Resulta que 1/αvb ≅ - 662582 ≅ 14823281 (mod 15485863) Por tanto, m*αvb / αvb = 8263449/98466598 = 8263449*14823281 = 128688 = m

Y recupera el mensaje original: M = 128688 = 7.263+8.262+9.26+14 = HIJO. Ataque al Criptosistema de ElGamal Un escucha, S, que quisiera romper el protocolo anterior, conocería G, n, αa , αb , αv y m*αvb y debería calcular m. Este problema se conoce como el problema de ElGamal(ElGamal Problem, EGP). Es fácil ver que la seguridad de este criptosistema es equivalente a del cambio de clave de Diffie-Hellman; por tanto, la

seguridad del criptosistema de ElGamal está basada en la dificultad del logaritmo discreto. Baste decir que el ataque contra este sistema, hoy por hoy, se considera intratable, dado que los mejores tiempos de computación para calcular algoritmos discretos son de tipo subexponencial.

BIBLIOGRAFIA QUIRANTES SIERRA, Arturo. Taller de Criptografía.2004 http://www.ugr.es/~aquiran/cripto/informes/info002.htm. PLANET CARSOFT. Argentina 2001. http://www.carsoft.com.ar/crip_asim.htm ANUJSETH.COM. 2003 http://www.anujseth.com/crypto/publickey.html JOYNER,D. KREMINSKI,R. TURISCO, J. Applied Abstract Álgebra. El algoritmo de ElGamal.2002 http://web.usna.navy.mil/~wdj/book/node48.html CERTAINTY KEY. Criptosystems. http://www.certainkey.com/resources/glossary.php?Elgamal WILLIAMS, Derek. http://www.louisville.edu/~dawill03/crypto/ElGamal.html WIKIPEDIA http://es.wikipedia.org/wiki/Criptografia_asimetrica GARCÍA HERNÁNDEZ, Arturo. SecureNet2002. http://securenet2002.tripod.com/PKE/pke.html FÚSTER SABATER, otros. Técnicas Criptográficas de Protección de Datos 2ª Edición. AlfaOmega Ra-ma Editores, 2001. CABALLERO GIL, Pino. Seguridad Informática – Técnicas Criptográficas. Computec Ra-ma Editores, 1997. ELGAMAL, T. A Public Key Criptosystem and a Signatura Schema based on Discrete Logarithms. IEEE Trans. Inform. Theory. 1985.