Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrados polialfabéticosCifrados polialfabéticos
Los métodos de cifrado en los que se sustituye un carácter por otro fijo se pueden atacar
realizando un ataque de frecuencias.
Una forma de evitar esto es usar un cifrado polialfabético.
En los cifrados polialfabéticos la sustitución que se aplica a cada carácter varía en
función de la posición que ocupa dentro del texto plano.
En realidad corresponde a la aplicación cíclica de n cifrados monoalfabéticos.
Vamos a estudiar uno de estos métodos
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
Johannes Trithemius (1462-1516) y Giambattista della Porta (1535-1615) contribuyen pero es Blaise de Vigenère (1523-1596) el que desarrolla el criptosistema hasta su forma final.
Al principio su interés por la criptología se debía a su trabajo como diplomático.
Con 39 años, Vigenère comenzó a examinar detalladamente las ideas de sus predecesores, tomando contacto con los textos de Alberti, Trithemius y Della Porta
Transformó estas ideas en una cifra poderosa y coherente que por eso lleva su nombre.
En 1586 publica el Traité des chiffres où secrètes manières d'escrire, en el cual propone su célebre tabla de sustitución.
J. Trithemius G. Della Porta
Blaise de Vigenère
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ejemplo Cifrado Polialfabético: Della Ejemplo Cifrado Polialfabético: Della PortaPorta
En la tabla de Della Porta aparece la primera sustitución bigrámica de la historia de la criptologíaSe necesita una tabla de 26 x 26 (alfabeto inglés) que se rellena con símbolos diferentes El alfabeto se escribe dos veces en el borde externo de la tabla: una vez de izquierda a derecha y otra de arriba hacia abajoPara cifrar se sustituye un símbolo por un par de letras en el texto claro. Por ejemplo,
CA
SA
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado Della PortaCifrado Della Porta
Aunque parece que con este método se evita el ataque por frecuencias, en la tabla se observa que algunas columnas dan pistas que facilitan la labor de los criptoanalistas. Para complicar un poco la acción de desencriptación actualmente se utilizan números (1 a 26x26 = 736) escritos aleatoriamente en la tabla
En el De furtivis literarum notis Della Porta presenta un disco cifrante, el segundo después del disco de Alberti.
El disco interno contiene una serie de símbolos que se pueden utilizar para el cifrado.
El disco externo posee un alfabeto ordenado, donde cada letra se acompaña por el número romano correspondiente.
Para generar los alfabetos para cifrar se alinean los símbolos con las letras.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
El cifrado de Vigenère es una generalización del Código de Cesar, pero en
lugar de desplazar cada letra un número fijo de posiciones para obtener la
letra cifrada, el desplazamiento es variable y determinado por una frase o
palabra (clave)
La fuerza de este cifrado es que la misma letra se cifra de maneras
diferentes. Así es inútil el análisis de frecuencia de las letras.
Este método resistió por tres siglos a los criptoanalistas, sin embargo
actualmente es fácil de romper gracias a un método desarrollado
independientemente por Babagge y Kasiski.
Una mejora sobre el cifrado de Vigenère es el sistema de Vernam,
utilizando una clave aleatoria de longitud k igual a la del mensaje. La
confianza en este nuevo criptosistema hizo que se utilizase en las
comunicaciones confidenciales entre la Casa Blanca y el Kremlin, hasta,
por lo menos, el año 1987.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
Primer paso: escribir la tabla
de Vigenère
Cada línea es un alfabeto
desplazando una letra con
respecto a la línea anterior.
Se puede utilizar cualquiera de
los 26 alfabetos para cifrar el
mensaje, en el orden que se
desee.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de Vigenère: EjemploCifrado de Vigenère: Ejemplo
Queremos codificar la frase: Más vale tarde que nunca
La clave del sistema de cifrado de Vigenère es una palabra elegida con
cuidado para que no sea fácil descifrar el mensaje. Vamos a usar la clave
olas
El mensaje a cifrar se descompone en bloques de longitud igual a la
longitud de la clave (en bloques de longitud 4)
A cada uno de estos bloques le aplicamos la clave y asociamos una nueva
letra utilizando la tabla de Vigenère.
Texto claro: MAS VALE TARDE QUE NUNCA
Criptograma: ALSÑOVEMOCDWFFEFJXCS
¿Cómo se llega a este criptograma?
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
http://www.xtec.es/~jjareno/activitats/criptologia/vigenere.htm
TEXTO CLARO: MAS VALE TARDE QUE NUNCA
CLAVE: OLAS
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
Si se cifra con este método hay que tener en cuenta:
– la clave debe ser suficientemente larga y difícil de adivinar
– los caracteres deben estar en el alfabeto
– Es frecuente que los ficheros empiecen por los mismos
bytes, un atacante puede calcular algunos caracteres de la
clave, y podrá descubrir el contenido del fichero
– Con ficheros grandes el algoritmo puede ser un poco lento e
ineficaz
Puedes cifrar tus mensajes con este método en:
http://mimosa.pntic.mec.es/jgomez53/javas/vigenerejm2.htm
Criptografía como recurso para el aula de matemáticas. El arte de esconder
¿Qué clave es mejor?¿Qué clave es mejor?
¿Cual de las claves son más adecuadas para un cifrado de Vigenère? ¿Por
qué
CERO,
COMPADRE,
OLA,
PAPA,
UNO Compadre mejor que cero
Cero mejor que papa
¿ola y uno?
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Beaufort: Variante de VigenèreBeaufort: Variante de Vigenère
Cifrado ideado por el almirante
ingles Sir Francis Beaufort, basado
en la misma tabla de Vigenère y
una clave, pero ahora se restan la
letra original y la clave.
Ejemplo:
Texto: ES MUY PARECIDO AL
ANTERIOR
Clave: cifra
Veamos como se hace para el
primer bloque
Texto cifrado: YQTXC NIONY UFRRP
CVMNJ UUO
C I F R A
2 8 5 17 0
E S M U Y
4 18 12 20 24
-2 -10 -7 -3 -24
24 16 19 23 2
Y Q T X C
http://www.apprendre-en-ligne.net/crypto/vigenere/beaufort.html
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Variante alemana de VigenèreVariante alemana de Vigenère
También existe una variante alemana: se resta al texto en claro la llave
http://serdis.dis.ulpgc.es/~ii-cript/PAGINA%20WEB%20CLASICA/CRIPTOGRAFIA/POLIALFABETICAS/Variante-%20Alemana%20Beafout.htm
Resumiendo los tres cifrados los podemos representar en el esquema:
VIGENERE BEAUFORT ALEMAN
Texto claro+
Clave
Clave-
Texto Claro
Texto claro-
clave
Texto cifrado Texto cifrado Texto cifrado
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Otra variante: Cifra GronsfeldOtra variante: Cifra Gronsfeld
Altera la frecuencia de aparición de las
letras, en forma parecida a la que se ve en
el Manuscrito Voynich (misterioso libro
ilustrado de contenidos desconocidos,
escrito hace unos 500 años por un autor
anónimo en un alfabeto no identificado y en
un idioma incomprensible denominado
voynichés)
El manuscrito ha sido objeto de intensos
estudios por numerosos criptógrafos
profesionales y aficionados, incluyendo
destacados especialistas en descifrados de
la 2ª Guerra Mundial
Fragmento del manuscrito Voynich
Nadie ha logrado descifrar una sola palabra. Esta sucesión de fracasos hace que se hable del misterioso manuscrito; pero ha alimentado también la teoría de que el libro no es más que un elaborado engaño, una secuencia de símbolos al azar sin sentido alguno.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de GronsfeldCifrado de Gronsfeld
Una de las tablas que se usaban antes de la era de los ordenadores para hacer un cifrado de este tipo.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0: C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
1: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
2: F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
3: H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
4: L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
5: N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
6: R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
7: T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
8: X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
9: C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
Ahora tenemos una serie de dígitos como clave. Con esta clave codificamos el texto utilizando el alfabeto desordenado que corresponde con cada dıgito de la clave, asi conseguimos que este metodo sea resistente al analisis de frecuencias.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Rompiendo el Cifrado de Rompiendo el Cifrado de VigenèreVigenère
El método resistió tres siglos a los criptoanalistas
Actualmente es fácil de romper gracias a un método desarrollado de forma independiente por Babagge y Kasisky
Charles Babbage (1791-1871) fue el criptoanalista más importante del siglo XIX
Primera persona que intenta desarrollar una máquina universal para resolver problemas
Descifró Vigenère, aunque no lo publicó se encontró posteriormente entre sus papeles
Utiliza fórmulas matemáticas (álgebra) para la criptología
Máquina diferencial Máquina analítica
Ch. Babbage
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Rompiendo el Cifrado de Vigenère: Rompiendo el Cifrado de Vigenère: KasiskiKasiski
Friedrich Wilhelm Kasiski (1805-1881), publicó en 1863 la forma de
romper el cifrado de Vigenère
Su método consiste en determinar la longitud de la clave en un cifrado
Vigenère, partiendo de palabras repetidas en el texto cifrado.
Podemos pensar con una probabilidad bastante grande que las palabras
repetidas en el texto cifrado no solo eran la misma antes del cifrado sino
que además la clave coincidió en la misma posición en ambas
ocurrencias.
Como la distancia entre palabras repetidas es múltiplo de la longitud de la
clave, era cuestión de buscar diferentes palabras que se repitieran y
hallar su máximo común divisor para encontrar un múltiplo cercano a la
longitud de la clave.
La longitud de la clave será este número o algún factor primo del mismo.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Cifrado de VigenèreCifrado de Vigenère
Una vez descubierta la longitud de la clave con la que se cifró el
documento tan solo hay que dividir el texto en bloques del mismo tamaño
que la longitud de la clave y aplicar el método estadístico tradicional del
cifrado de Cesar
Vamos a hacer intentar romper un texto cifrado con Vigenère.
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ejemplo de ataqueEjemplo de ataque
El texto se ha cifrado con Vigenère y vamos a descifrarlo paso a paso QLENQ WDOGB IKPIX GSVQA UFMJM CZHRL DEJVS EMUEH GMMTI HYFAT FWEKE UJVMX DAJLM YGIVG XWETR FFAQN JHRAZ ITBED QSTBR UANLX ZWPOJ ISJCU VGYFO AJXXW DMZGE FAPVK QAFER UEJOA IESUA NCTQA DAUTW WUSTB RUATI XWUUN THGGZ UEVED OUCHS UTOEN INQCF GPSUM RZMFM CZHRK UEKXR MQVVH IFNRF FELDE JWSKF RVLIK PETBV HARTH QHMRR VMGZC LTXJA SVBWU ANTNE DCUZX VGFRR VSKMD FLWWU STNEL DOKKI KQNVE QMZDF EEEMS CTVYM SVKTA QNKXH WEPLX WVQVR KMGEM VMVGE SVBRL QRINQ HQIXN EDYEE MISGN HNIMZ PFVSE MSKTV VQHRV IFXAJ LIJBI VGXWE FRUYD ASRLI DOOIM IBADV VMXDA JJYWR OIFEF QLENQ WDOGB RGEEU XXAQN VXRWX MRKKW ZDVNR XALZH IKOAG TDVQP IHPGZ GRKWW BOIEE EQSRT XJMVV LHWXA ZKISF RROIK PECFY JADVN RSTOA THWXN ZWSVQ UEIEB MRFWI DMSEN FWEDZ KIUFA DXRLQ ACVMW XORMV SHEJW IDMTF MEDTI EVLSL OEXMF YEELM VMDUX PUUEC HDGTQ LXGGD TRXWD MCFEE VQLTH QWFAT HQGXA UXYFD AKHRR CUVYV SSICX PJMYF WIDME JMVWX LRJYW EEVGG GDVRX RUGAC JYAQR VLTSO IFIIJ AAHNM VASKK IKCUZ GGWFR VLGAQ NKHWF AVVGX SYIEN QWDOU XXWXE WHRGX AKTPD MDVMY UMMZL ESZOD BPFAV VVMWZ TFLWW FEEME QFRVL WWJTF IMKAN LFIJA DVAET UTRGX WESVL IFFAP VMFOO UXGAY OJEEE QDZWE VQLRV EVQRR WSKPE UHWDM CYTVS PAPXP UADZZ SWZLR JYWYI INMKQ NFKZM QLRRG SZTRR TAPEL GGGYP FKXSY IVGXG FRRGU MULFM EENIV GXJMN JVYJD EEEEL UEIKE QQLTB IDAPV KSFAE CGYEQ RFIMW ETVGS WXEJM SVMVZ TYFNU VGGAZ CFGSW EUEHG ZACLT PIGIV KEFUE CNPLU MFLMW FEDXX AQNUH TJUSR HLEQT ZXRVA PIBWS MLRII JQZFL EWFEI GMVMD GTVSX AGXVE MNVGG AMWZL PSIAJ SCENO ILOSB RVFMG ZOSXP VQLZM IJMTL KE
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Pasos a seguir con método de Pasos a seguir con método de KasisnskiKasisnski
1.- Encontrar la longitud L de la clave:
– Buscar palabras repetidas: digramas, trigramas, …
– Calcular la distancia entre ellas: es múltiplo de la clave
– Calcular los divisores de estas distancias
– K será el MCD o alguno de sus factores primos
2.- Dividir el texto en L bloques (L subproblemas de Cesar)
- Aplicar a cada subtexto un análisis de frecuencias
3.- Unir los resultados para construir el texto en claro
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ataque de KasiskiAtaque de Kasiski
• ¿Cuál será la longitud de la clave? Para averiguarlo se cuentan las
veces que aparecen cadenas repetidas de longitud 3 (o mayor)….
• Esto puede ser bastante tedioso pero con la ayuda de aplicaciones
disponibles en la red es posible evitar este trabajo, por ejemplo en
http://pages.central.edu/emp/LintonT/classes/spring01/cryptography/java/kasiski.html
• Entre las cadenas que se repiten en el texto encontramos las
siguientes:
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ataque de KasiskiAtaque de Kasiski
Trigramas Frecuencia Posiciones en que aparece Distancia
ENQ: 3 2, 452, 788 450, 786, 336
NQW 3 3, 453, 789 450, 786, 336
QWD 3 4, 454, 790 450, 786, 336
WDO 3 5, 455, 791 450, 786, 336
IKP 3 10, 238, 538 228, 528, 300
IVG 4 67, 409, 985, 1003 342, 918, 936, 576, 594, 18
.........
El valor del máximo común divisor de estas distancias será un
múltiplo de la longitud de la clave.
Como mcd (450, 786, 336, 228, 528) = 6, la clave podría tener una
longitud de seis caracteres.
¡Pero hay demasiadas palabras con seis letras! ¿Qué podemos
hacer?
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ataque de KasiskiAtaque de Kasiski
Se va a intentar romper el texto cifrado analizando las frecuencias de seis
criptogramas independientes que han sido cifrados con la misma letra
de la clave, tomando para el primero, segundo, ..., los caracteres
separados por seis espacios
En cada bloque contamos la frecuencia de las letras, la más frecuente
debe corresponder a la letra E del texto en claro, la segunda a la A y la
tercera a la O
Criptografía como recurso para el aula de matemáticas. El arte de esconder
La regla AEOLa regla AEO
Si la posición relativa de la letra A es el valor 0, entonces la letra E está cuatro espacios más a la derecha de la A y la letra O está 14 espacios a la derecha de la letra A ó a 10 de la letra E
a b c d e f g h i j k l m n
0 1 2 3 4 5 6 7 8 9 10 11 12 13
o p q r s t u v w x y z
14 15 16 17 18 19 20 21 22 23 24 25
Buscamos las tres letras más frecuentes y que cumplan 0 +4 +10
También podemos tener en cuenta la S que es la siguiente letra más frecuente en la posición 19
Criptografía como recurso para el aula de matemáticas. El arte de esconder
La regla AEOLa regla AEO
A B C D E F G H I J K L M
23 3 4 14 12 13 4 1 1 1 0 1 27
N O P Q R S T U V W X Y Z
4 7 7 32 1 1 4 12 0 0 11 7 13
Para el primer bloque del ejemplo:
La solución que cumple con esto es MQA (27, 32, 23), la letra clave puede ser la M
¿Sois capaces de encontrar las restantes?
Criptografía como recurso para el aula de matemáticas. El arte de esconder
La regla AEOLa regla AEO
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
23 3 4 14 12 13 4 1 1 1 0 1 27 4 7 7 32 1 1 4 12 0 0 11 7 13
21 0 8 12 24 1 1 1 13 0 0 12 6 16 17 7 1 15 14 13 11 7 1 0 1 1
1 0 10 3 15 20 5 2 13 15 8 8 0 0 0 2 0 26 1 11 9 34 1 2 1 16
1 11 0 0 7 7 20 21 6 4 15 17 11 15 1 0 0 2 1 13 2 14 8 24 1 2
0 0 1 2 27 2 12 3 25 0 1 2 19 0 1 11 10 16 15 4 1 11 12 13 13 2
13 2 0 14 10 16 15 3 2 15 13 7 6 1 0 0 2 1 17 1 11 14 34 3 2 1
A E O M Q A (27, 32, 23) A E O (21, 24, 17) R V F (26, 34, 20) T X G (13, 24, 20) E I S (27, 25, 15) S W G (17, 34, 15)
La clave es: Martes
http://www.xtec.es/~jjareno/activitats/criptologia/vigenere.htm
http://www.xtec.es/~jjareno/activitats/criptologia/analisi_kasiski.htm
Criptografía como recurso para el aula de matemáticas. El arte de esconder
¡Por fin descifrado!¡Por fin descifrado!
El número Pi es digno de admiracióntres coma uno cuatro unotodas sus cifras siguientes también
son inicialescinco nueve dos, porque nunca se
termina.No permite abarcarlo con la mirada
seis cinco tres cincocon un cálculo ocho nuevecon la imaginación siete nueveo en broma tres dos tres, es decir,
por comparacióncuatro seis con cualquier otra cosados seis cuatro tres en el mundo.La más larga serpiente después de
varios metros se interrumpeIgualmente, aunque un poco más
tarde, hacen las serpientes fabulosas.
El cortejo de cifras que forman el número Pino se detiene en el margen de un folio, es capaz de prolongarse por la mesa, aa través del aire,a través del muro, de una hoja, del nido de un pájaro,de las nubes, directamente al cieloa través de la total hinchazón e inmensidad del cielo.¡Oh qué corta es la cola del cometa, como la de un ratón!¡Qué frágil el rayo de la estrella que se encorva en cualquier espacio!Pero aquí dos tres quince trescientos noventami número de teléfono la talla de tu camisa
Criptografía como recurso para el aula de matemáticas. El arte de esconder
año mil novecientos setenta y tres sexto pisonúmero de habitantes sesenta y cinco décimosla medida de la cadera dos dedos la charada y el códigoen la que mi ruiseñor vuela y cantay pide un comportamiento tranquilotambién transcurren la tierra y el cielopero no el número Pi, éste no,él es todavía un buen cincono es un ocho cualquierani el último sietemetiendo prisa, oh, metiendo prisa a la perezosa eternidadpara la permanencia.
¡Por fin descifrado!¡Por fin descifrado!
Wislawa Szymborska
( Premio Nóbel de Literatura 1996)
EL Número Pi
Criptografía como recurso para el aula de matemáticas. El arte de esconder
¿adivino la clave?¿adivino la clave?
http://www.xtec.es/~jjareno/activitats/criptologia/analisi_kasiski.htm
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Ejemplo de ataqueEjemplo de ataque
Para calcular los grupos de letras conocidos
http://pages.central.edu/emp/LintonT/classes/spring01/cryptography/java/kasiski.html
Frecuencias de las letras
http://pages.central.edu/emp/LintonT/classes/spring01/cryptography/java/textanalyzer.html
¿Longitud de la clave?
http://pages.central.edu/emp/LintonT/classes/spring01/cryptography/java/gcd.html
¿Qué clave se ha usado?http://www.xtec.es/~jjareno/activitats/criptologia/analisi_kasiski.htm
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Máquina HagelinMáquina Hagelin
S. B. Hagelin inventa en 1930
una máquina que es capaz
de generar textos
encriptados basados en
sustituciones polialfabéticas.
Se conoce como:
– Hagelin cryptograph
– M-209 machine
El ejercito americano la usó
hasta aproximadamente
1950.
Está basada en un método
que toma como base el
cuadro de Beaufort (variante
de Vigenère)
Criptografía como recurso para el aula de matemáticas. El arte de esconder
La máquina HagelinLa máquina Hagelin
Entre los años veinte y los treinta, Hagelin diseña diversas máquinas (B-
21, B-211, C-36, C-48, etc.) en las que a través de ruedas con piñones
realiza el cifrado.
La particularidad de estas máquinas (hacen millonario a Hagelin), estaba
en una periodicidad muy alta puesto que el número de dientes de las
diferentes ruedas eran primos entre sí.
Para seis ruedas estos valores eran 26, 25, 23, 21, 19 y 17, de forma que
el período era igual a su producto (101.405.850)
La ecuación matemática que representa al cifrado de Hagelin es:
Eki(Mj) = (ki - Mj) mod 26
Criptografía como recurso para el aula de matemáticas. El arte de esconder
Sustitución periódica basada en alfabetos desplazados, (utilizando la tabla) en la que se invierte el orden de las letras del alfabeto y luego se desplazan a la derecha.
La máquina HagelinLa máquina Hagelin