Chiffere og spioner

I dagens matematikhjørne vil jeg tage et kig på et emne, jeg diskuterede på National Children's Foundations årlige Science Camp for kids. Fonden søger børn og unge med videnskabelige interesser. Du behøver ikke at være ekstremt begavet, men du skal have en "videnskabelig streak". Meget gode skolekarakterer er ikke påkrævet. Prøv det, du kan måske lide det. Hvis du er en folkeskoleelev eller gymnasieelev, så søg. Normalt laver forældrene eller skolen indberetningerne, men det er ikke altid tilfældet. Find Fondens hjemmeside og find ud af det.

Der tales mere og mere i skolen om "kodning", med henvisning til den aktivitet, der tidligere var kendt som "programmering". Dette er en almindelig procedure blandt pædagogiske teoretikere. De graver gamle metoder frem, giver dem et nyt navn, og "fremskridt" sker af sig selv. Der er flere områder, hvor dette cykliske fænomen opstår.

Man kan konkludere, at jeg devaluerer didaktikken. Ingen. I civilisationens udvikling vender vi nogle gange tilbage til det, der var, blev forladt og nu genoplives. Men vores hjørne er matematisk, ikke filosofisk.

At tilhøre et bestemt fællesskab betyder også "fælles symboler", almindelige læsninger, ordsprog og lignelser. Enhver, der ulasteligt har lært det polske sprog "der er et stort krat i Szczebrzeszyn, en bille svirrer i sivene", vil straks blive afsløret som spion for en fremmed magt, hvis han ikke svarer på spørgsmålet om, hvad spætten laver. Selvfølgelig kvæler han!

Dette er ikke kun en joke. I december 1944 indledte tyskerne deres sidste offensiv i Ardennerne med store omkostninger. De mobiliserede soldater, der talte flydende engelsk, for at forstyrre de allierede troppers bevægelse, for eksempel ved at føre dem i den forkerte retning ved en korsvej. Efter et øjebliks overraskelse begyndte amerikanerne at stille soldaterne mistænkelige spørgsmål, hvis svar ville have været indlysende for en person fra Texas, Nebraska eller Georgia, men utænkelige for en, der ikke var vokset op der. Uvidenhed om realiteterne førte direkte til henrettelse.

Til sagen. Jeg anbefaler læserne bogen af ​​Lukasz Badowski og Zaslaw Adamashek "Laboratory in a Desk Drawer - Mathematics". Dette er en vidunderlig bog, der på glimrende vis viser, at matematik virkelig er nyttigt til noget, og at "matematikeksperiment" ikke er tomme ord. Den omfatter blandt andet den beskrevne konstruktion af "papgåden" - en enhed, som det kun vil tage os femten minutter at skabe, og som fungerer som en seriøs chiffermaskine. Ideen i sig selv var så kendt, de nævnte forfattere arbejdede smukt ud, og jeg vil lave lidt om på den og pakke den ind i mere matematisk tøj.

Cipher hacksave

På en af ​​gaderne i min dacha-landsby i forstæderne til Warszawa blev fortovet for nylig demonteret fra "trlinka" - sekskantede belægningsplader. Turen var ubehagelig, men matematikerens sjæl glædede sig. Det er ikke let at dække planet med regulære (dvs. regulære) polygoner. Det kan kun være trekanter, firkanter og regulære sekskanter.

Jeg har måske været lidt af en joke med denne inderlige glæde, men en sekskant er en smuk form. Det kan bruges til at lave en ret vellykket krypteringsenhed. Geometri vil hjælpe. Sekskanten har rotationssymmetri - den overlapper sig selv, når den drejes med en faktor på 60 grader. Et felt markeret for eksempel med bogstavet A i øverste venstre del fig. 1 efter at have drejet gennem denne vinkel, vil den også falde i boks A - og det samme med andre bogstaver. Så lad os skære seks firkanter ud fra gitteret, hver med et forskelligt bogstav. Vi lægger gitteret opnået på denne måde på et ark papir. I de frie seks felter skal du indtaste seks bogstaver i den tekst, som vi vil kryptere. Lad os rotere arket 60 grader. Seks nye felter vises - indtast de næste seks bogstaver i vores besked.

Ris. 1. Trlinks af glæde i matematik.

Til højre fig. 1 vi har tekst kodet på denne måde: "Der er et kæmpe tungt damplokomotiv på stationen."

Nu vil lidt skolematematik komme godt med. På hvor mange måder kan to tal arrangeres i forhold til hinanden?

Hvilket dumt spørgsmål? For to: enten den ene foran eller den anden.

Store. Og tre numre?

Det er heller ikke svært at liste alle indstillingerne:

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

Nå, det er for fire! Det kan stadig siges tydeligt. Gæt den rækkefølge, jeg har lagt ind:

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

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

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

3412, 4312, 3214, 3241, 3421, 4321

Når der er fem tal, får vi 120 mulige indstillinger. Lad os ringe til dem permutationer. Antallet af mulige permutationer af n tal er produktet af 1 · 2 · 3 · … · n, kaldet stærk og er markeret med et udråbstegn: 3!=6, 4!=24, 5!=120. Til næste nummer 6 har vi 6!=720. Vi vil bruge dette til at tilføje mere kompleksitet til vores sekskantede krypteringsskjold.

Vi vælger en permutation af tal fra 0 til 5, for eksempel 351042. Vores sekskantede scrambling-skive har en streg i midterfeltet - så den kan sættes "i nulstilling" - med bindestreg op, som i fig. 1. Vi placerer disken på denne måde på et ark papir, som vi vil skrive vores rapport på, men vi skriver den ikke med det samme, men roterer den tre gange 60 grader (dvs. 180 grader) og skriver seks bogstaver i tomme felter. Vi vender tilbage til startpositionen. Vi drejer skiven fem gange med 60 grader, det vil sige med fem "tænder" på vores skive. Vi trykker. Den næste skalaposition er positionen roteret 60 grader omkring nul. Den fjerde position er 0 grader, dette er startpositionen.

Forstår du, hvad der skete? Vi har en ekstra mulighed - at komplicere vores "maskine" mere end syv hundrede gange! Så vi har to uafhængige positioner af "automaten" - at vælge et gitter og vælge en permutation. Gitteret kan vælges på 66 = 46656 måder, permutation 720. Dette giver 33592320 muligheder. Over 33 millioner cifre! Næsten lidt mindre, fordi Nogle gitter kan ikke klippes ud af papir.

I den nederste del fig. 1 vi har en besked kodet således: "Jeg sender dig fire faldskærmsdivisioner." Det er let at forstå, at fjenden ikke kan få besked om dette. Men vil han forstå noget af dette:

TPOROPVMANVEORDISZ

ÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅ

selv med signaturen 351042?

Vi bygger Enigma - en tysk krypteringsmaskine

Ris. 2. Et eksempel på den indledende opsætning af vores krypteringsmaskine.

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

Som jeg allerede har nævnt, skylder jeg ideen om at skabe sådan en papmaskine til bogen "Lab in a Drawer - Mathematics". Min "konstruktion" er noget anderledes end den, dens forfattere har givet.

Krypteringsmaskinen, som tyskerne brugte under krigen, havde et genialt simpelt princip, der lidt ligner det, vi så med sekskantbekræftelsen. Hver gang er det det samme: bryde den hårde tildeling af et bogstav til et andet bogstav. Den skal kunne udskiftes. Hvordan gør man dette for at have kontrol over det?

Lad os ikke vælge en hvilken som helst permutation, men en der har cyklusser af længde 2. Kort sagt, noget som "Gaderipoluk" beskrevet her for et par måneder siden, men som dækker alle bogstaverne i alfabetet. Lad os blive enige om 24 bogstaver - uden ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Hvor mange sådanne permutationer? Dette er en opgave for gymnasieelever (de burde kunne løse det med det samme). Hvor mange? En masse? Flere tusinde? Ja:

1912098225024001185793365052108800000000 (lad os ikke engang prøve at læse dette nummer). Der er så mange muligheder for at indstille "nul"-positionen. Og det kan være svært.

Vores maskine består af to runde skiver. En af dem, som stadig står, har bogstaver skrevet på. Det er lidt ligesom urskiven på en gammel telefon, hvor man ringede til et nummer ved at dreje urskiven hele vejen. Rotary er den anden med et farveskema. Den nemmeste måde er at sætte dem på en almindelig prop ved hjælp af en nål. I stedet for kork kan du bruge et tyndt bræt eller tykt pap. Lukasz Badowski og Zaslav Adamaszek anbefaler at placere begge diske i et cd-hus.

Lad os forestille os, at vi ønsker at kode ordet ARMATY (Ris. 2 og 3). Indstil enheden til nulstilling (pil op). Bogstavet A svarer til F. Drej det interne kredsløb et bogstav til højre. Vi har bogstavet R at indkode, nu svarer det til A. Efter næste drejning ser vi at bogstavet M svarer til U. Den næste drejning (fjerde diagram) giver korrespondancen A - P. På den femte skive har vi T - A. Endelig (sjette cirkel) Y – Y Fjenden vil sandsynligvis ikke gætte på, at vores CFCFA'er vil være farlige for ham. Og hvordan vil "vores" læse udsendelsen? De skal have den samme maskine, den samme "programmerede", altså med samme permutation. Chifferen starter ved position nul. Så værdien af ​​F er A. Drej drejeknappen med uret. Bogstavet A er nu forbundet med R. Han drejer urskiven til højre og under bogstavet U finder M osv. Chifferekspedienten løber hen til generalen: "General, jeg melder, våbnene kommer!"

Ris. 3. Driftsprincippet i vores papir Enigma.

Ris. 3. Driftsprincippet i vores papir Enigma.

Mulighederne for selv en sådan primitiv Enigma er fantastiske. Vi kan vælge andre output-permutationer. Vi kan - og der er endnu flere muligheder her - ikke med en "serif" regelmæssigt, men i en bestemt, dagligt skiftende rækkefølge, svarende til en sekskant (for eksempel først tre bogstaver, så syv, så otte, fire ... .. osv. .).

Hvordan kan du gætte?! Og dog for polske matematikere (Marian Reevski, Henrik af Zigalski, Ezhi Ruzicki) skete. Den information, der blev opnået på denne måde, var uvurderlig. Tidligere havde de et lige så vigtigt bidrag til vores forsvars historie Vaclav Serpinski i Stanislav Mazurkevichsom overtrådte de russiske troppers kodeks i 1920. Det opsnappede kabel gav Piłsudski mulighed for at foretage den berømte manøvre fra Wieprz-floden.

Jeg husker Waclaw Sierpinski (1882-1969). Han virkede som en matematiker, for hvem omverdenen ikke eksisterede. Han kunne ikke tale om sin deltagelse i sejren i 1920, både af militære og... af politiske årsager (myndighederne i Den Polske Folkerepublik kunne ikke lide dem, der forsvarede os fra Sovjetunionen).

Ris. 4. Permutation (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Ris. 5. Flot dekoration, men ikke egnet til kryptering. For regelmæssigt.

1 job. Na fig. 4 du har en anden permutation til at skabe Enigma. Kopier tegningen over på en xerograf. Byg en bil, indkod dit for- og efternavn. Min CWONUE JTRYGT. Hvis du skal holde dine noter hemmelige, så brug en pap Enigma.

2 job. Krypter dit navn og efternavn på en af ​​de "biler", du så, men (opmærksom!) med en yderligere komplikation: vi drejer ikke et hak til højre, men ifølge skemaet {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - det vil sige først med en, så af to, så med tre, så med 2, så igen med 1, så med 2 osv., sådan en "wavelet" . Sørg for, at mit for- og efternavn er krypteret som CZTTAK SDBITH. Forstår du nu, hvor kraftfuld Enigma-maskinen var?

Løsning af problemet for gymnasieelever. Hvor mange konfigurationsmuligheder for Enigma (i denne version, som beskrevet i artiklen)? Vi har 24 bogstaver. Vi udvælger det første bogstavpar – dette kan gøres på

måder. Følgende par kan vælges på

metoder, yderligere

etc. Efter de passende beregninger (alle tal skal ganges) får vi

151476660579404160000

Divider derefter det tal med 12! (12 factorial), fordi de samme par kan opnås i en anden rækkefølge. Så i sidste ende får vi "totalt"

316234143225,

det er lidt over 300 milliarder, hvilket ikke virker som et svimlende stort tal for moderne supercomputere. Men hvis vi tager den tilfældige rækkefølge af selve permutationerne i betragtning, stiger dette tal betydeligt. Vi kan også tænke på andre typer af permutationer.

Se også: