Lekcia 07 - Kryptografia (Ako na mysterky?) Mystery Cache

O tejto sérii

Každé z riešení obsahuje cast informácie, ktorú budeš potrebovat neskôr pre záverecnú skúšku (desiatu kešku v sérii). Túto informáciu nájdeš vždy v Geocheckeri pre danú kešku, hned potom, ako zadáš jej správne vylúštené súradnice. Nezabudni si túto informáciu odpísat/odkreslit, odfotit alebo jednoducho uložit.

Lekcia c. 7: Kryptografia

Úvod

Co je to kryptografia?

Pojem kryptografia je odvodený z gréckych slov pre skrytý a písanie - je to teda veda o štúdiu skrytých správ.

Enkrypcia je konverzia jednoduchej informácie (plaintext) do "nezmyselného blábolu" (ciphertext). Dekrypcia je opacný proces, vytvorenie pôvodnej správy zo zašifrovaného textu. Šifra oznacuje metódu, ako táto konverzia prebieha.

Fungovanie šifry je ovplyvnené dvomi vecami - šifrou samotnou a klúcom (key). Klúc je tajný parameter šifry, ktorý je známy iba odosielatelovi a prijímatelovi zakryptovanej správy (áno, viem, nie je to úplne pravda, stací sa pozriet na algoritmy verejných klúcov, ale pre potrebu tejto lekcie nám postací aj takéto výrazne zjednodušujúce vysvetlenie).

Lúštenie mysteriek, ktoré obsahujú kryptografiu, je v podstate jednoduché - nájdi šifru, nájdi klúc a môžeš dešifrovat ciphertext. Proces, ktorým sa k týmto parametrom dostaneš a následne si budeš schopný precítat originálny text, sa nazýva kryptoanalýza.

Klasické versus moderné šifry

Klasická šifra je taká, ktorá funguje na základe písmen abecedy a proces šifrovania/dešifrovania obycajne prebieha rucne (použitím papiera a pera) alebo s použitím jednoduchých mechanických pomôcok (ako napríklad skytalé). Moderné šifry fungujú na základe bitov a bytov a potrebujú špeciálny pocítacový hardware a software. Prevažná väcšina šifier, ktoré nájdeš v mysterkách, sú šifry klasického typu.

(Zaujímavá historická vsuvka: Šifrovací software sa dá tiež považovat za zbran, preto od roku 1996 nemôže byt exportovaný do iných krajín, nakolko americká vláda (konkrétne teda International Traffic in Arms Regulations - ITAR) zakázala "vývoz" cohokolvek s enkrypciou silnejšou ako 40-bit. Naneštastie, 40-bitová enkrypcia nie je dostatocne silná, aby bezpecne ochránila informáciu na internete - toto spolu s faktom, že k tejto regulácii došlo práve v case najväcšieho boomu internetu, nás iba utvrdzuje v tom, že sa nejedná o náhodu).

Jednoduché substitucné šifry

Substitucná šifra je velmi jednoduchá - nahrádza každé písmeno abecedy iným písmenom alebo znakom. Klúcom k vylúšteniu takejto šifry je poznat spôsob, ako sa jednodtilé znaky mapujú na iné.

Cézarova šifra

Cézarova šifra je pomenovaná po Júliovi Cézarovi, ktorý ju používal pre bezpecnú komunikáciu so svojimi vojenskými velitelmi.

Cézar používal túto šifru s posunom (hodnota klúca) 3. Pre zakryptovanie správy bolo treba pre každý znak nájst písmeno, ktoré je v abecede o 3 miesta za písmenom, ktoré je šifrované. Z písmena A sa teda stalo D, z písmena B sa stalo E a tak dalej (ak sa posun dostal na koniec abecedy, pokracovalo sa znovu od A).

Pre zjednodušenie šifrovania aj dešifrovania sa casto používal tzv. šifrovací disk. Je to kruh s dvomi diskami, na ktorých je napísaná celá abeceda. Jeden z diskov sa otáca o dohodnutý posun, na druhom disku je potom lahké odcítat zašifrovaný znak. Táto šifra sa práve preto nazýva aj ROT (ako skratka pre rotate), nasledovaná císlom, ktoré predstavuje velkost posunu. Takže Cézarova šifra by bola nazývaná ROT3, na šifrovacom disku nižšie je pre zmenu znázornená šifra ROT7 (pri cítaní zvnútra von) alebo ROT19 (pri cítaní zvonku dnu).

Pre geokešerov je urcite najnámejšia verzia Cézarovej šifry s posunom 13 (teda ROT13). Všetky Hinty v popise kešky sú kódované práve v tejto šifre, takže skúsený geokešer dešifruje casto používané slová (ako napríklad ZNTARG) z hlavy, bez použitia akéhokolvek nástroja. ROT13 má zjavnú výhodu v tom, že enkrypcia a dekrypcia sú zhodné - A sa zakóduje na N a zároven N sa zakóduje na A.

Atbash

Atbash je substitucná šifra, ktorá ku každému písmenu v abecede priradí písmeno z opacného konca abecedy. Napríklad z písmena A sa stane Z, z písmena B sa stane Y, z písmena C sa stane X, atd. Pomenovanie Atbash pochádza z hebrejcinym kde písmeno Alef sa mení na Tav, Beth sa mení na Shin atd. Táto metóda môže byt použitá v akomkolvek jazyku, ktorý má zoradenú abecedu.

Kryptogram

Kryptogram si už možno videl v novinách alebo casopisoch. Kryptogram je v podstate rébus, ktorý používa jednoduchú substitucnú šifru. Mapovanie plaintextu na ciphertex je náhodné (nie v poradí ako je tomu u Cézarovej šifry a Atbash).

Pigpen

Jedna z najznámejších substitucných šifier, ktoré nepoužívajú abecedu, je šifra Pigpen (šifra prasacích chlievov). Je známa tiež aj ako Masonic alebo slobodomurárska šifra. Klúc k tejto šifre je zaradenie znakov do mriežky:

Pre zakryptovanie správy je každé písmeno textu nahradené jedným zo znakov z mriežky. Napr.:

Iné symboly

Substitucná šifra nemusí používat iba písmená. V podstate akákolvek sada znakov ci symbolov môže byt použitá ako reprezentácia písmen abecedy, napríklad aj :

• císla (A=1, B=2 atd., používané velmi casto)
  
• znaky z fontov (ci už nepísmenkové znaky, alebo celé obrázkové fonty)
• pocítacové kódy (napríklad ASCII alebo ABCDIC)
• obrázky
• ciarové kódy
• Morseovka
• námorná vlajková abeceda
• znaky tlacidlového telefónu (2 je A, 22 je B, 222 je C, 3 je D, ..)

Polyalfabetické šifry

Základným problémom jednoduchých substitucných šifier je, že sa na ne dá útocit kryptoanalytickou metódou nazývanou frekvencná analýza. Frekvencná analýza je vedecké pomenovanie pre prístup typu "spocítaj pocetnost jednotlivých znakov/písmen v ciphertexte". Znak/písmeno, ktoré sa vyskytuje v texte najcastejšie, bude s najvacsou pravdepodobnostou reprezentovat písmeno A, dalej budú nasledovat písmená O, E, I. Pocetnost písmen v anglickom texte je iná a ukazuje ešte väcšiu dominanciu písmen E, T, A, O, I a N.

Práve pre zabránenie jednoduchej frekvencnej analýzy boli vyvinuté komplexné substitucné šifry. Cielom týchto metód je pokúsit sa o viac-menej rovnomerné zastúpenie pocetnosti znakov v cielovom (zakryptovanom) texte.

V polyalfabetickej šifre jeden znak ciphertextu nezodpovedá jednému znaku plaintextu. Písmeno A sa na jednom mieste môže dekódovat na úplne iné písmeno, ako pri dekódovaní toho istého písmena umiestneného v texte na inom mieste.

Tabula recta

Ak je šifrovací disk hlavným nástrojom používaným pri substitucných šifrách, v prípade polyalfabetických šifier je týmto nástrojom tabula recta. Tabula recta vypadá napríklad nasledovne:

Vigenere

Vigenerova šifra je jedna z najviac používaných šifier, používajúcich tabulu recta. Šifra vyžaduje, aby sa odosielatel a prijímatel správy dohodli na slove, ktoré sa použije ako klúc. Napríklad, predpokladajme že správa ktorú chceš zašifrovat, je:

UTOKZACNEOSIEDMEJ

Odosielatel zvolí klúcové slovo a opakuje ho až kým bude mat rovnakú dlžku, ako správa. Ako príklad, klúcové slovo "CITRON" bude v celej svojej dlžke vyzerat ako:

CITRONCITRONCITRO

Teraz už len stací použit tabulu recta, použit šifrovaný text (UTOKZACNEOSIEDMEJ) ako riadok a klúc (CITRONCITRONCITRO) ako stlpec. Potom nahradíš každý znak z plaintextu korenšpodujúcim znakom z tabula recta. V našom príklade, znak na priesecníku riadka U a stlpca C je W. Dalej, priesecník riadka T a stlpca I je znak B. Dalším znakom bude logicky H, ako priesecník riadka O a stlpca T. Celá zašifrovaná správa teda bude vyzerat nasledovne:

WBHBNNEVXFGVGLFVX

Autokey

Paradoxne, Vigenere nebol tým, kto vymyslel šifru, ktorá nesie jeho meno. Tá bola vymyslená clovekom menom Giovan Batista Belaso v roku 1553. Šifra, ktorú vynaliezol Vigenere v roku 1586 sa nazýva autokey a je výrazne silnejšia.

Autokey je podobná klasickej Vigenere šifre, ale používa odlišný spôsob tvorby klúca a tým je ekrypcia výrazne silnejšia. Namiesto opakovania klúcového slova znovu a znovu, klúc pozostáva zo zvoleného klúcového slova za ktorým nasleduje samotná správa. Takže klúc pre náš príklad by bol:

CITRONUTOKZACNEOS

Enigma

Enigma je jedna z najviac sofistikovaných polyalfabetických šifier, ktoré kedy boli vytvorené. Bola vytvorená nemeckou armádou a intenzívne používaná pocas druhej svetovej vojny. Ak vieš po anglicky, precítaj si o tom ako bola Enigma prelomená, je to fascinujúci príbeh.

Enigma ako šifrovací prístroj je kombináciou elektrického a mechanického systému. Mechanický systém je zložený z klávesnice, sady rotacných valcov (rotorov) zoradených na jednej osi a krokového mechanizmu, ktorý otáca postupne jedným alebo viacerými rotormi pri každom stlacení.

Šifrovanie prebieha nasledovne: po stlacení klávesy sa uzavrie elektrický obvod. Prúd pretejá rôznymi súcastami, až sa nakoniec rozsvieti jedna z mnohých žiaroviek na panely, cím indikuje výsledné zašifrované písmeno.

Hodnota klúca pre Enigmu je kombináciou nasledujúcich údajov:

• poradie rotorov (nem. Walzenlage) - sústava rotorov a zároven poradie, v akom mali byt osadené
• pociatocná pozícia rotorov - vyberaná operátorom, iná pre každú správu
• nastavenie rotorov (nem. Ringstellung) - pozície v akej bolo potrebné nastavit abecedné krúžky v závislosti od okáblovania rotorov
• nastavenie rozvodnej dosky (nem. Steckerverbindungen) - schéma prepojenia zástrciek na rozvodnej skrini
• v neskorších verziách aj spôsob okáblovania reflektora.
  

Polygrafické šifry

Polygrafická šifra je taká šifra, ktorá používa nie jeden znak, ale skupinu znakov ako základnú jednotku pe enkrypciu. Pri jednoduchej šifre a jednotlivých znakoch je v podstate iba 26 možností, ako môže byt každý znak enkryptovaný, v prípade dvoj-písmenkových skupín v polygrafickej šifre je to však už 676 možností, co robí túto šifru silnejšou pred prípadným útokom.

Polybius mriežka

Niektoré známe polygrafické šifry používajú usporiadanie písmen, nazývané tiež Polybius mriežka (Polybius Square). Písmená sú zoradené zlava-doprava a zhora-dole (nakolko ide o mriežku rozmerov 5x5 a anglická abeceda má 26 znakov, pre písmená I a J sa obycajne používa iba jeden znak). Mriežka vyzerá nasledovne:

Tap (tukací) kód

Tento typ kódu, ktorý používa Polybius mriežku, bol používaný väznami - tukaním na potrubie alebo steny. Pre zakódovanie písmena väzen tuká tolko krát, o aký riadok ide, nasledované prestávkou, potom pocet tukov reprezentujúci stlpec, a znova prestávka. Takže napríklad slovo BACHA by bolo vytukané ako "tuk (prestávka) tuk tuk (prestávka) tuk (prestávka) tuk (prestávka) tuk (prestávka) tuk tuk tuk (prestávka) tuk tuk (prestávka) tuk tuk tuk (prestávka) tuk (prestávka) tuk". V prípade tohto väzenského kódu sa obycajne používala mriežka, kde písmená I a J boli samostatné, ale C a K používali iba jeden znak.

Playfair

Playfair je šifra, ktorá sa v mysterkách objavuje pravidelne. Táto šifra nebola objavená lordom Playfairom (hoci by k tomuto predpokladu jej názov priam nabádal), ale jeho priatelom Charlesom Wheatstoneom.

Štandardná polybius mriežka používa znaky abecedy zoradené zlava-doprava a zhora-dole, v prípade Playfair však mriežka zacína klúcovým slovom (duplicitné znaky sú odstránené) a až potom nasleduje zvyšok abecedy. Písmeno J sa nepoužíva (je nahradené písmenom I ešte pred zaciatkom kryptovania priamo v plaintexte). Ako príklad, mriežka pre Playfair by pri použití klúcového slova "CIPHER" vyzerala nasledovne:

Pre šifrovanie (a následné dešifrovanie) sú definované pravidlá (rozdielne kódovanie pre dvojicu znakov v riadku, stlpci, rovnaké znaky...), ak sa chceš o nich dozvediet viac, pozri sa na stránku Playfair vo Wikipedii.

Four-square

Šifra Four-square (štyri mriežky) používa dve klúcové slová a (ako napovedá jej názov) štyri Polybius mriežky usporiadané v matici 2x2. Je to velmi silná šifra, ktorá odstranuje relatívne slabé stránky šifry Playfair. V šifre Playfair, ak AB sa kryptuje ako XY, tak aj BA sa kryptuje ako YX, takže odhalenie jedného páru automoticky vyzrádza aj druhý pár. V prípade Four-square, AB sa môže kryptovat do úplne inej kombinácie ako BA.

Transpozicné šifry

Transpozicná šifra mení pozíciu písmen v plaintexte pre vytvorenie šifrovaného textu. Napríklad, správa ktorú chceme kódovat je:

STYRIOSEMSEDEM

Jeden zo spôsobov, ako sa dá táto správa zakryptovat, je rozdelit text rovnomerne do troch riadkov (a doplnit náhodné znaky na konci):

STYRI
OSEMS
EDEMX

Pre vytvorenie zakódovaného textu potom cítaj znaky zhora nadol:

SOETSDYEERMMISX

Samozrejme, vzor kódovania môže byt akýkolvek, nielen zhora dole. Ako príklad si predstav špirálu, striedanie cítania zlava-doprava a zprava-dolava, ale aj dalšie (rail-fence, route, ...). Ktorýkolvek vzor môže byt taký dlhý, na akom sa odosielatel a prijímatel dohodnú.

Knižné šifry

Knižná šifra používa ako šifrovací klúc nejký dlhý text, najcastejšie slovníky, náboženské knihy (ako napr. Biblia) vládne dokumenty (Vyhlásenie nezávislosti), ale casto aj obycajnú (samozrejme medzi odosielatelom a prijímatelom dohodnutú) beletriu.

Táto šifra kryptuje každé písmeno textu tak, že odkazuje na pozíciu tohto písmena v klúci - dokumente. Text je teda nahradený sústavou císiel, podla ktorých sa znaky dajú nájst v dokumente. Trojice císiel obycajne indikujú, že ide o císlo strany, císlo riadku a poradie znaku.

Kryptoanalýza

Konecným cielom kryptoanalýzy je vždy odhalit skrytú správu. Co znamená, že musíme odhalit klúc, ale aj šifru, ktorá bola použitá. Pri ich hladaní môžeš použit viaceré metódy:

Experiment

Neboj sa experimentovat a skúšat. Väcšina pokusov ta samozrejme k odkrytiu správy neprivedia, ale nenechaj sa odradit len preto, že prvý pokus nezafungoval.

Uhádni šifru a klúc

Priamo v listingu mysterky môžeš nájst nápovedu, ktorá ti prezradí aký klúc bol použitý a o akú šifru ide. Dokonca to môže byt v popise uvedené aj priamo. Ak nie, cez rôzne pomôcky alebo jemné náznaky ti autor obycajne prezradí, ktorým smerom hladat.

Hladaj znaky zo šifry Pigpen, morzeovku alebo symboly semaforu - sú lahko identifikovatelné a hned vieš, o akú šifru sa jedná.

Uhádni plaintext

Vzpomen si na úplne prvú radu z prvej lekcie v tejto sérii - Každé konanie zacínaj s víziou ciela. Obycajne hladáš súradnice, takže rozmýšlaj nad tým, akým spôsobom môžu byt zapísané. Ak vidíš dva riadky písmen, tak prvý riadok môže predstavovat zemepisnú dlžku a druhý zemepisnú šírku. Pokús sa nahradit prvé alebo posledné skupiny znakov slovami "SEVER" alebo "VYCHOD". Hladaj "SEVER STYRIDSATOSEM" alebo "SEVER STYRI OSEM" v prvom riadku... Ak bola správa zakódovaná jednoduchou substitucnou šifrou, nájdenie výskytu niektorého z týchto klúcových slov by ti malo stacit na odomknutie zvyška klúca a následne aj vylúštenie správy.

Hladaj fragmenty plaintextu

V kryproanalýze je velmi zriedkavé, že získaš celý klúc a plaintext naraz. Kryptoanalýza obycajne postupne zliepa dokopy malé kúsky plaintextu, ktoré sa ti už podarilo vylúštit. Hladaj, ci sa pocas tvojho experimentovania neobjavia slová alebo casti slov. A pokúšaj sa nájst slová alebo frázy, ktoré ocakávaš, že by sa mali objavit (nakolko máš urcité ocakávanie, co správa obsahuje).

Hladaj slová a vety

Ak vidíš zašifrovaný text s medzerami, bodkami a ciarkami, obycajne ide o silnú indikáciu, že správa je zašifrovaná substitucnou šifrou. Hladaj casto sa vyskytujúce slová (napríklad mená, oslovenia, názvy inštitúcií, ...), prípadne sa pozri na jednoznakové slová (v slovencine ich nie je vela - A, I, O, K, S, Z). Pokús sa nahradit tieto písmená a pozoruj, ci sa v texte neobjavujú iné slová.

Urob frekvencnú analýzu

Spocítaj pocetnosti jednotlivých znakov v správe. Dôležité je odhadnút, v akej reci je kódovaná správa, nakolko jednotlivé jazyky majú rozdielne frekvencie jednotlivých znakov. Najfrekventovanejšie znaky v slovencine sú A, O, E, I, ale v iných jazykoch je poradie iné.

Nahrad najcastejšie sa vykytujúci znak písmenom A, další v poradí písmenom O, další písmenom E, atd. Pozri sa, ci niektoré zhluky písmen náhle nezacínajú dávat zmysel. Ak nie, skús zmenit poradie písmen.

(Dobre sa pozri na frekvenciu písmen v slovencine a pokús sa aspon tie na prvých miestach si zapamätat. Táto znalost sa ti môže velmi dobre hodit napríklad pri hraní hry Obesenec.)

Hladaj páry písmen

Ak šifrovaný text obsahuje páry písmen, je to silný náznak toho, že mohla byt použitá šifra Playfair. Taktiež silným signálom je, ak sa medzi pármi nevyskytujú páry s duplicitnými písmenami (ako EE alebo HH), nakolko takéto páry Playfair jednoducho negeneruje. Ak šifrovaný text nie je zoskupený do dvojíc písmen, zgrupuj ho tak sám aby si sa presvedcil, ci sa v nom nachádzajú aj takéto "duplicitné" páry alebo nie.

Hladaj skupiny císiel

Ak tvoj text, ktorý lúštiš, obsahuje dvojice alebo trojice císiel, je možné že bola použitá knižná šifra. Hladaj v listingu akýkolvek náznak, ktorý by mohol prezradit, aký referencný dokument bol použitý.

Informacné zdroje

Velmi dobrým zdrojom je kryptografický portál na wikipédii. Wikipédia má dokonca aj celú samostatnú kategóriu venovanú klasickým šifrám.

Na internete sa dá nájst množstvo bezplatných online nástrojov, ktoré ti vedia výrazne ulahcit tvoju cestu od ciphertextu k plaintextu. Ja používam túto skvelú stránku, ale nepochybujem že pri troche snahy nájdeš množstvo iných.

---

Cvicenie c. 7: Severská láska

Ešte stále neviem, co si mám o tom celom vlastne mysliet.

Jej meno je Ingeborg, dcéra nórskeho velvyslanca. S oficiálnym titulom vojvodkyna je tridsiatasiedma v rade na nasledovníctvo královského trónu.

Naše stretnutie bolo nevinné, obaja sme sa prehrnali vešiakmi s oblecením vo vychytenom znackovom obchode. Nikdy nezabudnem na prvý moment, ked som ju zazrel... jej žiarivé lanové vlasy, úzka tvár, alabastrová pokožka a nákazlivý úsmev. Bola to láska na prvý pohlad pre nás oboch.

Naša posledná schôdzka bola božská... víno (Mocha Java Zinfandel), jedlo (severné Taliansko), dezert (zmrzlinové sundae) ... rozprávali sme sa, jedli sme, smiali sme sa. Po veceri sme spolu zablúdili do miestnych obchodíkov, pretože hladala nový kabát pre svoj plánovaný návrat domov do nórskej zimy. Ruka v ruke pri dlhej prechádzke po pláži sme dokonca fantazírovali o tom, že si raz kúpime spolocný dom.

Ale to bolo už pred celými tromi týždnami a dvoma dnami. Odvtedy sa už neozvala... moje telefonáty nedvíha, na moje SMS-ky, emaily a hlasové odkazy nikdy neprišla žiadna odpoved. Dokonca aj jej úcet na Facebooku už je neaktívny.

Vcera ráno som našiel cudný odkaz, ktorý zjavne niekto v noci strcil medzerou popod dvere. Vonia po jej parfúme a je písaný úhladným rukopisom. Ale nakolko nehovorím nórsky, vôbec tomu odkazu nerozumiem.

WDTNZDF, SNF PSLNPER WD ZQVCNP! WVPTDW EN SRCN ZRTR XED N EYZD N SABDW CVS YONS U SUYGYW ENLAZD. URTWD PN YPOLNURXTEAGRW, BR PD YXY WEN XTQY EROYZAT. NTR WYG YSRZ GRXEYXAZQY ERPAQTNPD P SVW, NCV WTNXN XNWN B FLNTYUPFRQY LYXA WNTN UBSNQ PY PTYUNFYW ERALYXBRERQY OYUYXA. GR NB OLDTDP ABFYPSTDUV! ONWNSNP PD EN SRE XRE, FRX PWR PRXRTD EN OTNBD OYX PSLYWYW N SV PD WD ZDSNT B SUYGQY YCTACRERQY LYWNEA? ERXNTRFY PYW ENPTN WDRPSY, FXR PN WYBRWR PSLRSEAS - XYPSNERP PN SNW TNQFY NASYW, GR SY PDZR SLYZQA EN YZDNZQ, NTR URL WD, EDFSY PD ENP ERCAXR UPDWNS. ZYPFYLY OY SRCN OYPTRW PUYGQY UYXDZN, NF PN WD OYXNLD NPOYE EN ZQUDTA UVFTBEAS B XYQTNXA WYGQY YSZN. UVBXUDQED WN EN FYYLXDENSYZQ, FSYLR OLDONGNW EN FYEDRZ SRGSY POLNUV. N ERBNCAXED EN SA PSNLA DEXDZFA FEDQA TNPFV, Y FSYLRG PD WD SYTFY LYBOLNUNT. WDTAGRW SN, DEJRCYLJ KH KL CA CV DF CU KR PM GK KC SQ OP ZE IT FL MU RD LV SH PC CV DF KC PM HK RT HK FU CK HK EK SH GP CU IT GK WR KC KC SQ OP ZT WK WR KC TH PV HP TI WK CK BL KC WC QI UM CK CV DF

Musím utekat ... niekto práve zdola zazvonil na zvoncek a na príjazdovej ceste parkuje velká cierna limuzína so zatemnenými sklami ... asi to pre mna dobre nevyzerá ... alebo áno?