Algoritmos

Algoritmos criptográficos

protocolo de tres envíos para transmisión de mensajes es un sistema que permite a un emisor enviar un mensaje a un receptor sin la necesidad de intercambiar claves. Este protoco para envío de mensajes no ha de confundirse con otros algoritmos que utilizan tres pasos para llevar a cabo una autenticación.

Este protocolo se llama así porque el emisor y el receptor intercambian un total de tres mensajes encriptados. El primer protocolo de tres pasos fue desarrollado por Adi Shamir en torno a 1980. El concepto básico del protocolo de tres pasos es que cada parte - emisor, receptor- tiene dos claves privadas, una para encriptar y otra para desencriptar. Las dos partes utilizan sus claves independientemente, primero para encriptar su mensaje y luego para desencriptarlo.

El protocolo utiliza una función de encriptación E y una de desencriptación D. La función de encriptación utiliza una clave de encriptación e para cambiar un mensaje de texto simple m a un mensaje cifrado E(e,m). Correspondiendo a cada clave de encriptación e hay una clave de descriptación d que permite recuperar el mensaje utilizando el función de desencriptación D(d,E(e,m))=m. En algunos casos, la función de encriptación y de desencriptación son la misma.

Para que la función de encriptado y la función de desencriptado sean adecuadas para el protocolo de tres pasos, se ha de cumplir la propiedad de que para cualquier mensaje m, cualquier clave de encriptado con su correspondiente clave de desencriptado d y cualquier clave independiente k, D(d,E(e,E(k,m))) = E(k,m). Es decir, ha de ser posible prescindir de la primera clave de encriptado e aunque se realice una segunda encriptación con la clave k. Esto siempre será posible con un cifrado conmutativo. Un cifrado conmutativo es un cifrado que no depende del orden, es decir, que satisface E(a,E(b,m))=E(b,E(a,m)) para todas las claves de encriptado a, b y para todos los mensajes m. Los encriptados conmutativos satisfacen la igualdad D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).

El protocolo de tres pasos funciona de la siguiente manera:

1. El emisor escoge una clave de encriptado s y su correspondiente clave de desencriptado t. El emisor encripta el mensaje m con la clave s E(s,m). Envía E(s,m) al receptor.
2. El receptor escoge una clave de encriptación r y su correspondiente clave de desencriptado q y re-encripta el primer mensaje E(s,m) con la clave r, devolviendo al emisor E(r,E(s,m)).
3. El emisor desencripta el segundo mensaje con su clave de desencriptado t. Por la propiedad conmutativa anteriormente descrita, D(t,E(r,E(s,m))) = E(r,m), que es el mensaje cifrado con la clave del receptor. El emisor envía E(r,m) al receptor.

Ahora, el receptor puede desencriptar el mensaje usando la clave q: D(q,E(r,m)) = m, el mensaje original.

Tómese en consideración que todas las operaciones que dependen de las claves privadas del emisor se han realizado por parte del emisor, y que todas las operaciones que dependen de las claves del receptor se han realizado por parte del receptor, indicando esto que ninguna de las partes ha necesitado intercambiar claves.

El protocolo de tres pasos de Shamir

El primer protocolo de tres envíos fue el creado por Adi Shamir, desarrollado en torno a 1980. También es conocido como Protocolo sin clave de Shamir, dado que no es necesario el intercambio de claves entre el emisor y el receptor. Aun así, emisor y receptor generan cada uno dos claves privadas, una para encriptar y otra para desencriptar mensajes. El algoritmo de Shamir utiliza exponenciación módulo un primo grande en ambas funciones: encriptación y desencriptación. Esto es E(e,m) = m^e mod p y D(d,m) = m^d mod p donde p es un primo grande. Para cualquier exponente e en el rango 1..p-1 con m.c.d(e,p-1) = 1. El correspondiente exponente de desencriptación debe satisfacer de≡ 1 (mod p-1). Esto se debe al Pequeño teorema de Fermat: D(d,E(e,m)) = m^de mod p = m.

El protocolo de Shamir tiene la deseada propiedad conmutativa, ya que E(a,E(b,m)) = m^ab mod p = m^ba mod p = E(b,E(a,m)).

El criptosistema de Massey-Omura

El criptosistema de Massey-Omura fue propuesto por James Massey y Kim K. Omura en 1982 como una posible mejora del protocolo de Shamir. El método Massey-Omura utiliza exponenciación en campos de Galois GF(2ⁿ) para encriptar y desencriptar. Esto es E(e,m)=m^e y D(d,m)=m^d donde los cálculos son realizados en cuerpos finitos de característica dos. Para cualquier exponente e con 0<e<2 style="line-height: 1em;" sup="">n

-1 y mcd(e,2ⁿ-1)=1, el correspondiente exponente de desencriptación es d tal que de ≡ 1 (mod 2ⁿ-1). Dado que el grupo multiplicativo del cuerpo GF(2ⁿ) tiene orden 2ⁿ-1, por el teorema de Lagrange se tiene que m^de=m para todo m en GF(2ⁿ)^*.

Cada elemento del cuerpo finito GF(2ⁿ) está representado como un vector binario sobre una base normal; se cumple que que cada vector de la base es el cuadrado del vector precedente. Esto significa que los vectores de la base son v¹, v², v⁴, v⁸, ... donde v es un elemento del cuerpo de orden máximo, es decir ${\displaystyle 2^{n}-1}$. Utilizando esta representación, elevar m a una potencia de la forma ${\displaystyle 2^{k}}$ se efectúa realizando desplazamientos cíclicos de las coordenadas de m en la base mencionada previamente. Esto significa que elevar m a una potencia arbitraria se efectúa haciendo, a lo sumo, n desplazamientos y n multiplicaciones en GF(2ⁿ). Además, varias multiplicaciones se pueden realizar en paralelo. Esto permite realizar estos cálculos mucho más rápido si existe la posibilidad de computación en paralelo.

Seguridad

Una condición necesaria para que el protocolo de tres envíos sea seguro es que el atacante sea incapaz de recabar información acerca del mensaje m mediante los envíos E(s,m), E(r,E(s,m)) y E(r,m) realizados.

Para las funciones utilizadas, tanto el en método de Shamir como en el de Massey-Omura, la seguridad se basa en la dificultad que supone calcular el logaritmo discreto en un cuerpo finito. Si un atacante pudiera calcular logaritmos discretos en GF(p) para el método de Shamir o en GF(2ⁿ) para el método de Massey-Omura, el protocolo quedaría vulnerado. La clave s podría ser calculada mediante los mensajes m^r y m^rs. Cuando s sea conocido, es fácil calcular el exponente de desencriptación t. Después, el atacante podría calcular m elevando el mensaje interceptado m^s a la potencia t. K. Sakurai y H. Shizuya mostraron que bajo ciertos supuestos romper el criptosistema de Massey-Omura sería equivalente a la suposición de Diffie-Hellman.

Autenticación

La descripción dada en este artículo sobre el protocolo de tres envíos no contempla ningún tipo de autenticación. Por lo tanto, este protocolo es susceptible a un ataque de tipo man-in-the-middle si un atacante fuera capaz de crear falsos mensajes, o de interceptar y sustituir los originales transmitidos.

El Protocolo de Transferencia de HiperTexto (Hypertext Transfer Protocol) es un sencillo protocolo cliente-servidor que articula los intercambios de información entre los clientes Web y los servidores HTTP. La especificación completa del protocolo HTTP 1/0 está recogida en el RFC 1945. Fue propuesto por Tim Berners-Lee, atendiendo a las necesidades de un sistema global de distribución de información como el World Wide Web.

Desde el punto de vista de las comunicaciones, está soportado sobre los servicios de conexión TCP/IP, y funciona de la misma forma que el resto de los servicios comunes de los entornos UNIX: un proceso servidor escucha en un puerto de comunicaciones TCP (por defecto, el 80), y espera las solicitudes de conexión de los clientes Web. Una vez que se establece la conexión, el protocolo TCP se encarga de mantener la comunicación y garantizar un intercambio de datos libre de errores.

HTTP se basa en sencillas operaciones de solicitud/respuesta. Un cliente establece una conexión con un servidor y envía un mensaje con los datos de la solicitud. El servidor responde con un mensaje similar, que contiene el estado de la operación y su posible resultado. Todas las operaciones pueden adjuntar un objeto o recurso sobre el que actúan; cada objeto Web (documento HTML, fichero multimedia o aplicación CGI) es conocido por su URL.

Etapas de una transacción HTTP.

Para profundizar más en el funcionamiento de HTTP, veremos primero un caso particular de una transacción HTTP; en los siguientes apartados se analizarán las diferentes partes de este proceso.

Cada vez que un cliente realiza una petición a un servidor, se ejecutan los siguientes pasos:

• Un usuario accede a una URL, seleccionando un enlace de un documento HTML o introduciéndola directamente en el campo Location del cliente Web.
• El cliente Web descodifica la URL, separando sus diferentes partes. Así identifica el protocolo de acceso, la dirección DNS o IP del servidor, el posible puerto opcional (el valor por defecto es 80) y el objeto requerido del servidor.
• Se abre una conexión TCP/IP con el servidor, llamando al puerto TCP correspondiente.
  Se realiza la petición. Para ello, se envía el comando necesario (GET, POST, HEAD,…), la dirección del objeto requerido (el contenido de la URL que sigue a la dirección del servidor), la versión del protocolo HTTP empleada (casi siempre HTTP/1.0) y un conjunto variable de información, que incluye datos sobre las capacidades del browser, datos opcionales para el servidor,…
• El servidor devuelve la respuesta al cliente. Consiste en un código de estado y el tipo de dato MIME de la información de retorno, seguido de la propia información.

Los récords en logaritmos discretos son los mejores resultados obtenidos hasta la fecha en la resolución del problema del logaritmo discreto, consistente en encontrar soluciones de x para la ecuación g^x = h, dados dos elementos g y h pertenecientes a un grupo cíclico finito G. La dificultad de resolver el problema es la base de la seguridad de numerosos sistemas criptográficos, entre ellos el protocolo Diffie-Hellman, el cifrado ElGamal, el Algoritmo de Firma Digital (DSA), o la criptografía de curvas elípticas. La elección más habitual de G utilizada en esos algoritmos incluye el grupo multiplicativo de enteros módulo p, el grupo multiplicativo de un cuerpo finito, y el conjunto de puntos de una curva elíptica sobre un cuerpo finito.

Enteros módulo p

El 18 de junio de 2005, Antoine Joux y Reynald Lercier anunciaron la computación de un logaritmo discreto módulo un número primo fuerte de 130 dígitos (431 bits) en tres semanas, utilizando para ello un ordenador HP AlphaServer GS1280 con 16 procesadores a 1.15 GHz ejecutando un algoritmo de criba general del cuerpo de números (GNFS).¹

El 5 de febrero del 2007, fue superado con el anuncio de Thorsten Kleinjung de la computación de un logaritmo discreto módulo un número primo fuerte de 160 dígitos (530 bits), usando de nuevo la criba general del cuerpo de números. La mayor parte de la computación fue realizada utilizando tiempo muerto de CPU en varios ordenadores de un clúster de computación en paralelo.²

Cuerpos finitos

El récord actual (a fecha de 2013) en un cuerpo finito de característica 2 fue anunciado por Antoine Joux el 21 de mayo de 2013. Su equipo fue capaz de computar logaritmos discretos en el cuerpo de 2⁶¹⁶⁸ = (2²⁵⁷)²⁴ elementos usando para ello menos de 550 horas de CPU. Esta computación fue realizada utilizando el mismo algoritmo de cálculo empleado en la computación reciente del cuerpo con 2⁴⁰⁸⁰ elementos.³

Los récords anteriores en cuerpos finitios de característica 2 fueron anunciados por:

• Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 11 de abril 2013. La nueva computación trataba con el cuerpo de 2⁶¹²⁰ elementos y demoró 749,5 horas de CPU.

• Antoine Joux el 22 de marzo de 2013. Utilizó el mismo algoritmo ⁴ para cuerpos de característica pequeña que en la anterior computación del cuerpo de 2¹⁷⁷⁸ elementos. Se computó en el cuerpo con 2⁴⁰⁸⁰ elementos, representado como una extensión de grado 255 del cuerpo con 2¹⁶ elementos, utilizando para ello menos de 14100 horas de CPU.⁵

• Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 19 de febrero de 2013. Utilizaron una nueva variante de la criba general del cuerpo de números con un cuerpo base de tamaño medio, para cuerpos binarios, para computar un logaritmo discreto en un cuerpo de 2¹⁹⁷¹ elementos. Para poder usar un cuerpo base de tamaño medio representaron el cuerpo como una extensión de grado 73 del cuerpo de 2²⁷ elementos. La computación demoró 3132 horas de CPU en un clúster SGI Altix ICE 8200EX utilizando procesadores de 6 núcleos Intel (Westmere) Xeon E5650.⁶

• Antoine Joux el 11 de febrero de 2013. Utilizaba un nuevo algoritmo para cuerpos de característica pequeña. Se computó en un cuerpo de 2¹⁷⁷⁸ elementos, representedo como una extensión de grado 127 del cuerpo con 2¹⁴ elementos. El cómputo se realizo en menos de 220 horas de CPU.⁷

El récord actual (a fecha de 2013) para un cuerpo finito de característica 2 de grado primo fue anunciado por el grupo CARAMEL el 6 de abril de 2013. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en una cuerpo de 2⁸⁰⁹ elementos.⁸ El récord anterior en un cuerpo finito de característica 2 de grado primo fue anunciado por Antoine Joux y Reynald Lercier el 23 de septiembre de 2005. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en un cuerpo de 2⁶¹³ elementos. El cómputo demoró 17 días en cuatro nodos de 16 procesadores, a 1.3 GHz cada uno, del súper-ordenador Teranova, basado en el Itanium 2.⁹

El récord actual (a fecha de 2012) para un cuerpo de característica 3 fue anunciado por una asociación entre Fujitsu, NICT y el equipo de la Universidad de Kyushu, que computaron un logaritmo discreto en el cuerpo de 3^6 · 97 elementos, de 923 bits de tamaño,¹⁰ empleando una variante de la criba general del cuerpo de números, superando así el récord anterior en el cuerpo de 3^6 · 71 elementos de 676 bits ¹¹ por un amplio margen.

Respecto a cuerpos de característica de tamaño "moderado", computaciones notables realizadas en 2005 incluyen aquélla sobre el cuerpo de 65537²⁵ elementos (401 bits), anunciada el 24 de octubre de 2005, y la del cuerpo de 370801³⁰ elementos (556 bits), anunciada el 9 de noviembre de 2005.¹² El récord actual (a fecha de 2013) para un cuerpo finito de característica "moderada" fue anunciada el 6 de enero de 2013. El equipo empleo una nueva variante de la criba general del cuerpo de números para el caso de primos medios para computar un logaritmo discreto en un cuerpo de 33341353⁵⁷ elementos (un cuerpo finito de 1425 bits).^13 14 Se había empleado la misma técnica unas semanas antes para computar un logaritmo discreto en un cuerpo de 33553771⁴⁷ elementos (un cuerpo finito de 1175 bits).^15 14

Curvas elípticas

La corporación Certicom ha propuesto una serie de desafíos relacionados con la Criptografía de curva elíptica. El nivel I involucra cuerpos de 109 y 131 bits. El nivel II incluye los de 163, 191, 239 y 359 bits. Se cree que todos los desafíos de nivel II son computacionalmente inviables.¹⁶

Los desafíos de nivel I que han sido superados son:¹⁷

• ECC2K-108, consistente en tomar un logaritmo discreto en una curva de Koblitz sobre un cuerpo de 2¹⁰⁸ elementos. El premio fue otorgado el 4 de abril del año 2000 a un grupo de unas 1300 personas, representado por Robert Harley. Utilizaron una paralelización del algoritmo rho de Pollard para logaritmos.

• ECC2-109, que consistía en tomar un logaritmo discreto en una curva sobre un cuerpo de 2¹⁰⁹ elementos. El 8 de abril de 2004 se otorgó el premio a un grupo de unas 2600 peronas representado por Chris Monico. También emplearon una versión paralelizada del algoritmo rho de Pollard para logaritmos, durando el cáculo 17 meses de tiempo real.

• ECCp-109, consistente en tomar un logaritmo discreto en una curva modulo un primo de 109 bits. El premio se otorgó el 15 de abril de 2002 a un grupo de 10308 personas, representado por Chris Monico. De nuevo se empleó una variante paralelizada del algoritmo rho de Pollard para logaritmos, demorando 549 días de tiempo real.

Ninguno de los desafíos de 131 bits (o superiores) han sido superados a fecha de 2010.

En julio de 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra y Peter L. Montgomery anunciaron que habían conseguido computar un logaritmo discreto en una curva elíptica módulo un primo de 112 bits. La computación fue realizada mediante un clúster de 200 PlayStation 3 durante 6 meses, empleando la versión paralelizada más común del algoritmo rho de Pollard para logaritmos.

2016: recuento de un récord criptográfico recuperado

El 27 de enero de 2014, el equipo conformado por Adj, Menezes, Oliveira y Rodríguez-Henríquez, resolvió el problema del logaritmo discreto en el campo finito GF(36·137), el cual fue el primero con importancia criptográfica en haber sido vulnerado utilizando el algoritmo parteaguas ideado por el profesor Antoine Joux en marzo de 2013. El tamaño del espacio de búsqueda de ese problema es de 2155, y el cálculo tomó un esfuerzo computacional de 888 horas-núcleo.1

El cálculo anunciado ese día fue un récord mundial con una duración muy breve, pues el 30 de enero de 2014, fue despedazado por el equipo europeo conformado por Granger Kleinjung-Zumbrägel, quienes ese día anunciaron el cómputo del logaritmo discreto en el campo finito GF(212·367) con un tamaño de 4,404 bits y con un espacio de búsqueda de 2698.

En el último capítulo de esta saga (hasta ahora), el lunes 18 de julio de 2016, el equipo conformado por Adj, Canales-Martínez, Cruz-Cortés, Menezes, Oliveira, Rivera-Zamarripa y Rodríguez-Henríquez, anunció a la lista de discusión de teoría de números, el cómputo exitoso del logaritmo discreto en el campo finito GF(36·509) con un tamaño de 4841 bits y un espacio de búsqueda de 2804. El cómputo anunciado por Adj et al. constituye el nuevo récord mundial absoluto para este tipo de problemas.2

El cómputo del logaritmo discreto en GF(36·509) tomó aproximadamente 220 años-núcleo, y fue computado por meses y con primor, en el clúster del Departamento de Computación del Cinvestav, en la supercomputadora Abacus y en un grupo de servidores del Departamento de combinatoria de la Universidad de Waterloo.

Calculado en su mayor parte en supercomputadoras del Centro, el récord mundial del problema del logaritmo discreto vuelve a ser nuestro, por lo que no nos alcanzan nuestros corazones para albergar tanta satisfacción y alegría combinadas.