01 julio 2007

Programa #40: Cortocifrado

Noticias

7ª jornada de gráficos en la uji
Mañana día 2 de julio tendrá lugar en el Aula Magna de la Escola Superior de Tecnologia i Ciències Experimentals de la Universitat Jaume I la séptima edición de las Jornadas Gráficas, organizado como cada año por el Departamento de Gráficos por Computador.

Esta edición se caracteriza por estar más orientada al terreno del desarrollo de videojuegos. Contará con la presencia de gente de la industria empresarial a nivel de la Comunidad Valenciana, destacando la mesa redonda sobre el estado actual del tejido empresarial en España y en nuestra comunidad.
En la sección de enlaces podréis consultar el programa completo de actividades.

El iPhone, ya a la venta en EE.UU.

A la espera de las primeras valoraciones del cacharrito, os dejamos con las impresiones del primer comprador del móvil de Apple: «Un sueño de un año hecho realidad. Es el mejor día de mi vida. Es Navidad, cumpleaños y Año Nuevo en un mismo día». Parece que le ha gustado, ¿no?

IBM lanza el nuevo superordenador más rápido del mundo

Se llama "Blue Gene/P", y es tres veces más potente que su antecesora (la más poderosa hasta ahora), "Blue Gene/L". A grandes rasgos, es como 100.000 veces más potente que un PC de los que podamos tener en casa. De hecho, mientras un PC doméstico suele tener dos procesadores (o cuatro, como mucho), esta máquina tiene casi 300.000 procesadores, frente a los 130.000 que tenía el modelo anterior. Su diseño, además, permite ampliar este número a 884.736.
El departamento de Energía del Laboratorio National Argonne de Illinois será uno de los afortunados que contarán con este modelo, que probablemente se destine a realizar simulaciones complejas para estudiar desde física de partículas hasta nanotecnología.
Sin embargo, la tecnología avanza a toda velocidad (nunca mejor dicho), y ya está en proyecto un computador aún más rápido, éste llamado "Roadrunner" (Correcaminos), que tendrá 16.000 procesadores Cell (diseñados para la PlayStation3 y especializados en cálculos aritméticos) que funcionarán en paralelo a otros 16.000 procesadores convencionales.

El Tema del Día

Criptografía

La criptografía lleva entre nosotros desde hace milenios. La ciencia de ocultar la información ha resultado imprescindible para ganar o perder guerras, y ocultar secretos de Estado.
La contrapartida de la criptografía es el criptoanálisis: descifrar el mensaje sin poseer la clave. El mundo de la transmisión de secretos es una batalla entre criptógrafos y criptoanalistas.

Existen dos técnicas para encriptar información: el más usado es el uso de claves (un conjunto de operaciones que convierten un texto normal en cifrado y viceversa) y los libros de códigos.

Un libro de códigos es como un diccionario: cada palabra o frase compleja están representadas por grupos de letras o cifras. El problema de este método es que sólo pueden usarse palabras con traducción asignada y hay que cambiar de manera regular los libros de códigos, lo que resulta muy costoso. Si no se hiciera así, los criptoanalistas terminarían por “romper” el código, ya que una de las reglas básicas de la criptografía es que las posibilidades de ruptura crecen con la cantidad de texto cifrado accesible.

Por ejemplo, a diario nos movemos entre un montón de información codificada, sin darnos cuenta. Sin ir más lejos, el código SMS con el que algunas personas se intercambian mensajes puede resultar completamente ininteligible para alguien que no conozca el "libro de códigos" con el que descifrar, por ejemplo, que la palabra o sílaba "que" se codifica como "k".

Aunque ya en el Antiguo Egipto podemos encontrar ejemplos de escritura cifrada (con valor ceremonial mágico), es en la Grecia clásica donde está mejor documentado su uso militar. Los éforos (gobernantes) espartanos transmitían las instrucciones a sus estrategas (generales) utilizando un bastón, el escítalo. Se preparaban varios bastones de idénticos diámetros, y se escribían las órdenes en una tira de pergamino enrollada a lo largo del bastón. Desenrollada, sólo contenía una sucesión de letras inconexas: para poder leer el mensaje era necesario otro bastón idéntico. Este tipo de método, en el que cada letra sigue siendo "ella misma", pero que está situada en otra parte en el mensaje, se llama "método de transposición".

A Julio César se le atribuye otro método, el método de desplazamiento o sustitución. Consiste en la sustitución de una letra por otra más adelantada en el abecedario. Por ejemplo, donde aparezca una A, colocamos una B; si aparece una B, colocamos una C, y así sucesivamente hasta la Z, donde colocaríamos una A. En concreto, la cifra del César (se le llama cifra porque a fin de cuentas le sumas un número de desplazamiento a cada letra, la clave, para obtener otra) consistía en lo siguiente, según las crónicas: “Sustituía la primera letra del alfabeto, la A, por la cuarta, D, y así sucesivamente”.

A lo largo de la historia, se ha hecho uso de la criptografía tanto por necesidad como por diversión. Leonardo da Vinci, por ejemplo, transponía sus anotaciones escribiendo especularmente. Para leer correctamente sus anotaciones, había que recurrir a un espejo.

La interceptación y criptoanálisis de mensajes oficiales ha sido el detonante de no pocas acciones políticas y militares. Esta tendencia se incrementó durante la Primera Guerra Mundial por la llegada del teléfono y la radio, y las nuevas formas de cifrado con máquinas automáticas. Pero si en algún momento de la historia la criptografía y el criptoanálisis han sido relevantes, ésta fue durante la Segunda Guerra Mundial.

A 80 kilómetros al noroeste de Londres se encuentra Bletchley Park. En 1938, el MI6 británico había escogido este emplazamiento como sede de su equipo de criptografía: acababa de nacer la Estación X. En el verano del año siguiente, un reducido grupo de criptoanalistas se dirigió hacia allí. Estaban disfrazados como miembros del “Captain Ridley’s Shooting Party”. Su misión: romper la máquina de cifrar nazi Enigma. (Existe un libro y una película homónimas que tratan circunstancialmente el asunto, pero sin duda la obra más recomendable -aún siendo de ficción- se trata de la trilogía del "Criptonomicón", de Neal Stephenson).

Inventada en 1918 para las transacciones bancarias, el operario introducía en ella el texto original y los circuitos de la Enigma, muy parecida a una máquina de escribir portátil, lo convertían en cifrado. El ejército nazi dependía de estas máquinas para sus acciones de guerra. Aunque antes los polacos, y más concretamente el brillante matemático Marian Rejewski, habían roto una primitiva Enigma en 1932, cuando el ejército alemán la probaba en sus maniobras. Incluso construyeron un duplicado.

Con la guerra, todo este conocimiento pasó a manos británicas y francesas. Para asegurar la inviolabilidad de la Enigma, los alemanes habían aumentado la complejidad de su diseño y la clave de cifrado se cambiaba diariamente, lo que obligaba a los criptoanalistas a encontrarla antes de poder descodificar los mensajes nazis. Pero los británicos tenían a su favor los errores cometidos por los operarios alemanes y un fallo fundamental en su diseño: una letra no podía ser codificada como ella misma.

En Bletchley Park trabajaba uno de los matemáticos más brillantes del siglo pasado: Alan Turing. De su prodigioso cerebro surgieron las bombas, dispositivos electromecánicos que reducían el tiempo necesario para encontrar la clave del día –si las cosas iban bien tardaban menos de una hora-. Estas bombas constituyeron la antesala al desarrollo del primer ordenador del mundo, Colossus, diseñado en Bletchley Park para romper el Lorenz, el código utilizado por Hitler para enviar órdenes a sus generales. La informática debe mucho a la criptografía.

Por su parte, la Marina norteamericana se enfrentaba al código japonés JN-25, constituido por 45.000 números de cinco dígitos donde cada uno representaba una palabra o una frase. En la primavera de 1942, los norteamericanos podían leer, con cierta dificultad, el JN-25. Justo entonces empezaron a recibir muchos mensajes refiriéndose a un objetivo designado como “AF”. Los oficiales de inteligencia del almirante Chester Nimitz, comandante en jefe de la flota del Pacífico, sospechaban que se referían a Midway. Para estar seguiros, difundieron una información falsa sobre un problema con la planta de destilación de agua de la isla. Y llegó la confirmación. Un mensaje codificado japonés decía: “AF está escaso de agua”. Los japoneses iban a atacar Midway y allí les estarían esperando. Esta batalla cambió el curso de la guerra en el Pacífico: los japoneses tuvieron que retirarse.

Aunque los códigos americanos también fueron rotos en numerosas ocasiones. Únicamente el usado por los Marines resistió todos los envites de los criptoanalistas japoneses. La razón: el cuerpo de Marines empleó el lenguaje navajo como criptosistema. Por su sintaxis y cualidades tonales, este lenguaje no escrito resulta ininteligible si no se ha recibido un intenso aprendizaje. El método utilizado era sencillo. Cuando un indio navajo recibía un mensaje por radio de un compañero, primero traducía cada palabra a su equivalente inglés. Después, usaba la primera letra de la palabra inglesa para construir la frase. Por ejemplo, la palabra Armada (Navy) podía encriptarse como “tsa” (needle, aguja) “wol-la-chee” (ant, hormiga) “ah-keh-di-glini” (victor, vencedor) “tsah-ah-dzoh” (yucca, yuca). Los navajos podían codificar, transmitir y descodificar tres líneas de mensaje en 20 segundos. Las máquinas de entonces tardaban 30 minutos.
Con el advenimiento de los ordenadores, el mundo criptográfico se revolucionó. Su rapidez de cálculo ha hecho que encontrar un sistema de cifrado inviolable sea cada vez más complicado.
Hasta la Segunda Guerra Mundial, todos los cifrados eran de clave secreta o simétricos, pues empleaban la misma clave para cifrar y para descifrar.

A finales de los años 40, el pionero en la teoría del a información, Claude E. Shannon, sugirió usar una mezcla de transposiciones y sustituciones. En los 70, IBM se hizo eco de la sugerencia de Shannon y desarrolló un sistema que bautizó con el nombre de LUCIFER. En 1976, el Gobierno de los EE.UU. adoptó una variante de este sistema, el DES –Data Encryption Standard–, el paradigma actual de la criptografía de clave secreta. La ventaja de estos criptosistemas es que se pueden utilizar claves aleatorias, lo que dificulta el proceso de criptoanálisis. Sin embargo, como emisor y receptor deben conocer la clave, ésta debe ser enviada y, por tanto, se puede interceptar.

La gran revolución llegó en 1975, cuando dos ingenieros electrónicos de la Universidad de Standford, Whitfield Diffie y Martín Hellman, crearon la criptografía de clave pública.
La nueva idea consistía en algo aparentemente imposible: un criptosistema donde hubiera dos claves, una para cifrar y otra para descifrar.

De esta forma, si tú y yo queremos intercambiar mensajes, cada uno crea su pareja de claves y hacemos pública la clave de cifrado. Entonces tú, usando mi clave de cifrar, me envías un mensaje. Aunque lo intercepten da igual: el único que puede recomponer el mensaje soy yo, que poseo la clave de descifrado. Yo puedo hacer exactamente lo contrario: usaré tu clave pública para enviarte el mensaje.

Visto de otro modo: Yo te envío una caja con una cerradura abierta, de la que sólo yo tengo la llave. Tú recibes la caja, escribes el mensaje, lo pones en la caja y la cierras con su cerradura (ahora no puedes leer el mensaje). Me envías la caja y yo la abro con mi llave. En este ejemplo, la caja con la cerradura es mi clave pública, y la llave de la cerradura es mi clave privada.

La idea es sencilla. El problema está en encontrar una función matemática que la lleve a la práctica. Diffie y Hellman sugirieron que una manera de diseñar sistemas criptográficos seguros era utilizando problemas computacionalmente irresolubles, esto es, que un ordenador tardara millones de años en encontrar la solución. En la actualidad, el método más utilizado es el llamado RSA, desarrollado en 1977 por Ronald Rivest, Adi Shamir y Leonard Adleman. Se basa en que no existe un algoritmo suficientemente eficiente para factorizar grandes números que sean producto de dos números primos (mayores que 10100). La pega es su velocidad. El sistema DES encripta a una velocidad de 20 Mb/sg, mientras que el RSA lo hace a unos 20 Kb/sg.

La seguridad de este sistema viene dado por el número de bits que se utilicen para obtener los dos números primos que generan la clave. Por ejemplo, una clave de 1024 bits puede obtener números hasta aproximadamente 10 elevado a 300. Con una clave de 2048 bits, el número asciende hasta 10 elevado a 600. Con 4096, hasta más de 10 elevado a 1200.

Con el ordenador más potente se tardaría millones de años en encontrar la clave privada. Pero Internet ha venido a cambiar las tornas. A través de la red tenemos acceso a cientos de miles de ellos, y todos constituyen un ordenador gigantesco. Fue así como se consiguió romper el RSA.

En 1993, Peter Shor publicó su algoritmo, mostrando que una computadora cuántica podría en principio mejorar la factorización en tiempo polinomial (un tiempo razonable, en contraposición al tiempo exponencial que tiene en una computadora normal), mostrando RSA como un algoritmo obsoleto. Sin embargo, las computadoras cuánticas no se esperan que acaben su desarrollo hasta dentro de muchos años.

En muchos casos, existe un algoritmo de descifrado encargado de reordenar la información y volverla inteligible, pero no siempre es así. Cuando existen ambas funciones, una para cifrar y otra para descifrar, se dice que el sistema criptográfico es de dos vías o reversible (a partir de un mensaje en claro se puede obtener uno cifrado y a partir de éste se puede obtener el mensaje original), mientras que cuando no existe una función para descifrar se dice que el sistema es de una sola vía (a partir de un mensaje cifrado no es posible obtener el mensaje en claro que lo generó; la aplicación de esto es, por ejemplo, para el almacenamiento de contraseñas).

Los usos más comunes del sistema de claves son la autenticación de usuarios y sistemas, la identificación del locutor, el cifrado de datos digitales, el firmado digital de datos, aumentar la seguridad de las comunicaciones y la garantía de "no repudio" (dado que actúa como un carnet de identidad, no podemos negar la autoría de un mensaje firmado con nuestra firma digital).

Para obtener una clave que podamos compartir con garantías con otra persona o entidad, podemos pedir un certificado digital. Existen varios tipos, en función de la información que contenga y a nombre de quién se emita. Puede ser, principalmente, de tipo personal o de persona jurídica.

Además, existen otros tipos de certificado digital utilizados en entornos más técnicos: de servidor seguro, utilizado en los servidores web que quieren proteger ante terceros el intercambio de información con los usuarios (reconocibles por tener en la barra de dirección de internet el protocolo https, en lugar del típico http), y de firma de código, para garantizar la autoría y la no modificación del código de aplicaciones informáticas.

Además, hay toda una infraestructura de servicios relacionados con la gestión y mantenimiento de estos certificados (que también caducan, tal y como lo haría un DNI, sólo que con un tiempo más limitado).

Freakcionario

Firma digital: Para asegurar la identidad de un correo, si disponemos de un sistema de clave pública y privada, podemos añadir al mensaje un anexo consistente en un "resumen" del mensaje, encriptado con nuestra clave privada. Podemos imaginar este resumen, simplificando, como coger la primera de cada 10 letras del mensaje. El mensaje no se puede reconstruir a partir de la firma, y difícilmente obtendremos las mismas 10 letras si modificáramos el mensaje para cambiar su contenido (en la realidad, se aplica una función matemática mucho más complicada para obtener este resumen). La otra persona recibe nuestro mensaje, cuya parte de la firma puede decodificar con nuestra clave pública. Entonces sólo tiene que comparar el contenido del resumen anexo con el que él mismo calcule del mensaje recibido, para averiguar así si el mensaje ha sido manipulado durante el envío.

Enlaces

VII Jornadas de Gráficos de la UJI
Breve biografía de Turing en la wikipedia
Criptografía en la wikipedia
Firma digital en la wikipedia
RSA en la wikipedia

Próximamente pondremos los cortocircuitos anteriores. Aún seguimos algo desorganizados de tiempo. Disculpad las molestias.