Chiffer og spioner
I dagens Math Corner skal jeg ta en titt på et tema jeg diskuterte på National Children's Foundations årlige Science Camp for kids. Stiftelsen søker barn og unge med vitenskapelige interesser. Du trenger ikke å være ekstremt begavet, men du trenger å ha en "vitenskapelig strek". Svært gode skolekarakterer kreves ikke. Prøv det, kanskje du liker det. Hvis du er ungdomsskole eller videregående elev, søk. Vanligvis er det foreldrene eller skolen som lager rapportene, men dette er ikke alltid tilfelle. Finn stiftelsens hjemmeside og finn ut.
Det snakkes mer og mer i skolen om «koding», med henvisning til aktiviteten som tidligere ble kalt «programmering». Dette er en vanlig prosedyre for teoretiske undervisere. De graver opp gamle metoder, gir dem et nytt navn, og «fremskritt» gjøres av seg selv. Det er flere områder hvor et slikt syklisk fenomen oppstår.
Det kan konkluderes med at jeg devaluerer didaktikk. Nei. I utviklingen av sivilisasjonen vender vi noen ganger tilbake til det som var, ble forlatt og nå gjenopplives. Men hjørnet vårt er matematisk, ikke filosofisk.
Å tilhøre et bestemt fellesskap betyr også "felles symboler", vanlige lesninger, ordtak og lignelser. Den som perfekt lærte det polske språket «det er et stort kratt i Szczebrzeszyn, en bille surrer i sivet» vil umiddelbart bli avslørt som en spion av en fremmed stat hvis han ikke svarer på spørsmålet om hva hakkespetten gjør. Klart han er i ferd med å kveles!
Dette er ikke bare en spøk. I desember 1944 startet tyskerne sin siste offensiv i Ardennene med store kostnader. De mobiliserte soldater som snakket flytende engelsk for å forstyrre bevegelsen til allierte tropper, for eksempel ved å lede dem i feil retning ved korsveier. Etter et øyeblikks overraskelse begynte amerikanerne å stille mistenkelige spørsmål til soldatene, hvis svar ville være åpenbare for en person fra Texas, Nebraska eller Georgia og ufattelige for noen som ikke vokste opp der. Uvitenhet om realitetene førte direkte til henrettelsen.
Til punktet. Jeg anbefaler til leserne boken av Lukasz Badowski og Zaslaw Adamashek "Laboratory in a Desk Drawer - Mathematics". Dette er en fantastisk bok som på glimrende vis viser at matematikk virkelig er nyttig for noe og at "matematikkeksperiment" ikke er tomme ord. Den inkluderer blant annet den beskrevne konstruksjonen av «pappgåten» – en enhet som det vil ta oss bare femten minutter å lage og som fungerer som en seriøs chiffermaskin. Ideen i seg selv var så kjent, de nevnte forfatterne løste den vakkert ut, og jeg skal endre den litt og pakke den inn i mer matematiske klær.
baufil
I en av gatene i min dacha-landsby i forstedene til Warszawa ble fortauet nylig demontert fra "trlinka" - sekskantede belegningsplater. Turen var ubehagelig, men sjelen til matematikeren gledet seg. Å dekke planet med vanlige (dvs. vanlige) polygoner er ikke lett. Det kan bare være trekanter, firkanter og vanlige sekskanter.
Kanskje jeg spøkte litt med denne åndelige gleden, men sekskanten er en vakker figur. Fra den kan du lage en ganske vellykket krypteringsenhet. Geometri vil hjelpe. Sekskanten har rotasjonssymmetri - den overlapper seg selv når den roteres med et multiplum av 60 grader. Feltet merket for eksempel med bokstaven A øverst til venstre Fig. 1 etter å ha snudd gjennom denne vinkelen, vil den også falle inn i boks A - og det samme med andre bokstaver. Så la oss kutte ut seks firkanter fra rutenettet, hver med en annen bokstav. Vi legger rutenettet oppnådd på denne måten på et papirark. I de seks ledige feltene skriver du inn seks bokstaver i teksten vi ønsker å kryptere. La oss rotere arket 60 grader. Seks nye felt vil dukke opp - skriv inn de neste seks bokstavene i meldingen vår.
Ris. 1. Trlenker av matematikkens glede.
Til høyre Fig. 1 vi har en tekst kodet på denne måten: "Det er et enormt tungt damplokomotiv på stasjonen."
Nå kommer litt skolematte godt med. På hvor mange måter kan to tall ordnes i forhold til hverandre?
For et dumt spørsmål? For to: enten den ene foran eller den andre.
Fint. Og tre tall?
Det er heller ikke vanskelig å liste opp alle innstillingene:
123, 132, 213, 231, 312, 321.
Vel, det er for fire! Det kan fortsatt staves tydelig. Gjett rekkefølgeregelen jeg la inn:
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 sifrene er fem, får vi 120 mulige innstillinger. La oss ringe dem kombinasjonsmuligheter. Antall mulige permutasjoner av n tall er produktet 1 2 3 ... n, kalt sterk og markert med et utropstegn: 3!=6, 4!=24, 5!=120. For neste nummer 6 har vi 6!=720. Vi bruker dette til å gjøre vårt sekskantede chifferskjold mer komplekst.
Vi velger en permutasjon av tall fra 0 til 5, for eksempel 351042. Vår sekskantede krypteringsskive har en strek i midtfeltet - slik at den kan settes "i nullposisjon" - en strek opp, som på fig. 1. Vi legger disken på denne måten på et ark som vi skal skrive rapporten vår på, men vi skriver den ikke med en gang, men snur den tre ganger med 60 grader (dvs. 180 grader) og skriver inn seks bokstaver i de tomme feltene. Vi går tilbake til startposisjonen. Vi dreier skiven fem ganger med 60 grader, det vil si fem "tenner" på skiven vår. Vi trykker. Den neste skalaposisjonen er posisjonen rotert 60 grader rundt null. Den fjerde posisjonen er 0 grader, dette er startposisjonen.
Forstår du hva som skjedde? Vi har en ekstra mulighet - å komplisere "maskinen" vår med mer enn syv hundre ganger! Så vi har to uavhengige posisjoner av "automaten" - valget av rutenettet og valget av permutasjonen. Rutenettet kan velges på 66 = 46656 måter, permutasjon 720. Dette gir 33592320 muligheter. Over 33 millioner chiffer! Nesten litt mindre, fordi noen rutenett kan ikke kuttes ut av papir.
I nedre del Fig. 1 vi har en melding kodet slik: "Jeg sender deg fire fallskjermdivisjoner." Det er lett å forstå at fienden ikke skal få vite om dette. Men vil han forstå noe av dette:
ТПОРОПВМАНВЕОРДИЗЗ
ÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅ
selv med signatur 351042?
Vi bygger Enigma, en tysk chiffermaskin
Ris. 2. Et eksempel på det første oppsettet av krypteringsmaskinen vår.
Permutasjoner (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Som jeg allerede har nevnt, skylder jeg ideen om å lage en slik pappmaskin til boken "Lab in a Drawer - Mathematics". Min "konstruksjon" er noe annerledes enn den som er gitt av forfatterne.
Chiffermaskinen som ble brukt av tyskerne under krigen hadde et genialt enkelt prinsipp, noe likt det vi så med sekskantsifferet. Hver gang det samme: bryte hard tildeling av et brev til en annen bokstav. Den må være utskiftbar. Hvordan gjøre det for å ha kontroll over det?
La oss velge ikke en hvilken som helst permutasjon, men en som har sykluser med lengde 2. Enkelt sagt, noe sånt som "Gaderipoluk" beskrevet her for noen måneder siden, men som dekker alle bokstavene i alfabetet. La oss bli enige om 24 bokstaver - uten ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Hvor mange slike permutasjoner? Dette er en oppgave for nyutdannede på videregående (de skal kunne løse det med en gang). Hvor mange? Mye av? Flere tusen? Ja:
1912098225024001185793365052108800000000 (la oss ikke engang prøve å lese dette nummeret). Det er så mange muligheter for å sette "null"-posisjonen. Og det kan være vanskelig.
Vår maskin består av to runde skiver. På en av dem, som fortsatt står, er det skrevet bokstaver. Det er litt som urskiven til en gammel telefon, hvor du slo et nummer ved å vri urskiven hele veien. Rotary er den andre med fargevalg. Det enkleste er å sette dem på en vanlig kork ved hjelp av en nål. I stedet for kork kan du bruke en tynn plate eller tykk papp. Lukasz Badowski og Zasław Adamaszek anbefaler å legge begge platene i en CD-boks.
Tenk deg at vi ønsker å kode ordet ARMATY (Ris. 2 og 3). Sett enheten til nullposisjon (pil opp). Bokstaven A tilsvarer F. Roter den interne kretsen en bokstav til høyre. Vi har bokstaven R å kode, nå tilsvarer den A. Etter neste rotasjon ser vi at bokstaven M tilsvarer U. Neste rotasjon (fjerde diagram) gir korrespondansen A - P. På den femte skiven har vi T - A. Til slutt (sjette sirkel ) Y – Y Fienden vil sannsynligvis ikke gjette at våre CFCFA-er vil være farlige for ham. Og hvordan vil "vår" lese utsendelsen? De må ha samme maskin, samme "programmerte", det vil si med samme permutasjon. Chifferen starter på posisjon null. Så verdien av F er A. Vri skiven med klokken. Bokstaven A er nå assosiert med R. Han vrir skiven til høyre og under bokstaven U finner M, osv. Chifferfunksjonæren løper til generalen: «General, jeg rapporterer, våpnene kommer!»
Ris. 3. Prinsippet for driften av vårt papir Enigma.
| Ris. 3. Prinsippet for driften av vårt papir Enigma. | ||
Mulighetene for selv en så primitiv Enigma er fantastiske. Vi kan velge andre utdatapermutasjoner. Vi kan - og det er enda flere muligheter her - ikke med en "serif" regelmessig, men i en viss, daglig skiftende rekkefølge, lik en sekskant (for eksempel først tre bokstaver, deretter syv, deretter åtte, fire ... .. osv. .).
Hvordan kan du gjette?! Og likevel for polske matematikere (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) skjedde. Informasjonen som ble oppnådd på denne måten var uvurderlig. Tidligere hadde de et like viktig bidrag til historien til vårt forsvar. Vaclav Serpinski i Stanislav Mazurkevichsom brøt koden for russiske tropper i 1920. Den avlyttede kabelen ga Piłsudski muligheten til å gjøre den berømte manøveren fra Vepsz-elven.
Jeg husker Vaslav Sierpinski (1882-1969). Han virket som en matematiker som omverdenen ikke eksisterte for. Han kunne ikke snakke om sin deltakelse i seieren i 1920 både av militære og ... av politiske årsaker (myndighetene i den polske folkerepublikken likte ikke de som forsvarte oss fra Sovjetunionen).
Ris. 4. Permutasjon (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Ris. 5. Vakker dekorasjon, men ikke egnet for kryptering. For regelmessig.
Oppgave 1. Na Fig. 4 du har en annen permutasjon for å lage Enigma. Kopier tegningen til xerografen. Bygg en bil, kode for- og etternavnet ditt. Min CWONUE JTRYGT. Hvis du trenger å holde notatene dine private, bruk Cardboard Enigma.
Oppgave 2. Krypter navnet ditt og etternavnet til en av "bilene" du så, men (oppmerksomhet!) med en ekstra komplikasjon: vi svinger ikke ett hakk til høyre, men i henhold til skjemaet {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - det vil si først av en, så av to, så av tre, så med 2, så igjen med 1, deretter med 2, osv., en slik "wavelet" . Sørg for at for- og etternavnet mitt er kryptert som CZTTAK SDBITH. Nå forstår du hvor kraftig Enigma-maskinen var?
Problemløsning for nyutdannede på videregående skole. Hvor mange konfigurasjonsalternativer for Enigma (i denne versjonen, som beskrevet i artikkelen)? Vi har 24 bokstaver. Vi velger det første bokstavparet - dette kan gjøres på
måter. Det neste paret kan velges på
måter, mer
etc. Etter de tilsvarende beregningene (alle tall må multipliseres), får vi
151476660579404160000
Deretter deler du tallet med 12! (12 faktorielle), fordi de samme parene kan oppnås i en annen rekkefølge. Så til slutt får vi "totalt"
316234143225,
det er litt over 300 milliarder, som ikke virker som et svimlende stort tall for dagens superdatamaskiner. Men hvis den tilfeldige rekkefølgen av selve permutasjonene tas i betraktning, øker dette tallet betydelig. Vi kan også tenke på andre typer permutasjoner.
Se også:
