Zadanie

Ak máte akékoľvek otázky ohľadom tejto, úlohy napíšte Michalovi Sládečkovi na

Andrej si minule prečítal knižku o historických šifrách a niektoré z nich sa mu veľmi zapáčili. Preto ich hneď naučil aj svojho kamaráta Adama a začali si posielať zašifrované odkazy. Teraz sa všade chvastajú, že nikto nikdy nezistí čo si píšu. Preto sme zachytili viacero ich správ a rozhodli sme, sa že ich dešifrujeme.

Úloha

Za úlohu máte dešifrovať niekoľko správ – odchytené správy Adama a Andreja.

Vo všetkých úlohach platí, že budú písať len anglickou 26 písmenovou abecedou a šifrovať budú iba písmena. To znamená, že všetky špeciálne znaky ako bodky, čiarky, úvodzovky alebo dokonca čísla zostanú nezmenené. Navyše, nerozlišujú medzi veľkosťou písmen a do výsledného zašifrovaného textu píšu iba veľké písmená.

  1. (3 body) V prvej podúlohe viete, že Andrej poslal Adamovi správu zašifrovanú pomocou Cézarovej šifry. Prebiehalo to tak, že sa najprv dohodli na nejakom kladnom celom čísle, ktoré budeme nazývať kľúč \(k\). Abecedu si napísali na kružnicu, a teraz vždy keď Andrej posiela Adamovi list, každé písmeno v tomto liste nahradí písmenom, ktoré leží na tejto kružnici o \(k\) pozícií ďalej. Na kružnicu si ju napísali preto, aby po písmene ‘Z’ nasledovalo opäť písmeno ‘A’. Keď chce Andrej zašifrovať slovo "zima" s kľúčom \(k=2\), napíše "BKOC".

Správa, ktorú sme odchytili sa nachádza tu: ksp.sk/~prask/2/3/3/sifraA.html

  1. (5 bodov) Andrej sa rozhodol zvýšiť bezpečnosť, pretože Cézarova šifra bola veľmi ľahko rozlúštiteľná. Rozhodol sa použiť substitučnú šifru. Andrej si do prvého riadku napísal pekne v poradí všetky písmená abecedy. Do druhého riadku tiež napísal písmená abecedy, ale v nejakom inom poradí. Vyzerať to mohlo napríklad takto:
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
T J M G D N A C O B E L W V X K Z Y Q R P I H U F S

Túto dvojicu riadkov si nazvime kľúč. Keď chce Andrej niečo zašifrovať a poslať Adamovi, každé písmeno v správe nahradí písmenom, ktoré je v kľúči napísané pod ním. Teda slovo "Adam" by zašifroval na "TGTW". O niektorých častiach Andrejovej správy si však vieme tipnúť, čo reprezentovali v originálnej správe a tie nám pomôžu šifru postupne rozšifrovať.

Zašifrovaná správa sa nachádza tu: ksp.sk/~prask/2/3/3/sifraB.html

  1. (7 bodov) Adam sa už naštval, že mu niekto stále číta správy, a teda sa rozhodol že to poriadne sťaží. Opäť používajú substitučnú šifru, ale tento raz si dal Adam pozor, aby v správe neboli žiadne ľahko uhádnuteľné časti ako pozdrav, podpis a podobne. Máte ale šťastie že správa je veľmi dlhá, to sa možno bude dať nejako využiť.

Správa sa nachádza tu: ksp.sk/~prask/2/3/3/sifraC.html

Odovzdávanie

Každý zašifrovaný text v sebe ukrýva tajné heslo. Toto heslo nie je zmysluplné, je to len zhluk písmen. Ak sa vám toto heslo podarí zistiť, choďte na stránku "prask.ksp.sk/specialne/prask/2/3/3/heslo/" (vraj lomítko na konci je dôležité) kde namiesto slova "heslo" napíšete zistené heslo. Ak ho budete mať rozšifrované správne, body sa vám pripíšu automaticky.

Podúloha a)

V tejto podúlohe ste mali za cieľ vylúštiť text zakódovaný Caesarovou šifrou. Na úspešné vyriešenie existuje viacero možností. Každá z nich ale využíva fakt, že máme len 26 možností pre kľúč. Posunúť abecedu o viac ako 26 písmen totiž nemá zmysel. Posunutím o 27 písmen dostaneme to isté ako posunutím o 1. Nič nám teda nebráni vyskúšať všetky možnosti.

Túto podúlohu zvládneme vyriešiť aj pomocou pera a papiera. Postupne si vyskúšame posunúť správu o niekoľko písmen dozadu, až kým nedostaneme zo správy niečo zmysluplné. Aby sme však nemuseli posúvať celý text, o ktorom aj tak rýchlo zistíme, že nie je správny, stačí nám vybrať si len jedno slovíčko, skúsiť na ňom rôzne hodnoty pre kľúč a potom vybrať tú správnu a pomocou nej rozšifrovať zvyšok správy.

Vyberieme si druhé slovo zo správy, "DZX". Je totiž krátke a bude sa nám na ňom rýchlo zisťovať kľúč.

0 DZX
1 EAY
2 FBZ
3 GCA
4 HDB
5 IEC
6 JFD
7 KGE
8 LHF
9 MIG
10 NJH
11 OKI
12 PLJ
13 QMK
14 RNL
15 SOM

Tu si hneď všimneme slovíčko "SOM". Je to pomerne časté slovenské slovo. Môžme teda skúsiť celú správu posunúť o 15 miest v abecede, čím odhalíme zašifrovaný text.

Pre tých lenivejších, existujú aj menej namáhavé postupy. Napr. napísať si program ktorý vypíše všetkých 26 možností pre originálnu správu, a nájsť si medzi nimi tú, ktorá dáva zmysel. A ešte rýchlejšie riešenie je nájsť si na internete takýto program, napr. http://www.mygeocachingprofile.com/codebreaker.caesarcipher.aspx

Podúloha b)

V tejto podúlohe už máme pre kľúč omnoho viacej možností, a nedokážeme ich vyskúšať všetky. Musíme na to ísť rozumnejšie. Vieme že každé písmeno sa nám zmenilo na nejaké iné. V texte ale máme dostatok informácii na to, aby sme si vedeli tieto pôvodné písmena zistiť. Tu sa nám oplatí využiť find and replace funkciu textového editoru, o ktorom bola reč v minulom zašifrovanom texte. Keďže celý zašifrovaný text má iba veľké písmená, ak o niektorom písmene zistíme jeho pôvodný tvar, nahradíme ho v texte malými písmenami. Ak napríklad zistíme, že sa "a" zašifrovalo na "d", nahradíme v texte všetky veľké "D" malým "a". Takto budeme mať prehľad o tom, čo sme už rozšifrovali a čo ešte nie.

Začnime tým úplne najočividnejším, a to sú odkazy. Vidíme text “JYYU://BBB.NWU.WN/”, z toho vieme určiť že "J" je "h", "Y" je "t", "U" je "p" a "B" je "w", lebo každý link začína "http://www.". To je dobrý začiatok. Až vymeníme tieto písmena, na prvom riadku správy budeme mať text "DhSR DIDP,". Keďže sa to nachádza na prvom riadku, mohlo by to byť oslovenie. A keďže druhé písmeno oslovenia je "h", môžme si tipnúť, že prvé slovo je "ahoj", a nahradiť príslušné písmenká. Na prvom riadku potom budeme mať "ahoj aIaP". Zo zadania vieme, že Andrej posiela list Adamovi, takže "aIaP" by mohlo byť v skutočnosti "adam". Na poslednom riadku by mal byť podpis, a je tam "aVdEKj", čo nemôže byť nič iné ako meno odosieľateľa "andrej"..

Teraz máme dosť písmen na to, aby sme si zvyšné domysleli z čiastočných slov, ktorých je tam teraz už neúrekom. Celý princíp spočíva v tom, že sa pozeráme na slová v ktorých poznáme väčšinu písmen a vieme odhadnúť, aké sú tie zvyšné. Napr. zo slov ako "poFedat", "pZWmeno", "mZmoMhodom" vieme uhádnuť, že to majú byť slová "povedat", "pismeno" a "mimochodom". Takýmto spôsobom zistíme postupne všetky písmena.

Podúloha c)

Tretia podúloha bola o dosť ťažšia. Na jej riešenie bolo potrebné použiť metódu zvanú frekvenčná analýza. Princíp tejto metódy je, že rôzne písmena sa v normálnom texte vyskytujú rozlične veľa krát. Napríklad, asi by sme ťažko našli v našom texte 60 krát písmeno "q", ktoré sa v slovenčine takmer nevyskytuje. Naopak, očakávame, že sa v ňom bude nachádzať naozaj veľa písmen "a" alebo "e".

Toto vieme pri riešení využiť nasledovne. Predstavme si, že sa písmeno "a" zašifrovalo na písmeno "W". To znamená, že v zašifrovanom texte sa nachádza toľko písmen "W", koľko bolo v pôvodnom texte písmen "a". A ak vieme, že "a" je najčastejšie slovenské písmeno a "W" sa v zašifrovanom texte nachádza najväčší počet krát, ľahko usúdime, že "W" je vlastne zašifrované "a".

S dešifrovaním textu môžeme začať tak, že si určíme nejaký typický slovenský1 text a spočítame, ako často sa v ňom vyskytujú jednotlivé písmená. Pomocou týchto počtov určíme tabuľku frekvencií jednotlivých písmen. Ak ste však vyriešili druhú šifru, získali ste našu frekvenčnú tabuľku (odkaz), ktorá bola uspôsobená na zašifrovaný text. Dala by sa použiť aj vlastná frekvenčná tabuľka, dešifrovanie by však bolo kúsok ťažšie. Následne si zrátame frekvencie v našom zašifrovanom texte. To urobíme napríklad pomocou stránky, ktorú sme vám tiež poskytli v druhej šifre (odkaz).

Môžeme začať s dešifrovaním. Vidíme že písmeno "D" sa nám vyskytuje v zašifrovanom texte najčastejšie, a často sa vyskytuje ako druhé písmeno v dvojpísmenových slovách. Navyše sa často vyskytuje aj osamote. Môžeme teda s vysokou istotou povedať, že "a" sa nám zašifrovalo na "D". Ďalšie písmeno, ktoré má v zašifrovanom texte vysokú frekvenciu je "N". Z tabuľky vidíme, že jeho frekvencia sa blíži frekvencii písmena "e". Môžme si buď tipnúť, že to "e" naozaj je, ale keďže sa blízko vyskytuje aj písmeno "o", môžeme zatiaľ urobiť niečo iné.

Pozrime sa radšej na dvojpísmenové slová, v ktorých na druhom mieste je "a". Všimnime si často sa vyskytujúce dvojice "Ca" a "Ga". Prečo práve tieto? Oboje z nich sa vyskytujú aj samostatne. To znamená, že sa pravdepodobne jedná o písmena "s" a "z", nevieme ale ktoré je ktoré. Toto skombinujeme s tabuľkou frekvencií, a zistíme že "s" má frekvenciu 4.3% zatiaľčo "z" len 2%. V našom texte má "C" frekvenciu 4.8% a "G" len 2.9%. Z toho vyvodíme, že "C" je zašifrované "s" a "G" je zašifrované "z".

Tým sme odhalili ďalšie dvojice, "Xz" a "sX". Mohlo by ísť o slová "az" a "sa", ale "a" už máme dešifrované, teda "X" nemôže byť "a". Jediné písmeno, ktoré tam sedí na obe slová je "u". Písmenami "z" a "s" sme si tiež dokázali hypotézu, že "e" je zašifrované ako "N", pretože sa nám v texte objavilo slovo "zasN", ktoré vylučuje možnosť, že "N" je "o" ("zaso" nie je rozumné slovo).

Odhalenie "e" nám môže pomôcť, stačí nájsť dvojpísmenové slovo končiace "e". Nájdeme viacero výskytov "Be". Možnosti sú slová "je", "ze". Keďže ale "z" už máme rozšifrované, "B" musí byť "j".

Môžme si teraz opäť siahnúť do frekvenčnej analýzy, keďže písmeno "T" sa v našom texte vyskytuje s frekvenciou 6.6%, pričom v obyčajnom texte sa "o" vyskytuje s frekvenciou 6.4%. Frekvencia žiadneho zostávajúceho písmena nie je blízko k tomuto číslu, a teda môžme s vysokou istotou povedať, že "T" je "o". Ďalšie písmeno na muške je "E", ktoré je v texte na viacerých miestach samo. Jednopísmenných slov v slovenčine nie je veľa, a už vôbec nie po tom, čo sme odstránili "a","z","s","o". Ostávajú nám len slová "i" a "v". Keby to ale bolo "i", vznikne nám viacero nezmyselných slov ako napríklad "ieAeQ". Takže písmeno "E" bude zašifrované "v".

Ukáže sa nám slovíčko "vojJou", ktoré môže byť jedine slovo "vojnou". Teda "J" je "n". Tiež sa ukazujú napríklad slová "soR" a "RaR" – možné "som" a "mam". Odkryl sa nám kus textu, "na vZmenu na nasom useWu", z ktorého vidíme, že "Z" je "y" a "W" je "k".

Teraz už máme odkrytých dosť slov na to, aby sme rovnakým spôsobom odkryli celý zvyšok textu.


  1. Samozrejme, v rôznych jazykoch sú vyskyty písmen rôzne. Napríklad v angličtine sú najčastejšie písmená "e" a "t".

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.