Chiffer och spioner

I dagens Math Corner ska jag ta en titt på ett ämne som jag diskuterade på National Children's Foundations årliga Science Camp för barn. Stiftelsen söker barn och ungdomar med vetenskapliga intressen. Du behöver inte vara extremt begåvad, men du behöver ha en "vetenskaplig streak". Mycket bra skolbetyg krävs inte. Prova det, du kanske gillar det. Om du är gymnasieelev eller gymnasieelev, ansök. Vanligtvis gör föräldrarna eller skolan anmälningarna, men så är inte alltid fallet. Hitta stiftelsens hemsida och ta reda på det.

Det pratas mer och mer i skolan om "kodning", med hänvisning till den aktivitet som tidigare kallades "programmering". Detta är en vanlig procedur för teoretiska utbildare. De gräver fram gamla metoder, ger dem ett nytt namn och "framsteg" görs av sig själv. Det finns flera områden där ett sådant cykliskt fenomen förekommer.

Man kan dra slutsatsen att jag nedvärderar didaktiken. Nej. I civilisationens utveckling återvänder vi ibland till det som var, övergavs och nu återupplivas. Men vår hörn är matematisk, inte filosofisk.

Att tillhöra en viss gemenskap betyder också "gemensamma symboler", vanliga läsningar, talesätt och liknelser. Den som perfekt lärde sig det polska språket "det finns ett stort snår i Szczebrzeszyn, en skalbagge surrar i vassen" kommer omedelbart att avslöjas som en spion för en främmande stat om han inte svarar på frågan om vad hackspetten gör. Klart han kvävs!

Det här är inte bara ett skämt. I december 1944 inledde tyskarna sin sista offensiv i Ardennerna till stora kostnader. De mobiliserade soldater som talade flytande engelska för att störa de allierade truppernas rörelse, till exempel genom att leda dem i fel riktning vid vägskäl. Efter en stunds överraskning började amerikanerna ställa misstänkta frågor till soldaterna, vars svar skulle vara uppenbara för en person från Texas, Nebraska eller Georgia och ofattbara för någon som inte växt upp där. Okunskap om verkligheten ledde direkt till avrättningen.

Till poängen. Jag rekommenderar till läsarna boken av Lukasz Badowski och Zaslaw Adamashek "Laboratory in a Desk Drawer - Mathematics". Det här är en underbar bok som på ett lysande sätt visar att matematik verkligen är användbart för något och att "matteexperiment" inte är tomma ord. Den innehåller bland annat den beskrivna konstruktionen av "kartonggåtan" - en apparat som tar oss bara femton minuter att skapa och som fungerar som en seriös chiffermaskin. Själva idén var så välkänd, de nämnda författarna utarbetade den vackert, och jag ska ändra på den lite och slå in den i mer matematiska kläder.

bågfilar

På en av gatorna i min dacha-by i Warszawas förorter demonterades trottoaren nyligen från "trlinka" - sexkantiga beläggningsplattor. Resan var obekväm, men matematikerns själ gladde sig. Att täcka planet med regelbundna (dvs regelbundna) polygoner är inte lätt. Det kan bara vara trianglar, kvadrater och vanliga hexagoner.

Jag kanske skämtade lite med denna andliga glädje, men hexagonen är en vacker figur. Av den kan du göra en ganska framgångsrik krypteringsenhet. Geometri kommer att hjälpa. Hexagonen har rotationssymmetri - den överlappar sig själv när den roteras med en multipel av 60 grader. Fältet markerat till exempel med bokstaven A uppe till vänster fikon. 1 efter att ha svängt genom denna vinkel kommer den också att falla in i ruta A - och samma sak med andra bokstäver. Så låt oss skära ut sex rutor från rutnätet, var och en med olika bokstav. Vi lägger rutnätet som erhållits på detta sätt på ett pappersark. I de fria sex fälten anger du sex bokstäver i texten som vi vill kryptera. Låt oss rotera arket 60 grader. Sex nya fält kommer att dyka upp - skriv in de nästa sex bokstäverna i vårt meddelande.

Ris. 1. Tränkar av matematikens glädje.

Till höger fikon. 1 vi har en text kodad på detta sätt: "Det står ett enormt tungt ånglok vid stationen."

Nu kommer lite skolmatte väl till pass. På hur många sätt kan två tal ordnas i förhållande till varandra?

Vilken dum fråga? För två: antingen en framför eller den andra.

Bra. Och tre siffror?

Det är inte heller svårt att lista alla inställningar:

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

Tja, det är för fyra! Det kan fortfarande stavas tydligt. Gissa vilken ordningsregel jag satte:

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 siffrorna är fem får vi 120 möjliga inställningar. Låt oss ringa dem permutationer. Antalet möjliga permutationer av n tal är produkten 1 2 3 ... n, anropad stark och markeras med ett utropstecken: 3!=6, 4!=24, 5!=120. För nästa nummer 6 har vi 6!=720. Vi kommer att använda detta för att göra vår sexkantiga chiffersköld mer komplex.

Vi väljer en permutation av siffror från 0 till 5, till exempel 351042. Vår hexagonala förvrängningsskiva har ett streck i mittfältet - så att det kan sättas "i nollläget" - ett streck upp, som i fig. 1. Vi lägger skivan på detta sätt på ett papper som vi ska skriva vår rapport på, men vi skriver den inte direkt, utan vänder den tre gånger 60 grader (dvs. 180 grader) och skriver in sex bokstäver i de tomma fälten. Vi återgår till startpositionen. Vi vrider ratten fem gånger med 60 grader, det vill säga med fem "tänder" på vår urtavla. Vi trycker. Nästa skalposition är positionen roterad 60 grader runt noll. Den fjärde positionen är 0 grader, detta är startpositionen.

Förstår du vad som hände? Vi har ytterligare en möjlighet - att komplicera vår "maskin" med mer än sjuhundra gånger! Så vi har två oberoende positioner för "automaten" - valet av rutnätet och valet av permutationen. Rutnätet kan väljas på 66 = 46656 sätt, permutation 720. Detta ger 33592320 möjligheter. Över 33 miljoner chiffer! Nästan lite mindre, eftersom vissa rutnät kan inte skäras ur papper.

I nedre delen fikon. 1 vi har ett meddelande kodat så här: "Jag skickar dig fyra fallskärmsdivisioner." Det är lätt att förstå att fienden inte ska få veta om detta. Men kommer han att förstå något av detta:

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

YYLOAKVMDEYCHESH,

även med signatur 351042?

Vi bygger Enigma, en tysk chiffermaskin

Ris. 2. Ett exempel på den första installationen av vår krypteringsmaskin.

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

Som jag redan nämnt är jag skyldig idén att skapa en sådan kartongmaskin till boken "Labb i en låda - matematik". Min "konstruktion" skiljer sig något från den som författarna gav.

Chiffermaskinen som tyskarna använde under kriget hade en genialiskt enkel princip, lite lik den vi såg med sexkantchifferet. Varje gång samma sak: bryta hård tilldelning av en bokstav till en annan bokstav. Det måste vara utbytbart. Hur gör man det för att ha kontroll över det?

Låt oss inte välja vilken permutation som helst, utan en som har cykler med längd 2. Enkelt uttryckt, något i stil med "Gaderipoluk" som beskrevs här för några månader sedan, men som täcker alla bokstäver i alfabetet. Låt oss komma överens om 24 bokstäver - utan ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Hur många sådana permutationer? Detta är en uppgift för gymnasieutexaminerade (de borde kunna lösa det direkt). Hur många? Massor? Flera tusen? Ja:

1912098225024001185793365052108800000000 (låt oss inte ens försöka läsa detta nummer). Det finns så många möjligheter att ställa in "noll"-läget. Och det kan vara svårt.

Vår maskin består av två runda skivor. På en av dem, som fortfarande står kvar, står bokstäver. Det är lite som ratten på en gammal telefon, där man slog ett nummer genom att vrida ratten hela vägen. Rotary är den andra med ett färgschema. Det enklaste sättet är att lägga dem på en vanlig kork med hjälp av en nål. Istället för kork kan du använda en tunn skiva eller tjock kartong. Lukasz Badowski och Zasław Adamaszek rekommenderar att du placerar båda skivorna i en CD-box.

Föreställ dig att vi vill koda ordet ARMATY (Ris. 2 och 3). Ställ enheten i nollläge (pil upp). Bokstaven A motsvarar F. Vrid den interna kretsen en bokstav åt höger. Vi har bokstaven R att koda, nu motsvarar den A. Efter nästa rotation ser vi att bokstaven M motsvarar U. Nästa rotation (fjärde diagrammet) ger överensstämmelsen A - P. På den femte ratten har vi T - A. Slutligen (sjätte cirkeln ) Y – Y Fienden kommer förmodligen inte gissa att våra CFCFAs kommer att vara farliga för honom. Och hur kommer "vårt" att läsa utskicket? De måste ha samma maskin, samma "programmerade", det vill säga med samma permutation. Chifferet börjar vid position noll. Så värdet på F är A. Vrid ratten medurs. Bokstaven A är nu associerad med R. Han vrider ratten åt höger och under bokstaven U hittar M, etc. Chiffertjänstemannen springer till generalen: "General, jag rapporterar, vapnen kommer!"

Ris. 3. Funktionsprincipen för vårt papper Enigma.

Ris. 3. Funktionsprincipen för vårt papper Enigma.

Möjligheterna med en sådan primitiv gåta är fantastiska. Vi kan välja andra utdatapermutationer. Vi kan - och det finns ännu fler möjligheter här - inte av en "serif" regelbundet, utan i en viss, dagligt föränderlig ordning, liknande en hexagon (till exempel först tre bokstäver, sedan sju, sedan åtta, fyra ... .. osv. .).

Hur kan du gissa?! Och ändå för polska matematiker (Marian Reevski, Henry Zigalski, Jerzy Ruzicki) hände. Den information som sålunda erhållits var ovärderlig. Tidigare hade de ett lika viktigt bidrag till vårt försvars historia. Vaclav Serpinsky i Stanislav Mazurkevichsom bröt mot de ryska truppernas kod 1920. Den avlyssnade kabeln gav Piłsudski möjlighet att göra den berömda manövern från Vepszfloden.

Jag minns Vaslav Sierpinski (1882-1969). Han verkade som en matematiker för vilken omvärlden inte existerade. Han kunde inte tala om sitt deltagande i segern 1920 både av militära och ... av politiska skäl (myndigheterna i den polska folkrepubliken gillade inte de som försvarade oss från Sovjetunionen).

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

Ris. 5. Vacker dekoration, men inte lämplig för kryptering. För regelbundet.

1 jobb. Na fikon. 4 du har en annan permutation för att skapa Enigma. Kopiera ritningen till xerografen. Bygg en bil, koda ditt för- och efternamn. Min CWONUE JTRYGT. Om du behöver hålla dina anteckningar privata, använd Cardboard Enigma.

2 jobb. Kryptera ditt namn och efternamn för en av "bilarna" du såg, men (obs!) med en ytterligare komplikation: vi vänder inte ett snäpp åt höger, utan enligt schemat {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - det vill säga först av ett, sedan av två, sedan med tre, sedan med 2, sedan igen med 1, sedan med 2, etc., en sådan "wavelet" . Se till att mitt för- och efternamn är krypterade som CZTTAK SDBITH. Förstår du nu hur kraftfull Enigma-maskinen var?

Problemlösning för gymnasieutexaminerade. Hur många konfigurationsalternativ för Enigma (i den här versionen, som beskrivs i artikeln)? Vi har 24 bokstäver. Vi väljer det första bokstäverparet - detta kan göras på

sätt. Nästa par kan väljas på

sätt, mer

etc. Efter motsvarande beräkningar (alla tal måste multipliceras) får vi

151476660579404160000

Dela sedan talet med 12! (12 factorial), eftersom samma par kan erhållas i en annan ordning. Så i slutändan får vi "totalt"

316234143225

det är drygt 300 miljarder, vilket inte verkar vara ett svindlande stort antal för dagens superdatorer. Men om den slumpmässiga ordningen av själva permutationerna tas med i beräkningen, ökar detta antal avsevärt. Vi kan också tänka på andra typer av permutationer.

Se även: