Šifre i špijuni
U današnjem Matematičkom kutku, pogledat ću temu o kojoj sam razgovarao na godišnjem naučnom kampu za djecu Nacionalne dječje fondacije. Fondacija traži djecu i mlade sa naučnim interesima. Ne morate biti izuzetno nadareni, ali morate imati "naučni trag". Vrlo dobre školske ocjene nisu potrebne. Probajte, možda vam se dopadne. Ako ste učenik viših razreda osnovne škole ili srednjoškolac, prijavite se. Obično roditelji ili škola sastavljaju izvještaje, ali to nije uvijek slučaj. Pronađite web stranicu Fondacije i saznajte.
U školi se sve više govori o "kodiranju", pri čemu se misli na aktivnost koja se ranije zvala "programiranje". Ovo je uobičajena procedura za teorijske edukatore. Iskopaju stare metode, daju im novo ime, a "napredak" je napravljen sam od sebe. Postoji nekoliko oblasti u kojima se takva ciklična pojava javlja.
Može se zaključiti da ja devalviram didaktiku. br. 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 koji je savršeno naučio poljski jezik “u Szczebrzeszynu je velika guštara, buba zuji u trsci” odmah će biti razotkriven kao špijun strane države ako ne odgovori na pitanje šta radi djetlić. Naravno da se guši!
Ovo nije samo šala. U decembru 1944. Nemci su pokrenuli poslednju ofanzivu na Ardene uz velike troškove. Mobilizirali su vojnike koji su tečno govorili engleski kako bi ometali kretanje savezničkih trupa, na primjer vodeći ih u pogrešnom smjeru na raskrsnici. Nakon trenutka iznenađenja, Amerikanci su vojnicima počeli postavljati sumnjiva pitanja, čiji bi odgovori bili očigledni osobi iz Teksasa, Nebraske ili Džordžije, a nepojmljivi nekome ko nije tamo odrastao. Nepoznavanje stvarnosti direktno je dovelo do pogubljenja.
Do tačke. Čitaocima preporučujem knjigu Lukaša Badowskog i Zaslava Adamašeka „Laboratorija u ladici stola – matematika“. Ovo je divna knjiga koja briljantno pokazuje da je matematika zaista korisna za nešto i da "matematički eksperiment" nisu prazne riječi. Uključuje, između ostalog, opisanu konstrukciju "kartonske enigme" - uređaja za koji će nam trebati samo petnaestak minuta da ga napravimo i koji radi kao ozbiljna mašina za šifriranje. Sama ideja je bila toliko poznata, pomenuti autori su je lijepo razradili, a ja ću je malo promijeniti i umotati u više matematičku odjeću.
nožne pile
Na jednoj od ulica mog sela dacha u predgrađu Varšave, pločnik je nedavno demontiran od „trlinka“ - šesterokutnih ploča za popločavanje. Vožnja je bila neugodna, ali se duša matematičara radovala. Pokrivanje ravni pravilnim (tj. pravilnim) poligonima nije lako. To mogu biti samo trokuti, kvadrati i pravilni šesterokuti.
Možda sam se malo našalio sa ovom duhovnom radošću, ali šestougao je divna figura. Od njega možete napraviti prilično uspješan uređaj za šifriranje. Geometrija će pomoći. Šestougao ima rotacijsku simetriju - preklapa se kada se rotira za više od 60 stepeni. Polje označeno, na primjer, slovom A u gornjem lijevom kutu sl. 1 nakon okretanja kroz ovaj ugao, takođe će pasti u polje A - a isto je i sa drugim slovima. Dakle, izrežemo šest kvadrata iz mreže, svaki sa različitim slovom. Ovako dobivenu rešetku stavljamo na list papira. U slobodnih šest polja unesite šest slova teksta koje želimo šifrirati. Zarotirajmo list za 60 stepeni. Pojavit će se šest novih polja - unesite sljedećih šest slova naše poruke.
Rice. 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 načina se dva broja mogu poredati jedan u odnosu na drugi?
Kakvo glupo pitanje? Za dvoje: ili jedan ispred ili drugi.
U redu. I tri broja?
Također nije teško navesti sva podešavanja:
123, 132, 213, 231, 312, 321.
Pa, to je za četiri! Još uvijek se može jasno navesti. Pogodite pravilo reda koje sam stavio:
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 su cifre pet, dobijamo 120 mogućih postavki. Pozovimo ih permutacije. Broj mogućih permutacija n brojeva je proizvod 1 2 3 ... n, tzv jak i označeno uzvičnikom: 3!=6, 4!=24, 5!=120. Za sljedeći broj 6 imamo 6!=720. Iskoristit ćemo ovo da naš heksagonalni štit za šifriranje učinimo složenijim.
Biramo permutaciju brojeva od 0 do 5, na primjer 351042. Naš heksagonalni disk za šifriranje ima crticu u srednjem polju - tako da se može staviti "u nultu poziciju" - crticu prema gore, kao na sl. 1. Disk na ovaj način stavljamo na list papira na kojem treba da napišemo naš izvještaj, ali ga ne pišemo odmah, već ga okrećemo tri puta za 60 stepeni (tj. 180 stepeni) i upisujemo šest slova prazna polja. Vraćamo se na početnu poziciju. Brojčanik okrećemo pet puta za 60 stepeni, odnosno za pet "zuba" našeg brojčanika. Mi štampamo. Sljedeća pozicija na skali je pozicija rotirana za 60 stepeni oko nule. Četvrta pozicija je 0 stepeni, ovo je početna pozicija.
Shvaćate li šta se dogodilo? Imamo dodatnu priliku - zakomplikovati našu "mašinu" više od sedamsto puta! Dakle, imamo dva nezavisna položaja "automata" - izbor mreže i izbor permutacije. Mreža se može izabrati na 66 = 46656 načina, permutacija 720. Ovo daje 33592320 mogućnosti. Preko 33 miliona šifri! Gotovo malo manje, jer neke mreže se ne mogu izrezati iz papira.
U donjem dijelu sl. 1 imamo poruku kodiranu ovako: "Šaljem vam četiri padobranske divizije." Lako je shvatiti da neprijatelju ne treba dozvoliti da sazna za ovo. Ali hoće li razumjeti išta od ovoga:
TPOROPVMANVEORDIZZ
JJLʹ̱OAKVMDEJČEŠ,
čak i sa potpisom 351042?
Gradimo Enigmu, njemačku mašinu za šifriranje
Rice. 2. Primjer početnog podešavanja naše mašine za šifrovanje.
Permutacije (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Kao što sam već spomenuo, ideju o stvaranju ovakve kartonske mašine dugujem knjizi "Laboratorija u ladici - Matematika". Moja „konstrukcija“ je nešto drugačija od one koju su dali njeni autori.
Mašina za šifrovanje koju su Nemci koristili tokom rata imala je genijalno jednostavan princip, donekle sličan onom koji smo videli sa heksadecimalnom šifrom. Svaki put ista stvar: prekinuti teško dodjeljivanje slova drugom pismu. Mora biti zamjenjiv. Kako to učiniti da biste imali kontrolu nad tim?
Hajde da izaberemo ne bilo koju permutaciju, već onu koja ima cikluse dužine 2. Jednostavno rečeno, nešto poput "Gaderipoluka" opisanog ovdje prije nekoliko mjeseci, ali pokriva sva slova abecede. Dogovorimo se oko 24 slova - bez ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Koliko je takvih permutacija? Ovo je zadatak za maturante (trebalo bi da ga odmah riješe). Koliko? Puno? Nekoliko hiljada? da:
1912098225024001185793365052108800000000 (nemojmo ni pokušavati pročitati ovaj broj). Postoji toliko mnogo mogućnosti za postavljanje "nulte" pozicije. I može biti teško.
Naša mašina se sastoji od dva okrugla diska. Na jednom od njih, koji još uvijek stoji, ispisana su slova. Pomalo liči na biranje starog telefona, gdje ste birali broj okretanjem točkića do kraja. Rotary je drugi sa shemom boja. Najlakši način je da ih stavite na običan čep pomoću igle. Umjesto plute, možete koristiti tanku ploču ili debeli karton. Lukasz Badowski i Zasław Adamaszek preporučuju stavljanje oba diska u CD kutiju.
Zamislite da želimo da kodiramo riječ ARMATY (Rice. 2 i 3). Postavite uređaj na nultu poziciju (strelica gore). Slovo A odgovara F. Okrenite unutrašnje kolo za 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) Y – Y Neprijatelj vjerovatno neće pogoditi da će naši CFCFA biti opasni za njega. A kako će "naši" pročitati depešu? Moraju imati istu mašinu, istu "programiranu", odnosno sa istom permutacijom. Šifra počinje na poziciji nula. Dakle, vrijednost F je A. Okrenite točkić u smjeru kazaljke na satu. Slovo A je sada povezano sa R. On okreće brojčanik udesno i ispod slova U nalazi M itd. Šifrarš trči generalu: "Generale, javljam, puške dolaze!"
Rice. 3. Princip rada našeg rada Enigma.
| Rice. 3. Princip rada našeg rada Enigma. | ||
Mogućnosti čak i tako primitivne Enigme su nevjerovatne. Možemo odabrati druge izlazne permutacije. Možemo - a tu je još više mogućnosti - ne po jednom "serifu" redovno, već određenim redoslijedom koji se svakodnevno mijenja, slično šesterokutu (na primjer, prvo tri slova, zatim sedam, pa osam, četiri... .. itd. .).
Kako možeš da pogodiš?! A ipak za poljske matematičare (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) dogodilo. Tako dobijene informacije bile su neprocjenjive. Oni su i ranije imali podjednako važan doprinos istoriji naše odbrane. Vaclav Serpinski i Stanislav Mazurkevichkoji je prekršio kodeks ruskih trupa 1920. Presretnuti kabl dao je Piłsudskom priliku da izvede čuveni manevar sa reke Veps.
Sjećam se Vasslava Sierpinskog (1882-1969). Delovao je kao matematičar za koga spoljašnji svet nije postojao. O svom sudjelovanju u pobjedi 1920. nije mogao govoriti iz vojnih i ... iz političkih razloga (vlasti Narodne Republike Poljske nisu voljele one koji su nas branili od Sovjetskog Saveza).
Rice. 4. Permutacija (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Rice. 5. Prekrasan ukras, ali nije pogodan za šifriranje. Previše redovno.
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 želite da vaše bilješke budu privatne, koristite Cardboard Enigmu.
Zadatak 2. Šifrirajte svoje ime i prezime jednog od "automobila" koje ste vidjeli, ali (pažnja!) s dodatnom komplikacijom: ne skrećemo za jedan zarez udesno, već prema šemi {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - to jest, prvo za jedan, zatim za dva, zatim za tri, zatim za 2, pa opet za 1, pa za 2, itd., takav "talasić" . Provjerite jesu li moje ime i prezime šifrirani kao CZTTAK SDBITH. Sada shvatate koliko je moćna bila mašina Enigma?
Rješavanje problema za maturante. Koliko opcija konfiguracije za Enigmu (u ovoj verziji, kako je opisano u članku)? Imamo 24 pisma. Odabiremo prvi par slova - to se može učiniti dalje
načine. Sledeći par se može izabrati
načina, više
itd. Nakon odgovarajućih proračuna (svi brojevi se moraju pomnožiti), dobijamo
151476660579404160000
Zatim podijelite taj broj sa 12! (12 faktorijala), jer se isti parovi mogu dobiti različitim redoslijedom. Tako da na kraju dobijemo "ukupno"
316234143225,
to je nešto više od 300 milijardi, što ne izgleda kao zapanjujuće veliki broj za današnje superkompjutere. Međutim, ako se uzme u obzir slučajni redoslijed samih permutacija, ovaj broj se značajno povećava. Možemo razmišljati i o drugim vrstama permutacija.
Vidi takođe:
