Ako rozlúštiť zašifrovanú správu

Autor: Martin Marušic | 24.2.2009 o 11:11 | Karma článku: 11,89 | Prečítané:  9661x

Určite ste sa už stretli, minimálne v literatúre alebo filme, s nejakým jednoducho zašifrovaným textom, ktorý mal byť určený iba osobe, ktorá vedela ako ho rozšifrovať. Ako ale postupovať, pokiaľ vás obsah zaujíma, ale kľúč neviete, to sa vám, aspoň pri použití najjednoduchších šifrovacích postupov, posnaží ukázať tento článok. Samozrejme za predpokladu, že sa nedržíte hesla, že gentlemani si navzájom nečítajú listy.

Výmena polôh písmen v texte

Najjednoduchšie a najrýchlejšie manuálne kódovanie je v texte (v ďalšom budú pod textom myslené nezašifrované vety, ktoré chcel odosielateľ príjemcovi zdeliť) vymeniť podľa nejakého postupu poradie písmen. Toto spomína už Herodotos a využilo sa to pri grécko-perzských vojnách. Proste dostanete do rúk správu (v ďalšom bude pod správou myslený už zašifrovaný text) typu:

PYLPFUMLAIEKAOLOYAMCRRNSOKSMJIZAULTOUIUMSLJAILSSZEKPETLOATN

Na jej rozlúštenie stačí sa trochu pohrať. Vyskúšať, napríklad či text nie je napísaný odzadu, či nie sú vymenené vždy dve a dve písmená (To by potom začínalo takto: YPPLUF...) alebo či sa nečíta iba isté písmeno v poradí. Ono tých možností transpozície (výmeny polohy písmen) nie je zase až tak veľa, navyše veľmi nám pomáha fakt, že je veľa dvojíc a trojíc písmen, ktoré sa za sebou v žiadnom slove nevyskytujú, čo nám hneď na začiatku ukáže, že uvažovaná šifra (v ďalšom sa pod šifrou bude rozumieť spôsob, postup, akým sa kódovalo) je nesprávna a okamžite od nej upustiť. Efektívne je skúsiť napísať text na štvorčekový papier pod seba a po istom počte písmen, začať nový stĺpec, pričom očakávať správu v riadkoch. Po chvíli ľahko prídete na možnosť:

P E R Z S K
Y K R A L P
L A N U J E
P O S L A T
F L O T I L
U O K O L O
M Y S U S A
L A M I S T
A M J U Z N
I C I M E  

Čiže vidno, že šifrovateľ správu vyrobil tak, že z textu zobral každé šieste písmeno a potom sa vrátil na začiatok k druhému v poradí a pokračoval až kým správa neobsahovala všetky písmená. Na druhej strane šifra založená na transpozícii nie je veľmi silná (pod silou šifry je myslené množstvo námahy potrebnej na jej objavenie) a viete si zrejme predstaviť, že sa dá v pomerne krátkej dobe prelomiť (pod prelomením je myslené rozkódovanie správy na pôvodný text).

Cézarová šifra

Druhou možnosťou je zašifrovať text tak, že zameníte jedno písmeno iným. Tento spôsob, substitúciu, prvýkrát opísal Július Cézar v svojej knihe Zápisky o vojne v Galii. Poslal list napísaný síce latinsky, ale s použitím gréckych písmen. V dnešnej dobe by to bolo mimoriadne naivné, stačilo by ten text prepísať napr. do Wordu a zmeniť typ písma, nehovoriac o tom, že veľa ľudí grécke písmená pozná. Aj v jeho časoch bola sila tejto šifry založená hlavne na negramotnosti obyvateľstva a nie na šikovnosti nápadu, hoci originalita sa mu uprieť nedá.

Iný, silnejší spôsob opísal Suetonius 150 rokov po jeho smrti v diele De vita Caesarium (O živote cisárov). Podľa neho Cézar kódoval správy tak, že posúval písmená o tri miesta v abecede. Využíval teda dve abecedy, abecedu textu nahradil abecedou správy

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 Z - pôvodná abeceda
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C - šifrovacia abeceda

Keď by teda chcel oznámiť vetu:

Tú poslednú dedinu nedobyjem, lebo maju Obelixa.

tak najskôr by napisal pôvodný text a pod neho prepísal písmenko po písmenku podľa tabuľky a takto získanú správu poslal:

T U P O S L E D N U D E D I N U N E D O B Y J E M L E B O M A J U O B E L I X A pôvodný text
W X S R V O H G Q X G H G L Q X Q H G R E B M H P O H E R P D M X R E H O L A D správa

Iste je jasné, že pokiaľ by v správe boli medzery, tak nám to po zachytení správy iba pomôže. Niektoré krátke slová proste skusmo odhadneme a tým prídeme šifre na kobylku. Taktiež sa dá tento systém upraviť na slovenskú abecedu s mäkčeňmi, háčikmi, vokáňmi a prehlasovaným a, ostanem ale naďalej pri abecede s 26 písmenami, ktoré sú na každej klávesnici.

Zdokonalenie

Takáto šifra sa ešte dá pomerne jednoducho prelomiť odhadnutím, lebo pri 26 písmenách máme 25 rôzne posunutých šifrovacích abeced (jedna je totožná s pôvodnou) a nedalo by nám veľa námahy preskúmať všetky. Zaujímavé to začína byť, keď sa zvolí šifrovacia abeceda náhodne. V tom prípade by počet všetkých rôznych abeced bolo číslo s 27 ciframi. Keďže je trochu náročné zapamätať si poradie 26 písmen, praktickou možnosťou je určiť si nejaké heslo. Toto heslo sa potom napíše na začiatok (alebo na koniec) a za heslom sa pokračuje v abecednom poradí s prihliadnutím na to, že každé písmeno môže byť v šifrovacej abecede iba raz. Ak by sa za heslo zvolila napríklad veta: Pretiahnem Kleopatru tak by abeceda mohla byť niektorý z nasledujúcich variantov:

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 Z - pôvodná abeceda
P R E T I A H N M K L O U B C D F G J Q S V W X Y Z - šifrovacia abeceda
Z Y X W V S Q J G F D C B U O L K M N H A I T E R P - šifrovacia abeceda

Na prvý pohľad sa zdá, že je to neprelomiteľná šifra, nie je totiž v nikoho silách prekontrolovať všetky možné abecedy a uhádnuť heslo podľa vzoru nbusr123 je práca s mizivou vyhliadkou na úspech. Hoci je pravda, že v siedmom storočí sa arabskému polyhistorovi Al-Khalilovi podarilo rozlúštiť správy určené byzantskému cisárovi, lebo predpokladal, že začínajú slovami V mene Božom a ono tomu skutočne tak bolo. Zrejme kvôli tomu sa silnejší spôsob šifrovania objavil až v 16. storočí, dovtedy sa odosielatelia snažili iba upraviť Cézarovú šifru o nejaké prídavné prvky, základný princíp substitúcie ale ostal.

Prelomenie Cézarovej šifry

Ako rozlúštiť takúto šifru prvýkrát opísal v deviatom storočí arabský filozof Al-Kindi. Pravdepodobne sa opieral o prácu iných arabských učencov, ktorí skúmali arabský jazyk. Slabinu Cézarovej šifry objavil nie v systéme kódovania ale v použitom jazyku. Početnosť, s akou sa vyskytujú jednotlivé písmená v ľubovoľnom texte, nie je rovnaká. Niektoré sa používajú častejšie, niektoré takmer vôbec a to platí nielen pre arabčinu, ale aj pre angličtinu, nemčinu, slovenčinu a prakticky všetky jazyky. Jeho myšlienkou bolo, v zakódovanej správe zistiť počet jednotlivých písmen a toto porovnať so štandardným výskytom jednotlivých písmen v jazyku. Dá sa to potom použiť aj v prípadoch, keď písmená nie sú nahradzované inými písmenami ale hociakými znakmi. Pokiaľ nájdeme v trojriadkovej správe štyroch snehuliačikov, môžme si byť istí, že snehuliak nie je znak pre písmeno Q. Keď budeme vedieť, ktoré znaky sa vyskytujú najčastejšie, pokúsime sa ich spáriť s najčastejšími znakmi porovnávacieho štandardu, postupne skúšať rôzne kombinácie, až sa nám text objaví. Ostáva už iba jediné - stanoviť ako často sa v písanom prejave objavujú jednotlivé písmená. To ukazuje nasledujúca tabuľka, kde je pod každým písmenom percentuálne vyjadrené jeho zastúpenie v bežnom texte.

Jazyk 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 Z zdroj  
slovenčina 11,4 2,0 3,5 3,6 8,1 0,1 0,2 2,4 7,4 2,0 4,0 4,9 3,2 5,5 9,8 3,1 0 4,3 5,3 5,0 3,4 4,7 0 0 2,5 3,5 1
angličtina 8,2 1,5 2,8 4,3 12,7 2,2 2,0 6,1 7,0 0,2 0,8 4,0 2,4 6,7 7,5 1,9 0,1 6,0 6,3 9,1 2,8 1,0 2,4 0,2 0,2 0,1 2
nemčina 6,5 1,9 3,1 5,1 17,4 1,7 3,0 4,8 7,6 0,3 1,2 3,4 2,5 9,8 2,5 0,8 0,1 7,0 7,3 6,2 4,4 0,7 1,9 0,1 0,1 1,1 3

1 - vlastný výskum na základe troch náhodne zvolených textov po 500 slov
2 - Beker, Piper: Cipher Systems: The Proctection of Communication, Northwood 1982, vyhodnotené z textov s celkovým počtom 100 000 slov
3 - Beutelspacher: Kryptologie, Braunschweig 1993, neznámy postup

Návod, ako takú správu dešifrovať nájdete tu.

Frekvenčná analýza

Otázkou ostáva do akej miery je táto početnostná analýza spoľahlivá. Zrejme by sme asi nerozkódovali vetu Strč prst skrz krk, ťažko si však predstaviť, že by ju niekto niekomu šifrovane posielal. Pokiaľ je správa príliš krátka, tak si veľmi nepomôžeme, predpokladaný výskyt písmen sa bude líšiť od skutočného. Na druhej strane, keď nazhromaždíme väčšie množstvo krátkych správ, budeme mať dosť materiálu na analýzu. Frekvenčná analýza je veľmi silnou pomôckou, nemožnu ju ale zase brať doslova a očakávať výsledky na stotiny percenta zhodné so štandartnou početnosťou písmen.

Ďalším faktorom by mohol by vplyv autora textu na výskyt jednotlivých písmen. Možno niekomu niečo hovorí francúzsky spisovateľ Georges Perec. Tento napísal tristostranový román La disparition, v ktorom sa nenachádza jediné písmeno E a román Les revenentes, v ktorom naopak niet inej samohlásky okrem E. Je to extrémny prípad, keď však niekto chce poslať šifrovanú správu zvyčajne nemá toľko času, aby sa hral so štylistikou a cielene preferoval nejaké písmeno. Navyše pokiaľ si niekto vyberie takúto šifru, určite predpokladá, že je bezpečná. Ak by mal pochybnosti, našiel by si iný spôsob šifrovania.

Zaujímavé je, že hoci každý človek má vlastný svojský spôsob vyjadrovania, pri dešifrácii to nehrá až takú veľkú rolu vzhľadom na to, že si uvedomujeme, že nejaká neistota tam je vždy, takže odchýlky od toho, čo považujeme za normál, do značnej miery tolerujeme. Prekvapujúce výsledky dostaneme, keď začneme skúmať text na úrovni slov. Analógiu Al-Kindiho frekvenčnej analýzy použili americkí vedci pri identifikácii autorstva tzv. Listov Federalistov, čo bol súbor 85 článkov, ktoré písali tvorcovia americkej ústavy, kde vysvetlovali jej filozofiu. Z historických zdrojov sa vedelo, že 51 z nich napísal Alexander Hamilton (prvý minister financií USA), 14 James Madison (štvrtý prezident USA) a 5 John Jay (prvý predseda najvyššieho súdu USA). Ostalo 15 článkov, ktoré nemali určeného autora. Postupne preskúmali 30 bežných slov a zistili, že každý autor má svojský odtlačok prstov v svojom texte. Napríklad Hamilton použil slovo the priemerne 91krát v tisíc slovách, Madison 94krát, ale Jay len 67krát. To je tak výrazný rozdiel, že podľa neho Jayov text od tých dvoch odlíšime iba s malou pravdepodobnosťou omylu. Keď takúto analýzu urobili na tridsiatich slovách nadobudli presvedčenie, že sporné listy písal Madison.

Úpravy Cézarovej šifry

Cézarovou šifrou sa však šifrovalo ešte aj v sedemnástom storočí, hoci bolo skupine špecialistov známe, že keď niekto list zachytí, tak ho s najväčšou pravdepodobnosťou rozlúšti. Občas sa odosielateľ snažil zmiasť skombinovaním substitúcie s transpozíciou, niekedy vynechal zámerne nejaké písmená ale zase tak, aby po dešifrácii príjemcom ešte text bol pochopiteľný. Toto by ale malo iba taký vplyv, že by sme to dešifrovali trochu dlhšie, celkový postup to nemenilo.

Inou možnosťou bolo vymyslieť špeciálne znaky pre nejaké slová. Tu by sme síce spozorneli, ale trik tiež prekukli. Pokiaľ v správe nájdeme 45 rozličných znakov, tak nám je jasné, že tam je niečo navyše. A to navyše môžu byť znaky pre nejaké slová. A keď už si dal niekto námahu vymyslieť znak pre slovo, určite to nebude také, čo použije raz za päť rokov. Potom už len stačí zistiť, že napr. v slovenčine je najrozšírenejšie slovo a (v milióne slov priemerne 33 133 krát, podobne je najrozšírenejšie prakticky vo všetkých jazykoch), potom byť a potom už len zámená spojky a predložky - v, na, sa, ten, on, že, z, ako. V druhej desiatke by sme našli sloveso mať, najbližšie podstatné meno človek je na 48. mieste.

Šifra Márie Stuartovej

A skutočne tejto úvahe zodpovedala aj tajná abeceda anglických katolíkov, ktorí sa s pomocou Márie Stuartovej snažili zvrhnúť Alžbetu I. v šesťnástom storočí. Okrem 23 symbolov pre písmená (nepoužívali j, v a w) mala štyri znaky, ktoré neznamenali absolútne nič a boli len na zmätenie, jeden znak označujúci zdvojenie predchádzajúceho písmena a špeciálne znaky pre slová and (a), for (pre), with (s),that (že), if (keď), but (ale), where (kde), ďalších 21 spojok, zámen a predložiek, štyri slovesá: send (poslať), receave (dostať) , lre (čítať), pray (modliť sa) a jedno podstatné meno - bearer (posol). Napriek tomu celú ich komunikáciu zachytil Sir Francis Walsingham, minister pre bezpečnosť, jeho ľudia šifru prelomili a Máriu to stálo krk.

Pritom veľa námahy by sme s tým určite nemali. Tie slová sa určite používali tak zriedka, že znaky, ktoré ich predstavovali, by sme hneď nechali bokom, že to nie sú písmená. Trochu zmätku by nám priniesli len tie bezvýznamové znaky a zdvojenie. Tu by sme si ale zase uvedomili, že pokiaľ máme abecedu, tá má obmedzený počet písmen a pokiaľ má niečo podobnú početnosť ako písmená tak to zjavne musí byť navyše. Poradili by sme si pozorným preskúmaním, aké znaky sú za nimi a aké znaky pred nimi. Aj v slovenčine by sme došli na to, že ak nájdeme skupinu dhrp, tak sme na zlej stope a naopak skupinu písmen pod, pre, za tvoriace predpony by sme aj v zopár málo vetách očakávali niekoľkokrát zopakované. Rovnako tak v angličtine sa dá určiť poradie najčastejších dvoch písmen, ktoré idú za sebou (prvé sú: th er on an re he in ed nd ha at en), najčastejších troch písmen (the and tha ent ion tio for nde has), najčastejších zdvojených hlások (ss ee tt ff ll mm oo). Postupne by sme šifru prelomili, netvrdím, že za päť minút, ale pokiaľ by sme vedeli o aký typ šifry ide, tak viac ako týždeň by to žiadnemu čitateľovi tohoto článku netrvalo.

Cardanova mriežková šifra

Iný typ šifrovania vymyslel v šesťnástom storočí matematik Girolamo Cardano. Dnes by sme ju realizovali asi tak, že by sme v hárku papiera vystrihli niekoľko okienok pre písmená, pod tento hárok by sme dali čistý papier a do vystrihnutých dier vpísali po písmenkách správu. Potom by sme vrchný hárok dali preč a na spodný by sme podľa ľubovôle dopísali znaky. Príjemca by ju dekódoval tak, že by priložil rovnakú šablónu s otvormi, kde by sa mu zjavila tajná správa. Takúto šifru by sme zrejme bez tej šablóny neprelomili. Mohlo by sa zdať, že taká správa by musela byť napísaná veľmi pozorne podľa mriežky, aby sa písmená po riadkoch neposúvali, nič by ale odosielateľovi nebránilo napísať správu na štvorčekový papier a potom ju prepísať. Prijímateľ by ju potom prepísal zase na štvorčekový papier a priložil šablónu. Frekvenčná analýza by nám zrejme dala veľmi zvláštny výsledok, ktorý by nás viedol k tomu, že to nie je Cézarová šifra, ale niečo iné, tu by sme ale zrejme bez výpočtovej techniky skončili.

Na záver spomeniem, že prvý plne automatizovaný šifrovací stroj vymyslel kráľ Svätopluk, čo je síce somarina, ale je to jedno, lebo až sem to aj tak nikto nedočíta...


 

Použité zdroje

Singh, S: Geheime botschaften, München, 2006
Švihran, L: Naj, naj, naj, Bratislava, 1988
Devlin, K: Jazyk matematiky, 2003, Praha
Cryptoanalysis hints
Lúštenie šifry pomocou frekvenčnej analýzy
História utajovaného oboru
Stručná história šifrovania

 

Páčil sa Vám tento článok? Pridajte si blogera medzi obľúbených a my Vám pošleme email keď napíše ďalší článok
Pridaj k obľúbeným

Hlavné správy

DOMOV

Kompromitujúce nahrávky už znervóznili viacerých

Niektoré nahrávky nie sú dodnes objasnené.

DOMOV

Kľúčová postava Gorily reportérom SME: Nemôžete sa pýtať

Malchárek je v akciovke so Siekelom.


Už ste čítali?