Článok v pdf

Tento diel seriálu začneme dvoma jednoduchými spôsobmi kódovania.

Mriežka

Kódovanie pomocou mriežky (tento kód nájdete aj pod názvom Fleissnerova otočná mriežka) spočíva v zápise jednotlivých písmen správy istým vopred dohodnutým spôsobom do tabuľky. Na kódovanie aj dekódovanie sa používa tabuľka s niekoľkým vystrihnutými políčkami – odtiaľ vznikol aj jej názov. Ako príklad si uvedieme mriežku 4×4. Nakreslite si na papieri dve štvorcové tabuľky 4×4 políčka s rovnakými rozmermi. Jednu z nich si vystrihnite a vystrihnite v nej tie políčka, ktoré sú znázornené čiernou farbou:

Túto vystrihnutú tabuľku budeme ďalej nazývať mriežka. Kódovať budeme správu V PONDELOK O PIATEJ. Do tabuľky budeme text vpisovať bez medzier, aj keď to nie je podmienkou – môžeme použiť aj medzery a v tabuľke bude potom niekoľko prázdnych políčok.

V prvom kroku položíme vystrihnutú mriežku na tabuľku tak, ako je na obrázku. Do políčok, ktoré sú vystrihnuté, zapíšeme po riadkoch prvé štyri písmená z nášho textu. Dostaneme tak tabuľku

Teraz mriežku otočíme o 90° v smere otáčania hodinových ručičiek a zapíšeme ďalšie štyri písmená postupne po jednotlivých riadkoch do voľných políčok. Potom tento postup ešte dvakrát zopakujeme – mriežku otočíme o 90° a zapíšeme písmená do voľných políčok. Nakoniec dostaneme takúto tabuľku (farebne sú odlíšené písmená vpisované v jednotlivých krokoch – svetlozelenou je prvý krok, oranžovou druhý, tmavozelenou tretí a modrou štvrtý):

Teraz už len správu prepíšeme po riadkoch do jedného riadka:

VDAEKTPOOPLNEOJI

Túto správu môžeme zaslať príjemcovi ľubovoľným spôsobom. Aby ju však vedel aj dekódovať, musí mať presne tú istú mriežku, ako máme my. To sa dá vyriešiť buď vzájomnou dohodou vopred alebo zaslaním v inej zásielke. Dekódovanie potom prebieha rovnakým spôsobom, ako sme správu kódovali – príjemca si nastaví mriežku na text a po riadkoch si prečíta prvé štyri písmená správy. Potom mriežku otočí a prečíta ďalšie štyri písmená atď. Ak by sme chceli zaslať dlhšiu správu, máme dve možnosti. Buď použijeme väčšiu mriežku, alebo text rozdelíme na niekoľko blokov po 16 písmen a tie postupne zakódujeme tou istou mriežkou.

Ak by ste si skúšali vyrábať mriežky náhodným výberom štyroch políčok, rýchlo by ste zistili, že nie všetky by boli použiteľné, pretože by sa vám stalo, že na jedno miesto by ste mali zapísať dve písmená. Preto treba vyberať políčka v mriežke postupne. Najprv si vystrihneme jedno políčko ľubovoľne (je vyznačené čiernou farbou). Potom si označíme tie políčka, do ktorých budeme vpisovať písmená po otočení mriežkou (sivá farba):

Potom si vystrihneme ľubovoľné zo zvyšných políčok a opäť si vyznačíme, ktoré políčka nemôžeme vystrihnúť. Dostaneme tak takúto mriežku, kde sú tmavou farbou vyznačené vystrihnuté políčka a jej svetlejším odtieňom sú zafarbené tie políčka, ktoré sú pokryté daným políčkom počas otáčania.

Pri práci s mriežkou s nepárnymi rozmermi treba dávať pozor na to, že stredné políčko ostane nevyužité, pretože to by sa pri otáčaní stále otočilo na seba (pri odosielaní správy tam môžete vložiť ľubovoľné písmeno).

Z hľadiska bezpečnosti je vhodné voliť väčšie mriežky, v ktorých nemusíte ani využiť všetky políčka – do tých nevyužitých môžete dať ľubovoľné písmená na zmätenie nepriateľa. Ak sa však dostane k vašej mriežke, nebude mať s dekódovaním žiaden problém.

Inou možnosťou je využívanie viacerých mriežok s rôznymi rozmermi – na prvých 16 písmen použijete jednu mriežku, na ďalších 36 môžete použiť mriežku a podobne.

Čiarový kód

Častokrát závisí úspešnosť dekódovania na správnom pohľade na kód. Dokážete dekódovať nasledujúci čiarový kód aj vy?

Ak chcete na riešenie prísť sami, zakryte si nasledujúce riadky, aby ste nevideli správne riešenie.

Princíp tohto čiarového kódu je veľmi jednoduchý – ozaj sa stačí na uvedený obrázok pozrieť z vhodného uhla. Ak sa naň pozriete z ľavej strany pod veľmi tupým uhlom, teda oči budú takmer na úrovni papiera, zobrazí sa vám zakódovaný text. Tak sa skúste pozrieť na obrázok ešte raz a zistíte, že Tento text sa už teraz číta veľmi ľahko, však?

Ak sa vám tento čiarový kód zapáčil, popíšeme aj postup, ako si ho môžete veľmi ľahko vyrobiť aj sami. V nejakom textovom editore si napíšete správu. Z textu si vyrobíte obrázok napr. vo formáte bmp, jpg alebo gif (zosnímete obrazovku a získaný obrázok upravíte v grafickom editore). No a teraz už len stačí obrázok dostatočne roztiahnuť, aby nebolo vidno jednotlivé písmená a prípadne otočiť.

Playfairova šifra

Táto šifra má už vyše 150 rokov – v roku 1854 ju navrhol Charles Wheatstone. Svoje pomenovanie však získala po škótskom barónovi Lyonovi Playfairovi, ktorý ju propagoval. Aj vďaka nemu sa dostala do služieb armády, pričom sa čiastočne používala ešte aj počas 2. svetovej vojny.

Princíp šifry spočíva v nahradzovaní dvojíc písmen inými dvoma písmenami. Z hľadiska typu ide teda o substitučnú šifru na dvojiciach písmen. Z hľadiska dekódovania je však oveľa náročnejšia, pretože dvojíc písmen je mnohonásobne viac ako jednotlivých písmen – ak máme 26 písmen, tak dvojíc písmen je až 676. Preto na jej úspešné dešifrovanie potrebujeme oveľa viac textu a nemôžeme použiť ani jednoduchú frekvenčnú analýzu písmen v abecede. Z hľadiska uplatnenia v armáde spočívali jej výhody v ľahkom vyškolení ľudí, rýchlosti a nízkych nákladoch na jej použitie.

Ukážme si, ako sa pomocou tejto šifry šifrovalo. Základným textom bude Šifrujeme Playfairovou šifrou. Tento text rozdelíme na skupiny po dvoch písmenách a pre jednoduchosť ho prevedieme na text bez diakritiky, medzier a rozlišovania malých a veľkých písmen:

SI FR UJ EM EP LA YF AI RO VO US IF RO UX

Na koniec textu sme pridali X, pretože text mal nepárnu dĺžku. Toto písmeno na konci môže byť ľubovoľné, ktoré kontextovo nesedí so zvyšným textom, alebo to môže byť vopred dohodnuté písmeno. V prípade, že sa v texte objaví dvojica rovnakých písmen za sebou, vložíme medzi ne vopred dohodnuté písmeno – napr. X, Q alebo W.

Ďalším krokom je príprava šifrovacej tabuľky. Tá bude mať tvar Polybiovho štvorca, o ktorom sme písali v minulom čísle časopisu – ide o tabuľku, do ktorej najprv napíšeme po riadkoch kľúčové slovo a potom dopíšeme ostatné písmená, pričom jedno písmeno musíme vynechať, aby ich bolo 25 – v našom prípade zlúčime písmená Q a W – vynecháme písmeno W (ak by sa v kódovanom texte vyskytlo W, nahradíme ho písmenom Q a z kontextu bude jasné, o ktoré písmeno ide). Zvoľme si za kľúčové slovo slovo MLADY VEDEC, teda po vynechaní opakujúcich sa písmen MLADYVEC. Dostaneme tak tabuľku

Teraz už môžeme šifrovať. Keďže berieme do úvahy dvojice písmen, môžu nastať tri prípady:

• obe písmená sú v rovnakom riadku,
• obe písmená sú v rovnakom stĺpci,
• písmená sú v rôznych riadkoch aj rôznych stĺpcoch.

Ak sú obe písmená v rovnakom riadku, každé z nich nahradíme písmenom, ktoré je v riadku od neho napravo. Ak ide o posledné písmeno v riadku, nahradíme ho prvým písmenom v danom riadku.

Ak sú obe písmená v rovnakom stĺpci, každé z nich nahradíme písmenom, ktoré je v stĺpci pod ním. Ak ide o posledné písmeno v stĺpci, nahradíme ho prvým písmenom v tomto stĺpci.

Ak sú písmená v rôznych riadkoch aj stĺpcoch, každé z nich nahradíme písmenom, ktoré sa nachádza v priesečníku jeho riadka a stĺpca, v ktorom sa nachádza druhé písmeno. Ako pomôcka nám môže slúžiť obdĺžnik, ktorý má strany rovnobežné so stranami tabuľky a ktorého protiľahlé vrcholy tvoria šifrovanú dvojicu písmen. Zašifrovanú dvojicu budú tvoriť zvyšné dva vrcholy obdĺžnika, pričom ale treba dávať pozor na ich poradie.

Dvojicu SI zašifrujeme ako UG, pretože písmená ležia v rôznych riadkoch aj stĺpcoch:

Ďalšiu dvojicu FR zašifrujeme ako KZ, pretože písmena F, R ležia v rovnakom stĺpci:

Dvojicu RO zašifrujeme ako NP, pretože písmená R, O ležia v tom istom riadku:

Nakoniec dostaneme takýto zašifrovaný text:

UG KZ XI VL CO AD FK CP NP EN XT KC NP XZ

Z tejto správy ešte pred prenosom odstránime medzery a posielame ju ako súvislý text. V pôvodnej verzii sa písmená zoskupovali po piatich na oklamanie nepriateľa.

Dešifrovanie bude prebiehať analogicky podľa troch pravidiel:

Ak sú obe písmená v rovnakom riadku, každé z nich nahradíme písmenom, ktoré je v riadku od neho naľavo. Ak ide o prvé písmeno v riadku, nahradíme ho posledným písmenom v danom riadku.

Ak sú obe písmená v rovnakom stĺpci, každé z nich nahradíme písmenom, ktoré je v stĺpci nad ním. Ak ide o prvé písmeno v danom stĺpci, nahradíme ho posledným písmenom v tomto stĺpci.

Ak sú písmená v rôznych riadkoch aj stĺpcoch, každé z nich nahradíme písmenom, ktoré sa nachádza v priesečníku jeho riadka a stĺpca, v ktorom sa nachádza druhé písmeno.

Vigenerova šifra

Jednoduchá substitučná (Cézarova) šifra je veľmi ľahko dešifrovateľná pomocou frekvenčnej analýzy. V 15. storočí sa objavili prvé náznaky jej možného vylepšenia u Leona Battistu Albertiho, ktorý navrhuje nepoužívať jednu šifrovaciu abecedu, ale dve, ktoré budú posunuté o rôzne počty písmen. Pri šifrovaní sa budú tieto dve abecedy striedať. Text, ktorý takto dostaneme, už bude odolný voči frekvenčnej analýze. Samotný autor však svoj nápad ďalej nerozvinul, a tak sa muselo čakať ďalej. V polovici 16. storočia Blaise de Vigenere na základe prác Albertiho, ale aj Trithemia a Portu, vytvoril svoju vlastnú šifru. Jej sila spočívala v tom, že nepoužívala len dve abecedy ako Albertiho šifra, ale 26 abecied, ktoré boli postupne posúvané o jedno písmeno. Ak by sme chceli použiť kompletnú slovenskú abecedu s diakritikou, dostali by sme oveľa väčší štvorec, ale na princípe šifrovania by sa nič nezmenilo. Na šifrovanie sa používa tzv. Vigenerov štvorec, v ktorom sú všetky abecedy zapísané. V niektorých publikáciách sa môžete stretnúť aj s tabuľkou, ktorá začína 2. riadkom a na konci je 1. riadok.

Šifrovať budeme pomocou kľúčového slova – hesla, ktoré pozná len príjemca a odosielateľ. Jeho odporúčaná dĺžka je aspoň 5 znakov, čím viac, tým lepšie. Za kľúčové slovo si zvolíme slovo HESLO (kľúčové slovo môže obsahovať aj viackrát to isté písmeno). Text, ktorý budeme šifrovať, bude VIGENEROVA ŠIFRA. Keďže používame anglickú abecedu bez medzier, musíme oba texty transformovať na text bez diakritiky a medzier:

VIGENEROVASIFRA

Kľúčové slovo napíšeme nad jednotlivé písmená šifrovaného textu, pričom ho opakujeme podľa potreby. Vo Vigenerovom štvorci vyznačíme riadky, ktoré budeme používať. Prvé písmeno šifrovaného textu V zašifrujeme pomocou riadku určeného prvým písmenom kľúčového slova, teda v riadku h. V tomto riadku nájdeme v hornom stĺpci písmeno v a v priesečníku tohto riadka a stĺpca nájdeme písmeno C. Druhé písmeno šifrovaného textu I budeme šifrovať pomocou riadka e. V stĺpci zodpovedajúcom písmenu i nájdeme písmeno M. Takto pokračujeme dovtedy, kým nebudeme mať zašifrovaný celý text:

Kľúčové slovo: H E S L O H E S L O H E S L O
Šifrovaný text: V I G E N E R O V A S I F R A
Zašifrovaný text: C M Y P B L V G G O Z M X C O

Vidíme, že rovnaké písmená môžu byť zašifrované rovnako (A sme zašifrovali dvakrát na O), ale nemusia (E sme zašifrovali raz na P a raz na L). Naopak, v zašifrovanom texte máme za sebou dvakrát písmeno G, avšak raz sme ním zašifrovali písmeno O a raz písmeno V.

Na prvý pohľad teda ide o veľmi dobrú šifru, ktorá by mala mať veľké praktické uplatnenie, pretože má k dispozícii veľmi veľké množstvo kľúčových slov – môže ním byť ľubovoľné slovo, slovné spojenie či reťazec písmen, ktorý nedáva žiaden zmysel. Avšak táto šifra sa neuplatnila nasledujúce dve storočia. Až s vynálezom telegrafu sa rozšírila a vzhľadom na enormný rozsah kľúčových slov ju ľudia pokladali za nerozlúštiteľnú – vyslúžila si názov le chiffre indéchiffrable (nerozlúštiteľná šifra). Na svoje dešifrovanie si musela počkať až do roku 1854 na Charlesa Babbagea, ktorý však svoj objav nepublikoval. Najavo vyšiel až v 20. storočí pri štúdiu jeho poznámok. O niečo neskôr, v roku 1863, zverejnil dôstojník pruskej armády Friedrich Wilhelm Kasiski v knihe Tajné šifry a umenie ich dešifrovať rovnakú techniku, ktorá je dnes známa pod menom Kasiského test.

V čom spočíva metóda dešifrovania tejto šifry? Jej slabinou je to, že pri použití krátkeho kľúčového slova a dlhého textu sa začnú niektoré slová opakovať aj po zašifrovaní. Ak sa pozrieme na náš krátky text, tak vidíme, že písmeno A bolo dvakrát zašifrované rovnako – ako písmeno O. Ak sa pozrieme do riadku pre kľúčové slovo, tak vidíme, že v oboch prípadoch bolo nad písmenom A písmeno O, teda písmená A boli od seba vzdialené 5 znakov. V každom jazyku existuje niekoľko charakteristických slov, ktoré sa často opakujú – napríklad v angličtine je to určitý člen the. Tieto tri písmená môžu byť pri kľúčovom slove dĺžky 5 zašifrované len 5 rôznymi spôsobmi. Pri použití kľúčového slova HESLO to môže byť len ALW, XZP, LSS, EVL a HOI. Ak v zašifrovanom texte nájdeme dostatočne veľakrát opakujúce sa reťazce, môžeme obmedziť výber možností na dĺžku kľúčového slova. Ak sa napr. reťazec ALW (ale môže to byť aj ľubovoľný iný) zopakuje prvýkrát po 80 znakoch, tak môžeme predpokladať, že kľúčové slovo má dĺžku, ktorá je deliteľom čísla 80. Ak sa iný reťazec (môžeme sa zamerať napríklad na štvorpísmenové) zopakuje po 55 písmenách, tak máme indíciu, že dĺžka kľúčového slova je deliteľom čísla 55. Keďže dĺžka kľúčového slova má deliť čísla 55 aj 80, vychádza nám jediná možnosť – kľúčové slovo bude mať 5 písmen.

Celý text rozdelíme na 5 častí – každé piate písmeno bude patriť do rovnakej skupiny. Na tieto časti už môžeme použiť štandardnú frekvenčnú analýzu. Navyše vieme oveľa viac – abeceda je len posunutá o niekoľko písmen, takže môžeme porovnávať nielen frekvencie samotných písmen v texte, ale aj susednosť písmen. Napríklad ak vieme, že sa v abecede niektoré susedné písmená vyskytujú veľmi často, resp. skoro vôbec (napr. písmená W, X sú v abecede vedľa seba, ale v slovenčine sa vyskytujú veľmi málo), tak môžeme hľadať rovnaké zákonitosti aj vo frekvenciách získaných z šifrovaného textu. Ak určíme správny posun, získame jedno písmeno z kľúčového slova. Takto dokážeme postupne určiť celé kľúčové slovo a dešifrovať zašifrovaný text.

Na nasledujúcom obrázku si môžete pozrieť frekvenčnú analýzu slovenského textu. Môžeme si všimnúť napríklad to, že písmená A, E a O majú oveľa vyššiu frekvenciu ako ostatné, ale aj to, že písmená Q, F, G, W a X majú skoro nulovú frekvenciu výskytu. Ak sa pozrieme na susednosť písmen, tak vidíme, že máme dve dvojice málo frekventovaných písmen: F, G a W, X. Môžeme si aj všimnúť rozdiely vo frekvenciách za sebou idúcich písmen – najväčší rozdiel je medzi písmenami E a F. Iný pohľad na obrázok nám môže povedať, že písmená R, S, T, U, V tvoria päticu približne rovnako často sa vyskytujúcich písmen, okolo ktorých sú tri skoro vôbec sa nevyskytujúce písmená. Takýchto pozorovaní môžete nájsť oveľa viac.

Predpokladajme, že sme frekvenčnou analýzou zašifrovaného textu dostali takéto rozdelenie písmen:

Vidíme, že písmená F a J sa vyskytujú výrazne častejšie ako ostatné, za písmenom J je veľmi veľký skok, písmená B, C a K, L sa nevyskytujú skoro vôbec. To, že nám napríklad chýba tretie výrazne početnejšie písmeno, sa mohlo stať tým, že v danom texte boli používané slová, ktoré ho neobsahovali. Na základe týchto charakteristík textu môžeme s veľkou pravdepodobnosťou určiť, že písmeno E sa posunulo na písmeno J, teda posun abecedy je o 5 písmen. Našu domnienku si môžeme overiť aj porovnaním s frekvenčnou tabuľkou pre slovenskú abecedu posunutú o 5 písmen.

Samozrejme, nie všetko musí byť také jasné, ako sme tu napísali. Musíme sa pripraviť aj na to, že nám to na prvýkrát nevyjde. Ale čím je text dlhší, tým je väčšia šanca, že nájdeme správnu dĺžku kľúčového slova a potom aj jeho jednotlivé písmená.

Martin Hriňák