Úvod do klasických a moderních metod šifrování

Jaro 2009, 2. přednáška

Jiný šifrový textYEVQK GQAUN PTIOL UIGFR ODBYB LTUSD OEBFV THOLS KHLSO JNVRF CBTXW CZSEM KIOUV PGVYK YOTNP QCEFU LQYKE EEUYS GCWGO ZZNBY MGQOJ IOAQE DHXPF JXSWV REFVK TWWVR EEFMB XMKDL FSASN ZTOCY GRHII UHWJJ UHXOW LFSTH GJGTV DIBRX ARJFR ISLNI OEHBS DPTII WDVLF DHPQP QIEIO FJXZK YNFZT RIDWX UEIUD PDWST VNKJZ XDDCJ MXREX DJUCS BUVLY OEFLX SEZSY XVLWT OPPUN VRRMS QHBXZ NTSHL SKHZM EQICR FUFTT EEWVO MMECP RPSBY JTTAE UHCCD ALNVZ YKNBO EJRLM KTEAF IZLIO LUIGF ROBTY UNHMS EHXDV SEZLZ XEXIO ZNWEB ZLLSB FZJSS FDUMF QUHNH FUHRC WHWFR HXARP MKEVH HREKD XCEAO QEDBK JFTHR DYDWD VSMJJ PUNCE AGIEV RUIJK NHSDE SLRTR UWTKY PZNDF ZZEYO EEGND LGXUJ KHIE

Počet znaků: 524

Četnosti znaků: 39, 27, 25, 25, 25, 24, 24, 23, 23, 23, 22, 20, 20, 20, 19, 19, 18, 17, 17, 16, 15, 14, 14, 13, 12, 10

Kasiského test: Poloha opakovaných bigramů, trigramů, atd.

Jde nejspíš o nějakou šifru s periodickým klíčem

Vigenérova šifraPoužívá periodicky několik různých posunutí abecedy. Klíčem bývalo obvykle nějaké slovo, které udávalo délku posunutí podlenásledující tabulky.

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 z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Tak například klíč slizoun určoval posunutí18 11 8 5 14 20 13.

Otevřený text kocka leze dirou se zašifroval následovně:

kocka leze dirouslizo unsl izoun

czkjo frrp lhfih

Polyalfabetická šifra

Podobná Vigenérově šifře, místo různých posunutí ale používárůzné obecné jednoduché substituce.

Každé písmeno otevřeného textu šifruje pomocí jiné permutace.Ideální je, pokud se žádná permutace nepoužívá dvakrát.

abcdefghijklmnopqrstuvwxyz1:gkqwhrjvoisnazcubdxplfytme2:cintzuhsymjabvoelxwpkfqgrd3:ekrwxpavqbslcfitudgjmhnyzo4:dqcuimhvrelnwgofjkztysabpx

Šifrujeme: kozasood

Vigenérovu šifru popsal již v roce 1586 Blaise de Vigenére.

Slabina: periodické heslo

Šifru rozluštil až Charles Babbage (1791-1875), profesor matematiky na Cambridge University

Řešení lze algoritmizovat pomocí indexu koincidence, kterývymyslel William F. Friedman kolem roku 1920.

Index koincidence je jeden z nejvýznamnějších statistickýchtestů používaných v kryptologii.

Index koincidenceZavedl William F. Friedman v roce 1925.

Neformálně je index koincidence dvou textů S a T nad stejnou abecedou Adefinovaný jako pravděpodobnost, že se v obou textech vyskytne stejný znak na stejném místě.

Definice. Jsou-li S = s1s2…sn a T = t1t2…tn dva texty téže délky nadstejnou abecedou A, pak definujeme index koincidence těchto dvou textů jako

Kappa(S,T) = Σ i δ(si,ti) / n,

sčítáme pro i = 1,2,…,n, δ(si,ti) je Kroneckerův symbol rovný 1 pokud si=ti arovný 0 v opačném případě.

Očekávaná hodnota Kappa(S,T). Jsou-li pravděpodobnosti výskytů jednotlivýchznaků abecedy A v textu S rovné p0p1…pk a pravděpodobnosti výskytů těchtoznaků v textu T jsou rovné q0q1…qk, pak očekávaná hodnota indexu koincidence

Kappa(S,T) = Σ j pjqj ,

sčítáme pro j = 1,2,…,n.

Očekávaná hodnota indexu koincidence jazyka

Jsou-li frekvence jednotlivých písmen abecedy v nějakém jazyce L rovnép0,p1,…p25 pak očekávaná hodnota indexu koincidence dvou textů v tomto jazyce se rovná

Kappa(S,T) = Σ j pj2 ,

sčítáme pro j = 0,2,…,25.

Toto číslo nezávisí na textech S a T, ale pouze na pravděpodobnostech pj,nazývá se proto očekávaný index koincidence jazyka L.

Zde jsou hodnoty očekávaného indexu koincidence nejčastějších jazyků podleKullbacka, 1976:

angličtina 6,61%němčina 7,62%francouzština 7,78%španělština 7,75%ruština 5,29% (32 znaků v abecedě)náhodný text 1/26 = 3,85% .

Tyto hodnoty samozřejmě závisí na použitých tabulkáchfrekvencí jednotlivých písmena u různých autorů se mohoulišit.

Invariance indexu koincidence

Tvrzení. Jsou-li dva texty S a T zašifrované polyalfabetickou šifrou za použitístejného klíče K, a označíme-li takto obdržené šifrové texty C a D, pak platí

Kappa (C,D) = Kappa (S,T) .

Důkaz. Označme si symbol na i-tém místě textu S, a ti symbol na i-tém místě textu T.

Protože πi je permutace, platísi = ti právě když ci = di pro každý index i.

Odtud a z definice indexu koincidence pak vyplývá rovnost

Kappa (C,D) = Kappa (S,T).

Protože je při šifrování použit stejný klíč pro oba texty, jsou symboly si a ti zašifrovány za použití stejné permutace πi.

Na i-tém místě šifrového textu C je tedy symbol ci = πi(si) a na i-tém místě šifrového textu D je symbol di = πi(si).

Průměrné indexy koincidencePro text T délky n a r přirozené číslo označme T r text, který dostanemez T cyklickým posunutím o r míst doprava.

Definice. Průměrný index koincidence dvou textů S a T téže délky n nad stejnou abecedou A definujeme jako číslo

Chi(S,T) = Σ r Kappa(S,T r) / n,

sčítáme přes r = 0,1,…, n – 1.

Definice. Průměrný index koincidence jednoho textu T délky n definujeme jako

Phi(T) = Σ r Kappa(T,T r) / (n-1),

sčítáme přes r = 1,…, n – 1.

Použití pro nalezení délky klíčeMáme-li daný šifrový text C délky n zašifrovaný nějakou polyalfabetickou šifrou, a chceme najít pravděpodobnou délku klíče,

postupně pro každé d = 2,3,…,n-1 napíšeme šifrový text do d sloupců, texty ve sloupcích označíme C1, C2,…,Cd ,

spočítáme průměrné indexy koincidence Phi(Cj) pro j = 1,2,…,d,

a pak jejich průměr Σ j Phi(Cj) / d .

To d, pro které se tato průměrná hodnota nejvíce blíží očekávanému indexukoincidence jazyka, ve kterém byl napsán otevřený text, je nejpravděpodobnějšídélka klíče.

Obvykle to vychází tak, že tato průměrná hodnota se blíží očekávanému indexukoincidence jazyka otevřeného textu pro násobky délky klíče, zatímco pro ostatníhodnoty d se blíží hodnotě indexu náhodného jazyka, který je mnohem menší.

Šifrovací strojeNevýhodou polyalfabetické šifry je složitost klíčů a jejichpředávání.

Proto byly v první polovině 20. století hojně používané šifrovací stroje. Nejznámější byly Enigma, Hagelin.

Transpoziční šifrySpočívají v přeházení pořadí (permutaci) písmen v otevřenémtextu.

Permutace bývala definována pomocí nějakého slova – klíče.

Například pomocí klíče nezny se šifrovalo následovně:

nezny

tancovalabychjaazsetrasu

21534

aacza tvyar cajeu obatn lhss

Jednoduchá transpozice

Dvojitá transpozice.

Používaná německou armádou v průběhu první světové válkya po ní až do roku 1928.

Také ji používala československá vláda v exilu v Londýně během druhé světové války ke komunikaci s domácím odbojem.

Proto měl domácí odboj takové ztráty.

Jak dvojitou transpozici rozluštit bylo popsáno ve francouzských novinách již na počátku první světové války v roce 1914.

Řešení je velmi usnadněné, jsou-li šifrovány zprávy stejné délky.

Šifrování dvojitou transpozicí vyžaduje dvě hesla. Například nezny octopus

Jednoduchá transpozice se použije dvakrát, napřed s prvnímheslem, a takto získaný šifrový text se ještě jednou šifrujejednoduchou transpozicí určenou druhým heslem.

Přání tancovala bych ja az se trasu

tak chobotnice svému milému zašifruje za použití hesla nezny

jako aacza tvyar cajeu obatn lhss a pokračuje dále

octopus

aaczatvyarcajeuobatnlhss

2163475Dostane tak

aaosa yuhzc aaatv elcrb stjn

Vernamova šifra

Dne 13.9.1918 Gilbert Vernam požádal o americký patent na údajně zcela bezpečnou šifru.

Vernamova šifra je vlastně Vigenerovo šifrou, u které je klíč stejně dlouhý jako otevřený text, a je navíc náhodně generovaný. Jinak řečeno, velikosti posunutí jednotlivých písmen jsou náhodné a navzájem nezávislé.Formálně můžeme Vernamovu šifru definovat následovně:

Je-li p1p2…..pn otevřený text (kódovaný čísly 0,1,…,25 ), a k1k2…..kn

náhodně generovaný klíč (tvořený čísly 0,1,…,25), pak šifrový textc1c2…..cn je definován jako ci = pi+ki mod 26 pro i=1,2,…,n.

Praktická využitelnost Vernamovy šifry je značně omezená nutností mít k dispozici bezpečný kanál pro výměnu klíče téže délky jako je otevřenýtext.

Bezpečnost Vernamovy šifry Intuitivně můžeme bezpečnost Vernamovy šifry nahlédnout

následovně.

Odposlechneme-li znak ci šifrového textu, pak vzhledem ke skutečnosti,že každá z 26 možností pro ki je stejně pravděpodobná a nezávislá na předchozích hodnotách klíče k1…ki-1, jsou všechny možnosti propi=ci - ki mod 26 stejně pravděpodobné.

Stručně řečeno, ze znalosti šifrového textu nemůžeme usoudit vůbec nic o otevřeném textu.

Claude Shannon dokázal, že Vernamova šifra je dokazatelně bezpečná,tj. že při použití Vernamovy šifry je pravděpodobnost P(p), že byl vyslánotevřený text p, rovná podmíněné pravděpodobnosti P(p|c), že byl vyslánotevřený text p za podmínky, že jeho šifrová podoba je c.

Dále dokázal, že jde o jedinou dokazatelně bezpečnou šifru.

Horká linka Washington-Moskva Vernamova šifra byla použita u horké linky mezi Bílým domem a

Kremlem po kubánské krizi v roce 1961. Horká linka měla za cíl

zabránit náhodnému vzniku jaderné války.

Klíče byly distribuovány v diplomatických zavazadlech v podobě děrnýchpásek.

Podmínkou bezpečnosti Vernamovy šifry je to, že žádná část klíče nenípoužita dvakrát k šifrování dvou různých textů. Celý klíč je nutno po použití zničit.

Dvojí použití klíče totiž vede na takzvanou knižní šifru, kterou lze snadnovyřešit.

Dvojí použití klíče

Použijeme-li jeden klíč k1k2…kn k zašifrování otevřeného textu p1p2…pn, dostaneme šifrový text c1c2…cn, kde ci = pi + ki mod 26pro i=1,2,…,n.

Použijeme-li stejný klíč k1k2…kn k zašifrování jiného otevřeného textu q1q2…qn, dostaneme šifrový text d1d2…dn, kde di = qi + ki mod 26pro i=1,2,…,n.

Odečtením obou šifrových textů dostaneme ci – di = pi – qi mod 26 pro i=1,2,…,n.

Odečtením obou šifrových textů dostaneme rozdíl dvou otevřených textů (v přirozeném jazyce). To je knižní šifra kdysi používaná zejména špiony.

Řešení knižní šifryK šifrovému textu pi – qi mod 26, i=1,2,…,n postupně přičítáme ve všech možnýchpolohách nejčastější slova otevřeného jazyka, ve kterém je text napsán.

Například w1w2…w6. Pokud je slovo použito v otevřeném textu q od místai+1, pak qi+1=w1, qi+2=w2,…,qi+6=w6.

Po přičtení tak dostaneme část otevřeného textu pi+1pi+2…pi+6.

Z ní můžeme uhádnout pokračování otevřeného textu p doleva a doprava, odtudpak odpovídající část otevřeného textu q, u něhož zase můžeme uhádnout prodloužení doleva a doprava, a tak střídavě rekonstruujeme oba otevřené textyp a q.

Proto dálnopis, do kterého se vkládaly pásky s klíčem u horké linky Moskva – Washington, po skončení rozhovoru použitou pásku odsekl a skartoval.

Expanze klíčeU moderních šifer se potřeba dlouhého náhodného klíče řešení pomocíexpanze klíče.

Z krátkého tajného klíče se generuje dlouhý klíč potřebné délky pomocí nějakého generátoru pseudonáhodných čísel. Původní tajný klíč sloužík počátečnímu nastavení generátoru.

David Kahn, The Codebreakers, Macmillan, New York, 1967, podrobné historické pojednání,

Knihy o historii kryptologie

Simon Singh, The Code Book, Fourth Estate Limited, 1999, česky Kniha kódů a šifer, nakladatelství Dokořán a Argo, 2003, populární úvod do šifrování,

Literatura ke klasické kryptologii• F.L.Bauer, Decrypted Secrets, Methods and Maxims of Cryptology,

Springer Verlag 1997, 2003,

mnohem odbornější kniha než předchozí.

Mnoho dalších odkazů je uvedeno v Bauerově knize.

The Kama Sutra, translated by Sir Richard Burton, 1883

Chapter Three, On the arts and sciences to be studied

• Singing• Dancing• The art of understanding writing in cypher, and the writing of words in a peculiar way • Art of applying perfumed ointments to the body, and of dressing the hair with unguents and perfumes and braiding it • Solution of riddles, enigmas, covert speeches, verbal puzzles and enigmatical questions

O významu kryptologie se lze dočíst také v knize

Klasická kryptoanalýzaJednoduchá záměna

Pomocí frekvenční analýzy jednotlivých znaků (monogramů), bigramů, trigramů, atd.

Nejstarší dochovaný text o této metodě:al-Kindí, Rukopis o dešifrování kryptografických zpráv, 9. století, objevené roku 1987 v Sülajmanově osmanském archivu v Istanbulu

Plné jméno autora:Abú Jusúf Jaqúb ibn Ishád ibn as-Sabbáh ibn `omrán ibn Ismail al-Kindí

Srovnání frekvencí jednotlivých písmen v angličtině a němčině v procentech

a b c d e f g h i j k l m8,04 1,54 3,06 3,99 12,51 2,30 1,96 5,49 7,26 0,16 0,67 4,14 2,536,47 1,93 2,68 4,83 17,48 1,65 3,06 4,23 7,73 0,27 1,46 3,49 2,58

n o p q r s t u v w x y z 7,09 7,60 2,00 0,11 6,12 6,54 9,25 2,71 0,99 1,92 0,19 1,73 0,09 9,84 2,98 0,96 0,02 7,54 6,83 6,13 4,17 0,94 1,48 0,04 0,08 1,14

Frekvenční analýza Frekvence jednotlivých znaků závisí na typu textu, jiná je u novinových

článků, jiná u románů nebo u odborných textů v závislosti na oboru.

Pořadí písmen od nejčastějšího k nejméně častému v angličtině:

atoanirshdlufcmpywgbvkxzjq L.Sacco, 1951etaonirshdlucmpfywgbvjkqxz D.Kahn, 1967etaonrishdlfcmugpywbvkxjqz A.G. Konheim, 1981

v němčině:enirsahtudlcgmwfbozkpjvqxy F. Kasiski, 1863enirstudahgolbmfczwkvpjqxy A. Figl, 1926enirsatdhulgocmbfwkzpvjyxq F.L. Bauer, 1993

ve francouzštině:enirsahtudlcgmwfbozkpjvqxy F. Kasiski, 1863eaistnrulodmpcvqgbfjhzxykw H.F. Gaines, 1939etainroshdlcfumgpwbyvkqxjz Ch. Eyraud, 1953

Frekvence bigramůNejčastější bigramy v angličtině podle A. Sinkova:

th he an in er re on es ti at st en or nd270 257 152 194 179 160 154 115 108 127 103 129 108 95

to nt ed is ar95 93 111 93 96

Čísla znamenají průměrný počet výskytů v textech o 10 000 znacích

Nejčastější bigramy v němčině takové, že obrácené bigramy se téměř nevyskytují:

th he ea nd nt ha ou ng hi eo ft sc rs

Následující dvojice bigramů mají prakticky stejnou frekvenci v němčině:

ar,re es,se an,na ti,it on,no in,ni en,ne at,tate,et or,ro to,ot ar,ra st,ts is,si ed,de of,fa

Frekvence trigramůNejčastější trigramy v angličtině jsou

the ing and ion tio ent ere her ate ver ter tha ati for hat ers his res ill are

průměrná délka slov

angličtina 4,5francouzština 4,4němčina 5,9ruština 6,3

frekvence samohlásek

40% 45% 39% 45%

frekvence hlásek lnrst

33%34%39%

nejčastější slova

angličina: the of and to a in that it is I for as němčina: die der und den am in zu ist daß esfrancouzština: de il le et que je la ne on les en ce

Řešení Vigenérovy šifryNezávisle Friedrich W. Kasiski a Charles Babbage v druhé polovině 19. stol.

Jejich řešení je založené na následujícím pozorování:

Vyskytuje-li se nějaký bigram xy v otevřeném textu dvakrát a vzdálenost mezioběma výskyty je násobkem délky klíče, pak je v obou případech zašifrován stejným bigramem cd.

V obou případech jsou totiž posunutí definována stejným bigramem kl klíče.

klíčotevřený textšifrový text

Nejdříve tedy odhadneme délku klíče tak, že v šifrovém textu najdeme všechnybigramy, které se vyskytují aspoň dvakrát a spočteme jejich vzdálenosti.

Poté najdeme číslo, které je nejčastěji dělitelem těchto vzdáleností. To je pravděpodobnou délkou klíče.

Opakovaný bigram v šifrovém textu může vzniknout i náhodně, ne všechny vzdálenosti opakovaných bigramů musí být násobkem délky klíče.

kl . . . . klxy . . . . xypq . . . . pq

Odhad velikosti posunutíMáme-li odhad délky klíče, můžeme pak odhadnout velikost jednotlivých posunutínásledovně.

Šifrový text pak napíšeme do tolika sloupců, kolik je odhadovaná délka klíče, a spočítáme frekvenci jednotlivých znaků v každém sloupci zvlášť.

Poté pro každý sloupec najdeme takové posunutí abecedy, které nejlépe odpovídáfrekvenci jednotlivých písmen v (přirozeném) jazyce otevřeného textu.

Pak už zbývá pouze dešifrovat text pomocí odhadnutých velikostí posunutí.

Řešení Vigenérovy šifry lze jednoduše algoritmizovat pomocí pojmu indexkoincidence.

Řešení transpozičních šiferJednoduchá transpozice. Máme-li k dispozici pouze jeden šifrový text dané délky, nezbývá než jej přehazovat za použití častých bigramů tak, abychom dostalismysluplný text.

Máme-li k dispozici více textů téže délky zašifrované stejnou permutací, napíšeme si je pod sebe, rozstříháme do sloupců a přehazujeme je opět tak, abychom ve všech řádcích současně dostali smysluplné texty. To je obvykle mnohem snazšínež v případě pouze jednoho textu.

V případě úplné tabulky můžeme její rozměr najít tak, že vyzkoušíme všechny možné tabulky, které lze celé vyplnit šifrovým textem dané délky.

Tabulka, pro kterou se tyto poměry nejvíce blíží poměru samohlásek a souhlásekv přirozeném jazyce otevřeného textu, je ta nejpravděpodobnější. Text si potomrozstříháme do sloupců a pokračujeme stejně jako u více textů téže délky.

Pro každou možnost spočítáme poměr samohlásek a souhlásek v jednotlivých řádcích.

Dvojitá transpozice Při více textech téže délky postupujeme na počátku stejně jako u

jednoduché transpozice.

Pokud uspějeme, je třeba najít ještě obě hesla, abychom mohli luštit i zprávyjiných délek.

Identifikace šifer

Jednoduchá záměna. Rozložení frekvencí písmen je stejné jako u přirozenéhojazyka.

Transpoziční šifry. Frekvence jednotlivých písmen je stejná jako u otevřeného textu v daném jazyce.

Polyalfabetická šifra s periodickým klíčem. Pomocí indexu koincidence.