Cifrados e espías
No Math Corner de hoxe, vou analizar un tema que discutín no Campamento de Ciencias Infantiles anual da National Children's Foundation. A fundación busca nenos e mozos con intereses científicos. Non tes que ser moi dotado, pero tes que ter unha vena científica. Non se requiren moi boas notas escolares. Proba, quizais che guste. Se es estudante de educación primaria ou secundaria, solicita. Normalmente, os informes son feitos polos pais ou pola escola, pero non sempre é así. Busca a web da Fundación e infórmate de todo.
Cada vez fálase máis na escola de "codificación", referíndose á actividade antes coñecida como "programación". Este é un procedemento común entre os teóricos da educación. Desenterran métodos antigos, danlles un novo nome e o "progreso" ocorre por si só. Son varias as zonas onde se produce este fenómeno cíclico.
Pódese concluír que desvalorizo a didáctica. Non. No desenvolvemento da civilización, ás veces volvemos ao que foi, foi abandonado e agora está a ser revivido. Pero o noso recuncho é matemático, non filosófico.
Pertenza a unha determinada comunidade significa tamén “símbolos comúns”, lecturas, refráns e parábolas comúns. Calquera persoa que aprendese inmaculadamente a lingua polaca "hai un gran mato en Szczebrzeszyn, un escaravello zumba entre as canas" será inmediatamente exposto como espía dunha potencia estranxeira se non responde á pregunta de que fai o paxaro. Claro que está atragantando!
Isto non é só unha broma. En decembro de 1944, os alemáns lanzaron a súa ofensiva final nas Ardenas con grandes gastos. Mobilizaron soldados que falaban inglés con fluidez para perturbar o movemento das tropas aliadas, por exemplo dirixíndoas na dirección equivocada nas encrucilladas. Despois dun momento de sorpresa, os estadounidenses comezaron a facerlles aos soldados preguntas sospeitosas, cuxas respostas serían obvias para unha persoa de Texas, Nebraska ou Xeorxia, pero impensables para alguén que non crecera alí. O descoñecemento das realidades levou directamente á execución.
Ata o punto. Recomendo aos lectores o libro de Lukasz Badovsky e Zaslav Adamasek "Laboratorio nun caixón de escritorio - matemáticas". Este é un libro marabilloso que demostra brillantemente que as matemáticas son realmente útiles para algo e que o "experimento matemático" non son só palabras baleiras. Inclúe, entre outras cousas, o deseño descrito dun "enigma de cartón", un dispositivo que só nos levará quince minutos en crear e que funciona como unha máquina de cifrado seria. A idea en si era tan coñecida, que os autores mencionados fixérona moi ben, e vouno cambiar un pouco e envolvela con roupa máis matemática.
Serras de cifrado
Nunha das rúas da miña vila de vacacións nos suburbios de Varsovia, un pavimento feito de "trlinka" -lousas hexagonais- foi desmantelado recentemente. Era incómodo viaxar, pero a alma do matemático alegrouse. Cubrir un plano con polígonos regulares (é dicir, regulares) non é doado. Estes só poden ser triángulos, cadrados e hexágonos regulares.
Quizais fose un pouco unha broma con esta alegría sincera, pero un hexágono é unha forma fermosa. Pódese usar para facer un dispositivo de cifrado bastante exitoso. A xeometría axudará. O hexágono ten simetría de rotación: superponse cando se xira un factor de 60 graos. Un campo marcado, por exemplo, coa letra A na parte superior esquerda fig. 1 despois de virar por este ángulo, tamén caerá no campo A - e o mesmo coas outras letras. Entón, imos recortar seis cadrados da grella, cada un cunha letra diferente. Coloque a reixa resultante nunha folla de papel. Nos seis campos libres, introduza seis letras do texto que queremos cifrar. Xiremos a folla 60 graos. Aparecerán seis novos campos: introduza as seguintes seis letras da nosa mensaxe.
Arroz. 1. Trlinks de alegría en matemáticas.
Á dereita fig. 1 temos o texto codificado deste xeito: "Hai unha enorme locomotora de vapor pesada na estación".
Agora un pouco de matemáticas escolares serán útiles. De cantas maneiras se poden ordenar dous números entre si?
Que pregunta máis estúpida? Para dous: ou un diante ou outro.
Genial. E tres números?
Tampouco é difícil enumerar todas as opcións:
123, 132, 213, 231, 312 e 321.
Ben, iso é para catro! Aínda se pode afirmar claramente. Adiviña a regra de orde que puxen:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
Cando hai cinco números, obtemos 120 opcións de configuración posibles. Chamémoslles permutacións. O número de posibles permutacións de n números é o produto de 1 · 2 · 3 · … · n, chamado forte e márcanse cun signo de admiración: 3!=6, 4!=24, 5!=120. Para o seguinte número 6 temos 6!=720. Usaremos isto para engadir máis complexidade ao noso escudo de cifrado hexagonal.
Escollemos unha permutación de números do 0 ao 5, por exemplo 351042. O noso disco de codificación hexagonal ten un guión no campo medio, para que se poida poñer "na posición cero", cun guión cara arriba, como na Fig. 1. Colocamos así o disco nunha folla de papel na que escribiremos o noso informe, pero non o escribimos de inmediato, senón que o xiramos tres veces 60 graos (é dicir, 180 graos) e escribimos seis letras no campos baleiros. Volvemos á posición inicial. Xiramos o dial cinco veces en 60 graos, é dicir, cinco "dentes" do noso disco. Estamos imprimindo. A seguinte posición da escala é a posición rotada 60 graos arredor de cero. A cuarta posición é de 0 graos, esta é a posición inicial.
Entendes o que pasou? Temos unha oportunidade adicional: complicar a nosa "máquina" máis de setecentas veces! Polo tanto, temos dúas posicións independentes do "autómata": escoller unha reixa e escoller unha permutación. A grella pódese escoller de 66 = 46656 formas, a permutación 720. Isto dá 33592320 posibilidades. Máis de 33 millóns de cifras! Case un pouco menos, porque Algunhas cuadrículas non se poden cortar de papel.
Na parte baixa fig. 1 temos unha mensaxe codificada así: "Envíoche catro divisións de paracaídas". É doado entender que o inimigo non pode ser informado sobre isto. Pero entenderá algo disto:
TPOROPVMANVEORDISZ
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
mesmo coa sinatura 351042?
Estamos construíndo Enigma, unha máquina de cifrado alemá
Arroz. 2. Un exemplo da configuración inicial da nosa máquina de cifrado.
Permutacións (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Como xa dixen, débolle a idea de crear unha máquina de cartón así ao libro "Lab in a Desk Drawer - Mathematics". A miña "construción" é algo distinta á dada polos seus autores.
A máquina de cifrado utilizada polos alemáns durante a guerra tiña un principio enxeñosamente sinxelo, algo semellante ao que vimos co cifrado hexadecimal. Cada vez é o mesmo: romper a difícil asignación dunha carta a outra letra. Debe ser substituíble. Como facelo para ter control sobre el?
Escollemos non unha permutación calquera, senón unha que teña ciclos de lonxitude 2. En pocas palabras, algo así como o “Gaderipoluka” descrito aquí hai uns meses, pero que abrangue todas as letras do alfabeto. Poñemos de acordo en 24 letras - sen ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Cantas permutacións hai? Esta é unha tarefa para os titulados de secundaria (deberían poder resolvelo de inmediato). Cantos? Moito? Varios miles? Si:
1912098225024001185793365052108800000000 (non tentemos nin ler este número). Hai moitas posibilidades para establecer a posición "cero". E pode ser difícil.
A nosa máquina consta de dous discos redondos. Un deles, que aínda está en pé, ten escritas letras. É un pouco como a marcación dun teléfono antigo, onde marcaba un número xirando o dial ata o final. Rotary é o segundo con esquema de cores. O xeito máis sinxelo é poñelos nunha cortiza normal usando un alfinete. En lugar de cortiza, podes usar unha placa fina ou cartón groso. Lukasz Badowski e Zaslav Adamaszek recomendan colocar ambos os discos nunha caixa de CD.
Imaxinemos que queremos codificar a palabra ARMATY (Arroz. 2 e 3). Coloque o dispositivo na posición cero (frecha cara arriba). A letra A corresponde a F. Xira o diagrama interno unha letra cara á dereita. Temos a letra R para codificar, agora corresponde a A. Despois da seguinte rotación vemos que a letra M corresponde a U. A seguinte rotación (cuarto diagrama) dá a correspondencia A - P. No quinto dial temos T - A. Finalmente (sexto círculo) D – D O inimigo probablemente non se decatará de que os nosos CFC serán perigosos para el. Como lerá "o noso pobo" o despacho? Deben ter a mesma máquina, idénticamente “programada”, é dicir, coa mesma permutación. O cifrado comeza na posición cero. Polo tanto, o valor de F é igual a A. Xire o disco no sentido horario. A letra A está agora asociada con R. Xira o disco cara á dereita e debaixo da letra U atopa M, etc. O criptógrafo corre cara ao xeneral: "Xeneral, informe, as armas están chegando!"
Arroz. 3. O principio de funcionamento do noso papel Enigma.
| Arroz. 3. O principio de funcionamento do noso papel Enigma. | ||
Incluso as capacidades dun Enigma tan primitivo son sorprendentes. Podemos escoller outras permutacións de saída. Podemos, e aquí hai aínda máis posibilidades, non só unha "serif" regularmente, senón nunha determinada orde cambiante diariamente, como un hexágono (por exemplo, as tres primeiras letras, despois sete, despois oito, catro... . .etc. .).
Como podes adiviñar?! E aínda para os matemáticos polacos (Marian Reevski, Henrique de Zigalski, Ezhi Ruzicki) aconteceu. A información obtida deste xeito foi inestimable. Anteriormente, tiveron unha contribución igualmente importante á historia da nosa defensa Vaclav Serpinski i Stanislav Mazurkevichque violou o código das tropas rusas en 1920. O cable interceptado deulle a Piłsudski a oportunidade de realizar a famosa manobra dende o río Wieprz.
Lembro a Waclaw Sierpinski (1882-1969). Parecía un matemático para o que non existía o mundo exterior. Non puido falar da súa participación na vitoria de 1920, tanto por motivos militares como... políticos (as autoridades da República Popular Polaca non lles gustaban os que nos defendían da Unión Soviética).
Fig. 4. Permutación (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Arroz. 5. Bonita decoración, pero non é apta para o cifrado. Demasiado regularmente.
1 traballo. Na fig. 4 tes outra permutación para crear Enigma. Copia o debuxo nun xerógrafo. Constrúe un coche, codifica o teu nome e apelidos. O meu CWONUE JTRYGT. Se necesitas manter as túas notas en segredo, utiliza un Enigma de cartón.
2 traballo. Cifra o seu nome e apelidos dun dos "coches" que viu, pero (¡atención!) cunha complicación adicional: non xiramos nin unha muesca cara á dereita, senón segundo o patrón {1, 2, 3, 2, 1 , 2, 3 , 2, 1, ....} - é dicir, primeiro por un, despois por dous, despois por tres, despois por 2, despois de novo por 1, despois por 2, etc. ". Asegúrate de que o meu nome e apelidos se cifrarán como CZTTAK SDBITH. Agora entendes o poderosa que era a máquina Enigma?
Resolver o problema dos graduados de secundaria. Cantas opcións hai para personalizar Enigma (nesta versión, como se describe no artigo)? Temos 24 letras. Seleccione o primeiro par de letras; isto pódese facer
formas. O seguinte par pódese seleccionar en
métodos, ademais
etc. Despois dos cálculos axeitados (todos os números deben ser multiplicados) obtemos
151476660579404160000
Entón divide este número por 12! (12 factorial) porque os mesmos pares pódense obter en diferentes ordes. Entón, ao final temos "só"
316234143225,
é algo máis de 300 millóns, o que non parece un número asombrosamente grande para as supercomputadoras modernas. Non obstante, se temos en conta a orde aleatoria das propias permutacións, este número aumenta significativamente. Tamén podemos pensar noutro tipo de permutacións.
Ver tamén:
