Šifry a špioni
V dnešním Matematickém koutku se podívám na téma, o kterém jsem diskutoval na každoročním vědeckém táboře pro děti National Children's Foundation. Nadace vyhledává děti a mládež s vědeckými zájmy. Nemusíte být extrémně nadaní, ale musíte mít „vědecký nádech“. Nejsou vyžadovány velmi dobré školní známky. Zkuste to, mohlo by se vám to líbit. Pokud jste studentem vyšší základní školy nebo střední školy, přihlaste se. Hlášení obvykle podávají rodiče nebo škola, ale ne vždy tomu tak je. Najděte si webové stránky nadace a zjistěte to.
Ve škole se stále více mluví o „kódování“, čímž se odkazuje na činnost dříve známou jako „programování“. Toto je běžný postup pro teoretické pedagogy. Vykopou staré metody, dají jim nové jméno a „pokrok“ se dělá sám. Existuje několik oblastí, kde k takovému cyklickému jevu dochází.
Dá se usuzovat, že devalvuji didaktiku. Ne. Ve vývoji civilizace se občas vracíme k tomu, co bylo, bylo opuštěno a nyní se obnovuje. Ale náš kout je matematický, ne filozofický.
Příslušnost k určité komunitě znamená také „společné symboly“, společná čtení, výroky a podobenství. Ten, kdo se dokonale naučil polsky „ve Szczebrzeszyně je velká houština, v rákosí bzučí brouk“, bude okamžitě odhalen jako špión cizího státu, pokud neodpoví na otázku, co dělá datel. Samozřejmě, že se dusí!
To není jen vtip. V prosinci 1944 zahájili Němci s velkými náklady poslední ofenzívu v Ardenách. Mobilizovali vojáky, kteří mluvili plynně anglicky, aby narušili pohyb spojeneckých jednotek, například tím, že je na křižovatkách navedli špatným směrem. Po chvíli překvapení začali Američané klást vojákům podezřelé otázky, na které by člověku z Texasu, Nebrasky či Gruzie odpovídaly a pro někoho, kdo tam nevyrůstal, nepředstavitelné. Neznalost reálií vedla přímo k popravě.
Do té míry. Čtenářům doporučuji knihu Lukasze Badowského a Zaslawa Adamasheka "Laboratoř v zásuvce psacího stolu - Matematika". Je to nádherná kniha, která brilantně ukazuje, že matematika je opravdu k něčemu užitečná a že „matematický experiment“ nejsou prázdná slova. Jeho součástí je mimo jiné popsaná konstrukce „kartonové záhady“ – zařízení, jehož vytvoření nám zabere pouhých patnáct minut a které funguje jako seriózní šifrovací stroj. Nápad sám o sobě byl tak známý, zmínění autoři ho krásně zpracovali a já to trochu pozměním a zahalím do matematickejších šatů.
pily na železo
Na jedné z ulic mé vesničky na předměstí Varšavy byla nedávno demontována dlažba z „trlinky“ – šestihranných dlažebních desek. Jízda byla nepohodlná, ale duše matematika se radovala. Pokrýt rovinu pravidelnými (tedy pravidelnými) polygony není jednoduché. Mohou to být pouze trojúhelníky, čtverce a pravidelné šestiúhelníky.
Možná jsem s tou duchovní radostí trochu žertoval, ale šestiúhelník je krásná postava. Z něj můžete vytvořit poměrně úspěšné šifrovací zařízení. Geometrie pomůže. Šestiúhelník má rotační symetrii - při otočení o násobek 60 stupňů se překrývá. Pole označené např. písmenem A vlevo nahoře Obr. 1 po otočení o tento úhel spadne také do pole A - a to samé s dalšími písmeny. Vystřihneme si tedy z mřížky šest čtverců, každý s jiným písmenem. Takto získanou mřížku dáme na list papíru. Do volných šesti polí zadejte šest písmen textu, který chceme zašifrovat. Otočme list o 60 stupňů. Objeví se šest nových polí - zadejte dalších šest písmen naší zprávy.
Rýže. 1. Trlinky radosti z matematiky.
Vpravo Obr. 1 máme takto zakódovaný text: "Na nádraží stojí obrovská těžká parní lokomotiva."
Nyní se vám bude hodit trocha školní matematiky. Kolika způsoby mohou být dvě čísla vůči sobě uspořádána?
Jaká hloupá otázka? Pro dva: buď jeden vepředu, nebo druhý.
Pokuta. A tři čísla?
Není také těžké vypsat všechna nastavení:
123, 132, 213, 231, 312, 321.
No, je to pro čtyři! Stále se to dá jasně vyjádřit. Hádejte pravidlo objednávky, které jsem zadal:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
Když jsou číslice pět, dostaneme 120 možných nastavení. Zavolejme jim permutace. Počet možných permutací n čísel je součin 1 2 3 ... n, tzv silný a označeno vykřičníkem: 3!=6, 4!=24, 5!=120. Pro další číslo 6 máme 6!=720. Použijeme to, aby byl náš šestiúhelníkový šifrovací štít složitější.
Zvolíme permutaci čísel od 0 do 5, například 351042. Náš šestiúhelníkový míchací disk má ve středním poli pomlčku - aby se dal dát "do nulové polohy" - pomlčku nahoru, jako na obr. 1. Disk takto položíme na list papíru, na který máme napsat naši zprávu, ale nepíšeme ji hned, ale otočíme ji třikrát o 60 stupňů (tedy o 180 stupňů) a zadáme šest písmen v prázdná pole. Vracíme se do výchozí pozice. Číselníkem otočíme pětkrát o 60 stupňů, tedy o pět „zubů“ našeho číselníku. tiskneme. Další pozicí stupnice je pozice otočená o 60 stupňů kolem nuly. Čtvrtá poloha je 0 stupňů, toto je výchozí poloha.
Chápeš, co se stalo? Máme další příležitost – zkomplikovat si svůj „stroj“ více než sedmsetkrát! Máme tedy dvě nezávislé polohy "automatu" - volbu mřížky a volbu permutace. Mřížku lze zvolit 66 = 46656 způsoby, permutace 720. To dává 33592320 možností. Více než 33 milionů šifer! Téměř o něco méně, protože některé mřížky nelze z papíru vystřihnout.
Ve spodní části Obr. 1 máme zprávu zakódovanou takto: "Posílám vám čtyři parašutistické divize." Je snadné pochopit, že nepřítel by o tom neměl vědět. Ale pochopí něco z toho:
ТПОРОПВМАНВЕОРДИЗЗ
YYLOAKVMDEYCHESH,
i s podpisem 351042?
Stavíme Enigmu, německý šifrovací stroj
Rýže. 2. Příklad počátečního nastavení našeho šifrovacího stroje.
Перестановки (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NZ) (PY) (RY).
Jak jsem již zmínil, za myšlenku vytvořit takový kartonážní stroj vděčím knize „Lab in a Drawer - Mathematics“. Moje „konstrukce“ je poněkud odlišná od té, kterou uvedli její autoři.
Šifrovací stroj používaný Němci za války měl geniálně jednoduchý princip, trochu podobný tomu, který jsme viděli u hexadecimální šifry. Pokaždé to samé: přerušit tvrdé přiřazení písmene k jinému písmenu. Musí být vyměnitelné. Jak to udělat, abyste nad tím měli kontrolu?
Zvolme ne jakoukoliv permutaci, ale takovou, která má cykly o délce 2. Jednoduše řečeno něco jako před pár měsíci zde popisovaný „Gaderipoluk“, ale pokrývající všechna písmena abecedy. Domluvme se na 24 písmenech - bez ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Kolik takových permutací? To je úkol pro maturanty (měli by to hned umět vyřešit). Kolik? Hodně? Několik tisíc? Ano:
1912098225024001185793365052108800000000 (toto číslo se ani nepokoušejme číst). Možností nastavení „nulové“ polohy je tolik. A to může být těžké.
Náš stroj se skládá ze dvou kruhových kotoučů. Na jednom z nich, který stále stojí, jsou napsána písmena. Je to trochu jako ciferník starého telefonu, kde jste vytočili číslo otočením ciferníku až na doraz. Rotary je druhý s barevným schématem. Nejjednodušší způsob je nasadit je na běžný korek pomocí špendlíku. Místo korku můžete použít tenkou desku nebo silnou lepenku. Lukasz Badowski a Zasław Adamaszek doporučují umístit oba disky do CD boxu.
Představte si, že chceme zakódovat slovo ARMATY (Rýže. 2 a 3). Nastavte zařízení do nulové polohy (šipka nahoru). Písmeno A odpovídá F. Otočte vnitřní obvod o jedno písmeno doprava. Máme písmeno R ke kódování, nyní odpovídá A. Po dalším otočení vidíme, že písmeno M odpovídá U. Další otočení (čtvrtý diagram) dává korespondenci A - P. Na pátém číselníku máme T - A. Konečně (šestý kruh) Y – Y Nepřítel pravděpodobně neuhodne, že pro něj budou naše CFCFA nebezpečné. A jak budou „naši“ číst zásilku? Musí mít stejný stroj, stejně „naprogramovaný“, tedy se stejnou permutací. Šifra začíná na pozici nula. Hodnota F je tedy A. Otáčejte kolečkem ve směru hodinových ručiček. Písmeno A je nyní spojeno s R. Otočí ciferníkem doprava a pod písmenem U najde M atd. Šifrovač běží ke generálovi: "Generále, hlásím se, jdou zbraně!"
Rýže. 3. Princip fungování naší papírové Enigmy.
| Rýže. 3. Princip fungování naší papírové Enigmy. | ||
Možnosti i tak primitivní Enigmy jsou úžasné. Můžeme zvolit jiné výstupní permutace. Můžeme – a je zde ještě více příležitostí – ne jednou „patkou“ pravidelně, ale v určitém, denně se měnícím pořadí, podobném šestiúhelníku (například nejprve tři písmena, pak sedm, pak osm, čtyři ... .. atd..).
Jak můžeš hádat?! A přesto pro polské matematiky (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) Stalo. Takto získané informace byly neocenitelné. Dříve měly neméně důležitý příspěvek do historie naší obrany. Václav Serpinski i Stanislav Mazurkevičkterý v roce 1920 porušil kodex ruských vojsk. Zachycený kabel dal Piłsudskému příležitost provést slavný manévr z řeky Vepsz.
Vzpomínám na Václava Sierpinského (1882-1969). Vypadal jako matematik, pro kterého vnější svět neexistuje. O své účasti na vítězství v roce 1920 nemohl hovořit jak z vojenských, tak...z politických důvodů (orgány Polské lidové republiky neměly rády ty, kteří nás bránili před Sovětským svazem).
Rýže. 4. Permutace (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Rýže. 5. Krásná dekorace, ale nehodí se k šifrování. Příliš pravidelně.
1 úloha. Na Obr. 4 máte další permutaci k vytvoření Enigmy. Zkopírujte výkres do xerografu. Postavte auto, zadejte své jméno a příjmení. Můj CWONUE JTRYGT. Pokud potřebujete, aby byly vaše poznámky soukromé, použijte Cardboard Enigma.
2 úloha. Zašifrujte své jméno a příjmení jednoho z „aut“, které jste viděli, ale (pozor!) s další komplikací: neotočíme se o jeden zářez doprava, ale podle schématu {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - tedy nejprve po jedničce, pak po dvou, pak po třech, pak po 2, pak zase po 1, pak po 2 atd., taková „vlnka“ . Ujistěte se, že mé jméno a příjmení jsou zašifrovány jako CZTTAK SDBITH. Už chápete, jak silný byl stroj Enigma?
Řešení problémů pro absolventy středních škol. Kolik možností konfigurace pro Enigmu (v této verzi, jak je popsáno v článku)? Máme 24 písmen. Vybereme první dvojici písmen - to lze provést na
způsoby. Další pár lze vybrat na
způsoby, více
atd. Po odpovídajících výpočtech (všechna čísla je třeba vynásobit) dostaneme
151476660579404160000
Pak toto číslo vydělte 12! (12 faktoriálů), protože stejné páry lze získat v jiném pořadí. Takže nakonec dostaneme "totální"
316234143225,
to je něco málo přes 300 miliard, což se na dnešní superpočítače nezdá jako ohromující číslo. Pokud se však vezme v úvahu náhodné pořadí samotných permutací, toto číslo výrazně naroste. Můžeme uvažovat i o jiných typech permutací.
Viz též:
