chch
Zajímavosti z kryptologie Vít Hrubý
22. 8. 2011
ologie chch
Kryptologie
Hledání zpusobu ˚ bezpeˇcné komunikace, která by zajistila, že nikdo nepovolaný se ke zpráveˇ nedostane Steganografie - ukrytí zprávy Kryptografie - zašifrování zprávy
ologie chch
Steganografie
Zpusob ˚ tajné komunikace, spoˇcívající v ukrytí zprávy, tak že se k ní nepˇrítel nedostane ˇ Recko - voskové psací tabulky, zpráva napsaná na hlaveˇ otroka ˇ Cína - hedvábné kuliˇcky Itálie - Giovanni Porta - vejce natvrdo
ologie chch
Kryptografie Šifrování - otevˇrený text se pˇrevádí na šifrový text Dešifrování - opaˇcný proces šifrování, pˇríjemce získá z šifry otevˇrený text ˇ Luštení(kryptoanalýza) - získávání otevˇreného textu z šifer, avšak bez znalosti šifrovacího systému a klíˇce. ˇ na dva základní druhy Kryptografie se delí 1
Transpozice
2
Substituce
ologie chch
Transpozice
ˇ písmena zprávy-permutace Transpoziˇcní šifra mezi sebou zamení písmen. Poˇcet možných permutací je roven n! Zpráva o 3 písmenech 3! = 6 možností. ˇ - 40! = 8 · 1047 možností Prumerná ˚ veta Poˇcet možných klíˇcu˚ urˇcuje bezpeˇcnost šifry Transpoziˇcní klíˇc
ologie chch
Transpozice
Skytala
Plot Pˇr. Otevˇrený text: Transpoziˇcní šifra plot TASOINŠFALT ˇ RNPZCÍIRPO ˇ Šifrový text: TASOINŠFALTRNPZCÍIRPO
ologie chch
Substituce nahrazení písmen otevˇreného textu jinými písmeny nebo znaky 4. století Kamasútra Julius Caesar - Zápisky o válce Galské Caesarova šifra - šifrová abeceda vznikne posunutím otevˇrené abecedy o tˇri místa ABCDEF GHI J KLMNOP QRST UVWXYZ XYZ ABCDEFGHI J KL MNOPQRST UVW
ologie chch
Monoalfabetcká substituˇcní šifra U Caesarovy je míra bezeˇcnosti nízká, existuje 25 potencionálních klíˇcu˚ Šifrovací abeceda lze vytvoˇrit podle daného klíˇce, hesla. Obecneˇ se tato metoda nazývá monoalfabetcká substituˇcní šifra. Heslo: šifry ABCDEFGHI J K L MNOP QRST UVWX YZ SI F RYAB CDEGHJ KL MNOPQT UV WXZ ˇ r nemožné náhodné uhodnutí klíˇce je témeˇ
ologie chch
Kryptoanalýza první metody - 10. století Arábie, lingvistický výzkum Koránu. Frekvenˇcní kryptoanaýza ˇ ˇ písmeno Ceština - nejˇcastejší E(10,5%) Zdokonalení šifer - klamaˇce, nomenklátory, homofonní šifra
cˇ etnost výskytu písmen v cˇ eském jazyce
ologie chch
Polyalfabetická šifra
využívá k šifrování ne jednu, ale více šifrovacích abeced. 16.stol. Blaise de Vigenere - Vigenerova šifra (26 abeced) Klíˇcové slovo - heslo Otevˇrený text Šifrový text
S B T
I L T
F A F
R I Z
A S S
S E W
I D L
F E J
R V M
A I I
S G Y
I E M
F N S
R E V
A R R
S E W
ologie chch
ologie chch
Neprolomitelná šifra
ˇ Vigenerovy šifry - Charles Babbage 19.století Vyluštení (specifiˇcnost jazyka) Vernamova šifra - absolutneˇ bezpeˇcná (matematicky dokázáno). Šifrovací heslo je stejneˇ dlouhé jako samotná zpráva. ˇ V praxi težko použitelné - jedineˇcnost hesla, pˇresný poˇcet znaku, ˚ náhodná písmena
ologie chch
Polybiuv ˚ cˇ tverec Substituˇcní šifra, kde každé písmeno je nahrazeno dvojicí cˇ ísel. 1 2 3 4 5
1 A F L Q V
2 B G M R W
3 C H N S X
4 D I/J O T Y
5 E K P U Z
Tabulka se obvykle vytváˇrí pomocí hesla. Podle hesla Ostrava by vypadala takto: 1 2 3 4 5
1 O V F L U
2 S B G M W
3 T C H N X
4 R D I/J P Y
5 A E K Q Z
ologie chch
ˇ Kryptologie 1. svetové války Na konci 19. století vynalezeno rádio(Guglielmo Marconi) S vynálezem rádia vzniká potˇreba vysílané zprávy bezpeˇcneˇ šifrovat. Až do konce 1 sv. války nikdo nevymyslel šifru relativneˇ snadno ˇ rozluštitelnou šifru(Nemecká šifra ADFGVX) Používání kódových knih. ˇ Zimmermanova telegramu. Vstup USA do války díky rozluštení
ologie chch
ADFGVX ˇ Bˇrezen 1918-pˇred zahájením nemecké ofenzívy ˇ Rozluštena G-J. Painvinem, porovnáváním opakujících se slov na zaˇcátcích a koncích zpráv. Šifra spoˇcívá v kombinaci dvou metod-substituce(pomocí substituˇcního klíˇce) a transpozice(pomocí permutaˇcního klíˇce). Substituce se provádí pomocí písmenkové analogie Polybiova cˇ tverce. A D F G V X
A A G M S Y 5
D B H N T Z 6
F C I O U 1 7
G D J P V 2 8
V E K Q W 3 9
X F L R X 4 0
ologie chch
ADFGVX Otevˇrený text: Letní škola Substituˇcní klíˇc: Je 22. srpna Transpoziˇcní klíˇc: Léto Substituˇcní tabulka: A D F G V X
A J N G O X 5
D E A H Q Y 6
F 2 B I T Z 7
G S C K U 1 8
V R D L V 3 9
X P F M W 4 0
Substituovaný text: L FV
E AD
T GF
N DA
I FF
S AG
K FG
O GA
L FV
A DA
ologie chch
ADFGVX Substituovaný text se napíše po ˇrádcích do tabulky, která má poˇcet sloupcu˚ stejný jako poˇcet písmen transpoziˇcního hesla. L 2 F G F F F
E 1 V F F G V
T 4 A D A G D
O 3 D A G A A
ˇ Šifrový text se nakonec napíše po sloupcích vzestupne. VFFGVFGFFFDAGAAADAGD
ologie chch
Mechanizace šifrování
Šifrovací disk - 15. století, Ital Alberti, mechanická pomucka ˚ k Vigeneroveˇ šifˇre ˇ E.H.Hebern - 1918 první šifrovací stroj s rotorem, pozdeji ˇ petirotorový - 265 možností Arthur Schrebius - 1927 odkoupil patent od Nizozemce H.A.Kocha, stroji dal název Enigma(ˇrecky záhada)
ologie chch
Enigma
vojenská enigma se skládala ze tˇrí cˇ ástí: 1
klávesnice pro zadávání otevˇreného textu
2
šifrovací jednotka s disky(rotory)
3
signalizaˇcní lalmpiˇcky
ologie chch
Enigma Pˇríklad disku(pro jednoduchost se 6 písmeny) a b c d e f
C A D B E F
Pˇri zápisu každého písmene se disk otoˇcí o 1/6(1/26) a b c d e f
A D B E C F
ologie chch
Enigma
ˇ Duležitou ˚ souˇcístí stroje byl reflektor, umožnující jednoduchost dešifrování
ologie chch
Enigma ˇ Bezpoˇcnost byla zvýšena dalšími dvema prvky: 1
ˇ vymenitelné šifrovací disky
2
propojovací deska
ologie chch
Enigma
Celkový poˇcet nastavení Enigmy byl závislý na: 1
Nastavení disku˚ - 263 = 17576
2
Uspoˇrádání disku˚ - 3! = 6
3
Nastavení propojovací desky - 100 391 791 500
17576 × 6 × 100 391 791 500 = 1, 06 · 1016 možných nastavení
ologie chch
ˇ Enigmy Luštení
Polské Biuro Szyfrow ˇ Plány stroje získané špionáží - neloajální Nemec H.T.Schmidt ˇ - unikátní tˇrímístný klíˇc Problém pˇri luštení Marian Rejewski - tabulka závislostí jednotlivých písmen denního klíˇce
ologie chch
ˇ Enigmy Luštení tabulka závíslostí: AB CDEF GHI J KL MNOPQRST UVWXYZ FQHPL WOGBMVRX UY CZ I TNJ EA SDK Rejewski provedl cyklickou dekompozici této permutace, tím uspoˇrádal písmena do cyklu. ˚ A→F →W →A B→Q→Y →K →V →E →L→R→I→B C→H→G→O→Y →D→P→C J→M→X →S→T →N→U→J Délka cyklu˚ - 4,9,7,7
ologie chch
ˇ Enigmy Luštení ˇ ˇ eˇ písmen na propojovací desce se Duležitým ˚ zjištením byl, že pˇri zmen ˇ nezmenila délka cyklu Zameníme-li K ↔ L A→F →W →A B→Q→Y →L→V →E →K →R→I→B C→H→G→O→Y →D→P→C J→M→X →S→T →N→U→J Délka cyklu˚ - 4,9,7,7
ologie chch
ˇ Enigmy Luštení Rejevski zužil ˚ poˇcet možných denních klíˇcu˚ z 1, 06 · 1016 na 105 456(17 567 · 6) Katalog cyklu˚ podle všech možných natavení ˇ Šifrování propojovací desky lušteno logickou úvahou Bomby-mechanické stroje hledající denní nastavení 1938-další dva disky −→ 60 možných nastavení disku˚
ologie chch
Britští luštitelé
Bletchy park Enigma Luftwaffe - chyby v šifrování Námoˇrní Enigma - 8 disku˚ Další stroje - SZ-40, SZ-42(binární šifrování), Japonský Purpur
ologie chch
Šifrování za války
USA-Navaho SSSR-Jednorázové klíˇce Británie-Naval cipher, Playfair
ologie chch
Playfair Búrské války, 1.sv.válka, 2.sv.válka(SOE) Princip - Playfair nešifruje jednotlivá písmena, ale dvojice písmen. Pomocí hesla "pˇríklad Playfair"vytvoˇríme tabulku 5x5 P A C N U
R D E O V
I/J Y G Q W
K F H S X
L B M T Z
ˇ Text, který chceme zašifovat nyní rozdelíme do dvojic. Otevˇrený text:Ostravská univerzita OS TR AV SK AU NI VE RZ IT AX
ologie chch
Playfair Nyní nastanou tˇri možnosti: 1
Dvojice písmen leží jiném ˇrádku a sloupci - písmena se doplní na obdelník.(TR → OL)
2
Písmena leží ve stejném ˇrádku - jako šifrová se berou písmena vpravo(OS → QT)
3
Písmena leží se stejném sloupci - vybírají se písmena pod (SK → XF) P A C N U
R D E O V
I/J Y G Q W
K F H S X
L B M T Z
Šifrový text: QT OL DU XF CP QP RO LV LQ FU
ologie chch
ˇ Ceskoslovenské šifrování Praha-Londýn(Paˇríž, Istanbul, Moskva) Metoda TTS(transpozice, transpozice, substituce) Sady hesel(0-9,R) Otevˇrený text: Ostravaská univerzita Hesla:2-Beneš, R-Masaryk 1.Transpozice: B 1 O V N Z
E 2 S S I I
N 4 T K V T
Výsledný text: OVNZSSIIRÁEATKVTAUR
E 3 R A E A
Š 5 A U R
ologie chch
ˇ Ceskoslovenské šifrování 2.Transpozice:
M 4 O I V
A 1 V R T
S 6 N Á A
A 2 Z E U
R 5 S A R
Dostáváme: VRTZEUIKOIVSARNÁAST
Y 7 S T
K 3 I K
ologie chch
ˇ Ceskoslovenské šifrování 3.Substituce:tabulka od cˇ ísla 22 A 22 N 37 Ž 07
B 23 O 38 . 08
C 24 P 39 ? 09
ˇ C 25 Q 40 10
D 26 R 41 / 11
E 27 ˇ R 42 1 12
ˇ E 28 S 43 2 13
F 29 Š 44 3 14
G 30 T 45 4 15
H 31 U 01 5 16
I 32 V 02 6 17
J 33 W 03 7 18
K 34 X 04 8 19
L 35 Y 05 9 20
Výsledná šifra: 02414506270132343832024322413722224345 ˇ Rozdelená do bloku˚ po 5 písmenech: 02414 50627 01313 43832 02432 24137 22224 34598
M 36 Z 06 0 21
ologie chch
Šifrování veˇrejným klíˇcem Elektronika, výpoˇcetní technika - binární šifrování Problém distribuce klíˇcu˚ Alice a Bob ˇ W.Diffie, M. Hellman - jednosmerná funkce ˇ Obousmerná funkce y = 3x ˇ Jednosmerná funkce y ≡ 3x (mod 7) x 3x 3x (mod 7)
0 0 0
1 3 3
2 6 6
3 9 2
4 12 5
5 15 1
6 18 4
ologie chch
Princip Diffie-Hellman šifrování Fce αx (mod p), kde p je prvoˇcíslo a α ∈ Zp , (2 ≤ α ≤ p − 2) Na zaˇcátku se Alice a Bob veˇrejneˇ domluví na hodnotách α a p Alice zvolí tajné cˇ íslo z
Bob zvolí tajné cˇ íslo y
Vypoˇcítá A = αz (mod p) a pošle ho Bobovi
Vypoˇcítá B = αy (mod p) a pošle ho Alici
Nyní vypoˇcítá šifrovací klíˇc K = B z (mod p)
Nyní vypoˇcítá šifrovací klíˇc K = Ay (mod p)
ˇ ke stejnému výsledku K Alice i Bob dospeli (αz )y = αzy = (αy )z
ologie chch
Diffie-Hellman pˇríklad α = 5, p = 7 Alice zvolí z = 4 A = 54 (mod 7) = = 625 (mod 7) = 2 K = 64 (mod 7) = = 1296 (mod 7) = 1
Bob zvolí y = 3 B = 53 (mod 7) = = 125 (mod 7) = 6 K = 23 (mod 7) = = 8 (mod 7) = 1
Z hlediska útoˇcníka nelze klíˇc snadno zjistit. Známé jsou hodnoty α, p, A, B. Jde o to vypoˇcítat logα A (mod p) = z. Tento úkol se nazývá Discrete logarithm problem.
ologie chch
Asymetrické šifrování
První myšlenka W.Diffie Rozdílný šifrovací a dešifrovací klíˇc RSA(Rivest, Shamir, Adleman)-první asymetrická šifra. Založena na souˇcinu dvou velkých prvnoˇcísel Faktorizace
ologie chch
RSA Alice si zvolí dveˇ velká náhodná prvoˇcísla p a q (v ˇrádech 10150 ) a vypoˇcítá si následující hodnoty: n =p·q Φ = (p − 1) · (q − 1) = n + 1 − p − q e; (1 < e < Φ) a platí gcd(e, Φ) = 1 d; e · d ≡ 1 (mod Φ) Jako Alicin veˇrejný klíˇc slouží dvojice (n,e).Oznaˇcme si otevˇrený text m a šifrový text c Šifrování se provádí pomocí funkce f : f : c = me
(mod n)
Dešifrování se provádí inverzní operací f −1 : f −1 : m = c d
(mod n)
ologie chch
RSA-pˇríklad Chceme Alici poslat písmeno F. V ASCII kódu je F reprezentováno jako 1000110, v desítkové soustaveˇ 70. Oznaˇcíme m=70. Zvolíme cˇ ísla p=11 a q=13.Tedy n = p · q = 143. Vypoˇcítáme hodnotu Φ = (p − 1) · (q − 1) = 10 · 12 = 120. Zvolíme libovolneˇ e = 7; gcd(e, Φ) = 1 Známe (n,e), mužeme ˚ zašifrovat zprávu: c = me
(mod n) = 707
(mod 143) = 60
Alice si vypoˇcítá d=103; e · d (mod Φ) = 1 a dešifruje zprávu: m = cd
(mod n) = 60103
(mod 143) = 70 = F
ologie chch
ˇ Umocnování v Zn Algoritmus: Vstup: a ∈ Zn , k ∈ Z; 0 ≤ P k < n, kde k je ve dvojkové soustaveˇ reprezentováno jako k = ti=0 ki 2i = k0 20 + k1 21 + · · · + kt 2t Výstup: b = ak mod n 1 2 3
4
Jesliže k = 0, pak 1 → b a→A Jestliže, k0 = 1,pak a → b a k0 = 0,pak 1 → b ∀i ∈ h1; ti poved’te: a) A2 mod n → A b) Jestliže ki = 1,pak A · b mod n
5
b = ak mod n
b = 60103 mod 143 k = (103)10 = (1100111)2 i ki A b
0 1 60 60
1 1 25 70
2 1 53 135
3 0 92 135
4 0 27 135
5 1 14 31
6 1 53 70
ologie chch
Identifikace v RSA Alice pošle Bobovi zprávu, jakou jistotu muže ˚ mít Bob, že je zpráva práveˇ od Alice? Šifrování RSA tuto identifikaci umožní: 1
2 3
4
Alice chce poslat zprávu. Zná Bobuv ˚ veˇrejný klíˇc fB (nB , eB ) a svuj ˚ dešifrovací klíˇc fA−1 (nA , dA ) K zašifrování podpisu P použije funkci fB fA−1 (P) Bob k dešifrování použije nejprve svuj ˚ dešifrovací klíˇc fB−1 . Dostává fB−1 fB fA−1 (P) = fA−1 (P). Poté aplikuje Alicin veˇrejný klíˇc fA fA−1 (P) = P fA−1 nezná nikdo jiný než Alice, zpráva je pravá
ologie chch
Budoucnost kryptologie
Nalezení rychlých metod faktorizace ˇ Rešení problému diskrétních logaritmu˚ Kvantové poˇcítaˇce
ologie chch
Literatura Singh S.: Kniha kódu˚ a šifer, Nakladatelství dokoˇrán a Argo, Praha 2003. ˇ tajemství, Nakladatelství XYZ, Praha Janeˇcek J.: Rozluštená 2008. Menezes A.,van Oorschot P., Vanstone S.: Handbook of applied cryptography,CRC Press,1997. Koblitz N.: A course in Number Theory and Cryptograghy, Springer, New York 1994.
ologie chch
ˇ Dekuji za pozornost
