Cifre e spie
Nell'angolo della matematica di oggi, darò un'occhiata a un argomento che ho discusso all'annuale campo scientifico per bambini della National Children's Foundation. La fondazione cerca bambini e giovani con interessi scientifici. Non devi essere estremamente dotato, ma devi avere una "vena scientifica". Non sono richiesti ottimi voti scolastici. Provalo, potrebbe piacerti. Se sei uno studente delle scuole elementari o delle superiori, fai domanda. Di solito sono i genitori o la scuola a fare le segnalazioni, ma non sempre è così. Trova il sito web della Fondazione e scoprilo.
A scuola si parla sempre di più di "codifica", riferendosi all'attività precedentemente nota come "programmazione". Questa è una procedura comune per gli educatori teorici. Scavano vecchi metodi, danno loro un nuovo nome e il "progresso" viene fatto da solo. Ci sono diverse aree in cui si verifica un tale fenomeno ciclico.
Si può concludere che svaloro la didattica. No. Nello sviluppo della civiltà, a volte torniamo a ciò che era, è stato abbandonato e ora viene rianimato. Ma il nostro angolo è matematico, non filosofico.
Appartenere a una determinata comunità significa anche "simboli comuni", letture comuni, detti e parabole. Colui che ha imparato perfettamente la lingua polacca "c'è un grande boschetto a Szczebrzeszyn, uno scarafaggio ronza tra i canneti" sarà immediatamente smascherato come una spia di uno stato straniero se non risponde alla domanda su cosa sta facendo il picchio. Certo che sta soffocando!
Questo non è solo uno scherzo. Nel dicembre 1944, i tedeschi lanciarono la loro ultima offensiva nelle Ardenne a grandi spese. Hanno mobilitato soldati che parlavano correntemente l'inglese per interrompere il movimento delle truppe alleate, ad esempio guidandole nella direzione sbagliata agli incroci. Dopo un momento di sorpresa, gli americani hanno cominciato a porre ai soldati domande sospette, le cui risposte sarebbero state ovvie per una persona del Texas, del Nebraska o della Georgia e inconcepibili per qualcuno che non fosse cresciuto lì. L'ignoranza della realtà ha portato direttamente all'esecuzione.
Al punto. Raccomando ai lettori il libro di Lukasz Badowski e Zaslaw Adamashek "Laboratorio in un cassetto della scrivania - Matematica". Questo è un libro meraviglioso che mostra brillantemente che la matematica è davvero utile per qualcosa e che "l'esperimento di matematica" non è parole vuote. Include, tra le altre cose, la costruzione descritta dell '"enigma di cartone", un dispositivo che richiederà solo quindici minuti per essere creato e che funziona come una seria macchina cifrante. L'idea in sé era così ben nota, gli autori menzionati l'hanno elaborata magnificamente, e la cambierò un po' e la avvolgerò in abiti più matematici.
seghetti
In una delle strade del mio villaggio di dacia alla periferia di Varsavia, la pavimentazione è stata recentemente smantellata da "trlinka" - lastre di pavimentazione esagonali. La corsa era scomoda, ma l'anima del matematico si rallegrava. Coprire il piano con poligoni regolari (cioè regolari) non è facile. Può essere solo triangoli, quadrati ed esagoni regolari.
Forse ho scherzato un po' con questa gioia spirituale, ma l'esagono è una bella figura. Da esso puoi creare un dispositivo di crittografia abbastanza efficace. La geometria aiuterà. L'esagono ha simmetria rotazionale: si sovrappone a se stesso quando viene ruotato di un multiplo di 60 gradi. Il campo contrassegnato, ad esempio, con la lettera A in alto a sinistra Fico. 1 dopo aver girato attraverso questo angolo, cadrà anche nella casella A - e lo stesso con altre lettere. Quindi ritagliamo sei quadrati dalla griglia, ognuno con una lettera diversa. Mettiamo la griglia così ottenuta su un foglio di carta. Nei sei campi liberi, inserisci sei lettere del testo che vogliamo crittografare. Ruotiamo il foglio di 60 gradi. Appariranno sei nuovi campi: inserisci le successive sei lettere del nostro messaggio.
Riso. 1. Trilli della gioia della matematica.
A destra Fico. 1 abbiamo un testo codificato in questo modo: "C'è un'enorme locomotiva a vapore pesante alla stazione".
Ora un po' di matematica scolastica tornerà utile. In quanti modi si possono disporre due numeri l'uno rispetto all'altro?
Che domanda stupida? Per due: o uno davanti o l'altro.
Bene. E tre numeri?
Inoltre non è difficile elencare tutte le impostazioni:
123, 132, 213, 231, 312, 321.
Bene, è per quattro! Può ancora essere chiaramente esplicitato. Indovina la regola dell'ordine che ho messo:
1234, 1243, 1423 4123, 1324, 1342,
1432 4132, 2134, 2143, 2413 4213
2314, 2341, 2431 4231, 3124, 3142,
3412 4312, 3214, 3241, 3421 4321
Quando le cifre sono cinque, otteniamo 120 possibili impostazioni. Chiamiamoli permutazioni. Il numero di possibili permutazioni di n numeri è il prodotto 1 2 3 ... n, chiamato сильный e contrassegnati da un punto esclamativo: 3!=6, 4!=24, 5!=120. Per il prossimo numero 6 abbiamo 6!=720. Lo useremo per rendere più complesso il nostro scudo cifrato esagonale.
Scegliamo una permutazione di numeri da 0 a 5, ad esempio 351042. Il nostro disco di rimescolamento esagonale ha un trattino nel campo centrale - in modo che possa essere messo "in posizione zero" - un trattino in alto, come in fig. 1. Mettiamo il disco in questo modo su un foglio su cui dobbiamo scrivere la nostra relazione, ma non lo scriviamo subito, ma lo giriamo tre volte di 60 gradi (cioè 180 gradi) e scriviamo sei lettere in i campi vuoti. Torniamo alla posizione di partenza. Giriamo il quadrante cinque volte di 60 gradi, cioè di cinque "denti" del nostro quadrante. Stampiamo. La posizione della scala successiva è la posizione ruotata di 60 gradi attorno allo zero. La quarta posizione è 0 gradi, questa è la posizione di partenza.
Capisci cosa è successo? Abbiamo un'ulteriore opportunità: complicare la nostra "macchina" di oltre settecento volte! Quindi, abbiamo due posizioni indipendenti dell '"automa": la scelta della griglia e la scelta della permutazione. La griglia può essere scelta in 66 = 46656 modi, permutazione 720. Questo dà 33592320 possibilità. Oltre 33 milioni di cifre! Quasi un po' meno, perché alcune griglie non possono essere ritagliate dalla carta.
Nella parte inferiore Fico. 1 abbiamo un messaggio codificato in questo modo: "Ti mando quattro divisioni di paracadute". È facile capire che al nemico non dovrebbe essere permesso di saperlo. Ma capirà qualcosa di tutto questo:
ТПОРОПВМАНВЕОРДИЗЗ
YYLOAKVMDEYCHESH,
anche con firma 351042?
Stiamo costruendo Enigma, una macchina di cifratura tedesca
Riso. 2. Un esempio della configurazione iniziale della nostra macchina di crittografia.
Permutazioni (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Come ho già accennato, devo l'idea di creare una macchina di cartone del genere al libro "Lab in a Drawer - Mathematics". La mia "costruzione" è in qualche modo diversa da quella data dai suoi autori.
La macchina cifrante usata dai tedeschi durante la guerra aveva un principio ingegnosamente semplice, in qualche modo simile a quello che abbiamo visto con il cifrario esadecimale. Ogni volta la stessa cosa: rompere duro assegnazione di una lettera a un'altra lettera. Deve essere sostituibile. Come farlo per avere il controllo su di esso?
Scegliamo non una qualsiasi permutazione, ma una che abbia cicli di lunghezza 2. In poche parole, qualcosa come il "Gaderipoluk" descritto qui qualche mese fa, ma che copre tutte le lettere dell'alfabeto. Mettiamoci d'accordo su 24 lettere - senza ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Quante di queste permutazioni? Questo è un compito per i diplomati delle scuole superiori (dovrebbero essere in grado di risolverlo subito). Quanti? Molti? Molte migliaia? SÌ:
1912098225024001185793365052108800000000 (non proviamo nemmeno a leggere questo numero). Ci sono così tante possibilità per impostare la posizione "zero". E può essere difficile.
La nostra macchina è composta da due dischi tondi. Su uno di essi, che è ancora in piedi, sono scritte delle lettere. È un po' come il quadrante di un vecchio telefono, in cui si compone un numero ruotando completamente il quadrante. Il Rotary è il secondo con una combinazione di colori. Il modo più semplice è metterli su un normale tappo di sughero usando uno spillo. Invece del sughero, puoi usare una tavola sottile o un cartone spesso. Lukasz Badowski e Zasław Adamaszek consigliano di mettere entrambi i dischi in una scatola per CD.
Immagina di voler codificare la parola ARMATY (Riso. 2 e 3). Impostare il dispositivo in posizione zero (freccia su). La lettera A corrisponde a F. Ruotare il circuito interno di una lettera verso destra. Abbiamo la lettera R da codificare, ora corrisponde ad A. Dopo la rotazione successiva, vediamo che la lettera M corrisponde a U. La rotazione successiva (quarto diagramma) dà la corrispondenza A - P. Sul quinto quadrante abbiamo T - A. Infine (sesto cerchio) Y – Y Il nemico probabilmente non indovinerà che i nostri CFCFA saranno pericolosi per lui. E come leggerà il dispaccio il “nostro”? Devono avere la stessa macchina, la stessa "programmata", cioè con la stessa permutazione. La cifra inizia dalla posizione zero. Quindi il valore di F è A. Ruota la manopola in senso orario. La lettera A è ora associata alla R. Gira la manopola verso destra e sotto la lettera U trova la M, ecc.
Riso. 3. Il principio di funzionamento della nostra carta Enigma.
| Riso. 3. Il principio di funzionamento della nostra carta Enigma. | ||
Le possibilità anche di un Enigma così primitivo sono sorprendenti. Possiamo scegliere altre permutazioni di output. Possiamo - e ci sono ancora più opportunità qui - non di un "serif" regolarmente, ma in un certo ordine che cambia quotidianamente, simile a un esagono (ad esempio, prima tre lettere, poi sette, poi otto, quattro ... .. ecc. .).
Come puoi indovinare?! Eppure per i matematici polacchi (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) accaduto. Le informazioni così ottenute sono state preziose. In precedenza, hanno dato un contributo altrettanto importante alla storia della nostra difesa. Vaclav Serpinski i Stanislav Mazurkevičche ha violato il codice delle truppe russe nel 1920. Il cavo intercettato ha dato a Piłsudski l'opportunità di effettuare la famosa manovra dal fiume Vepsz.
Ricordo Vaslav Sierpinski (1882-1969). Sembrava un matematico per il quale il mondo esterno non esisteva. Non poteva parlare della sua partecipazione alla vittoria nel 1920 sia per motivi militari che ... per motivi politici (alle autorità della Repubblica popolare polacca non piacevano coloro che ci difendevano dall'Unione Sovietica).
Riso. 4. Permutazione (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Riso. 5. Bella decorazione, ma non adatta per la crittografia. Troppo regolarmente.
Lavoro 1. Na Fico. 4 hai un'altra permutazione per creare Enigma. Copia il disegno sulla xerografia. Costruisci un'auto, codifica il tuo nome e cognome. Il mio CWONUE JTRYGT. Se hai bisogno di mantenere private le tue note, usa Cardboard Enigma.
Lavoro 2. Criptiamo il tuo nome e cognome di una delle “macchine” che hai visto, ma (attenzione!) con un'ulteriore complicazione: giriamo non di una tacca a destra, ma secondo lo schema {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - cioè prima di uno, poi di due, poi di tre, poi di 2, poi di nuovo di 1, poi di 2, ecc., un tale "wavelet" . Assicurati che il mio nome e cognome siano crittografati come CZTTAK SDBITH. Ora capisci quanto era potente la macchina Enigma?
Risoluzione dei problemi per i diplomati delle scuole superiori. Quante opzioni di configurazione per Enigma (in questa versione, come descritto nell'articolo)? Abbiamo 24 lettere. Selezioniamo la prima coppia di lettere: questo può essere fatto
modi. È possibile scegliere la coppia successiva
modi, di più
eccetera. Dopo i calcoli corrispondenti (tutti i numeri devono essere moltiplicati), otteniamo
151476660579404160000
Quindi dividi quel numero per 12! (12 fattoriale), perché le stesse coppie possono essere ottenute in un ordine diverso. Quindi alla fine otteniamo "totale"
316234143225
sono poco più di 300 miliardi, che non sembra un numero sbalorditivo per i supercomputer di oggi. Tuttavia, se si tiene conto dell'ordine casuale delle permutazioni stesse, questo numero aumenta in modo significativo. Possiamo anche pensare ad altri tipi di permutazioni.
Vedi anche:
