ejemplo metodo kasiski

Técnicas históricas:

Cifrados de substitución (2)

Principios, herramientas y protocolos de criptografía

Yann Frauel – Semestre 2007-1

JUFRA FOTLJ CACFX CJBAV IFEOS SLSRT

FEFXW TRFED FCVUN EFVCX NDUSP HHPVE VC

Substitución polialfabéticaCriptoanálisis por palabra probable

Etienne Bazeries (s. 19)

Palabra probable: “ALICIA”

ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHGMKAEQ HGPXT EGKOO SKMBG MPXTE YXMPXLEPKS LNWWC TFLOF TYBQL BMPHG WGOZWBEONB MEPBC YNMPZ NBOYT SFYSY YUIAHGYKBY ETZPC GGHTZ BEQIE VCDKX EETZLACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOAMAXAM KZKBG CEYLS FECDW QXBLH TOVIAICCAC IGXBP BMWGX DCYXS FBHZO FTYBQLDQZB BUFKT QRGHP VIQNR CCSIH RECDWQXBLS DDIRE XZLMQ SATRZ CKSAN BLPCIESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBGGTWXP RFSYD MPRRS YNIWR AWDDW VVTGBEMWRA OYSLS GKOYC UMGBS YNWSE TZXOVXRWSR OVIET QTYVI AZSYO ZEPBC YVIQVMCWYO MNTDL BMGRW SXKVI ETDCY UMAXBEOMRY TALIW VVTRP VIWEX ZTQQS AXGJDWHNFW EYTST BOPCB EEXZL MQSAT RLMWRHGOCO TMTBC YZWVY HAPXW W

Substitución polialfabéticaCriptoanálisis por el método Kasiski/Babbage

Substitución polialfabéticaCriptoanálisis por el método Kasiski/Babbage

Charles Babbage (1854) / Friedrich Wilhelm Kasiski (1863)

APRENDIMOS A UTILIZAR LA PRENSACLAVECLAVE C LAVECLAV EC LAVECLCARZRFTMJW C FTDPKKAM PC ARZRUL

Repetición del texto claro + Repetición de la clave

=

Repetición del texto cifrado

ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHGMKAEQ HGPXT EGKOO SKMBG MPXTE YXMPXLEPKS LNWWC TFLOF TYBQL BMPHG WGOZWBEONB MEPBC YNMPZ NBOYT SFYSY YUIAHGYKBY ETZPC GGHTZ BEQIE VCDKX EETZLACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOAMAXAM KZKBG CEYLS FECDW QXBLH TOVIAICCAC IGXBP BMWGX DCYXS FBHZO FTYBQLDQZB BUFKT QRGHP VIQNR CCSIH RECDWQXBLS DDIRE XZLMQ SATRZ CKSAN BLPCIESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBGGTWXP RFSYD MPRRS YNIWR AWDDW VVTGBEMWRA OYSLS GKOYC UMGBS YNWSE TZXOVXRWSR OVIET QTYVI AZSYO ZEPBC YVIQVMCWYO MNTDL BMGRW SXKVI ETDCY UMAXBEOMRY TALIW VVTRP VIWEX ZTQQS AXGJDWHNFW EYTST BOPCB EEXZL MQSAT RLMWRHGOCO TMTBC YZWVY HAPXW W

ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHGMKAEQ HGPXT EGKOO SKMBG MPXTE YXMPXLEPKS LNWWC TFLOF TYBQL BMPHG WGOZWBEONB MEPBC YNMPZ NBOYT SFYSY YUIAHGYKBY ETZPC GGHTZ BEQIE VCDKX EETZLACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOAMAXAM KZKBG CEYLS FECDW QXBLH TOVIAICCAC IGXBP BMWGX DCYXS FBHZO FTYBQLDQZB BUFKT QRGHP VIQNR CCSIH RECDWQXBLS DDIRE XZLMQ SATRZ CKSAN BLPCIESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBGGTWXP RFSYD MPRRS YNIWR AWDDW VVTGBEMWRA OYSLS GKOYC UMGBS YNWSE TZXOVXRWSR OVIET QTYVI AZSYO ZEPBC YVIQVMCWYO MNTDL BMGRW SXKVI ETDCY UMAXBEOMRY TALIW VVTRP VIWEX ZTQQS AXGJDWHNFW EYTST BOPCB EEXZL MQSAT RLMWRHGOCO TMTBC YZWVY HAPXW W

Substitución polialfabéticaCriptoanálisis por el método Kasiski/Babbage

Intervalo 1: 196 = 2 x 2 x 7 x 7 Intervalo 2: 70 = 2 x 5 x 7 Intervalo 3: 217=7 x 31

→ La clave tiene longitud 7

Substitución polialfabéticaCriptoanálisis por el método Kasiski/Babbage

La misma letra de la clave se repite cada séptima letra del texto

→ Cada séptima letra fue cifrada con el mismo alfabeto Podemos extraer cada séptima letra

➔ a partir de la primera letra → sub-texto 1➔ a partir de la secunda letra → sub-texto 2➔ etc.

Cada sub-texto es el resultado de un cifrado monoalfabético

Se aplican las técnicas de criptoanálisis monoalfabética a cada sub-texto

ELXMHHKGXKTBGEBNYHTTVTHTTFXGELIXXBBBGRELXTNSTTNGFRATAKBTWTZBMTWTXTTXXFBXTGBH

CGFSGGOMMSFQWOCBSGZZCZVSQDACCHCBDHQUHCCSZRBOZRQGSSWGOOSZSQSCCDSDBARZGWOZROCA

DZLCMPOPPLLLGNYOYYPBDLLITWMEDTCPCZLFPCDDLZLYZASTYYDBYYYXRTYYWLXCELPTJEPLLCYP

WXVOKXSXXNOBOBNYYKCEKAIZYOKYWOABYODKVSWDMCPKNOYWDNDESCNOOYOVYBKYOIVQDYCMMOZX

QOUTATKTLWFMZMMTUBGQXCITVAZLQVCMXFQTIIQIQKCBMZAXMIWMLUWVVVZIOMVUMWIQWTBQWTWW

XIIEEEMEEWTPWEPSIYGIEIYMWMKSXIIWSTZQQHXRSSIYMSWPPWVWSMSXIIEQMGIMRVWSHSESRMVW

BAAGQGBYPCYHBPZFAEHEEAAPVABFBAGGFYBRNRBEAAEEQZBRRRVRGGEREAPVNREAYVEANTEAHTYW

Sub-textos extraídos:

ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHG

MKAEQ HGPXT EGKOO SKMBG MPXTE YXMPX

Substitución polialfabéticaCriptoanálisis por el método Kasiski/Babbage

(William Friedman 1920)

Índice de coincidencia

Texto de n letras

Contiene n1 x A, n

2 x B, etc.

Probabilidad de sacar una A: n1/n

Probabilidad de sacar otra A después de la primera: (n

1-1)/(n-1)

Probabilidad de sacar dos A: n1/n x (n

1-1)/(n-1)

Permite distinguir entre monoalfabético y polialfabético

Lengua Alemán Inglés Español Francés Italiano Aleatorio

Índice deCoincidencia

0.072 0.065 0.074 0.074 0.075 0.038

Índice de coincidencia

IC=∑i=1

26 ni ni− 1

nn− 1

Probabilidad de sacar 2 letras idénticas:

Índice de coincidencia

En términos de frecuencias:

ni

n~ni− 1

n− 1~ f iSi n es grande:

Entonces: IC=∑i=1

26

f i2

A B C D E F G H I J K L M24 30 25 15 29 11 23 13 22 1 13 19 26

N O P Q R S T U V W X Y Z12 23 18 19 18 27 34 5 19 28 24 31 22

A B C D E F G H I J K L M2 9 0 0 4 3 6 5 1 0 3 3 2

N O P Q R S T U V W X Y Z3 0 0 0 2 1 17 0 1 2 10 1 1

Criptograma completo

Cada séptima letra

Total: 531

Total: 76

Índice de coincidencia

LongitudÍndice de coincidencia

de clave

1 0.042

2 0.043 0.043

3 0.043 0.040 0.041

4 0.045 0.044 0.041 0.042

5 0.048 0.045 0.048 0.039 0.043

6 0.044 0.044 0.040 0.046 0.042 0.036

7 0.093 0.077 0.082 0.069 0.065 0.083 0.086

8 0.045 0.042 0.045 0.040 0.043 0.043 0.038 0.036

9 0.050 0.042 0.032 0.049 0.041 0.035 0.034 0.036 0.052

Índice de coincidencia

Una “bomba” para una Enigma de 4 rotores

Alan Turing(1912 – 1954)

Criptoanálisis de Enigma

Substitución poligrámica

La substitución no se hace por letras, sino por paquetes de n letras

Ejemplos:➔ Cifrado de Playfair➔ Cifrado de Hill

B Y D G ZJ S F U PL A R K XC O I V EQ N M H T

B Y D G ZJ S F U PL A R K XC O I V EQ N M H T

B Y D G ZJ S F U PL A R K XC O I V EQ N M H T

Cifrado de Playfair(Charles Wheatstone 1854)

OK → VAKO → AV

FJ → USVE → EC

BL → JCRM → ID

Letras dobles: insertar un nulo (X)

Substitución poligrámica

Substitución poligrámicaCifrado de Playfair

Cifrar:

ME GUSTAN ESOS CABALLOS GRISES

con la clave PLAYFAIR.

Substitución poligrámicaCifrado de Playfair

Decifrar:

AMPRN GPORD QV

con la clave PLAYFAIR.

Cifrado de Hill(Lester S. Hill 1929)

Substitución poligrámica

Usa una fórmula matemática Opera sobre n-gramas Realiza una transformación lineal Usa aritmética modulo 26

Cifrar

Descifrar

Substitución poligrámicaCifrado de Hill

P: texto claro, C: texto cifrado

Clave

Ejemplo:

Substitución poligrámicaCifrado de Hill

[9 45 7 ][

AB ]=

Ejemplo:

Substitución poligrámicaCifrado de Hill

[9 45 7][

AB ]=[9 4

5 7][12]=[17

19]=[QS ]

Necesitamos el inverso de la matriz de ciframiento:

Substitución poligrámicaCifrado de Hill

Descifrar

[a bc d ]

− 1

mod 26=ad− bc − 1[ d − b− c a ]mod 26

determinante Matrizadjunta

ad− bc− 1 existe ⇔ mcd ad− bc ,26=1

Ejemplo:

Substitución poligrámicaCifrado de Hill

[9 45 7]

− 1

=

Ejemplo:

Substitución poligrámicaCifrado de Hill

[9 45 7]

− 1

=9×7− 5×4− 1[ 7 − 4− 5 9 ]

9×7− 5×4− 1=43− 1

=17− 1=23

[9 45 7]

− 1

=23[ 7 − 4− 5 9 ]=[ 161 − 92

− 115 207 ]=[ 5 1215 − 1]

Criptoanálisis de substitución poligrámica

Análisis de frecuencia➔ Difícil porque los grupos son más numerosos que las

letras solas➔ Casi imposible para más que bigramas

Palabra probable

CMYPZ GTAYO EQBYQ JLAOW INELN NECNN 

UESZT YTFRU OWYXH KYADM NJRUK CUFZP 

YPNNM XWSQQ OJMGO JZQZQ FLVAY XGIPR 

OPUFJ WTSVA ATQU

Cifrado de Hill: Criptoanálisis por palabra conocida

Contiene: GEORGE PAPANDREOU

CMYPZ GTAYO EQBYQ JLAOW INELN NECNN 

UESZT YTFRU OWYXH KYADM NJRUK CUFZP 

YPNNM XWSQQ OJMGO JZQZQ FLVAY XGIPR 

OPUFJ WTSVA ATQU

Cifrado de Hill: Criptoanálisis por palabra conocida

Contiene: GEORGE PAPANDREOU

CriptogramaOJ MG OJ ZQ ZQ FL VA YX

(15;10) (13;7) (15;10) (0;17) (0;17) (6;12) (22;1) (25;24)

Texto llano(7;5) (15;18) (7;5) (16;1) (16;1) (14;4) (18;5) (15;21)

GE OR GE PA PA ND RE OU

Cifrado de Hill: Criptoanálisis por palabra conocida

D [1510 ]=[75] y D [13

7 ]=[1518]

Cifrado de Hill: Criptoanálisis por palabra conocida

D[15 1310 7 ]=[7 15

5 18]

D=[7 155 18][

15 1310 7 ]

− 1

=[7 155 18][

7 − 13− 10 15 ]

=[− 101 134− 145 205]=[3 4

11 23]