Šifre i špijuni

U današnjem matematičkom kutku bacit ću pogled na temu o kojoj sam raspravljao na godišnjem znanstvenom kampu za djecu Nacionalne zaklade za djecu. Zaklada traži djecu i mlade sa znanstvenim interesima. Ne morate biti iznimno nadaren, ali morate imati “znanstvenu crtu”. Vrlo dobre školske ocjene nisu potrebne. Probajte, možda vam se svidi. Ako ste viši razred osnovne škole ili srednjoškolac, prijavite se. Obično roditelji ili škola podnose prijave, ali to nije uvijek slučaj. Pronađite web stranicu Zaklade i saznajte.

U školi se sve više govori o "kodiranju", misleći na aktivnost koja se ranije zvala "programiranje". Ovo je uobičajeni postupak za teoretske edukatore. Iskopaju stare metode, daju im novo ime i "napredak" dolazi sam od sebe. Postoji nekoliko područja u kojima se pojavljuje takav ciklički fenomen.

Može se zaključiti da didaktiku obezvrjeđujem. Ne. U razvoju civilizacije ponekad se vraćamo na ono što je bilo, napušteno i sada se oživljava. Ali naš kutak je matematički, a ne filozofski.

Pripadnost određenoj zajednici znači i "zajedničke simbole", zajednička čitanja, izreke i parabole. Onaj tko je savršeno naučio poljski jezik "u Szczebrzeszynu je velika šikara, u trsci zuji buba" odmah će biti razotkriven kao špijun strane države ako ne odgovori na pitanje što radi djetlić. Naravno da se guši!

Ovo nije samo šala. U prosincu 1944. Nijemci su uz velike troškove pokrenuli svoju posljednju ofenzivu u Ardenima. Mobilizirali su vojnike koji su tečno govorili engleski kako bi ometali kretanje savezničkih trupa, primjerice tako što su ih na raskrižjima vodili u krivom smjeru. Nakon trenutka iznenađenja, Amerikanci su vojnicima počeli postavljati sumnjiva pitanja, čiji bi odgovori bili očigledni osobi iz Teksasa, Nebraske ili Georgije, a nepojmljivi nekome tko nije tamo odrastao. Nepoznavanje stvarnosti dovelo je izravno do smaknuća.

Do točke. Čitateljima preporučujem knjigu Lukasza Badowskog i Zaslawa Adamasheka "Laboratorij u ladici stola - matematika". Ovo je prekrasna knjiga koja sjajno pokazuje da je matematika zaista korisna za nešto i da "matematički eksperiment" nisu prazne riječi. Uključuje, među ostalim, i opisanu konstrukciju "kartonske enigme" - uređaja za čiju izradu će nam trebati svega petnaestak minuta i koji radi poput ozbiljnog stroja za šifriranje. Sama ideja je bila toliko poznata, spomenuti autori su je lijepo razradili, a ja ću je malo izmijeniti i zaogrnuti matematičkim ruhom.

pile za metal

Na jednoj od ulica mog vikend sela u predgrađu Varšave nedavno je demontiran trotoar od „trlinke” - šesterokutnih ploča za popločavanje. Vožnja je bila neugodna, ali se duša matematičara radovala. Pokrivanje ravnine pravilnim (tj. pravilnim) poligonima nije lako. To mogu biti samo trokuti, kvadrati i pravilni šesterokuti.

Možda sam se malo našalio s ovom duhovnom radošću, ali šesterokut je lijep lik. Od njega možete napraviti prilično uspješan uređaj za šifriranje. Geometrija će pomoći. Šesterokut ima rotacijsku simetriju - preklapa se sam sa sobom kada se zakrene višekratnik od 60 stupnjeva. Polje označeno npr. slovom A gore lijevo sl. 1 nakon okretanja kroz ovaj kut, također će pasti u polje A - i isto je s ostalim slovima. Dakle, izrežimo šest kvadrata iz mreže, svaki s različitim slovom. Ovako dobivenu rešetku stavimo na list papira. U slobodnih šest polja upisujemo šest slova teksta koji želimo šifrirati. Zarotirajmo list za 60 stupnjeva. Pojavit će se šest novih polja - unesite sljedećih šest slova naše poruke.

Riža. 1. Trlinkovi radosti matematike.

Desno sl. 1 imamo tekst kodiran na ovaj način: "Na stanici je ogromna teška parna lokomotiva."

Sada će vam dobro doći malo školske matematike. Na koliko se načina mogu međusobno poredati dva broja?

Kakvo glupo pitanje? Za dvoje: ili jedan ispred ili drugi.

Izvrsno. A tri broja?

Također nije teško navesti sve postavke:

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

Pa to je za četvero! Još uvijek se može jasno navesti. Pogodi pravilo redoslijeda koje sam postavio:

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

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

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

3412, 4312, 3214, 3241, 3421, 4321

Kada je znamenki pet, dobivamo 120 mogućih postavki. Nazovimo ih permutacije. Broj mogućih permutacija n brojeva je umnožak 1 2 3 ... n, tzv jak i označeno uskličnikom: 3!=6, 4!=24, 5!=120. Za sljedeći broj 6 imamo 6!=720. Iskoristit ćemo ovo da naš heksagonalni šifrirani štit bude složeniji.

Biramo permutaciju brojeva od 0 do 5, na primjer 351042. Naš šesterokutni disk za kodiranje ima crticu u srednjem polju - tako da se može staviti "u nultu poziciju" - crtica gore, kao na sl. 1. Ovako disk stavimo na list papira na koji trebamo napisati naše izvješće, ali ga ne pišemo odmah, već ga tri puta okrenemo za 60 stupnjeva (tj. 180 stupnjeva) i upišemo šest slova. prazna polja. Vraćamo se u početni položaj. Brojčanik okrenemo pet puta za 60 stupnjeva, odnosno za pet "zuba" našeg brojčanika. Mi ispisujemo. Sljedeći položaj skale je položaj zakrenut za 60 stupnjeva oko nule. Četvrta pozicija je 0 stupnjeva, ovo je početna pozicija.

Shvaćate li što se dogodilo? Imamo dodatnu priliku - zakomplicirati naš "stroj" više od sedam stotina puta! Dakle, imamo dva nezavisna položaja "automatona" - izbor mreže i izbor permutacije. Mreža se može odabrati na 66 = 46656 načina, permutacija 720. To daje 33592320 mogućnosti. Preko 33 milijuna šifri! Gotovo malo manje, jer neke se rešetke ne mogu izrezati iz papira.

U donjem dijelu sl. 1 imamo poruku kodiranu ovako: "Šaljem vam četiri padobranske divizije". Lako je razumjeti da se neprijatelju ne smije dopustiti da to sazna. Ali hoće li razumjeti išta od ovoga:

TPOROPVMANVEORDISZ

YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

čak i s potpisom 351042?

Gradimo Enigmu, njemački stroj za šifriranje

Riža. 2. Primjer početnog postavljanja našeg stroja za šifriranje.

Permutacije (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Kao što sam već spomenuo, ideju o stvaranju takvog stroja za karton dugujem knjizi "Laboratorij u ladici - matematika". Moja “konstrukcija” je nešto drugačija od one koju su dali njeni autori.

Stroj za šifriranje kojim su se Nijemci koristili tijekom rata imao je genijalno jednostavan princip, donekle sličan onom koji smo vidjeli s heksadecimalnom šifrom. Svaki put isto: prekinuti teško dodjeljivanje slova drugom slovu. Mora biti zamjenjiv. Kako to učiniti kako bi imali kontrolu nad njim?

Odaberimo ne bilo koju permutaciju, već onu koja ima cikluse duljine 2. Jednostavno rečeno, nešto poput "Gaderipoluka" opisanog ovdje prije nekoliko mjeseci, ali pokrivajući sva slova abecede. Dogovorimo se oko 24 slova - bez ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Koliko je takvih permutacija? Ovo je zadatak za maturante (odmah bi ga trebali riješiti). Koliko? Puno? Nekoliko tisuća? Da:

1912098225024001185793365052108800000000 (nemojmo ni pokušavati pročitati ovaj broj). Postoji toliko mnogo mogućnosti za postavljanje "nulte" pozicije. I zna biti teško.

Naš stroj se sastoji od dva okrugla diska. Na jednom od njih, koji još uvijek stoji, ispisana su slova. Pomalo je poput brojčanika starog telefona, gdje ste birali broj okretanjem brojčanika do kraja. Rotary je drugi sa shemom boja. Najlakši način je da ih stavite na obični čep pomoću igle. Umjesto pluta možete koristiti tanku dasku ili debeli karton. Lukasz Badowski i Zasław Adamaszek preporučuju stavljanje oba diska u CD kutiju.

Zamislite da želimo kodirati riječ ARMATY (Riža. 2 i 3). Postavite uređaj u nulti položaj (strelica gore). Slovo A odgovara F. Rotirajte unutarnji krug jedno slovo udesno. Imamo slovo R za kodiranje, sada ono odgovara A. Nakon sljedeće rotacije, vidimo da slovo M odgovara U. Sljedeća rotacija (četvrti dijagram) daje korespondenciju A - P. Na petom brojčaniku imamo T - A. Konačno (šesti krug ) D – D Neprijatelj vjerojatno neće pretpostaviti da će naši CFCFA biti opasni za njega. A kako će “naši” čitati depešu? Moraju imati isti stroj, isto "programiran", odnosno s istom permutacijom. Šifra počinje na poziciji nula. Dakle, vrijednost F je A. Okrenite brojčanik u smjeru kazaljke na satu. Slovo A sada je povezano s R. Okreće brojčanik udesno i ispod slova U nalazi M itd. Šifrant trči do generala: "Generale, javljam, oružje stiže!"

Riža. 3. Princip rada našeg lista Enigma.

Riža. 3. Princip rada našeg lista Enigma.

Mogućnosti čak i tako primitivne Enigme su nevjerojatne. Možemo odabrati druge izlazne permutacije. Možemo - a ima tu još više mogućnosti - ne jednim "serifom" redovito, nego u određenom, svakodnevno promjenjivom redoslijedu, slično šesterokutu (primjerice, prvo tri slova, zatim sedam, pa osam, četiri... .. itd. .).

Kako možete pogoditi?! Pa ipak za poljske matematičare (Marian Reevski, Henrik od Zigalskog, Eži Ružicki) dogodilo se. Tako dobiveni podaci bili su neprocjenjivi. Prethodno su imali jednako važan doprinos u povijesti naše obrane. Vaclav Serpinski i Stanislav Mazurkevichkoji je prekršio kodeks ruskih trupa 1920. Presretnuti kabel dao je Piłsudskom priliku da izvede poznati manevar s rijeke Vepsz.

Sjećam se Vaslava Sierpinskog (1882-1969). Činio se poput matematičara za kojeg vanjski svijet ne postoji. O svom sudjelovanju u pobjedi 1920. godine nije mogao govoriti ni iz vojnih, ni iz ... političkih razloga (vlasti Poljske Narodne Republike nisu voljele one koji su nas branili od Sovjetskog Saveza).

Riža. 4. Permutacija (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Riža. 5. Prekrasan ukras, ali nije prikladan za šifriranje. Previše redovito.

Zadatak 1. Na sl. 4 imate još jednu permutaciju za stvaranje Enigme. Kopirajte crtež na kserograf. Napravi auto, kodiraj svoje ime i prezime. Moj CWONUE JTRYGT. Ako svoje bilješke trebate zadržati privatnima, upotrijebite Cardboard Enigmu.

Zadatak 2. Šifrirajte svoje ime i prezime jednog od “automobila” koje ste vidjeli, ali (pažnja!) uz dodatnu komplikaciju: ne skrećemo ni jedan zarez udesno, već prema shemi {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - dakle, prvo za jedan, pa za dva, pa za tri, pa za 2, pa opet za 1, pa za 2 itd., takav "valić" . Provjerite jesu li moje ime i prezime šifrirani kao CZTTAK SDBITH. Shvaćate li sada koliko je moćan bio stroj Enigma?

Rješavanje problema za maturante. Koliko opcija konfiguracije za Enigmu (u ovoj verziji, kako je opisano u članku)? Imamo 24 slova. Odaberemo prvi par slova - to se može učiniti na

načine. Sljedeći par se može odabrati na

načina, više

itd. Nakon odgovarajućih izračuna (svi brojevi se moraju pomnožiti), dobivamo

151476660579404160000

Zatim taj broj podijelite s 12! (12 faktorijela), jer se isti parovi mogu dobiti različitim redoslijedom. Tako da na kraju dobijemo "total"

316234143225,

to je nešto više od 300 milijardi, što se ne čini kao zapanjujuća brojka za današnja superračunala. Međutim, ako se uzme u obzir slučajni redoslijed samih permutacija, taj se broj znatno povećava. Možemo se sjetiti i drugih vrsta permutacija.

Vidi također: