Frekvenční analýza a substituční šifry Marek Kumpošt Laboratoř bezpečnosti a aplikované kryptografie Fakulta informatiky Masarykova univerzita Brno Frekvenční analýza a substituční šifry 21. dubna 2010 1 / 16 Obsah Q Úvod - transpoziční a substituční šifry O Kryptoanalýza Q Frekvenční analýza - postup Q Frekvenční analýza - příklad Frekvenční analýza a substituční šifry 21. dubna 2010 2/16 Rozdělení šifer podle způsobu šifrování • Transpoziční šifry ►• Písmena zprávy se uspořádají jiným způsobem - přesmyčka ►• Přeuspořádání písmen otevřeného textu ►• Problém při dešifrování -je potřeba použít stejný postup ►• Vhodnější použít jednodušší „předpis" ►• Např. zpráva navinutá na tyči konkrétního průměru ►• Např. rozdělení zprávy do dvou řádků a napojení za sebe • Substituční šifry ►• Nahrazení písmen otevřeného textu podle nějakého pravidla - A^V.D^X.H^B.I^G.K^J.M^C.O^Q.R^L.S^N.U^E, W^F.Y^P.Z^T - schůzka o půlnoci —>■ NMBETJV Q YERSQMG ►• Caesarova (posuvná) šifra - písmeno zprávy nahrazeno písmenem o tři pozice dále v abecedě (celkem 25 odlišných šifer) ►• Nemusíme nutně posouvat, lze i přeskládat abecedu (4 * 1026 možností) ► abcdefghijklmnopqrstuvwxyz ► VESLOABCDFGHIJKMNPQRTUWXYZ Frekvenční analýza a substituční šifry 21. dubna 2010 3/16 Substituční šifry - algoritmus a klíč • Algoritmus je šifrovací metoda použita k šifrování • Klíč specifikuje detaily použitého šifrování - např. posun o n písmen • Bez klíče by nemělo být možné dešifrovat zprávu • Kerckhoff (1883) - bezpečnost šifrovacího systému nesmí záviset na utajení algoritmu, ale pouze na utajení klíče • Prostor klíčů musí být značný (Caesarova šifra vs. substituční algoritmus) • Snadné použití a vysoký stupeň bezpečnosti ►• Odesílatel definuje nějaké přeuspořádání písmen abecedy ►• Útočník musí hledat toto přeuspořádání ►• Klíč musí sdílet obě komunikující strany -jednoduchost klíče —> snížení rizika nedorozumění ►• Jako klíč můžeme použít klíčové slovo nebo klíčovou frázi ► Např. klíč JULIUS CAESAR -► JULISCAER ► abcdefghijklmnopqrstuvwxyz ► JULISCAERTVWXYZBDFGHKMNOPQ Frekvenční analýza a substituční šifry 21. dubna 2010 4/16 Celkem tedy... • Díky této jednoduchosti dominovala substituční šifra v tajné komunikaci velmi dlouhou dobu • Natolik bezpečný systém, že neexistovala motivace pro jeho vylepšování • Věřilo se, že obrovské množství klíčů zajišťuje nerozlustitelnost • Nakonec nalezen způsob, jak výrazně luštění urychlit. .. ►• Unikátní kombinace lingvistiky a statistiky ►• Kryptoanalýza - dešifrování zprávy bez znalosti klíče (poprvé Arabové, 9. století) • Monoalfabetická šifra ►• Nahrazuje písmeno textu vždy stejným znakem v šifrované podobě ►- a je např. vždy šifrováno jako T ►• Četnosti písmen v otevřeném i zašifrovaném textu se zachovávají • Polyalfabetická šifra ►• Nahrazuje písmeno textu vždy různým znakem v šifrované podobě ►• a je šifrováno jako T, jindy jako S ►• V šifrovaném textu se nezachovávají četnosti písmen otevřeného textu Frekvenční analýza a substituční šifry 21. dubna 2010 5/16 Kryptoanalýza - snaha dešifr. text bez znalosti klíče • Zaměříme se na frekvenční analýzu • Poprvé Arabové, založeno na znalostech lingvistiky a statistiky • Známe-li jazyk zprávy, nalezneme odlišný otevřený text v tomtéž jazyce a spočteme výskyty jednotlivých písmen. Písmena setřídíme podle četnosti. Totéž provedeme se šifrovaným textem. Písmena šifrovaného textu nahradíme odpovídajícím způsobem podle četností písmen v otevřeném textu. • V současnosti známe rozložení písmen nejběžnějších jazyků • Angličtina - a:8,2; b:l,5; c:2,8; d:4,3; e:12,7; f:2,2; g:2,0; h:6,l; i:7,0; j:0,2; k:0,8; 1:4,0; m:2,4; n:6,7; o:7,5; p:l,9; q:0,l; r:6,0; s:6,3; t:9,l; u:2,8; v:l,0; w:2,4; x:0,2; y:2,0; z:0,l ►• Vzorek 100 365 znaků anglické abecedy (noviny a beletrie) • Problém u krátkých zpráv (From Zanzibar to Zambia and Zaire, ozone zones make zebras run zany zigzags) • Alespoň sto písmen pro naději na úspěch Frekvenční analýza a substituční šifry 21. dubna 2010 6/16 Frekvenční analýza - postup při hledání klíče • Zjištění, v jakém jazyce může být zpráva napsána • Určení četností písmen • Určení četností digramů a trigramů • Identifikace nejčastěji se vyskytujících písmen • Postupné odkrývání původního textu a určování dalších písmen • Dešifrování zprávy a zjištění použitého klíče Frekvenční analýza a substituční šifry 21. dubna 2010 7/16 Frekvenční analýza - příklad • Text je v angličtině • Zašifrován monoalfabetickou substituční šifrou • Neznáme klíč PCQVM JYPDL BYKLY SOKBX BJXWX VBXVZ CJPOE YPDKB XBJYU XJLBJ OOKCP KCPLB OLBCM KXPVX PVIYJ KLPYD BLQBO PKBOB XVOPV OVLBO LXROC ISXXJ MIKBO JCKOX PVEYK KOVLB ODJCM PVZOI CJOBY SKXUY PDDJO XLEYP DICJX LBCMK XPVXP VCPOP YDBLK YBXNO ZOOPJ OACMP LYPDL CUCML BOIXZ ROKCI FXKLX DOKXP VLBOR ODOPV KCIXP AYOPL EYPDK SXUYS XEOKC ZCRVX KLCAJ XNOXI XNCJC IUCMJ SXGOK LUOFY RCDMO LXROK IJCSL BOLBC MKXPV XPVCP OPYDB LK • 337 znaků - není to mnoho na mechanickou frekvenční analýzu • Zjistíme četnosti jednotlivých písmen šifrované zprávy Frekvenční analýza a substituční šifry 21. dubna 2010 8/16 Frekvenční analýza - příklad • Zjištění četností jednotlivých písmen šifrované zprávy 0 38 ###################################### X 34 ################################## P 31 ############################### C 27 ########################### K 26 ########################## B 25 ######################### L 25 ######################### Y 19 ################### J 18 ################## V 18 ################## D 14 ############## 1 11 ########### M 10 ########## Frekvenční analýza a substituční šifry 21. dubna 2010 9/16 Frekvenční analýza - příklad • Nejčastější znaky jsou 0 P X • Nejspíše budou odpovídat nejčetnějším písmenům anglické abecedy e t a • Nemůžeme si být jisti pořadím • Podíváme se, jaká písmena nejčastěji sousedí s 0 P X • 0, X se páruje s většinou písmen (kromě 7, resp. 8 z nich) • P se nepáruje s 15ti písmeny - pravděpodobně souhláska • 00 nalezneme dvakrát, XX ani jednou - častý výskyt ee v angl. textech • Takže pravděpodobně 0=e, X=a • Následně se snažíme odhalit písmeno h - velmi častý výskyt před e ale vzácně po něm (the, then, they) • B se před 0 vyskytuje devětkrát, takže pravděpodobně B=h • Nejčastější trigramy XPV YPD LBO - zřejmě XPV=and LB0=the Frekvenční analýza a substituční šifry 21. dubna 2010 10 / 16 Frekvenční analýza - příklad • Dešifrujeme text s dosavadními znalostmi • 0=e X=a B=h L=t P=n V=d n—d- —n-t h—t- -e-ha h-a-a dhad- —ne- -n—h ah---- a-th- ee—n —nth eth— -anda nd--- -tn— ht-he n-heh adend edthe ta-e- —aa----he---ea nd----edth e---- nd-e- —eh- —a— n---e at—n----a th---andan d-nen —ht- -ha-e -een- e---n t-n-t ----t he-a- -e--- -a-ta -e-an dthe- e-end----an —ent —n— -a----a-e—----da -t----a-ea- a----------------a-e- t-e—------e ta-e-------1 heth- —and and-n en—h t- • Vidíme následující možná slova: th- ee; -heh adend edthe; th---- andan d-nen —ht; -ha-e -een; • Proto stanovíme J=r K=s C=o M=u N=v Z=b Frekvenční analýza a substituční šifry 21. dubna 2010 11 / 16 Frekvenční analýza - příklad • Dešifrujeme text s dosavadními znalostmi • 0=e X=a B=h L=t P=n V=d J=r K=s C=o M=u N=v Z=b no-du r-n-t h-st- -esha hra-a dhadb orné- -n-sh ahr— arthr eeson sonth ethou sanda nd—r stn— ht-he nsheh adend edthe ta-eo —aar u-she rosea nd—s sedth e-rou ndbe- oreh- -sa— n—re at—n —ora thous andan donen —hts -have beenr e-oun t-n-t o-out he-ab -eso- -asta -esan dthe- e-end so-an —ent —n-s -a---- a-eso bo-da sto-r avea- avoro —our -a-es t-e— -o-ue ta-es -ro-t hetho usand andon en—h ts • Vidíme následující možná slova: no-du r-n-; ta-e; -rou ndbe-oreh-; thous andan donen —hts -have been • Proto stanovíme Q=w Y=i D=g R=l I=f Frekvenční analýza a substituční šifry 21. dubna 2010 12 / 16 Frekvenční analýza - příklad • Dešifrujeme text s dosavadními znalostmi • 0=e X=a B=h L=t P=n V=d J=r K=s C=o M=u N=v Z=b Q=w Y=i D=g R=l I=f nowdu ringt histi -esha hra-a dhadb orne- ingsh ahri- arthr eeson sonth ethou sanda ndf ir stnig htwhe nsheh adend edthe taleo f-aar uf she rosea nd-is sedth egrou ndbef orehi -sa-i nggre at-in gfora thous andan donen ights ihave beenr e-oun tingt o-out hef ab lesof -asta gesan dthel egend sofan -ient -ings -a-i- a-eso bolda sto-r aveaf avoro f-our -a-es t-e-i logue tales fro-t hetho us and andon enigh ts • Určíme zbytek klíče A= =c G=j E=k S= =m F=p H=q T= =x U=y V=z IH1BIBBWMII EH -rekvenční analýza a substituční šifry 21. dubna 2010 13 / 16 Frekvenční analýza - příklad • Dešifrujeme text • 0=e X=a B=h L=t P=n V=d J=r K=s C=o M=u N=v Z=b Q=w Y=i D=g R=l I=f A=c G=j E=k S=m F=p H=q T=x U=y V=z nowdu ringt histi mesha hraza dhadb ornek ingsh ahriy arthr eeson sonth ethou sanda ndfir stnig htwhe nsheh adend edthe taleo fmaar ufshe rosea ndkis sedth egrou ndbef orehi msayi nggre atkin gfora thous andan donen ights ihave beenr ecoun tingt oyout hefab lesof pasta gesan dthel egend sofan cient kings mayim akeso bolda stocr aveaf avoro fyour maj es tyepi logue tales fromt hetho usand andon enigh ts • a vložíme správně mezery. Frekvenční analýza a substituční šifry 21. dubna 2010 14 / 16 Frekvenční analýza - příklad • Výsledný text Now during this time Shahrazad had borne King Shahriyar three sons. On the thousand and first night, when she had ended the tale of Maaruf, she rose and kissed the ground before him, saying: "Great King, for a thousand and one nights I have been recounting to you the fables of past ages and the legends of ancient kings. May I make so bold as to crave a favor of your majesty?" Epilogue, Tales from the Thousand and One Nights • abcdefghij klmnopqrstuvwxyz • XZAVOIDBYGERSPCFHJKLMNQTUW Frekvenční analýza a substituční šifry 21. dubna 2010 15 / 16 Dotazy? Díky za pozornost a přeji hodně úspěchu při luštění! xkumpostOfi.muni.cz Frekvenční analýza a substituční šifry 21. dubna 2010 16 / 16