Cifras e espiões

No Math Corner de hoje, vou dar uma olhada em um tópico que discuti no acampamento anual de ciências da National Children's Foundation para crianças. A fundação procura crianças e jovens com interesses científicos. Você não precisa ser extremamente talentoso, mas precisa ter uma "veia científica". Notas escolares muito boas não são exigidas. Experimente, você pode gostar. Se você é aluno do ensino fundamental ou médio, inscreva-se. Normalmente são os pais ou a escola que fazem as denúncias, mas nem sempre é assim. Encontre o site da Fundação e descubra.

Fala-se cada vez mais na escola sobre "codificação", referindo-se à atividade anteriormente conhecida como "programação". Este é um procedimento comum para educadores teóricos. Eles desenterram métodos antigos, dão a eles um novo nome, e o "progresso" é feito por si mesmo. Existem várias áreas onde ocorre um fenômeno tão cíclico.

Pode-se concluir que desvalorizo ​​a didática. Não. No desenvolvimento da civilização, às vezes voltamos ao que era, foi abandonado e agora está sendo revivido. Mas nosso canto é matemático, não filosófico.

Pertencer a uma determinada comunidade também significa "símbolos comuns", leituras comuns, ditos e parábolas. Aquele que aprendeu perfeitamente a língua polonesa “há um grande matagal em Szczebrzeszyn, um besouro está zumbindo nos juncos” será imediatamente exposto como espião de um estado estrangeiro se não responder à pergunta sobre o que o pica-pau está fazendo. Claro que ele está sufocando!

Isso não é apenas uma piada. Em dezembro de 1944, os alemães lançaram sua última ofensiva nas Ardenas com grande despesa. Eles mobilizaram soldados que falavam inglês fluentemente para interromper o movimento das tropas aliadas, por exemplo, levando-os na direção errada em encruzilhadas. Após um momento de surpresa, os americanos começaram a fazer perguntas suspeitas aos soldados, cujas respostas seriam óbvias para uma pessoa do Texas, Nebraska ou Geórgia e inconcebíveis para quem não cresceu lá. A ignorância das realidades levou diretamente à execução.

Ao ponto. Recomendo aos leitores o livro de Lukasz Badowski e Zaslaw Adamashek "Laboratory in a Desk Drawer - Mathematics". Este é um livro maravilhoso que mostra de forma brilhante que a matemática é realmente útil para alguma coisa e que "experimento matemático" não são palavras vazias. Inclui, entre outras coisas, a construção descrita do "enigma de papelão" - um dispositivo que nos levará apenas quinze minutos para criar e que funciona como uma máquina de cifras séria. A ideia em si era tão conhecida que os autores mencionados a elaboraram lindamente, e vou mudá-la um pouco e envolvê-la em roupas mais matemáticas.

serras

Em uma das ruas da minha aldeia dacha nos subúrbios de Varsóvia, o pavimento foi recentemente desmontado de “trlinka” - lajes de pavimentação hexagonais. A viagem foi desconfortável, mas a alma do matemático alegrou-se. Cobrir o plano com polígonos regulares (isto é, regulares) não é fácil. Só pode ser triângulos, quadrados e hexágonos regulares.

Talvez eu tenha brincado um pouco com essa alegria espiritual, mas o hexágono é uma bela figura. A partir dele, você pode criar um dispositivo de criptografia bastante bem-sucedido. A geometria vai ajudar. O hexágono tem simetria rotacional - ele se sobrepõe quando girado por um múltiplo de 60 graus. O campo marcado, por exemplo, com a letra A no canto superior esquerdo FIG. 1 depois de virar por esse ângulo, ela também cairá na caixa A - e o mesmo com outras letras. Então, vamos cortar seis quadrados da grade, cada um com uma letra diferente. Colocamos a grade assim obtida em uma folha de papel. Nos seis campos livres, insira seis letras do texto que queremos criptografar. Vamos girar a folha 60 graus. Seis novos campos aparecerão - digite as próximas seis letras da nossa mensagem.

Arroz. 1. Trlinks da alegria da matemática.

À direita FIG. 1 temos um texto codificado desta forma: "Há uma enorme e pesada locomotiva a vapor na estação."

Agora, um pouco de matemática escolar será útil. De quantas maneiras dois números podem ser arranjados um em relação ao outro?

Que pergunta idiota? Para dois: ou um na frente ou o outro.

Multar. E três números?

Também não é difícil listar todas as configurações:

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

Bem, é para quatro! Ele ainda pode ser claramente explicado. Adivinhe a regra de ordem que coloquei:

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 os dígitos são cinco, temos 120 configurações possíveis. Vamos chamá-los permutações. O número de permutações possíveis de n números é o produto 1 2 3 ... n, chamado forte e marcado com um ponto de exclamação: 3!=6, 4!=24, 5!=120. Para o próximo número 6 temos 6!=720. Usaremos isso para tornar nosso escudo de cifra hexagonal mais complexo.

Escolhemos uma permutação de números de 0 a 5, por exemplo 351042. Nosso disco de embaralhamento hexagonal tem um traço no campo do meio - para que possa ser colocado "na posição zero" - um traço para cima, como na fig. 1. Colocamos o disco dessa maneira em uma folha de papel na qual temos que escrever nosso relatório, mas não o escrevemos imediatamente, mas o giramos três vezes em 60 graus (ou seja, 180 graus) e inserimos seis letras em os campos vazios. Voltamos à posição inicial. Giramos o mostrador cinco vezes em 60 graus, ou seja, em cinco "dentes" do nosso mostrador. Nós imprimimos. A próxima posição da escala é a posição girada 60 graus em torno de zero. A quarta posição é 0 graus, esta é a posição inicial.

Você entende o que aconteceu? Temos uma oportunidade adicional - para complicar nossa "máquina" em mais de setecentas vezes! Assim, temos duas posições independentes do "autômato" - a escolha da grade e a escolha da permutação. A grade pode ser escolhida de 66 = 46656 maneiras, permutação 720. Isso dá 33592320 possibilidades. Mais de 33 milhões de cifras! Quase um pouco menos, porque algumas grades não podem ser cortadas em papel.

Na parte inferior FIG. 1 temos uma mensagem codificada assim: "Estou lhe enviando quatro divisões de pára-quedas". É fácil entender que o inimigo não deve saber disso. Mas ele vai entender alguma coisa disso:

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

YYLOAKVMDEYCHESH,

mesmo com assinatura 351042?

Estamos construindo a Enigma, uma máquina de cifragem alemã

Arroz. 2. Um exemplo da configuração inicial de nossa máquina de criptografia.

Permutações (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Como já mencionei, devo a ideia de criar tal máquina de papelão ao livro "Lab in a Drawer - Mathematics". Minha “construção” é um pouco diferente daquela dada por seus autores.

A máquina de cifra usada pelos alemães durante a guerra tinha um princípio engenhosamente simples, um pouco semelhante ao que vimos com a cifra hexadecimal. Toda vez a mesma coisa: quebrar a atribuição difícil de uma carta para outra carta. Deve ser substituível. Como fazê-lo para ter controle sobre ele?

Vamos escolher não qualquer permutação, mas uma que tenha ciclos de comprimento 2. Simplificando, algo como o "Gaderipoluk" descrito aqui há alguns meses, mas cobrindo todas as letras do alfabeto. Vamos concordar em 24 letras - sem ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Quantas dessas permutações? Esta é uma tarefa para graduados do ensino médio (eles devem ser capazes de resolvê-la imediatamente). Quantos? Um monte de? Vários milhares? Sim:

1912098225024001185793365052108800000000 (nem vamos tentar ler esse número). Há tantas possibilidades para definir a posição "zero". E pode ser difícil.

Nossa máquina consiste em dois discos redondos. Em um deles, que ainda está de pé, estão escritas cartas. É um pouco como o dial de um telefone antigo, onde você disca um número girando o dial todo. Rotary é o segundo com um esquema de cores. A maneira mais fácil é colocá-los em uma rolha normal usando um alfinete. Em vez de cortiça, você pode usar uma placa fina ou papelão grosso. Lukasz Badowski e Zasław Adamaszek recomendam colocar os dois discos em uma caixa de CD.

Imagine que queremos codificar a palavra ARMATY (Arroz. 2 e 3). Coloque o dispositivo na posição zero (seta para cima). A letra A corresponde a F. Gire o circuito interno uma letra para a direita. Temos a letra R para codificar, agora ela corresponde a A. Após a próxima rotação, vemos que a letra M corresponde a U. A próxima rotação (quarto diagrama) dá a correspondência A - P. No quinto mostrador temos T - A. Finalmente (sexto círculo) S – Y O inimigo provavelmente não vai adivinhar que nossos CFCFAs serão perigosos para ele. E como “nosso” lerá o despacho? Devem ter a mesma máquina, o mesmo "programado", ou seja, com a mesma permutação. A cifra começa na posição zero. Portanto, o valor de F é A. Gire o dial no sentido horário. A letra A agora está associada a R. Ele gira o dial para a direita e sob a letra U encontra M, etc. O escriturário corre para o general: "General, estou relatando, as armas estão chegando!"

Arroz. 3. O princípio de funcionamento do nosso papel Enigma.

Arroz. 3. O princípio de funcionamento do nosso papel Enigma.

As possibilidades até mesmo de um Enigma tão primitivo são incríveis. Podemos escolher outras permutações de saída. Podemos - e há ainda mais oportunidades aqui - não por uma "serifa" regularmente, mas em uma certa ordem de mudança diária, semelhante a um hexágono (por exemplo, três primeiras letras, depois sete, depois oito, quatro ... .. etc. .).

Como você pode adivinhar?! E ainda para os matemáticos poloneses (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) ocorrido. As informações assim obtidas foram inestimáveis. Anteriormente, eles tiveram uma contribuição igualmente importante para a história da nossa defesa. Vaclav Serpinski i Stanislav Mazurkevichque violou o código das tropas russas em 1920. O cabo interceptado deu a Piłsudski a oportunidade de fazer a famosa manobra do rio Vepsz.

Lembro-me de Vaslav Sierpinski (1882-1969). Parecia um matemático para quem o mundo exterior não existia. Ele não pôde falar sobre sua participação na vitória em 1920, tanto por motivos militares quanto ... por razões políticas (as autoridades da República Popular da Polônia não gostaram daqueles que nos defenderam da União Soviética).

Arroz. 4. Permutação (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Arroz. 5. Decoração bonita, mas não adequada para criptografia. Demasiado regularmente.

Tarefa 1. Na FIG. 4 você tem outra permutação para criar o Enigma. Copie o desenho para o xerógrafo. Construa um carro, codifique seu nome e sobrenome. Meu CWONUE JTRYGT. Se você precisar manter suas anotações privadas, use o Cardboard Enigma.

Tarefa 2. Criptografe seu nome e sobrenome de um dos “carros” que você viu, mas (atenção!) com uma complicação adicional: não viramos um entalhe para a direita, mas de acordo com o esquema {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - isto é, primeiro por um, depois por dois, depois por três, depois por 2, depois novamente por 1, depois por 2, etc., tal “wavelet” . Certifique-se de que meu nome e sobrenome estejam criptografados como CZTTAK SDBITH. Agora você entende o quão poderosa era a máquina Enigma?

Resolução de problemas para graduados do ensino médio. Quantas opções de configuração para Enigma (nesta versão, conforme descrito no artigo)? Temos 24 letras. Selecionamos o primeiro par de letras - isso pode ser feito em

maneiras. O próximo par pode ser escolhido em

maneiras, mais

etc. Após os cálculos correspondentes (todos os números devem ser multiplicados), obtemos

151476660579404160000

Em seguida, divida esse número por 12! (12 fatorial), porque os mesmos pares podem ser obtidos em uma ordem diferente. Então, no final, obtemos "total"

316234143225,

isso é pouco mais de 300 bilhões, o que não parece ser um número muito grande para os supercomputadores de hoje. No entanto, se a ordem aleatória das próprias permutações for levada em consideração, esse número aumenta significativamente. Também podemos pensar em outros tipos de permutações.

Veja também: