Xifrats i espies

Al racó de matemàtiques d'avui, donaré un cop d'ull a un tema que vaig parlar al campament científic anual per a nens de la National Children's Foundation. La fundació busca nens i joves amb interessos científics. No cal que siguis extremadament dotat, però sí que cal tenir una "venta científica". No calen molt bones notes escolars. Prova-ho, potser t'agrada. Si sou un estudiant de secundària o secundària, sol·liciteu-lo. Normalment els pares o l'escola fan els informes, però no sempre és així. Busca el web de la Fundació i informa't.

Cada cop es parla més a l'escola de “codificació”, referint-se a l'activitat que abans es coneixia com a “programació”. Aquest és un procediment comú per als educadors teòrics. Exteguen mètodes antics, els donen un nou nom i el "progrés" es fa per si mateix. Hi ha diverses àrees on es produeix aquest fenomen cíclic.

Es pot concloure que devaluo la didàctica. No. En el desenvolupament de la civilització, de vegades tornem al que va ser, va ser abandonat i ara es reviu. Però el nostre racó és matemàtic, no filosòfic.

Pertànyer a una determinada comunitat significa també “símbols comuns”, lectures, dites i paràboles comuns. Aquell que va aprendre perfectament la llengua polonesa "hi ha un gran matoll a Szczebrzeszyn, un escarabat brunzit a les canyes" serà immediatament exposat com un espia d'un estat estranger si no respon a la pregunta de què està fent el picot. És clar que s'està sufocant!

Això no és només una broma. El desembre de 1944, els alemanys van llançar la seva última ofensiva a les Ardenes amb un gran cost. Van mobilitzar soldats que parlaven anglès amb fluïdesa per interrompre el moviment de les tropes aliades, per exemple conduint-los en la direcció equivocada a les cruïlles de camins. Després d'un moment de sorpresa, els nord-americans van començar a fer preguntes sospitoses als soldats, les respostes serien òbvies per a una persona de Texas, Nebraska o Geòrgia i inconcebibles per a algú que no hi creixia. El desconeixement de les realitats va portar directament a l'execució.

Fins al punt. Recomano als lectors el llibre de Lukasz Badowski i Zaslaw Adamashek "Laboratori en un calaix d'escriptori - Matemàtiques". Aquest és un llibre meravellós que demostra de manera brillant que les matemàtiques són realment útils per a alguna cosa i que "l'experiment matemàtic" no són paraules buides. Inclou, entre altres coses, la construcció descrita de l'"enigma del cartró", un dispositiu que només ens trigarà quinze minuts a crear i que funciona com una màquina de xifrat seriosa. La idea en si era tan coneguda, els autors esmentats la van treballar molt bé, i la canviaré una mica i l'embolicaré amb roba més matemàtica.

serres per a metals

En un dels carrers del meu poble de datxa als suburbis de Varsòvia, el paviment es va desmuntar recentment de "trlinka": lloses hexagonals. El viatge va ser incòmode, però l'ànima del matemàtic es va alegrar. Cobrir el pla amb polígons regulars (és a dir, regulars) no és fàcil. Només pot ser triangles, quadrats i hexàgons regulars.

Potser vaig fer broma una mica amb aquesta alegria espiritual, però l'hexàgon és una figura preciosa. A partir d'ell podeu fer un dispositiu de xifratge bastant reeixit. La geometria ajudarà. L'hexàgon té simetria de rotació: se superposa quan es gira per un múltiple de 60 graus. El camp marcat, per exemple, amb la lletra A a la part superior esquerra fig. 1 després de girar per aquest angle, també caurà a la casella A - i el mateix amb altres lletres. Així que tallem sis quadrats de la quadrícula, cadascun amb una lletra diferent. Posem la graella obtinguda d'aquesta manera en un full de paper. Als sis camps lliures, introduïu sis lletres del text que volem xifrar. Girem la làmina 60 graus. Apareixeran sis camps nous: introduïu les sis lletres següents del nostre missatge.

Arròs. 1. Trlinks de l'alegria de les matemàtiques.

A la dreta fig. 1 tenim un text codificat d'aquesta manera: "A l'estació hi ha una enorme locomotora de vapor pesada".

Ara una mica de matemàtiques escolars seran útils. De quantes maneres es poden ordenar dos nombres entre si?

Quina pregunta més estúpida? Per a dos: o un davant o l'altre.

Bé. I tres números?

Tampoc és difícil enumerar tots els paràmetres:

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

Bé, és per a quatre! Encara es pot explicar clarament. Endevina la regla d'ordre que vaig posar:

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

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

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

3412, 4312, 3214, 3241, 3421, 4321

Quan els dígits són cinc, obtenim 120 configuracions possibles. Anem a cridar-los permutacions. El nombre de permutacions possibles de n nombres és el producte 1 2 3 ... n, anomenat fort i marcat amb un signe d'exclamació: 3!=6, 4!=24, 5!=120. Per al següent número 6 tenim 6!=720. Ho farem servir per fer més complex el nostre escut de xifrat hexagonal.

Escollim una permutació de nombres del 0 al 5, per exemple 351042. El nostre disc de codificació hexagonal té un guionet al camp central -per tal que es pugui posar "en la posició zero"- un guió cap amunt, com a la fig. 1. Posem el disc d'aquesta manera en un full de paper on hem d'escriure el nostre informe, però no l'escrivim de seguida, sinó que el girem tres vegades 60 graus (és a dir, 180 graus) i introduïm sis lletres a els camps buits. Tornem a la posició inicial. Girem el dial cinc vegades 60 graus, és a dir, cinc "dents" del nostre dial. Imprimim. La següent posició de l'escala és la posició girada 60 graus al voltant de zero. La quarta posició és de 0 graus, aquesta és la posició inicial.

Entens què va passar? Tenim una oportunitat addicional: complicar la nostra "màquina" més de set-centes vegades! Per tant, tenim dues posicions independents de l'"autòmat": l'elecció de la graella i l'elecció de la permutació. La graella es pot triar de 66 = 46656 maneres, permutació 720. Això dóna 33592320 possibilitats. Més de 33 milions de xifres! Gairebé una mica menys, perquè algunes graelles no es poden tallar del paper.

A la part inferior fig. 1 tenim un missatge codificat així: "Us envio quatre divisions de paracaigudes". És fàcil entendre que no s'ha de permetre que l'enemic s'assabenti d'això. Però entendrà alguna cosa d'això:

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

YYLOAKVMDEYCHESH,

fins i tot amb la signatura 351042?

Estem construint Enigma, una màquina de xifrat alemanya

Arròs. 2. Un exemple de la configuració inicial de la nostra màquina de xifratge.

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

Com ja he comentat, dec la idea de crear una màquina de cartró com el llibre "Lab in a Drawer - Mathematics". La meva "construcció" és una mica diferent de la que van donar els seus autors.

La màquina de xifratge utilitzada pels alemanys durant la guerra tenia un principi enginyós i senzill, una mica semblant al que vam veure amb el xifrat hexadecimal. Cada cop el mateix: trencar l'assignació dura d'una carta a una altra. Ha de ser substituible. Com fer-ho per tenir-ne el control?

Triem no cap permutació, sinó una que tingui cicles de longitud 2. En poques paraules, una cosa com el "Gaderipoluk" descrit aquí fa uns mesos, però que cobreix totes les lletres de l'alfabet. Posem-nos d'acord en 24 lletres - sense ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Quantes permutacions d'aquest tipus? Aquesta és una tasca per als graduats de batxillerat (haurien de poder resoldre-ho de seguida). Quants? Molt de? Uns quants milers? Sí:

1912098225024001185793365052108800000000 (ni intentem ni llegir aquest número). Hi ha tantes possibilitats per establir la posició "zero". I pot ser difícil.

La nostra màquina consta de dos discs rodons. En un d'ells, que encara està en peu, hi ha escrites cartes. És una mica com el marcatge d'un telèfon antic, on marcaves un número girant el dial fins al final. Rotary és el segon amb un esquema de colors. La manera més senzilla és posar-los en un tap de suro normal amb un passador. En comptes de suro, podeu utilitzar un tauler prim o un cartró gruixut. Lukasz Badowski i Zasław Adamaszek recomanen col·locar els dos discos en una caixa de CD.

Imagineu que volem codificar la paraula ARMATY (Arròs. 2 i 3). Establiu el dispositiu a la posició zero (fletxa cap amunt). La lletra A correspon a la F. Gira el circuit intern una lletra cap a la dreta. Tenim la lletra R per codificar, ara correspon a A. Després del següent gir, veiem que la lletra M correspon a U. El següent gir (quart diagrama) dóna la correspondència A - P. Al cinquè dial tenim T - A. Finalment (sisè cercle ) S – S Probablement l'enemic no endevinarà que els nostres CFCFA seran perillosos per a ell. I com llegiran els "nostres" el despatxo? Han de tenir la mateixa màquina, la mateixa "programada", és a dir, amb la mateixa permutació. El xifrat comença a la posició zero. Per tant, el valor de F és A. Gireu el dial en sentit horari. La lletra A s'associa ara amb la R. Gira el dial cap a la dreta i sota la lletra U troba M, etc. L'oficinista del xifratge corre cap al general: "General, estic informant, arriben les pistoles!"

Arròs. 3. El principi de funcionament del nostre paper Enigma.

Arròs. 3. El principi de funcionament del nostre paper Enigma.

Les possibilitats d'un Enigma tan primitiu són sorprenents. Podem triar altres permutacions de sortida. Podem, i encara hi ha més oportunitats aquí, no per una "serif" regularment, sinó en un ordre que canvia diàriament, semblant a un hexàgon (per exemple, tres primeres lletres, després set, després vuit, quatre ... .. etc. .).

Com ho pots endevinar?! I tanmateix per als matemàtics polonesos (Marian Reevski, Henry Zigalski, Jerzy Ruzicki) succeït. La informació així obtinguda va ser inestimable. Anteriorment, van tenir una contribució igualment important a la història de la nostra defensa. Vaclav Sierpinski i Stanislav Mazurkevitxque va violar el codi de les tropes russes el 1920. El cable interceptat va donar a Piłsudski l'oportunitat de fer la famosa maniobra des del riu Vepsz.

Recordo Vaslav Sierpinski (1882-1969). Semblava un matemàtic per a qui el món exterior no existia. No va poder parlar de la seva participació en la victòria de 1920 tant per motius militars com... polítics (a les autoritats de la República Popular de Polònia no els agradaven els que ens defensaven des de la Unió Soviètica).

Fig. 4. Permutació (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Arròs. 5. Decoració bonica, però no apta per al xifratge. Massa regularment.

Treball 1. Na fig. 4 tens una altra permutació per crear Enigma. Copia el dibuix al xerògraf. Construeix un cotxe, codifica el teu nom i cognom. El meu CWONUE JTRYGT. Si necessiteu mantenir les vostres notes privades, feu servir Cardboard Enigma.

Treball 2. Xifra el teu nom i cognoms d'un dels "cotxes" que has vist, però (atenció!) amb una complicació addicional: no girem ni una osca cap a la dreta, sinó segons l'esquema {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - és a dir, primer per un, després per dos, després per tres, després per 2, després de nou per 1, després per 2, etc., com una "wavelet" . Assegureu-vos que el meu nom i cognoms estiguin xifrats com a CZTTAK SDBITH. Ara enteneu com de poderosa era la màquina Enigma?

Resolució de problemes per als graduats de batxillerat. Quantes opcions de configuració per a Enigma (en aquesta versió, tal com es descriu a l'article)? Tenim 24 lletres. Seleccionem el primer parell de lletres; això es pot fer

maneres. La següent parella es pot triar

maneres, més

etc. Després dels càlculs corresponents (tots els nombres s'han de multiplicar), obtenim

151476660579404160000

Aleshores divideix aquest nombre per 12! (12 factorial), perquè els mateixos parells es poden obtenir en un ordre diferent. Així que al final obtenim "total"

316234143225,

això són poc més de 300 milions, que no sembla una xifra sorprenentment gran per als superordinadors actuals. Tanmateix, si es té en compte l'ordre aleatori de les permutacions, aquest nombre augmenta significativament. També podem pensar en altres tipus de permutacions.

Vegeu també: