O šifře
Původ této šifry je poněkud zastřen tajemstvím, neboť její autor není znám. Jistě víme jen to, že první zmínka o této šifře se v literatuře objevuje v roce 1983 v knize Elements of Cryptology autorů M. Davia a J. M. Goethalse, a následně také v knize Secure Digital Communications od G. Longa. Obě publikace ovšem obsahují především její matematický popis.
Podle všeho se tedy jedna spíše než o praktickou a v historii skutečně uživánou šifru především o matematický konstrukt sloužící k výuce kryptografie. Jak uvidíme dále, je to matematický konstrukt velmi užitečný, neboť v jeho popisu lze v nějaké podobě nalézt zobecnění některých dalších substitučních šifer.
Jejím základem je převod otevřeného textu do šifrované zprávy pomocí jednoduché lineární rovnice o třech proměnných (z nichž jedna proměnná je částečně závislá na druhé). Tato rovnice má obecný tvar:
E(x) = (a · x + b) mod m
Kde výraz E(x) vyjadřuje, zašifrovaný znak x, a (a · x + b) je běžný matematický výraz, jehož hodnota se vyjádří jako a násobené x (což je číselná hodnota písmene otevřené zprávy) a k výsledku přičteným b.
Méně známý je operátor mod tedy modulo, který nám v této rovnici vystupuje jako část mod m, kde m je velikost abecedy. Operátor modulo je pak zbytek po celočíselném dělení. Z praktických důvodů se celočíslené dělení odlišuje použitím jiného znaku pro operátor dělení a stalo se zvykem používat znak %. Tato zvyklost je dodržena i v následujícím textu.
Například pro podíl 10 % 3 = 3, zbytek 1. Právě tento zbytek je hodnotou modulo. Lze tedy napsat, že 10 mod 3 = 1. Podobně například 17 mod 5 = 2, neboť 17 % 5 = 3, zbytek 2 a tedy 3 · 5 = 15 + zbytek 2 = 17.
Důležitou okolností výše zmíněné rovnice je vztah mezi hodnotami m a a, které by měly být zvoleny jako nesoudělná čísla.
Nesoudělná čísla jsou taková čísla, která nemají více než jednoho společného dělitele tzn. 1. Například pro čísla 26 (velikost anglické abecedy) a 5 stanovíme soudělnost takto: 26 je beze zbytku dělitelné 1, 2, 13 a 26; 5 je dělitelné 1 a 5; čísla 26 a 5 jsou tedy nesoudělná, neboť kromě 1 nemají žádného společného dělitele.
A proč je to vlastně důležité? Souvisí to s počtem možností převodu znaků otevřeného textu do šifrované zprávy. Pokud by byla čísla soudělná, nemuselo by být možné zašifrovaný text opět rozšifrovat, neboť by existovalo více možností jak převést znaky zašifrované zprávy zpět do otevřeného textu.
Velikost abecedy může být různá. Pro angličtinu platí typicky velikost abecedy 26, nebo s čísly 26 + 10 = 36 znaků. Pokud zahrneme i varianty velkých a malých písmen bude to 2 · 26 + 10 = 62 znaků. Například velká česká abeceda disponuje 42 znaky + 10 čísly, tedy celkově 52 znaky. Proč jich má tolik? Především kvůli nabodeníčkům jako jsou čárky, háčky a kroužek, a oproti řadě jiných jazyků obsahuje písmeno Ch.
Abeceda se pro účely afinní šifry (obvykle) čísluje od nuly. Pro češtinu tedy může vypadat např. takto:
A Á B C Č D Ď E É Ě F G H CH I Í J K L M N Ň O Ó P Q
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
R Ř S Š T Ť U Ů V W X Y Ý Z Ž 0 1 2 3 4 5 6 7 8 9
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Za povšimnutí stojí fakt, že tato verze české abecedy nezahrnuje písmeno Ú, čímž místo 52 znakové abecedy dostáváme abecedu 51 znakovou. To nám dává větší volnost pro volbu čísla a, neboť 51 je dělitelné čísly 1, 3, 17 a 51, zatímco číslo 52 je dělitelné 1, 2, 4, 13, 26 a 52.
Pokud tedy budeme chtít afinní šifrou zašifrovat například otevřený text ŽLUŤOUČKÝ KŮŇ a zvolíme si a = 7 a b = 5, bude postup šifrování vypadat takto:
Otevřený text Ž L U Ť O U Č K Ý K Ů Ň
Číslo podle abecedy 40 18 32 31 22 32 4 17 38 17 33 21
Zašifrované číslo 30 29 25 18 6 25 33 22 16 22 32 50
Zašifrovaný text t š q l ď q ů o j o u 9
Například pro první písmeno otevřeného textu Ž (které má ve zvolené abecedě hodnotu 40) vypadá výpočet následovně:
E(x) = (a · x + b) mod m
E(40) = (7 · 40 + 5) mod 51
E(40) = 285 mod 51
E(40) = 30
Hodnota 30 odpovídá ve zvolené abecedě písmenu t.
Postup dešifrování se pak řídí inverzní matematickou funkcí, která je zde ovšem poněkud ztížena ireverzibilní povahou operátoru modulo. Dešifrování proto probíhá s pomocí výrazu:
D(x) = c · (x - b) mod m
Konstanta c je tzv. modulární multiplikativní inverze. Za tímto lehce děsivým názvem se skrývá číslo, které splňuje rovnici 1 = (c · a) mod m. Pro naši abecedu o velikosti m = 51 a zvolená čísla a = 7 a b = 5 je to hodnota 22. A skutečně (22 · 7) mod 51 = 1.
Pokud je autorovi známo, neexistuje žádný obecný analytický postup, který by umožňoval konstantu c přímo vypočítat. Numerický postup vyžaduje trochu trpělivosti a zkoušení, které z čísel je to pravé. V dnešní době počítačů s tabulkovými kalkulátory je však jeho odhad hrubou silou otázkou chvíle přemýšlení a správně formulovaného vzorečku (obvykle něco jako "=MOD(Z*A; M)", kde Z je zkoušené číslo) aplikovaného na číselnou řadu od 1 do m. To číslo Z, pro které výjde hodnota 1 je hledané číslo c. S pomocí c pak můžeme výpočet otočit podle přechozího výrazu, což bude vypadat takto:
Zašifrovaný text t š q l ď q ů o j o u 9
Zašifrované číslo 30 29 25 18 6 25 33 22 16 22 32 50
Číslo podle abecedy 40 18 32 31 22 32 4 17 38 17 33 21
Otevřený text Ž L U Ť O U Č K Ý K Ů Ň
Například pro první písmeno šifrovaného textu t (které má ve zvolené abecedě hodnotu 30) vypadá výpočet následovně:
D(x) = c · (x - b) mod m
D(30) = 22 · (30 - 5) mod 51
D(30) = 550 mod 51
D(30) = 40
Hodnota 40 odpovídá ve zvolené abecedě písmenu Ž.
Tato šifra je matematickým zobecněním některých monoalfabetických substitučních schémat. Například nastavíme-li a = 1, pak získáme Caesarovu šifru, neboť klíčem bude posun o b znaků, tedy E(x) = (x + b) mod m. Podobně nastavením a = -1 a b = 0 získáme matematický předpis pro šifru Atbaš, tedy E(x) = (-1 · x) mod m.
Vzhledem k tomuto faktu sdílí s uvedenými šiframi i všechny nevýhody, tedy především snadnou prolomitelnost frekvenční analýzou a v případě dešifrování dvou a více zpráv zašifrovaným stejnou sadou klíčů (tedy hodnot a a b) je možné vyřešením soustavy rovnic dospět přímo k sadám hodnot klíčů. Stejný vzorec se používá také v nejjednodušších generátorech pseudonáhodných čísel tzv. Lineárních kongruentálních generátorech, které ovšem díky tomu nejsou dnes použivány jako kryptograficky bezpečné.
O keši
Pro získání souřadnic keše bude potřeba rozluštit následující šifru. Použitá abeceda je výše uvedená varianta české abecedy (pozor na písmeno Ch a záměnu písmen malého L a 1 (jedničky)!).
Číslo a je počet všech mostů a lávek pro pěší a cyklisty, které na území (katastru) města Rožnova pod Radhoštěm spojují oba břehy řeky Bečvy sečteno s počtem kostelů (libovolného vyznání) na tomtéž území. Číslo b je absolutní hodnota rozdílu nadmořských výšek kopců Klúzov a Kozinec v metrech. Oba údaje lze bez obtíží zjistit například s pomocí OpenStreetMap.org.
Po jejím vyluštění získáte heslo, které zadáte na stránce http://gc.rozen.cz/GC93J87. Pokud bude správně, dostanete souřadnice finálky a hint pro hledání.
athoávghuvn4uůťchchžovůvž1vá
Přeji hodně trpělivosti při luštění a štěstí při lovu!
Za betatest děkuji kvetos007.
Zdroje
Součást série Historie šifer
Tato keš vznikla jakou součást série věnované historii šifrování. Keše jsou nejen exkurzí do principu fungování a okolností vzniku nejvýznamnějších šifer, ale také výzvou k jejich vyřešení, která vás dovede na zajímavá místa v širším okolí Rožnovské Bečvy.