Veľká letná detektívno-šifrovacia hra

Riešenie - 4. šifry, nepozerajte ak sa nechcete ukrátiť o radosť z rozlúštenia bez pomoci

Štvrá šifra bola poslednou šifrou súťaže, jej predposlednou úlohou. Štvrtú šifru sme vytvorili ako kombináciu dvoch dôležitých šifier z histórie kryptografie.

Blaise de Vigenère, po ktorom je pomenovaná Vigenèrova šifra sa narodil v roku 1523.
Ako hovorí pomôcka pre štvrtú šifru "Tvorca šifrovacej metódy ktorou je zašifrovaná posledná šifra súťaže sa narodil v roku, ktorého súčet posledného dvojčíslia sa rovná číslu pred posledným dvojčíslim :)" súčet 2+3 dáva storočie v roku Vigenèrovho narodenia.

Štvrtá šifra ako finálna šifra súťaže mala byť obtiažna, zvolili sme Vigenèrovu šifru, ktorá odolávala riešeniu stovky rokov. Vigenèrova šifra je substitučnou šifrou s viacerými šifrovacími abecedami.

Prvým krokom je vytvorenie Vigenèrovho štvorca

šifrovacie abecedy sa v ňom vyberaju pomocou kľúčového slova. To sme zvolili podľa ďalšej význačnej šifry histórie, je ním slovo enigma.

Enigma bol šifrovací prístroj s ktorým je spojená najväčšia lúštiteľská bitka druhej svetovej vojny. Príbeh jej riešenia je strhujúci, medzi postavami hrajúcimi v ňom dôležitú úlohu sú géniovia ako bol Alan Turing. Je popísaný napríklad v knihe Simona Singhta, Kniha kódov a šifier či na filmovom plátne vo filme Enigma. 

Vo Vigenèrovom štvorci potom šifrovanie postupuje nasledujúcim spôsobom
 

riadok sa zvolí podľa písmen kľúcového slova (červené obdĺžniky). Prvými slovami otvoreného textu, ktorý sme šifrovali, bolo "peknyvykon...". Písmena otvoreného textu sa šifrujú podľa stĺpcov (modré obdĺžniky). Prvé písmeno otvoreného textu je p, prvým písmenom kľúčového slova je e. Modrý obdĺžnik pod p sa pretína s červeným obdĺžnikom vytvoreným podľa e. Ich prienik udáva zašifrované písmeno t (žltý štvorec).

e ako druhe pismeno v slove pekny sa sifruje n, druhým písmenom kľúčového slova enigma, výsledkom je r. k sa potom šifruje písmenom i z kľúčového slova na s.

A tak sa otvorený text celej šifry

peknyvykonbodkapravesterozriesilivigenerovusifrubodkatocostehladalijepatjednabodkadevatdevatosemtrimedzeratripatdevatbodkadvapatsestpatmedzeraporozlusteniciselnamnapistenamailsutazecostezistili

zašifruje na

trstkvcxwtnohxivdazrazqrsmzoqsmyqbugiamxavyfqldufblqmtspwyfelyijmlmwmvmtnrltmbsqsgpeznbjqvegwyqmxeqsqddrzgfrmcizpeznbhadonlbmpegakettnbsqddrzgbovbhrgsxrvooiwrttmmrnxoetiaismipfczmzipwyfedvazulm

Pozrime sa na výber z úspešných riešení, ktoré ste nám poslali.

Martin Baláž

1. najprv som skúsil zistiť, čo to je za šifru: Najprv som spravil frekvenčnú analýzu pre jednotlivé písmená. Vo výsledku bolo každé aspoň dvakrát, čiže (takmer) naisto to nie je monoalfabetická substitúcia. Tipujem Vigenèra.
2. chcem zistiť dĺžku kľúča. Teda robím frekvenčnú analýzu pre dvojice až pätice... dvakrát sa vyskytujú reťazce "sqddrzg", "pwyfe" a "peznb".
3. nájdem, koľko znakov je medzi nimi (teda ich začiatky). "pwyfe" sú od seba 114 znakov, "sqddrzg" 36 znakov, "peznb" 30 znakov. Aby platil predpoklad, že sú to naozaj rovnaké slová zašifrované jedným kľúčom, musí dĺžka kľúča deliť všetky tieto čísla. Spoločné delitele týchto čísel sú 1, 2, 3 a 6, najpravdepodobnejšie vyzerá práve 6.
4. skúšam niekoľko šesťpísmenových slov (pceska, finale, noctua, ...), neúspešne.
5. počítam, koľko bude trvať bruteforce. 26^6 = približne 310 miliónov, píšem program.
6. nechám si vypísať všetky riešenia s tým, že ak výsledný text obsahuje q, w, alebo x, okamžite ho zahodím.
7. "qwx" filtrom prejde iba osem možných kľúčov z 310 000 000, jediný zmysluplný je "enigma" a riešenie vidím vedľa neho.


Lucia Fojtová

"Sifra vigenere byla relativne jednoducha. Opet bylo na prvni pohled patrne, ze by se mohlo jednat o substituci. Ale protoze ty jednoduche uz byly v predchozich kolech, a taky index koincidence moc slovenstinu nepripominal -> rovnou jsme zkusili variantu polyalfabeticke sifry. Predpoklad (odhad) byl, ze klicem bude nejake slovo o delce 4-10 znaku. Pro kazdou delku hesla jsme zkusili urcit posun jednotlivych podskupin textu, az se u delky 6 zacalo rysovat slovo enigma. Zbytek uz byl otazkou chvilicky. Takze trocha stesti a jinak analyticky postup."


Daniela Forisekova

"No Vigener bol celkom slusny hardcore, kedze jedine co som na to pouzila z vypoctovej techniky bol MS Excel :) " a ďalej "Postup riesenia bol asi taky, ze zaklad samozrejme frekvencka, po pochopeni ze naozaj v tom nebude nic ine a skutocne mam riesit posun o heslo bez hesla (grrr :)), tak som zacala skusat ako heslo nejake slova, co by mohli byt v sifre (ako uz predtym uspesne pouzite slovo "sifra", "gratulujeme", "uspesne" atd.). S tym ze kluc som si pisala vzdy aj s vsetkymi moznymi posunmi - teda sifra som skusala ako SIFRASIFRASIFRA..., IFRASIFRASIFRA..., FRASIFRASIFRA... atd. Sledovala som to, ze ak sa tam taketo slovo nachadza v texte, tak jeho dekodovanim sa mi v tom dekodovanom texte zobrazi na prislusnom mieste pouzite heslo, alebo jeho cast. Takze som sa v tej mase nahodnych pismen snazila hladat nejake zmysluplne slovo. Toto presne sa mi nepodarilo, ale pri dvoch posunoch SIFRA mi tam niekde vznikli dva rovnake 5-pismenove substringy (tiez sa to podobalo na zmysluplne slovo, tak som si to vsimla pri tych nahodnych znakoch) - to boli bud niektore slova BODKA alebo niektora z cifier, neviem uz teraz presne na ktorych poziciach to bolo. Takze bolo jasne, ze mam nejake slovo, co sa v rieseni nachadza 2x, a zhodou okolnosti vzdy rovnako posunute voci heslu. Toto bolo asi trocha aj stastie, ale tak aj to obcas treba. Z ich polohy som usudila, ze kluc ma bud 6 alebo 9 znakov - rovnake pismena boli o 18 znakov od seba - takze potom som spravila frekvencku na kazdy 6. znak a kazdy 9. a snazila sa zistit posun v abecede pre kazde pismeno. Tu sa da frekvencka krasne pouzit, lebo posuvame celu abecedu, takze vieme, ako by mal vyzerat vysledny graf (ja som to mapovala hlavne podla substringu WXYZABCDEFG, to ma 2 prazdne, 2 takmer prazdne, peak na A, potom tri malo pocetne, peak na E a zase prazdne F,G, to sa da v tych vyslednych frekvenckach krasne najst, prikladam printscreen). No a uz pri tych 6-znakovych ked som mala urcene E.I.M. tak mi to udrelo do oci ze Enigma, tak som vyskusala a fakt to bolo ono. (na tom printscreene mi chyba posledny stlpec frekvencky, tak v tom nehladajte ziadny skryty umysel, to len uprostred noci ked clovek kopiruje vzorce tak sa obcas sekne, vsimla som si to az teraz).
Myslim, ze bolo jednoduchsie mozno aj spravit hned frekvencku postupne na 5-9 znakov, heslo urcite nedate ani prilis dlhe ani prilis kratke :) a vycitat to rovno z toho. No ale prvykrat v zivote som musela riesit nieco taketo hrubou silou, tak nenapadne cloveka ten najefektivnejsi postup hned na prvykrat.."
 

Dvojčíslie v otvorenom texte bolo poslednou úlohou na vyriešenie. Viacerí z tvaru a usporiadania oboch čísel rovno hádali, že ide o geografické súradnice, čo bol správny tip. Pozícia na ktorú súradnice smerovali, geografická širka 51.9983 a geografická dĺžka 359.2565 priamo súvisia so štvrtou šifrou.

Súradnice smerujú do mesta Bletchley Park v ktorom sa lúštili nacistické šifry zašifrované Enigmou. Enigma bolo kľúčové slovo štvrtej šifry a súradnice smerujú na Národné počítačové múzeum (The National Museum of Computing - tnmoc.org), v bloku H múzea je šesť počítačov Colossus používaných na riešenie pokročilej verzie šifry Enigma. Týchto šesť počítačov vytvorilo prvé počítačové centrum v histórii.

A to je záver tejto šifrovacej šúťaže. Sme radi, keď ste sa pri jej riešení zabavili :)