Šifry a špióni

V dnešnom matematickom kútiku sa pozriem na tému, o ktorej som diskutoval na každoročnom vedeckom tábore pre deti National Children's Foundation. Nadácia hľadá deti a mládež s vedeckými záujmami. Nemusíte byť extrémne nadaný, ale musíte mať „vedecký nádych“. Nevyžadujú sa veľmi dobré známky v škole. Vyskúšajte, možno sa vám bude páčiť. Ak ste študentom vyššej základnej školy alebo strednej školy, prihláste sa. Správy zvyčajne podávajú rodičia alebo škola, ale nie vždy to tak je. Nájdite webovú stránku nadácie a dozviete sa.

V škole sa čoraz viac hovorí o „kódovaní“, pričom sa odkazuje na činnosť predtým známu ako „programovanie“. Toto je bežný postup pre teoretických pedagógov. Vykopú staré metódy, dajú im nové meno a „pokrok“ sa robí sám. Existuje niekoľko oblastí, kde sa takýto cyklický jav vyskytuje.

Dá sa usúdiť, že devalvujem didaktiku. nie Vo vývoji civilizácie sa občas vraciame k tomu, čo bolo, bolo opustené a teraz sa znovu oživuje. Ale náš kútik je matematický, nie filozofický.

Príslušnosť k určitej komunite znamená aj „spoločné symboly“, spoločné čítania, výroky a podobenstvá. Ten, kto sa dokonale naučil poľský jazyk „v Szczebrzeszyne je veľká húština, v rákosí bzučí chrobák“, bude okamžite odhalený ako špión cudzieho štátu, ak neodpovie na otázku, čo robí ďateľ. Samozrejme, že sa dusí!

Toto nie je len vtip. V decembri 1944 začali Nemci s veľkými nákladmi poslednú ofenzívu v Ardenách. Zmobilizovali vojakov, ktorí hovorili plynulou angličtinou, aby narušili pohyb spojeneckých jednotiek, napríklad ich naviedli nesprávnym smerom na križovatkách. Po chvíli prekvapenia začali Američania klásť vojakom podozrivé otázky, odpovede na ktoré by boli pre človeka z Texasu, Nebrasky či Gruzínska zrejmé a pre niekoho, kto tam nevyrastal, nepredstaviteľné. Neznalosť reálií viedla priamo k poprave.

K veci. Čitateľom odporúčam knihu Lukasza Badowského a Zaslawa Adamasheka "Laboratórium v ​​zásuvke stola - matematika". Je to úžasná kniha, ktorá brilantne ukazuje, že matematika je naozaj na niečo užitočná a že „matematický experiment“ nie sú prázdne slová. Jeho súčasťou je okrem iného aj opísaná konštrukcia „kartónovej záhady“ – zariadenia, ktorého vytvorenie nám zaberie len pätnásť minút a ktoré funguje ako seriózny šifrovací stroj. Samotný nápad bol taký známy, spomínaní autori ho krásne rozpracovali a ja ho trochu pozmením a zabalím do matematickejších šiat.

píly na železo

Na jednej z ulíc mojej dachovej dediny na predmestí Varšavy bol nedávno demontovaný chodník z „trlinky“ – šesťhranných dlažobných dosiek. Jazda bola nepríjemná, ale duša matematikára sa tešila. Pokryť rovinu pravidelnými (t. j. pravidelnými) polygónmi nie je jednoduché. Môžu to byť iba trojuholníky, štvorce a pravidelné šesťuholníky.

Možno som trochu žartoval s touto duchovnou radosťou, ale šesťuholník je krásna postava. Z toho môžete vytvoriť pomerne úspešné šifrovacie zariadenie. Pomôže geometria. Šesťuholník má rotačnú symetriu – pri otočení o násobok 60 stupňov sa prekrýva. Pole označené napríklad písmenom A vľavo hore obr. 1 po otočení cez tento uhol spadne aj do políčka A - a to isté s ostatnými písmenami. Vystrihneme si teda z mriežky šesť štvorcov, každý s iným písmenom. Takto získanú mriežku dáme na list papiera. Do voľných šiestich polí zadajte šesť písmen textu, ktorý chceme zašifrovať. Otočme list o 60 stupňov. Objaví sa šesť nových polí - zadajte ďalších šesť písmen našej správy.

Ryža. 1. Trlinky radosti z matematiky.

Vpravo obr. 1 máme takto zakódovaný text: "Na stanici je obrovská ťažká parná lokomotíva."

Teraz príde vhod trocha školskej matematiky. Koľkými spôsobmi možno vzájomne usporiadať dve čísla?

Aká hlúpa otázka? Pre dvoch: buď jeden vpredu, alebo druhý.

Dobre. A tri čísla?

Nie je ťažké uviesť všetky nastavenia:

123, 132, 213, 231, 312, 321.

No je to pre štyroch! Stále sa to dá jasne formulovať. Hádajte pravidlo objednávky, ktoré som dal:

1234, 1243, 1423, 4123, 1324, 1342,

1432, 4132, 2134, 2143, 2413, 4213,

2314, 2341, 2431, 4231, 3124, 3142,

3412, 4312, 3214, 3241, 3421, 4321

Keď sú číslice päť, dostaneme 120 možných nastavení. Zavolajme im permutácií. Počet možných permutácií n čísel je súčin 1 2 3 ... n, tzv silný a označené výkričníkom: 3!=6, 4!=24, 5!=120. Pre ďalšie číslo 6 máme 6!=720. Použijeme to na to, aby bol náš hexagonálny šifrovací štít zložitejší.

Zvolíme permutáciu čísel od 0 do 5, napríklad 351042. Náš šesťhranný miešací disk má v strednom poli pomlčku - aby sa dal dať "do nulovej polohy" - pomlčku hore, ako na obr. 1. Disk takto položíme na list papiera, na ktorý máme napísať našu správu, ale nepíšeme ju hneď, ale otočíme ju trikrát o 60 stupňov (teda o 180 stupňov) a zadáme šesť písmen v prázdne polia. Vraciame sa do východiskovej polohy. Ciferník otočíme päťkrát o 60 stupňov, teda o päť „zúbkov“ nášho ciferníka. Tlačíme. Ďalšia poloha stupnice je poloha otočená o 60 stupňov okolo nuly. Štvrtá poloha je 0 stupňov, toto je východisková poloha.

chápeš čo sa stalo? Máme možnosť navyše – skomplikovať si našu „mašinku“ viac ako sedemstonásobne! Máme teda dve nezávislé polohy "automatu" - výber mriežky a výber permutácie. Mriežku je možné zvoliť 66 = 46656 spôsobmi, permutácia 720. To dáva 33592320 možností. Viac ako 33 miliónov šifier! Takmer o niečo menej, pretože niektoré mriežky sa nedajú vystrihnúť z papiera.

V spodnej časti obr. 1 máme zakódovanú správu takto: "Posielam vám štyri výsadkové divízie." Je ľahké pochopiť, že nepriateľ by sa o tom nemal dozvedieť. Ale pochopí niečo z tohto:

ТПОРОПВМАНВЕОРДИЗЗ

YYLOAKVMDEYCHESH,

aj s podpisom 351042?

Budujeme Enigmu, nemecký šifrovací stroj

Ryža. 2. Príklad počiatočného nastavenia nášho šifrovacieho stroja.

Permutácie (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Ako som už spomenul, za myšlienku vytvorenia takéhoto kartónového stroja vďačím knihe „Laboratórium v ​​zásuvke - Matematika“. Moja „konštrukcia“ sa trochu líši od tej, ktorú uvádzajú jej autori.

Šifrovací stroj používaný Nemcami počas vojny mal geniálne jednoduchý princíp, trochu podobný tomu, ktorý sme videli pri hexadecimálnej šifre. Zakaždým to isté: prelomiť tvrdé priradenie písmena k druhému písmenu. Musí byť vymeniteľné. Ako to urobiť, aby ste to mali pod kontrolou?

Vyberme si nie hocijakú permutáciu, ale takú, ktorá má cykly dĺžky 2. Zjednodušene povedané, niečo ako „Gaderipoluk“ popísaný tu pred pár mesiacmi, ale pokrývajúci všetky písmená abecedy. Dohodnime sa na 24 písmenách – bez ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Koľko takýchto permutácií? Toto je úloha pre maturantov (mali by ju vedieť hneď vyriešiť). Koľko? Veľa? Niekoľko tisíc? Áno:

1912098225024001185793365052108800000000 (toto číslo ani neskúšajme čítať). Možností nastavenia „nulovej“ polohy je toľko. A môže to byť ťažké.

Náš stroj sa skladá z dvoch okrúhlych kotúčov. Na jednom z nich, ktorý ešte stojí, sú napísané písmená. Je to trochu ako ciferník starého telefónu, kde ste vytáčali číslo úplným otočením ciferníka. Rotary je druhý s farebnou schémou. Najjednoduchšie je navliecť ich na obyčajný korok pomocou špendlíka. Namiesto korku môžete použiť tenkú dosku alebo hrubú lepenku. Lukasz Badowski a Zasław Adamaszek odporúčajú vložiť oba disky do CD boxu.

Predstavte si, že chceme zakódovať slovo ARMATY (Ryža. 2 a 3). Nastavte zariadenie do nulovej polohy (šípka hore). Písmeno A zodpovedá F. Otočte vnútorný obvod o jedno písmeno doprava. Máme písmeno R na zakódovanie, teraz zodpovedá A. Po ďalšom otočení vidíme, že písmeno M zodpovedá U. Ďalšie otočenie (štvrtý diagram) dáva korešpondenciu A - P. Na piatom číselníku máme T - A. Nakoniec (šiesty kruh) Y – Y Nepriateľ pravdepodobne neuhádne, že naše CFCFA budú pre neho nebezpečné. A ako budú „naši“ čítať zásielku? Musia mať rovnaký stroj, rovnako „naprogramovaný“, teda s rovnakou permutáciou. Šifra začína na pozícii nula. Hodnota F je teda A. Otočte ovládač v smere hodinových ručičiek. Písmeno A je teraz spojené s R. Otočí ciferník doprava a pod písmenom U nájde M atď. Šifrovač beží ku generálovi: "Generál, hlásim sa, idú zbrane!"

Ryža. 3. Princíp fungovania našej papierovej Enigmy.

Ryža. 3. Princíp fungovania našej papierovej Enigmy.

Možnosti aj takejto primitívnej Enigmy sú úžasné. Môžeme zvoliť iné výstupné permutácie. Môžeme - a je tu ešte viac príležitostí - nie pravidelne jednou „pätkou“, ale v určitom, denne sa meniacom poradí, podobne ako šesťuholník (napríklad najskôr tri písmená, potom sedem, potom osem, štyri ... .. atď..).

Ako môžeš hádať?! A predsa pre poľských matematikov (Marián Reevski, Henryk Žigalski, Jerzy Ruzicki) Stalo. Takto získané informácie boli neoceniteľné. Predtým mali nemenej dôležitý vklad do histórie našej obrany. Václav Serpinski i Stanislav Mazurkevičktorý v roku 1920 porušil kódex ruských vojsk. Zachytený kábel dal Piłsudskému príležitosť urobiť slávny manéver z rieky Vepsz.

Pamätám si na Václava Sierpinského (1882-1969). Pôsobil ako matematik, pre ktorého vonkajší svet neexistuje. O svojej účasti na víťazstve v roku 1920 nemohol hovoriť tak z vojenských, ako aj z politických dôvodov (orgány Poľskej ľudovej republiky nemali radi tých, ktorí nás bránili pred Sovietskym zväzom).

Ryža. 4. Permutácia (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Ryža. 5. Krásna dekorácia, ale nie je vhodná na šifrovanie. Príliš pravidelne.

Úloha 1. Na obr. 4 máte ďalšiu permutáciu na vytvorenie Enigmy. Skopírujte výkres na xerograf. Postavte auto, zadajte svoje meno a priezvisko. Môj CWONUE JTRYGT. Ak potrebujete mať svoje poznámky súkromné, použite Cardboard Enigma.

Úloha 2. Zašifrujte svoje meno a priezvisko jedného z „aut“, ktoré ste videli, ale (pozor!) s ďalšou komplikáciou: neotočíme sa o jeden zárez doprava, ale podľa schémy {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - teda najprv o jednotku, potom o dve, potom o tri, potom o 2, potom znova o 1, potom o 2 atď., taká „vlnka“ . Uistite sa, že moje meno a priezvisko sú zašifrované ako CZTTAK SDBITH. Teraz už chápete, aký silný bol stroj Enigma?

Riešenie problémov pre absolventov stredných škôl. Koľko možností konfigurácie pre Enigmu (v tejto verzii, ako je popísané v článku)? Máme 24 písmen. Vyberieme prvý pár písmen - to sa dá urobiť

spôsoby. Ďalší pár je možné zvoliť na

spôsoby, viac

atď. Po zodpovedajúcich výpočtoch (všetky čísla sa musia vynásobiť) dostaneme

151476660579404160000

Potom toto číslo vydeľte 12! (12 faktoriál), pretože rovnaké páry možno získať v inom poradí. Takže nakoniec dostaneme "totálne"

316234143225,

to je niečo málo cez 300 miliárd, čo sa na dnešné superpočítače nezdá ako závratne veľké číslo. Ak sa však vezme do úvahy náhodné poradie samotných permutácií, toto číslo sa výrazne zvýši. Môžeme myslieť aj na iné typy permutácií.

Pozri tiež: