Boletín ENIGMA - nº 67
1 de Abril de 2009
Boletín del Taller de Criptografía
de Arturo Quirantes Sierra
Dirección original: http://www.cripto.es/enigma/boletin_enigma_67.htm
CRIPTOGRAFÍA HISTÓRICA - Renace la bomba
CRIPTO 101 - La cifra de Playfair
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ñadopara 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 cotilleo. 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://www.cripto.es/licencia/deed.es.htm
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 2007
Vuelta a la Página principal del Boletín ENIGMA