-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 _____________________________________________________________________ | | | ======= == === === ==== == == === | | = == = = = = == == = | | = = = = = = = = = = = = | | xxxxx x x x x xxxxxx x x x x x | | x x x x x x x x x xxxxxxx | | x x xx x x x x x x x | | xxxxxxx xxx xx xxx xxxxx xxx xxx xxx xxx | |_____________________________________________________________________| Boletín del Taller de Criptografía de Arturo Quirantes http://www.cripto.es Número 67 1 de Abril de 2009 ======================================================================== EDITORIAL CRIPTOGRAFÍA HISTÓRICA - Renace la bomba CRIPTO 101 - La cifra de Playfair ======================================================================== <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> EDITORIAL <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> Hoy seré breve. De hecho, este boletín tiene menor extensión que lo habitual. Hace algunos días me sometí a una operación de cirugía quirúrgica (estrabismo, por si a alguien le interesa), y aunque fue un éxito no tengo los ojos para muchos trotes. Afortunadamente, buena parte del boletín estaba ya escrito. En el apartado negativo, se quedan algunas noticias en el tintero. Pero tranquilos, que ya la aprovecharemos. En la parte positiva, me alegra informaros de un proyecto de arqueología criptográfica llevado a cabo con éxito. También estoy contento porque retomo la sección "Cripto 101", donde todos aprenderemos algo más de los sistemas de cifra tradicionales. Hoy toca el cifrado de Playfair, que no fue inventado por Playfair, como podréis comprobar. Que os aproveche a todos, y nos vemos el mes que viene. <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> CRIPTOGRAFÍA HISTÓRICA <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> =----------------------------------------------------------------------= Renace la Bomba =----------------------------------------------------------------------= Bletchley Park parece ser uno de esos personajes de película que, cuando parece que va a caer para no levantarse, logra sacar fuerzas de flaqueza y seguir en pie. Ya en Junio de 2008 nos hicimos eco de sus últimos problemas de financiación ("Bletchley Park te necesita", Boletín ENIGMA 61). Los muchos amigos de BP acudieron al rescate y, aunque dista de estar en buena situación, nadie tira la toalla. Empresas como IBM y PGP (http://www.pgp.com/stationx/) anunciaron contribuciones al respecto, a las que recientemente se sumaron English Heritage y el propio ayuntamiento de Milton Keynes. Muestra del entusiasmo que levanta BP en Inglaterra es el grado de apoyo que muestran los lectores de The Register (www.theregister.co.uk), una publicación mordaz y crítica con cualquier noticia que se le ponga por delante. Que Bletchley Park está en forma no hay quien lo dude, a juzgar por una noticia reciente que acabamos de conocer: acaban de terminar una réplica de la Bomba criptoanalítica de Turing. Los aficionados de este Taller recordarán que la "Bomba" es un dispositivo electromecánico diseñado para descifrar los códigos Enigma durante la Segunda Guerra Mundial. La primera bomba, de origen polaco, tiene poco que ver con la británica, pero ambas comparten la misma filosofía. Cuando Rejewski y su grupo se lanzaron de lleno a la tarea de reventar la Enigma, uno de los problemas consistía en determinar la posición y orientación de sus rotores. La idea era construir una máquina que replicase la Enigma, y en la que los rotores pudiesen moverse rápidamente, de forma que en un plazo de tiempo razonablemente pequeño pudiesen probarse todas las combinaciones posibles de posición de rotores. Posteriormente los ingleses construyeron otro dispositivo llamado bomba, destinado al mismo uso pero técnicamente mucho más complejo. Si la bomba polaca aprovechaba vulnerabilidades en el envío de los indicadores de clave, la británica atacaba directamente el texto cifrado, buscando concordancias o incompatibilidades. Aprenderíamos mucho estudiando el funcionamiento de ambas bombas. Pero lo dejaremos para más adelante. Hoy tan sólo hablaremos de una pequeña curiosidad: ¿por qué ambas máquinas recibieron el mismo nombre? Algunos ven en ello un "copy+paste" de los británicos, y aprovechan para declamar que los polacos hicieron todo el trabajo. No es ese el caso, como veremos en otro momento. Pero sí resulta curioso el origen del término. Primero, los polacos. Wladyslav Kozaczuk, en su libro "Enigma" afirma que Jerzy Rozycki, uno de los "tres magníficos" polacos, a bautizó la máquina en honor de un helado que estaban tomando en un momento dado [Bomba en singular, Bomby en plural]. Dicho helado era redondo, con una cobertura de chocolate, y se asemejaba a la típica bomba esférica que vemos en los dibujos animados. Efectivamente, un helado no tiene nada que ver con una máquina criptoanalítica, pero posiblemente les dio el arrebato y le pusieron dicho nombre porque les dio la gana (yo les entiendo: vean cómo denomino yo mis programas "serios" en http://www.ugr.es/~aquiran/codigos.htm). Casi mejor eso que llamarla "tinto de verano", hubiera quedado poco serio de cada a la historia. En cuanto a la bomba británica, se suele admitir que el nombre procedía del ruido que hacía la máquina mientras probaba todas las posibilidades, una especie de tic-tac (ahora sería bip-bip, como nos muestran en las películas). John Harper, el líder del equipo que acaba de terminar el proyecto de reconstrucción de la bomba en Bletchley Park, dice que "se decía que nuestras bombas [se refiere a la versión inglesa] hacían tanto ruido como una batería de agujas de tejer." La versión norteamericana no hacía dicho ruido, si bien hay testigos que recuerdan que hacía mucho ruido, pero si las máquinas británicas eran denominadas bombas, tiene sentido que las norteamericanas (más potentes y rápidas, pero esencialmente idénticas) fuesen asimismo llamadas así. Cualquier que fuese el origen del nombre, ahora tenemos una bomba nuevecita en Bletchley Park. Al igual que su primo Colossus, las bombas fueron destruidas después de la guerra, pero se guardaron planos que en los años 70 dieron origen al comienzo del proyecto de reconstrucción que acaba de terminar con éxito. Por cierto, que los entusiastas a la criptografía que viajen a Estados Unidos podrán ver una bomba naval auténtica en el Museo Criptológico Nacional de Estados Unidos (http://cripto.es/museo/ncm2003/ncm12.jpg). La británica es una reconstrucción, pero hecha de la forma más fiel posible. En Bletchley Park afirman que, cada vez que British Telecom actualizaba una centralita, cogían y arramblaban con todas las válvulas de vacío que encontraban; de esa forma, no sólo han podido reconstruir la Bomba, sino que también tienen repuestos para años. No he podido confirmarlo, pero si se pasan ustedes por ahí, podrán comprobarlo. Y ya puestos, envíenme una foto de la bomba, por favor. <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> CRIPTO 101 <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> =----------------------------------------------------------------------= La cifra de Playfair =----------------------------------------------------------------------= Charles Wheatstone fue una de las mentes científicas típicas del siglo XIX. Su campo de interés pasaba por diversas facetas de la Física. Uno de los inventos por los que es más conocido hoy es el denominado "puente de Wheatstone", un instrumento para determinar el valor de una resistencia eléctrica. En la actualidad, su puente apenas es usado más que en laboratorios de didáctica, y como profesor me alegré de desecharlo de mi propio laboratorio hace años. Curiosamente, Wheatstone no inventó su propio puente, sino que tan sólo lo popularizó a partir de un invento de Samuel Cristie. En el campo de la criptografía, Wheatstone es conocido por inventar una máquina de cifra de bolsillo. Fue usada por España durante la Segunda Guerra Mundial. Pero no hablaremos de ella, sino de otro tipo de cifrado inventado por Wheatstone. Para su desgracia, dicho sistema lleva en la actualidad el nombre de otra persona. Sin embargo, fue mérito suyo (al contrario que su puente), y aquí vamos a darle el mérito que se merece. Su sistema de cifra se conoce como Playfair. La cifra Playfair es un buen ejemplo de cómo un sistema criptográfico no tiene que ser complicado para cumplir su función. Es uno de esos "códigos de trinchera", diseñado para ser empleado en el fragor del campo de batalla con poco más que papel y lápiz. Es de funcionamiento muy sencillo, y vamos a verlo a continuación. Lo primero que necesitamos es ordenar las letras del alfabeto en la forma de un cuadrado 5x5. Si cuentan bien, tenemos más de 25 letras en el alfabeto, de forma que tenemos un problema. Incluso en el idioma inglés, sobra una letra. Pero no es problema, ya que tomaremos el convenio de considerar las letras I y J como una sola. Existen muchas formas de organizar las letras del alfabeto. Vamos a tomar, para nuestro ejemplo, el puro y simple orden alfabético. Tenemos así nuestro cuadrado Playfair siguiente: A B C D E F G H IJ K L M N O P Q R S T U V W X Y Z A continuación, escojamos nuestro mensaje: TALLER DE CRIPTOGRAFIA" (y disculpen la forma de presumir). El sistema Playfair cifra dígrafos, es decir, grupos de dos letras, de modo que necesitamos trocear nuestro mensaje: TA LL ER DE CR IP TO GR AF IA Primer problema: tenemos dos letras iguales (LL). Debemos evitarlo. ¿Cómo? Pues, por ejemplo, insertando una letra X entre ellas. Como entonces, tendremos una letra sola al final del mensaje, le añadimos otra X y listo: TA LX LE RD EC RI PT OG RA FI AX Vamos a cifrar. El sistema es fácil. En principio, las dos letras a cifrar forman la mitad de un rectángulo en nuestra tabla. No hay más que tomar las otras dos letras, y tenemos el cifrado hecho. En nuestra tabla, podemos comprobar que las letras A-Q-T-D forman un rectángulo, de forma que TA se convierte en QD. ¿Por qué no en DQ? En principio, sería posible, pero para evitar la ambigüedad se toma la norma de que cada letra se transforma en la que se encuentra en su misma fila. El siguiente dígrafo, LX, forma rectángulo con las letras N y V. L se encuentra en la misma fila que L, de modo que LX => NV. Siguiendo este esquema, nuestro mensaje queda cifrado de la siguiente forma: QD NV PA TB ... y tenemos un problema. El siguiente dígrafo es EC, y como vemos ambas letras yacen en la misma fila, es decir, no forman rectángulo alguno. No hay problema. En ese caso, cada letra se sustituye por la que hay a su derecha. C, por tanto, se convierte en D, y E ... !vaya, hombre, E no tiene nada a su derecha! Pero no hay problema, usaremos un orden circular. Es decir, pasamos de E a A. De esa forma, CE se convierte en DA. En caso de que dos letras se hallen en la misma columna, se aplicaría un criterio similar: cada letra se sustituye por la que hay debajo suya (y si es la última de la columna, pasamos a la primera). Así sí podemos cifrar nuestro mensaje tranquilamente: ta lx le rd ec ri pt og ra fi ax QD NV PA TB AD TG OU IM QB GK CV Como pueden darse cuenta, hemos cifrado og como IM, pero también podíamos haber usado JM, ya que I-J representan el mismo signo, como dije antes. Esto introduce una pequeña incertidumbre al descifrar, pero a cambio tenemos un sistema compacto y cómodo de uso. Para descifrar, se usa el mismo procedimiento, pero al revés. Tomamos QD y lo sustituimos por ta, ya que eso completa el rectángulo. Para dígrafos en la misma fila, sustituimos cada letra por la que se encuentra a su izquierda; y si están en la misma columna, por la que se encuentra encima suya. !Y ya está! El sistema Playfair se compacto, rápido de usar, bastante seguro al eliminar problemas tales como frecuencias de letras y dígrafos, así como disfrutar de otras ventajas. Sólo por citar una, supongamos que quisiésemos cifrar "qtaller de criptografía". Como ven, es un texto llano casi idéntico al anterior. Pero fíjense en lo que obtenemos: qt al xl er de cr ip to gr af ia RU FQ VN BU EA BS KO YT MW FL FD es decir, un texto cifrado que se parece al anterior como un huevo a una castaña. Un sistema tan bonito tiene una pega. Una muy grande. Básicamente, que no hay secreto. Una vez conocido el modo de cifrar, cualquiera puede hacerlo, ya que el sistema es el mismo para todos. Para evitar eso, lo que hacemos es escoger una tabla de Playfair desordenada. La forma habitual es tomar una palabra clave, que situamos en la parte superior de la tabla, y luego rellenamos con las letras que sobran. Es decir, si uso la palabra clave QUIRANTES, obtengo la siguiente tabla: Q U IJ R A N T E S B C D F G H K L M O P V W X Y Z Y, por supuesto, podemos escoger una tabla de forma totalmente desordenada. Solamente necesitamos que ambos interlocutores acuerden de antemano la tabla que van a usar. El número de posibles tablas (es decir, nuestro espacio de claves) es enorme: 25!, es decir, del orden de dieciséis cuatrillones de posibilidades. Por supuesto, si el Playfair fuera tan bueno, lo usaríamos sin pudor, ya que es equivalente a una clave simétrica de 84 bits. Por supuesto, tiene sus debilidades criptoanalíticas. Pero todo a su tiempo. Bien, si Charles Wheatstone inventó la cifra que no lleva hoy su nombre, ¿por qué ese tal Playfair le robó la primacía? ¿Y quién es ese Playfair, ya puestos a ello? Bien, la verdad es que no podemos culparle en absoluto, porque no fue culpa suya. Vamos con un poco de cotille. Lyon Playfair, primer Barón Playfair de St. Andrews, era buen amigo de Wheatstone. Además de ello, fue entre otras cosas viceorador en la Cámara de los Comunes, director general de correos y presidente de la British Association for the Advancement of Science (Asociación Británica para el Avance de la Ciencia), una asociación que aún existe, aunque en enero pasado cambió su nombre por British Science Association. No se les ocurra abreviarlo a BSA, que les sienta fatal. Lyon Playfair aprendió el sistema de cifrado diseñado por su amigo, y en una cena en enero de 1854 lo mostró como "cifra simétrica de Wheatstone". La importancia de dicha cena se entenderá rápidamente si decimos que entre los asistentes se encontraban el futuro primer ministro Lord Palmerston (entonces Ministro de Interior) y el propio Príncipe Alberto, marido de la reina Victoria. Ambos personajes aprendieron la cifra tan bien que pocos días después enviaron a Playfair sendas cartas cifradas con el nuevo sistema. Wheatstone y Playfair intentaron convencer al Foreign Office de las ventajas de su sistema. Pero la respuesta oficial es que resultaba demasiado complicado. Cuenta David Kahn que Wheatstone afirmó que tres de cada cuatro estudiantes de escuela elemental podrían aprenderlo en quince minutos, a lo que se le respondió "puede ser, pero nunca conseguirá enseñárselo a los agregados". Playfair no se arredró, e intentó convencer al príncipe Alberto de que sería un sistema muy útil de vistas a la inminente guerra de Crimea. Finalmente fue adoptado por el Ejército, que al parecer lo usó en la guerra de los Boers. Sin embargo, el altruista intento de Playfair por popularizar el método de cifra de su amigo hizo que a la postre fuese conocido como "cifra Playfair", nombre con el que lo conocemos hoy día. La cifra Playfair sobrevivió a la llegada del siglo XX con buena salud. Fue usada por los británicos durante la Primera Guerra Mundial. Incluso más adelante, conforme avanzaban los sistemas criptográficos, el Playfair continuó usándose ocasionalmente, debido no tanto a su resistencia como a su facilidad de uso. En Agosto de 1943, los supervivientes de una lancha torpedera hundida en el Pacífico lograron enviar un mensaje cifrado con Playfair. Los norteamericanos lograron criptoanalizar el mensaje y enviar una partida de rescate tras las líneas enemigas para rescatara a sus marinos. Por cierto, la lancha torpedera era la PT-109, y entre los tripulantes figuraba el entonces teniente John Fitzgerald Kennedy. Lo que salvó al futuro presidente fue el hecho de que la cifra Playfair no es perfecta. El hecho de que cifre letras a pares reduce grandemente las frecuencias de las letras individuales, pero no tanto las de los dígrafos. En principio, una cifra Playfair con una tabla fija convierte cada para de letras en otro par de letras único. En el ejemplo anterior, TA siempre se convertirá en QD. Es decir, viene a ser un sistema de sustitución simple, sólo que en vez de cifrar letras ciframos pares de letras. Un atacante con textos cifrados de longitud suficiente podrá extraer información sobre el texto llano, y a partir de ahí reconstruir el cuadrado Playfair. Hay diversos procedimientos para "arañar" información. Fíjese el lector en el siguiente cuadrado Playfair, usado antes: Q U IJ R A N T E S B C D F G H K L M O P V W X Y Z Como vimos antes, en la mayoría de los casos los dígrafos en texto llano y sus equivalentes cifrados forman rectángulos. Cada letra se sustituye por la correspondiente de su misma fila. Eso quiere decir que la letra E (la más frecuente de nuestro alfabeto) podrá ser sustituida por las letras N, T, S, B. A veces, cuando el dígrafo se encuentre en columna, podrá ser sustituida por F. Y pare usted de contar. Es decir, las letras del cuadrado que tengamos en la misma fila o columna que las letras más frecuentes (EAO) tendrán a aparecer más en el texto cifrado. En ocasiones, puede echarse mano del método de "palabra probable", es decir, hacer cierta suposiciones sobre el texto llano y ver dónde nos lleva. Pero en general, una cantidad de texto cifrado suficientemente elevado permite criptoanalizar el sistema Playfair con éxito. Eso es lo que salvó a los supervivientes de la PT-109. El sistema Playfair fue modificado con el tiempo para aprovechar su sencillez de manejo. El conocido como Playfair Doble utiliza dos cuadrados diferentes, uno para cifrar y otro para descifrar. La policía alemana lo utilizó durante la Segunda Guerra Mundial, aunque para su desgracia los genios de Bletchley Park ya lo tenían dominado. En la actualidad, un sistema Playfair lo bastante largo caería con gran facilidad. Sin embargo, para mensajes cortos y usando cambios de cuadrado frecuente, podría dar algún quebradero de cabeza a los profesionales. Como diría el creador de PGP, es el tipo de sistema para proteger información frente a tu hermanita pequeña. ======================================================================== El boletín ENIGMA es una publicación gratuita del Taller de Criptografía, y se rige por las normas de la licencia de Creative Commons "Reconocimiento-NoComercial-CompartirIgual". Se permite su libre copia, distribución y comunicación para fines no lucrativos, citando nombre y referencia. Para más información, véase la licencia Creative Commons en sus formas reducida y completa: http://creativecommons.org/licenses/by-nc-sa/2.5/es/deed.es http://creativecommons.org/licenses/by-nc-sa/2.5/es/legalcode.es PARA DARSE DE ALTA: envíe un mensaje a la dirección alta arroba cripto.es añadiendo las palabras alta_enigma en el asunto (subject). PARA DARSE DE BAJA, envíe un mensaje a la dirección baja arroba cripto.es añadiendo las palabras baja_enigma en el asunto (subject) Para comentarios a este boletín (dudas, preguntas, consultas, críticas, noticias, colaboraciones, etc.), estoy a su disposición en la dirección noticias arroba cripto.es Página del Boletín Enigma (incluyendo números atrasados): http://www.cripto.es/enigma.htm (c) Arturo Quirantes 2009. ======================================================================== -----BEGIN PGP SIGNATURE----- Version: PGP 6.5i iQA/AwUBSdMlOg7Y43Xkw2u9EQJpKwCfS34c2Cfj9O8bbFIBblDgkIXbA7wAoMSE Dvk7v57AWVap3RazHxC1nQoK =W5lg -----END PGP SIGNATURE-----