00000001 - Jednoduchá kalkulačka
00000010 - Odebírání zápalek
00000100 - Gregoriánský kalendář
00001000 - Hádání kombinace
00010000 - Vigenérova šifra
00100000 - Hledání min
01000000 - Házení kostkou
10000000 - Conway's Game of Life
Minulý bit Malé hry o Velkého Bajta moc účastníků nepřitáhl, doufám že ne pro svoji nevelkou obtížnost, ale spíš proto že se kolem nás děje hromada zajímavějších věcí, než je společenská stolní hra vyžadující logické uvažování. Spousta těch zajímavostí naopak jakoukoliv logiku popírá, ba často i vylučuje. Politici ve jménu boje proti terorizmu volají po zpřísnění podmínek a nejlépe zákazu šifrování, a vesele ignorují skutečnost že pařížští vrazi žádné šifrování nepoužívali, nehledě na to že ve Francii je už dávno zakázané. Stejně tak volají po zvýšení rozpočtů tajných služeb, kterým ale v posledních letech rozpočty prudce rostly, jenom se to jaksi neprojevilo na jejich výkonech, natož schopnostech. A volají i po dalších zákazech a nařízeních, jaké nebyly běžné ani v nejhorších totalitních režimech minulosti, jako by jejich největší touhou bylo terorizovat vlastní voliče...
Takže, co provést, aby naše dopisy či maily nečetl každý úchyl a fízl, kterému se dostanou do jeho předlouhých a nikým nekontrolovaných pařátů? Musíme pro to udělat trochu víc než jenom říct:
Nešmíruj, šmíráku!
Například je potřeba umět svojí korespondenci zašifrovat a také rozšifrovat. Dnes s počítači, tablety a mobily chytřejšími než jejich uživatelé je to celkem jednoduché, ale může se stát že žádný takový přístroj zrovna nebude po ruce, nebo ho nebude možné z jakéhokoliv důvodu použít, a tak je potřeba umět nějakou šifru používat jenom s tužkou a papírem. Pro to se moderní počítačové šifry vůbec nehodí, je potřeba sáhnout trochu hlouběji do historie.
Nejrůznější tajná písma, číselné kódy a chlívkové šifry používané ke hrám na dětských táborech je možné rovnou zavrhnout, protože k ničemu jinému než dětskému hraní se nehodí. Stejně špatně je na tom i slavná Caesarova šifra, vyskytující se dnes v "důvěrné" komunikaci na některých internetových fórech v obměně zvané ROT13:
Kód: Vybrat vše
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
Je to prostě abeceda přestřižená napůl, a složená pod sebe, odpovídá tak Caesarově šifře s posunem 13. Při šifrování nebo dešifrování se písmeno z jenoho řádku nahradí písmenem z druhého. ROT13 se vzdáleně podobá starověké šifře Atbaš, vyskytující se v hebrejských svitcích, ta se liší tím že ta přestřižená abeceda není posunutá pod sebe, ale zlomená napůl:
Kód: Vybrat vše
ABCDEFGHIJKLM
ZYXWVUTSRQPON
Říká se tomu odborně reciproká abeceda, použití šifry je stejné jako v minulém případě. Obrácení pořadí písmen má jednu velkou výhodu, zatímco při běžném pořadí jsou pro šifrování a dešifrování potřeba dva různé procesy, u reciprokých šifer stačí jenom jeden, protože dochází k zrcadlovému efektu. Tím se zjednoduší používání a sníží se také riziko chyb šifranta.
Bezpečnost takhle jednoduchých šifer je velmi nízká, Caesarova šifra podlehla arabským luštitelům už v devátém století, ti evropští měli za nimi jenom 400 let zpoždění. Kteroukoliv substituční monoalfabetickou šifru (takovou kde se jedna abeceda nahrazuje druhou) je možné pomocí počítače zlomit za pár tisícin sekundy.
Další možností utajení zprávy je zpřeházení písmen textu podle domluveného klíče. Existuje spousta transpozičních šifer, od psaní pozpátku přes kryptex, otočné a překlápěcí šifrovací mřížky, všelijaké míchání sloupců a řádků, až k moderním matematickým variacím jako je americký DES, ale ty, které jsou použitelné kdekoliv v terénu, by počítači neodolaly déle než pár minut. Daní za jejich rostoucí složitost by mohlo být i několikahodinové ruční luštění, což je velmi otravná práce s velkou pravděpodobností chyb. Takže tudy cesta také nevede.
Už někdy ve čtrnáctém století se objevila myšlenka, která způsobila šifrovací revoluci - použití více šifrových abeced. Nejdřív dvě, pak čtyři, potom třináct, což už je půlka abecedy, a ve století šestnáctém konečně došlo k použití stejného počtu šifrových abeced, jako má abeceda písmen! Popsal jí ve své knize francouzský diplomat Blaise de Vigenére, který sice nebyl jejím vynálezcem, ale jak už to bývá, je s ní spojován dodnes a šifra nese jeho jméno. Po několik staletí byla považována za nerozluštitelnou, a také se tak nazývala: Vigenérova šifra - Le Chiffre Indéchiffrable.
Vrcholem polyalfabetických šifer byla šifra Vernamova, která vznikla na konci První světové války, a která je jedinou šifrou s matematicky prokázanou nerozluštitelností. Ta byla také první, kterou používaly telekomunikační stroje - dálnopisy. V Německu o málo později vznikl slavný šifrovací stroj Enigma, který používá několikanásobné polyalfabetické šifrování, ale jeho systém byl poměrně brzy prolomen polskými matematiky, což přispělo k rychlejší porážce nacistického režimu.
Pro strojní šifry je potřeba šifrovací přístroj, ale ten je problém přenášet a ukrýt před zvědavci (Enigma byl kufr těžký dvanáct kilogramů), což je vylučuje z našeho okruhu. Pomůcky pro šifrování je také potřeba nenápadně ukrýt, nebo jimi musí být úplně běžné předměty, které u sebe může mít každý, aniž by vzbudily podezření.
A proto právě Vigenérova šifra je úkolem pro bit 00010000.
Pro její používání stačí pouze tužka a papír, šifrovací tabulku je možné mít složenou třeba v peněžence nebo se dá během chvilky vytvořit kdykoliv je potřeba, a také je jí možno nahradit šifrovacím diskem, který americká armáda používala od dob Občanské války až po Druhou světovou. Tohle je můj osobní, s vnitřním kotoučem otočeným na stranu s reciprokou abecedou:
V té době sice už dávno existovala metoda pro její rozluštění, ale byla to velmi zdlouhavá a náročná činnost. Jako první jí objevil anglický matematik Charles Babbage, vynálezce prvního programovatelného počítače. Princip šifrování je jednoduchý, odesílatel i příjemce mají smluvené heslo, kterým se text zprávy zašifruje. Heslo bývá slovo nebo věta, která se dobře pamatuje, a pro celou zprávu se neustále opakuje. To opakování je slabé místo Vigenérovy šifry. Pro ukázku použijeme heslo OKURKA:
Kód: Vybrat vše
heslo: OKUR KAO K URKAOKU RKAOK
text: MALÁ HRA O VELKÉHO BAJTA
Mezery se přeskakují a v šifrovaném textu úplně vynechávají, aby případnému luštiteli neusnadňovaly práci. Pro šifrování je potřeba výše zmíněná tabulka:
Postup šifrování/dešifrování je jednoduchý:
- Podle písmene hesla vybereme v tabulce správný řádek.
- Najdeme na něm písmeno textu, a z horního obráceného řádku ve stejném sloupci opíšeme písmeno šifry.
Písmeno hesla určuje o kolik bude šifrová abeceda posunutá vůči skutečné:
První písmeno hesla je O, první písmeno zprávy je M, tomu odpovídá zašifrované písmeno B.
Druhé písmeno hesla je K, druhé písmeno zprávy je A, tomu odpovídá zašifrované písmeno J.
Třetí písmeno hesla je U, třetí písmeno zprávy je L, tomu odpovídá zašifrované písmeno I:
Kód: Vybrat vše
OKUR KAO K URKAOKU RKAOK
MALÁ HRA O VELKÉHO BAJTA
BJI...
A tak to děláme pořád dokola, písmenko po písmenku, až zašifrujeme celou zprávu. Také je možné písmeno textu najít v horním obráceném řádku a písmeno šifry ve vybraném, díky reciprokému pořadí je to v obou případech stejná dvojice (na rozdíl od původní Vigenérovy šifry s abecedami v přirozeném pořadí). Pro urychlení práce lze celou zprávu rozepsat pod jednou napsané heslo, a šifrovat jí po sloupcích, vždy podle stejného písmena hesla. Není ho tak potřeba hledat znovu při každém opakování:
Kód: Vybrat vše
OKURKA O...
------ ------
MALÁHR B
AOVELK N
ÉHOBAJ J
TA U
Již zašifrovaný sloupec otevřeného textu je dobré pro přehlednost proškrtnout, aby se nám už nepletl. Po zašifrování se celá zpráva opět opíše po řádcích a vyjde stejný kód jako při předchozím postupu. Dešifrování proběhne zase úplně stejně, vlastně se při něm šifrovaný text ještě jednou zašifruje stejným heslem, a tím se opět odkryje. Díky tomu se program pro počítač velmi zjednoduší, protože nemusí umět dvě různé činnosti, ale vystačí jenom s jednou.
Vigenérova šifra není neprolomitelná, ale je možné jí použít na kratší zprávy, při dodržení několika pravidel:
- Heslo musí být dostatečně dlouhé aby se opakovalo co nejméně, v ideálním případě stejně dlouhé jako je zpráva, mělo by být složené z náhodných znaků a neobsahovat existující slova.
- Žádné heslo se nikdy nesmí použít dvakrát, protože porovnáním dvou zpráv zašifrovaných stejným heslem je možné i bez znalosti jejich obsahu to heslo odhalit, a obě zprávy potom rozšifrovat.
- Ani zpráva se nesmí zašifrovat dvakrát různým heslem, protože stejně jako v předchozím případě je možné porovnáním odhalit původní zprávu i bez znalosti těch hesel.
Takže úkol tohoto kola je napsat program, který bude šifrovat heslem, podle reciproké tabulky, Vigenérovou šifrou. Musí dodržet několik zásad, aby různé programy stejné zprávy zašifrovaly stejně:
- Mezery a veškeré bílé znaky se vynechávají, jako by neexistovaly.
- Jiné znaky v textu, které nejsou v šifrovací tabulce (třeba číslice, otazník, vykřičník...), se nešifrují, ale ponechají tak jak jsou.
- Písmena s diakritikou se buď převedou na písmena bez diakritiky, nebo se berou jako znaky které nejsou v tabulce, viz předchozí bod (jak kdo uzná za vhodné).
- Heslo může obsahovat pouze znaky které jsou v tabulce (takže ABCDEFGHIJKLMNOPQRSTUVWXYZ nebo abcdefghijklmnopqrstuvwxyz), ostatní se vyhází.
- Text se po zašifrování/dešifrování vypisuje ve "slovech" po pěti písmenech, aby se dal snadno a bez chyb opsat z papíru nebo na papír. A bylo by dobré tuhle nudli občas zalomit na další řádek, třeba na šířku stránky (80 sloupců).
Jsem zvědavý, kdo dokáže jako první rozluštit tenhle text:
Kód: Vybrat vše
WIWTP QNJHD S,UCA BQQKE WZYVN I,YGE HSDLJ NLHYW CNGMS XEJ,O TBUDZ LVRSX YRSBO XVBBI QA,FT XEOHV
WICPG RFUZF ICQGU SHYSI YVBZW CAECP QWDSM JZJEE JV.WG XZAUL GOZHK WQQKW HQLMG EWAQL KVART IGVSN
YZSVL YGTFQ CBIIV HFTFR JSMYI ,QNKP LBRIZ XKUYH SRYVL IMFKJ YRIGK NBWKO XTCXW SNFGC PVAI. NVOXV
IMKHL MADJD YJQYN BYIXM LHXZR MGZZF ICMGO G,VOY XGREM HQJCK KYXSW SGWYH DZVOY GZLQV TFLCA S,JSX
NPZVT MZOHD PFTIS WPOX. UVRFP D.
Heslo je "Mala hra o velkeho Bajta".