Wrocław, 28.03.2010
Politechnika Wrocławska
Wydział Informatyki i Zarządzania
Kierunek Informatyka
Bezpieczeństwo i ochrona danych
Kryptoanaliza klasycznych algorytmów szyfrowania
Prowadzący:
Przemysław Skawiński
Mgr inż. Paweł Siemionko
164534
ANALIZA WA
ASNOŚCI DOST
PNYCH ALGORYTMÓW
Do porównania cech tekstów w różnych językach wykorzystałem ten sam tekst ze strony
http://lipsum.com/ w 6 językach:
" polskim
" angielskim
" niemieckim
" francuskim
" włoskim
" hiszpańskim
(tekst posiada ok 2500 znaków dla każdego języka)
1. Jaki zmieniają się obserwowane parametry?
1. Wartość entropii:
polski 4,30
angielski 4,17
niemiecki 4,11
francuski 3,99
włoski 4,00
hiszpański 4,02
Zakładamy, że maksymalna możliwa wartość entropii wynosi 4,7. Widzimy, że dla
różnych języków entropia przyjmuje różne wartości. Najmniejsza entropia występuje dla
języka francuskiego, największa dla polskiego.
2. Entropia TJ dla języka angielskiego wynosi 4,17
Entropia TT zaszyfrowanego algorytmami:
cezara 4,17
podstawienia 4,17
playfaira 4,45
adfgvx 2,44
homofonów 7,89
permutacji 4,17
vigenerea
3 (KOT) 4,54
4 (PIES) 4,54
5 (BRONY) 4,59
hilla
2x2 4,67
3x3 4,68
5x5 4,68
Bardzo wyraz
nie widać wpływ niektórych algorytmów szyfrowania na entropię
tekstu tajnego. W algorytmach Cezara, podstawieniowym i permutacyjnym entropia nie
zmienia się w ogóle (gdyż występuje w nich jedynie zamiana miejsc występowania znaków
lub ich podmiana na inne z tego samego alfabetu, w pozostałych możemy zobaczyć pewne
zmiany. Najlepsze wyniki uzyskały metoda Hilla dla tablicy 3x3 i 5x5 i Homofony (max
entropia = 8).
2
3. Histogramy tekstu w różnych językach
3
4
4. Histogramy TT w języku angielskim zaszyfrowanych za pomocą algorytmów:
5
6
Proste metody szyfrowania nie zmieniają histogramu tekstu należącego do danego języka. Na
pierwszych rysunkach widać histogramy, które osiągają takie same wartości lecz dla innych
liter. Umożliwia to w łatwy sposób dopasowanie znaków tekstu tajnego do znaków, które
występują w tekście jawnym.
7
5. Digramy i Trigramy TJ w różnych językach
Digram Analiza . Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 IE 3.3352 61 1 NIE 1.6575 24
2 NI 2.7337 50 2 LOR 1.3122 19
3 ST 2.1870 40 3 WIE 1.3122 19
4 EM 1.6949 31 4 ORE 1.1740 17
5 OR 1.6949 31 5 PRZ 1.1740 17
6 TE 1.6949 31 6 REM 1.1740 17
7 CH 1.4762 27 7 IPS 1.1050 16
8 ER 1.4215 26 8 PSU 1.1050 16
9 RA 1.4215 26 9 SUM 1.1050 16
10 UM 1.3669 25 10 YCH 1.0359 15
11 CZ 1.3122 24 11 RZE 0.9669 14
12 NA 1.3122 24 12 TEK 0.7597 11
13 PR 1.3122 24 13 EKS 0.6906 10
14 RZ 1.3122 24 14 KST 0.6906 10
15 NE 1.2575 23 15 NYC 0.6906 10
16 RE 1.2028 22 16 IEJ 0.6215 9
17 YC 1.2028 22 17 CZY 0.5525 8
18 EN 1.1482 21 18 EGO 0.5525 8
19 LO 1.1482 21 19 IEL 0.5525 8
20 NY 1.1482 21 20 TER 0.5525 8
21 OW 1.1482 21 21 WAN 0.5525 8
22 WI 1.1482 21 22 CZN 0.4834 7
23 ZY 1.1482 21 23 ENI 0.4834 7
24 PO 1.0388 19 24 ERA 0.4834 7
25 AN 0.9841 18 25 IER 0.4834 7
Digram Analiza Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 IN 3.1029 57 1 THE 2.4620 34
2 RE 2.9396 54 2 ORE 1.5206 21
3 OR 2.5041 46 3 LOR 1.4482 20
4 TH 2.4496 45 4 REM 1.3758 19
5 HE 2.1775 40 5 ING 1.2310 17
6 ER 1.7964 33 6 IPS 1.2310 17
7 ON 1.6875 31 7 PSU 1.2310 17
8 TE 1.5787 29 8 SUM 1.2310 17
9 LO 1.4698 27 9 AND 1.0138 14
10 ED 1.4154 26 10 ION 0.8689 12
11 EN 1.3609 25 11 VER 0.7241 10
12 UM 1.3609 25 12 TER 0.6517 9
13 AN 1.3065 24 13 TIO 0.6517 9
14 ES 1.1976 22 14 AGE 0.5793 8
15 IS 1.1976 22 15 ATI 0.5793 8
16 IT 1.1976 22 1 16 ECT 0.5793 8
17 OF 1.1976 22 17 ENT 0.5793 8
18 EM 1.1432 21 18 ERE 0.5793 8
19 NG 1.1432 21 19 NTE 0.5793 8
8
 20 TI 1.1432 21 20 OOK 0.5793 8
21 AR 1.0887 20 21 ABL 0.5069 7
22 NT 1.0887 20 22 ASS 0.5069 7
23 SE 1.0887 20 23 BLE 0.5069 7
24 SU 1.0887 20 24 ERA 0.5069 7
Digram Analiza Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 ER 4.6063 86 1 EIN 1.9417 28
2 EN 2.7852 52 2 DER 1.8724 27
3 DE 2.5710 48 3 LOR 1.3870 20
4 IN 2.5174 47 4 ORE 1.3870 20
5 CH 2.4638 46 5 REM 1.3176 19
6 EI 2.3567 44 6 IPS 1.2483 18
7 TE 2.1960 41 7 PSU 1.2483 18
8 OR 1.9818 37 8 SUM 1.2483 18
9 RE 1.9282 36 9 CHE 0.9709 14
10 ES 1.8211 34 10 TER 0.9015 13
11 IE 1.7675 33 11 VON 0.9015 13
12 GE 1.4997 28 12 DIE 0.7628 11
13 ND 1.4997 28 13 GEN 0.7628 11
14 EM 1.3390 25 14 SCH 0.7628 11
15 ST 1.3390 25 15 UND 0.7628 11
16 UM 1.3390 25 16 CHT 0.6935 10
17 LE 1.2855 24 17 DES 0.6935 10
18 ON 1.2855 24 18 INE 0.6935 10
19 UN 1.2855 24 19 UCH 0.6935 10
20 NE 1.1248 21 20 AND 0.6241 9
21 LO 1.0712 20 21 ICH 0.6241 9
22 SU 1.0712 20 22 RTE 0.6241 9
23 BE 1.0177 19 23 ACH 0.5548 8
24 HE 1.0177 19 24 ASS 0.5548 8
25 IT 1.0177 19 25 ERT 0.5548 8
26 IP 0.9641 18 26 IGE 0.5548 8
Digram Analiza Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 ES 3.0973 63 1 REM 1.4825 22
2 DE 2.8515 58 2 LOR 1.4151 21
3 RE 2.8515 58 3 ION 1.2803 19
4 TE 2.4090 49 4 IPS 1.2803 19
5 EN 2.2124 45 5 ORE 1.2803 19
6 LE 2.2124 45 6 PSU 1.2803 19
7 ON 2.2124 45 7 SUM 1.2803 19
8 NT 2.1141 43 8 ENT 1.2129 18
9 EM 1.8682 38 9 EXT 1.1456 17
10 AN 1.5733 32 10 TEX 0.9434 14
11 UR 1.5733 32 11 TIO 0.9434 14
12 OR 1.4258 29 1 12 XTE 0.9434 14
13 OU 1.3766 28 13 CON 0.8086 12
14 SU 1.3766 28 14 LES 0.8086 12
15 SE 1.3274 27 15 AGE 0.7412 11
9
 16 TI 1.3274 27 16 DES 0.7412 11
17 DU 1.2783 26 17 EUR 0.7412 11
18 NS 1.2783 26 18 ONT 0.7412 11
19 RA 1.2291 25 19 ANS 0.6739 10
20 UM 1.2291 25 20 ANT 0.6739 10
21 IT 1.1799 24 21 EST 0.6739 10
22 LO 1.1799 24 22 AIT 0.6065 9
23 IS 1.1308 23 23 DAN 0.6065 9
24 LA 1.1308 23 24 LUS 0.6065 9
25 CO 1.0816 22 25 QUE 0.6065 9
26 ET 1.0816 22 26 TRA 0.6065 9
Digram Analiza Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 TE 2.4643 50 1 DEL 1.5783 25
2 TO 2.3164 47 2 STO 1.1995 19
3 RE 2.2178 45 3 LOR 1.1364 18
4 ON 2.0700 42 4 EST 1.0732 17
5 ER 1.9714 40 5 ORE 1.0732 17
6 DE 1.9221 39 6 ION 1.0101 16
7 DI 1.9221 39 7 NTE 0.9470 15
8 SE 1.6757 34 8 RAT 0.8838 14
9 EN 1.6264 33 9 TES 0.8838 14
10 IN 1.6264 33 10 IPS 0.8207 13
11 RA 1.6264 33 11 PSU 0.8207 13
12 OR 1.5771 32 12 REM 0.8207 13
13 RI 1.5771 32 13 SUM 0.8207 13
14 ES 1.4786 30 14 ASS 0.7576 12
15 AT 1.4293 29 15 ELL 0.7576 12
16 NE 1.4293 29 16 GGI 0.7576 12
17 ST 1.4293 29 17 ZIO 0.7576 12
18 AR 1.3800 28 18 ENE 0.6944 11
19 CO 1.3800 28 19 ONI 0.6944 11
20 EL 1.3800 28 20 AGG 0.6313 10
21 IO 1.3800 28 21 CHE 0.6313 10
22 LO 1.2814 26 22 CON 0.6313 10
23 AL 1.1828 24 23 ILI 0.6313 10
24 EM 1.1828 24 24 ONE 0.6313 10
Digram Analiza . Trigram Analiza
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 DE 3.8514 84 1 LOR 1.3035 21
2 EN 3.2095 70 2 NTE 1.2415 20
3 ES 2.7510 60 3 ORE 1.2415 20
4 OR 2.3842 52 4 QUE 1.1794 19
5 RE 2.2467 49 5 REM 1.1794 19
6 TE 2.2008 48 6 EXT 1.1173 18
7 AS 1.8799 41 7 IPS 1.1173 18
8 RA 1.6965 37 8 8 PSU 1.1173 18
9 LO 1.6506 36 9 SUM 1.1173 18
10 TO 1.6506 36 10 ENT 1.0552 17
11 NT 1.6048 35 11 TEX 1.0552 17
10
 12 EL 1.5131 33 12 XTO 1.0552 17
13 ER 1.5131 33 13 CON 0.8690 14
14 DO 1.4672 32 14 EST 0.8690 14
15 LA 1.4214 31 15 IEN 0.8690 14
16 ON 1.4214 31 16 ADO 0.7449 12
17 OS 1.4214 31 17 DEL 0.7449 12
18 EM 1.3297 29 18 POR 0.7449 12
19 AL 1.2838 28 19 TRA 0.7449 12
20 AR 1.2380 27 20 ERA 0.6207 10
21 CI 1.2380 27 21 IDO 0.6207 10
22 UM 1.1921 26 22 ION 0.6207 10
23 AN 1.1463 25 23 RAS 0.6207 10
24 LE 1.1463 25 24 ANO 0.4966 8
25 NE 1.1463 25 25 ENE 0.4966 8
26 UE 1.1463 25 26 LAS 0.4966 8
6. Digramy i Trigramy TT języka angielskiego zaszyfrowanego różnymi algorytmami:
Digram Analiza angielski>, klucz > angielski>, klucz >
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 OT 3.1029 57 1 ZNK 2.4620 34
2 XK 2.9396 54 2 UXK 1.5206 21
3 UX 2.5041 46 3 RUX 1.4482 20
4 ZN 2.4496 45 4 XKS 1.3758 19
5 NK 2.1775 40 5 OTM 1.2310 17
6 KX 1.7964 33 6 OVY 1.2310 17
7 UT 1.6875 31 7 VYA 1.2310 17
8 ZK 1.5787 29 8 YAS 1.2310 17
9 RU 1.4698 27 9 GTJ 1.0138 14
10 KJ 1.4154 26 10 OUT 0.8689 12
Digram Analiza , klucz , klucz
>. >.
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 RM 3.1029 57 1 GSV 2.4620 34
2 IV 2.9396 54 2 LIV 1.5206 21
3 LI 2.5041 46 3 OLI 1.4482 20
4 GS 2.4496 45 4 IVN 1.3758 19
5 SV 2.1775 40 5 HFN 1.2310 17
6 VI 1.7964 33 6 KHF 1.2310 17
7 LM 1.6875 31 7 RKH 1.2310 17
8 GV 1.5787 29 8 RMT 1.2310 17
9 OL 1.4698 27 9 ZMW 1.0138 14
10 VW 1.4154 26 10 RLM 0.8689 12
11
Digram Analiza angielski>, klucz >. angielski>, klucz >
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 SF 1.5579 37 1 DSF 0.5055 12
2 QM 1.3895 33 2 FLW 0.4634 11
3 FS 1.3053 31 3 SFL 0.4634 11
4 WS 1.3053 31 4 FSL 0.4212 10
5 SD 1.2632 30 5 WSF 0.4212 10
6 OQ 1.1789 28 6 ESD 0.3791 9
7 PQ 1.1789 28 7 INY 0.3791 9
8 DS 1.0105 24 8 LWI 0.3791 9
9 AQ 0.9263 22 9 MWS 0.3791 9
10 PS 0.9263 22 10 WIN 0.3791 9
Digram Analiza angielski>, klucz , klucz ABCDEFGHIJKLMNOPQRSTUVWXYZ0123 ABCDEFGHIJKLMNOPQRSTUVWXYZ0123
456789>> 456789>>.
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 AA 7.0991 336 1 FAA 2.1133 100
2 FA 6.5286 309 2 AAA 2.0710 98
3 AF 6.0004 284 3 AGF 1.9865 94
4 FF 5.8103 275 4 AFA 1.9231 91
5 GF 5.0919 241 5 AAF 1.6906 80
6 AD 4.8595 230 6 FAD 1.6061 76
7 FD 4.7750 226 7 FFF 1.4793 70
8 DF 4.5637 216 8 DGF 1.4370 68
9 AG 4.3313 205 9 GAA 1.3948 66
10 FG 4.2256 200 10 DFF 1.3736 65
Digram Analiza angielski>, klucz <>> angielski>, klucz <>>
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 AI 2.4390 2 1 CSM 11.1111 1
2 JV 2.4390 2 2 JVA 11.1111 1
3 PY 2.4390 2 3 JVR 11.1111 1
4 UC 2.4390 2 4 OQQ 11.1111 1
5 VA 2.4390 2 5 TAW 11.1111 1
6 WY 2.4390 2 6 UDJ 11.1111 1
7 AA 1.2195 1 7 XVL 11.1111 1
8 AF 1.2195 1 8 YGY 11.1111 1
9 AW 1.2195 1 9 ZYW 11.1111 1
10 AZ 1.2195 1
Digram Analiza szyfrowanie , klucz , klucz PARAMETER: BINARY, 0,1,1,0,1,1>>. PARAMETER: BINARY, 0,1,1,0,1,1>>
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 EO 1.5960 29 1 LMS 1.1963 17
2 EN 1.3759 25 2 RIM 1.1963 17
3 RI 1.3759 25 3 ETE 0.4926 7
4 TE 1.3209 24 4 FRI 0.4222 6
12
 5 ET 1.2658 23 5 ENE 0.3519 5
6 TS 1.2658 23 6 EON 0.3519 5
7 EE 1.2108 22 7 EEN 0.2815 4
8 NT 1.2108 22 8 ENS 0.2815 4
9 EI 1.1558 21 9 ENT 0.2815 4
10 EP 1.1558 21 10 OEO 0.2815 4
Digram Analiza angielski>, klucz > angielski>, klucz >.
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 AA 0.9799 18 1 BDS 0.9413 13
2 DS 0.9799 18 2 IPA 0.5793 8
3 BD 0.9254 17 3 PVT 0.5793 8
4 EB 0.9254 17 4 ZAA 0.5069 7
5 WI 0.9254 17 5 ZDZ 0.5069 7
6 AQ 0.8710 16 6 AQA 0.4345 6
7 IP 0.8710 16 7 AWN 0.4345 6
8 PA 0.8710 16 8 CGM 0.4345 6
9 DZ 0.8165 15 9 EBV 0.4345 6
10 PV 0.8165 15 10 GJU 0.4345 6
Digram Analiza angielski>, klucz , klucz ALPHABET_OFFSET: 0 ALPHABET_OFFSET: 0
MULTIPLICATION_VARIANT: 1 >> MULTIPLICATION_VARIANT: 1 >>
No. Część łańcucha % Częstotliwość No. Część łańcucha % Częstotliwość
1 RK 0.8710 16 1 RKB 0.8689 12
2 KB 0.7077 13 2 SXO 0.5793 8
3 XO 0.6532 12 3 RVJ 0.5069 7
4 DV 0.5988 11 4 ZVT 0.5069 7
5 HF 0.5988 11 5 AOR 0.4345 6
6 PT 0.5988 11 6 DVF 0.4345 6
7 WK 0.5988 11 7 GYM 0.4345 6
8 GY 0.5444 10 8 NGY 0.4345 6
9 RV 0.5444 10 9 ORC 0.4345 6
10 SY 0.5444 10 10 YMK 0.4345 6
Di- i Tri- gramy podobnie jak histogramy mogą pomóc podczas kryptoanalizy tekstu tajnego.
13
7. Analiza wartości autokorelacji TT w języku angielskim
14
Wykresy te są bardzo do siebie podobne i ciężko za ich pomocą wywnioskować jakiego użyto
algorytmu, metoda porównywania wykresów autokorelacji w mniejszym stopniu pomaga przy
kryptoanalizie tekstu.
2. Jak można wykorzystać dostępne w programie CrypTool narzędzia analizy
tekstów do określenia jakiego użyto algorytmu szyfrowania dla zadanego TT?
3. Jak można wykorzystać dostępne w programie CrypTool narzędzia analizy
tekstów do określenia hasła użytego przy szyfrowaniu?
Teksty zaszyfrowane monoalfabetowymi metodami szyfrowania można wykryć poprzez
badanie entropii bądz
histogramu. Entropia w zaszyfrowanym tekście będzie miała taką samą
wartość jak w tekście jawnym. Dzięki histogramowi który będzie miał identyczne wartości lecz dla
innych liter niż w oryginale można odczytać klucz użyty do szyfrowania.
Algorytmy Hill a i Homofony osiągają natomiast wysokie wartości entropii, a algorytm
ADFGVX bardzo niską wartość.
15
ANALIZA DOSTARCZONYVH PLIKÓW
1_1.txt
Do zaszyfrowania TJ został wykorzystany szyfr cezara z kluczem E. W odnalezienu
odpowiedniego algorytmu i klucza pomogła analiza entropii (była równa entropii języka
angielskiego oraz hostogram (najczęściej występującą literą była litera I co mogło wskazywać że
użyto przesunięcia E
1_2.txt
Do zaszyfrowania TJ został wykorzystana permutacja z kluczem: 6, 2, 19, 15, 18, 1, 17, 14, 10,
13, 16, 12, 9, 5, 8, 11, 7, 4, 20, 3. Entropia i histogram były identyczne jak dla języka ang.
Znajomość TJ pomogła w odszyfrowaniu klucza.
1_3.txt
Entropia i histogram wskazują na algorytm Playfair
1_4.txt
Do zaszyfrowania TJ wykorzystany został szyfr zamiany z kluczem: DZIEWCKAOLS.
Entropia była identyczna jak dla j.ang. Histogram wskazywał że litery były przesunięte.
1_5.txt
Do zaszyfrowania TJ został wykorzystany szyfr Vigenera z kluczem DAJMITENOC. Na
algorytm wskazywała wysoka entropia
2_1_adfgvx.txt
Próby odszyfrowania tekstu metodą ręczną lub automatyczną nie powiodły się
2_2_Caesar.txt
Dzięki przeanalizowaniu histogramu udało się rozszyfrować tekst i złamać klucz, klucz to G
2_3_Substitusion.txt
Próby odszyfrowania tekstu metodą ręczną lub automatyczną nie powiodły się
2_4_Vigenere.txt
Dzięki wykorzystaniu automatycznego łamania szyfrów udało się rozszyfrować tekst i złamać
klucz, klucz to PROSTY
3_1.txt
Po przeanalizowaniu entropii oraz histogramu można było stwierdzić że jest to jeden z
algorytmów monoalfabetowych, najczęściej występującą literą była litera P co mogło wskazywać że
użyto szyfru Cezara z przesunięciem K po odszyfrowaniu tekst okazał się prawdziwy,
szyfr Cezara klucz: K
3_2.txt
Analiza entropii i histogramy wskazała na użycie algorytmu zamiany, automatyczna
kryptoanaliza odszyfrowała tekst i klucz: POYSTAWIENUCFGHVKLMQRDBXJZ
3_3.txt
Wysoka entropia wskazywała na algorytm Vigenera lub Hilla po przeprowadzeniu
automatycznej kryptoanalizy algorytmu Vigenera udało się odszyfrować tekst a otrzymany klucz to
SCISLETAJNEHASLO
16
plik entropia język
1.1 3,96 włoski
1.2 4,00 francuski
1.3 4,13 angielski
1.4 4,03 hiszpański
1.5 4,26 polski
1.6 4,15 niemiecki
2.1 4,13 angielski
2.2 4,00 francuski
2.3 4,27 polski
2.4 4,04 hiszpański
2.5 3,97 włoski
2.6 4,16 niemiecki
1. Od czego zależy moc algorytmu?
Moc algorytmu zależy od tego jak wiele informacji o wykorzystanym algorytmie i
zastosowanym kluczu jesteśmy w stanie wywnioskować na podstawie analizy tekstu tajnego,
wykorzystując m.in. Entropię TT, histogram czy autokorelację.
2. Jak można podnieść moc szyfrowania dla poznanej klasy szyfrów?
Należy zadbać, by częstość występowania znaków jak i n-gramów była taka sama. Analiza
histogramu dla algorytmów podstawieniowych to jeden z najprostszych sposobów na złamanie
klucza.
17