Ejemplo metodo kasiski

1. Técnicas históricas:
Cifrados de substitución (2)
Principios, herramientas y protocolos de criptografía
Yann Frauel – Semestre 2007-1

2. JUFRA FOTLJ CACFX CJBAV IFEOS SLSRT
FEFXW TRFED FCVUN EFVCX NDUSP HHPVE VC
Substitución polialfabética
Criptoanálisis por palabra probable
Etienne Bazeries (s. 19)
Palabra probable: “ALICIA”

3. ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHG
MKAEQ HGPXT EGKOO SKMBG MPXTE YXMPX
LEPKS LNWWC TFLOF TYBQL BMPHG WGOZW
BEONB MEPBC YNMPZ NBOYT SFYSY YUIAH
GYKBY ETZPC GGHTZ BEQIE VCDKX EETZL
ACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOA
MAXAM KZKBG CEYLS FECDW QXBLH TOVIA
ICCAC IGXBP BMWGX DCYXS FBHZO FTYBQ
LDQZB BUFKT QRGHP VIQNR CCSIH RECDW
QXBLS DDIRE XZLMQ SATRZ CKSAN BLPCI
ESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBG
GTWXP RFSYD MPRRS YNIWR AWDDW VVTGB
EMWRA OYSLS GKOYC UMGBS YNWSE TZXOV
XRWSR OVIET QTYVI AZSYO ZEPBC YVIQV
MCWYO MNTDL BMGRW SXKVI ETDCY UMAXB
EOMRY TALIW VVTRP VIWEX ZTQQS AXGJD
WHNFW EYTST BOPCB EEXZL MQSAT RLMWR
HGOCO TMTBC YZWVY HAPXW W
Substitución polialfabética
Criptoanálisis por el método Kasiski/Babbage

4. Substitución polialfabética
Criptoanálisis por el método Kasiski/Babbage
Charles Babbage (1854) / Friedrich Wilhelm Kasiski (1863)
APRENDIMOS A UTILIZAR LA PRENSA
CLAVECLAVE C LAVECLAV EC LAVECL
CARZRFTMJW C FTDPKKAM PC ARZRUL
Repetición del texto claro + Repetición de la clave
=
Repetición del texto cifrado

5. ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHG
MKAEQ HGPXT EGKOO SKMBG MPXTE YXMPX
LEPKS LNWWC TFLOF TYBQL BMPHG WGOZW
BEONB MEPBC YNMPZ NBOYT SFYSY YUIAH
GYKBY ETZPC GGHTZ BEQIE VCDKX EETZL
ACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOA
MAXAM KZKBG CEYLS FECDW QXBLH TOVIA
ICCAC IGXBP BMWGX DCYXS FBHZO FTYBQ
LDQZB BUFKT QRGHP VIQNR CCSIH RECDW
QXBLS DDIRE XZLMQ SATRZ CKSAN BLPCI
ESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBG
GTWXP RFSYD MPRRS YNIWR AWDDW VVTGB
EMWRA OYSLS GKOYC UMGBS YNWSE TZXOV
XRWSR OVIET QTYVI AZSYO ZEPBC YVIQV
MCWYO MNTDL BMGRW SXKVI ETDCY UMAXB
EOMRY TALIW VVTRP VIWEX ZTQQS AXGJD
WHNFW EYTST BOPCB EEXZL MQSAT RLMWR
HGOCO TMTBC YZWVY HAPXW W

6. ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHG
MKAEQ HGPXT EGKOO SKMBG MPXTE YXMPX
LEPKS LNWWC TFLOF TYBQL BMPHG WGOZW
BEONB MEPBC YNMPZ NBOYT SFYSY YUIAH
GYKBY ETZPC GGHTZ BEQIE VCDKX EETZL
ACIAH VLIIY ATSIZ TMPTQ TYVWV FDWOA
MAXAM KZKBG CEYLS FECDW QXBLH TOVIA
ICCAC IGXBP BMWGX DCYXS FBHZO FTYBQ
LDQZB BUFKT QRGHP VIQNR CCSIH RECDW
QXBLS DDIRE XZLMQ SATRZ CKSAN BLPCI
ESOYK BYETZ ZNMMQ TRAOZ SZNQS YAWBG
GTWXP RFSYD MPRRS YNIWR AWDDW VVTGB
EMWRA OYSLS GKOYC UMGBS YNWSE TZXOV
XRWSR OVIET QTYVI AZSYO ZEPBC YVIQV
MCWYO MNTDL BMGRW SXKVI ETDCY UMAXB
EOMRY TALIW VVTRP VIWEX ZTQQS AXGJD
WHNFW EYTST BOPCB EEXZL MQSAT RLMWR
HGOCO TMTBC YZWVY HAPXW W

7. Substitución polialfabética
Criptoaná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

8. Substitución polialfabética
Criptoaná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

9. ELXMHHKGXKTBGEBNYHTTVTHTTFXGELIXXBBBGRELXTNSTT
NGFRATAKBTWTZBMTWTXTTXXFBXTGBH
CGFSGGOMMSFQWOCBSGZZCZVSQDACCHCBDHQUHCCSZRBOZR
QGSSWGOOSZSQSCCDSDBARZGWOZROCA
DZLCMPOPPLLLGNYOYYPBDLLITWMEDTCPCZLFPCDDLZLYZA
STYYDBYYYXRTYYWLXCELPTJEPLLCYP
WXVOKXSXXNOBOBNYYKCEKAIZYOKYWOABYODKVSWDMCPKNO
YWDNDESCNOOYOVYBKYOIVQDYCMMOZX
QOUTATKTLWFMZMMTUBGQXCITVAZLQVCMXFQTIIQIQKCBMZ
AXMIWMLUWVVVZIOMVUMWIQWTBQWTWW
XIIEEEMEEWTPWEPSIYGIEIYMWMKSXIIWSTZQQHXRSSIYMSW
PPWVWSMSXIIEQMGIMRVWSHSESRMVW
BAAGQGBYPCYHBPZFAEHEEAAPVABFBAGGFYBRNRBEAAEEQZ
BRRRVRGGEREAPVNREAYVEANTEAHTYW
Sub-textos extraídos:

12. ECDWQ XBLGZ XOIAX FLVUI AMSCO TEGHG
MKAEQ HGPXT EGKOO SKMBG MPXTE YXMPX
Substitución polialfabética
Criptoanálisis por el método Kasiski/Babbage

13. (William Friedman 1920)
Índice de coincidencia
Texto de n letras
Contiene n
1
x A, n
2
x B, etc.
Probabilidad de sacar una A: n
1
/n
Probabilidad de sacar otra A después de la primera:
(n
1
-1)/(n-1)
Probabilidad de sacar dos A: n
1
/n x (n
1
-1)/(n-1)
Permite distinguir entre monoalfabético y polialfabético

14. Lengua AlemánInglésEspañolFrancésItalianoAleatorio
Índice de
Coincidencia
0.072 0.065 0.074 0.074 0.075 0.038
Índice de coincidencia
IC=∑
i=1
26
n
in
i−1
nn−1
Probabilidad de sacar 2 letras idénticas:

15. Índice de coincidencia
En términos de frecuencias:
n
i
n
~
n
i−1
n−1
~f
i
Si n es grande:
Entonces:IC=∑
i=1
26
f
i
2

16. ABCDEFGH IJKLM
2430251529112313221131926
NOPQRSTUVWXYZ
1223181918273451928243122
ABCDEFGH IJKLM
2900436510332
NOPQRSTUVW XYZ
300021170121011
Criptograma completo
Cada séptima letra
Total: 531
Total: 76
Índice de coincidencia

17. Longitud
Índice de coincidencia
de clave
1 0.042
2 0.0430.043
3 0.0430.0400.041
4 0.0450.0440.0410.042
5 0.0480.0450.0480.0390.043
6 0.0440.0440.0400.0460.0420.036
7 0.0930.0770.0820.0690.0650.0830.086
8 0.0450.0420.0450.0400.0430.0430.0380.036
9 0.0500.0420.0320.0490.0410.0350.0340.0360.052
Índice de coincidencia

18. Una “bomba” para una Enigma de 4 rotores
Alan Turing
(1912 – 1954)
Criptoanálisis de Enigma

19. 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

20. BYDGZ
JSFUP
LARKX
COIVE
QNMHT
BYDGZ
JSFUP
LARKX
COIVE
QNMHT
BYDGZ
JSFUP
LARKX
COIVE
QNMHT
Cifrado de Playfair
(Charles Wheatstone 1854)
OK ® VA
KO ® AV
FJ ® US
VE ® EC
BL ® JC
RM ® ID
Letras dobles: insertar un nulo (X)
Substitución poligrámica

21. Substitución poligrámica
Cifrado de Playfair
Cifrar:
ME GUSTAN ESOS CABALLOS GRISES
con la clave PLAYFAIR.

22. Substitución poligrámica
Cifrado de Playfair
Decifrar:
AMPRN GPORD QV
con la clave PLAYFAIR.

23. 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

24. Cifrar
Descifrar
Substitución poligrámica
Cifrado de Hill
P: texto claro, C: texto cifrado
Clave

25. Ejemplo:
Substitución poligrámica
Cifrado de Hill
[
94
57][
A
B]
=

26. Ejemplo:
Substitución poligrámica
Cifrado de Hill
[
94
57][
A
B]
=[
94
57][
1
2]
=[
17
19]
=[
Q
S]

27. Necesitamos el inverso de la matriz de ciframiento:
Substitución poligrámica
Cifrado de Hill
Descifrar
[
ab
cd]
−1
mod26=ad−bc
−1
[
d−b
−ca]
mod26
determinante
Matriz
adjunta
ad−bc
−1
existe⇔mcdad−bc,26=1

28. Ejemplo:
Substitución poligrámica
Cifrado de Hill
[
94
57]
−1
=

29. Ejemplo:
Substitución poligrámica
Cifrado de Hill
[
94
57]
−1
=9×7−5×4
−1
[
7−4
−59]
9×7−5×4
−1
=43
−1
=17
−1
=23
[
94
57]
−1
=23[
7−4
−59]
=[
161−92
−115207]
=[
512
15−1]

30. 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

31. 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

32. 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

33. Criptograma
OJ 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[
15
10]
=[
7
5]
yD[
13
7]
=[
15
18]

34. Cifrado de Hill:
Criptoanálisis por palabra conocida
D[
1513
107]
=[
715
518]
D=[
715
518][
1513
107]
−1
=[
715
518][
7−13
−1015]
=[
−101134
−145205]
=[
34
1123]