61Likes
Após ver o filme "The Imitation Game", indicado ao oscar de melhor filme de 2014, onde Benedict Cumberbatch, indicado a melhor ator, interpreta Alan Turing, pai da ciência da computação, muitos de vocês, aposto, se perguntaram como funcionavam as geringonças apresentadas no filme. Nesse tópico, pretendo abordar o assunto de forma a trazer uma visão mais simplista de como funciona tanto o Enigma quanto a Bomba. Além de complementar o filme, é um evento histórico importante pra humanidade: a partir daí, Turing conseguiu prover a máquina universal que ele mesmo propora alguns anos antes e que era posta em dúvida por vários estudiosos. O resultado disso é a computação moderna, pilar do mundo atual.
"Mas eu preciso ver o filme antes?"
Não necessariamente. Posso fazer a analogia com o cavalo de Tróia. Se você ler em algum lugar que dentro do cavalo haviam gregos, isso vai estragar a experiência de ver o filme Tróia (aquele com o Brad Pitt)? Obviamente que se você não conhecer a história, a chance de se surpreender aumenta. Por conta disso, eu recomendo fortemente que vejam o filme antes. Mas, que fique claro, não é obrigatório.
Enigma
Fazendo uma revisão histórica rápida: durante o Império Romano, Julio César usou uma das primeiras e mais famosas criptografias que permitia uma troca de mensagens entre seus exércitos de forma mais segura. Chama-se Cifra de César, e funciona de maneira bem simples: rotaciona-se o alfabeto por um número pré-determinado de posições e faz-se a correspondência direta da letra a ser criptografada com sua correspondente na cifra. A imagem abaixo exemplifica:
Cerca de 2000 anos depois de Cesar, eclode a Segunda Guerra Mundial. Nisso, a criptografia era obrigatória, já que qualquer um com um rádio conseguiria interceptar as comunicações dos exércitos apenas ajustando a freqüência de recepção dos aparelhos. Encabeçados pela Alemanha nazista, o Eixo usava a máquina Enigma para troca segura de mensagens. Pensava-se ser um código inquebrável.
A máquina Enigma (ou, em alemão, "Rätzel", puzzle) foi inventada por um engenheiro alemão em 1918. Servia para troca de mensagens não apenas militares, mas civis. Na guerra, ela fora uma das grandes armas alemãs: a Blitzkrieg, "guerra-relâmpago" consistia em ataques rápidos e eficientes com o objetivo de pegar o inimigo despreparado. Obviamente que, para que tudo saísse conforme desejado, era necessário um sistema de comunicação eficiente e confiável. O Enigma cuidou disso.
Do ponto de vista do usuário, a máquina funcionava da seguinte forma: acertavam-se algumas configurações descritas numa espécie de manual, e digitava-se a mensagem. A cada letra digitada, outra letra acendia no painel. Então, letra por letra, escrevia-se a mensagem codificada para que pudesse ser enviada por rádio (via código Morse). Quem recebia a mensagem primeiramente decodificava o código Morse, acertava-se as configurações conforme descrito no mesmo manual de quem escreveu a mensagem anteriormente e, finalmente, digitava o código na máquina. A cada letra digitada, outra letra era iluminada no painel. Anotava-se, então, letra por letra acesa, e, ao final, tinha-se a mensagem original.
"Mas como que ninguém conseguia decifrar a mensagem?!"
Bem, chegaremos lá, mas em poucas palavras, você precisava ter o manual para saber como configurar a máquina. Além disso, as configurações da máquina eram modificadas a cada 24h: ou seja, de nada adiantava saber a configuração da máquina num dia, já que no outro ela seria totalmente diferente. Esse manual de instruções para configurar o Enigma também era bastante seguro: só mostrava as configurações para os próximos 7 dias. Era carregado pelos mensageiros dentro de uma espécie de garrafa que continha uma substância corrosiva no interior de um vidro: caso capturados, bastava derrubar esse cantil que a folha de papel tão preciosa seria destruída pelo ácido sem que ninguém desconfiasse. No entanto, por mais que conseguissem capturar algum manual, ele só teria validade por 7 dias, antes que um novo entrasse em vigor.
"Mas se era uma questão de configuração da máquina, porque não testar todas as configurações até conseguir decodificar a mensagem?"
Para responder isso, é necessário saber como a máquina funcionava mais tecnicamente. Imaginem um relógio, com ponteiros de segundos, minutos e horas. A cada volta do ponteiro de segundos, o ponteiro de minutos muda de posição. A cada volta do ponteiro de minutos, o ponteiro de horas muda de posição. O Enigma funcionava com três engrenagens principais que movimentavam-se de maneira parecida com um relógio. A cada letra digitada, a engrenagem "dos segundos" avançava, gerando uma nova configuração. Ou seja, se digitássemos a letra "A" na máquina e ela retornasse um "F", digitando "A" novamente ela poderia retornar um "W", por exemplo, devido a esse movimento de engrenagem. Ademais, quando a primeira engrenagem "de segundos" completava um ciclo (26 posições, já que temos 26 letras no alfabeto e cada posição do rotor correspondia a uma letra), a outra engrenagem "de minutos" era impulsionada. Como num relógio, quando essa engrenagem completasse um ciclo, então a engrenagem "de horas" avançava. A imagem abaixo ilustra o conjunto de engrenagens:
Agora vamos calcular o número de combinações diferentes que podemos arranjar as engrenagens (vou chamar de variável C1):
C1 = 26*26*26 = 17.576 (vou colocar pontos pra facilitar a leitura dos números)
Além disso, a máquina continha 5 engrenagens, e devia-se selecionar apenas 3 dessas. Ou seja, mais um elemento que temos que computar: para a primeira posição, tem-se 5 escolhas. Escolhida a primeira posição, tem-se 4 para a segunda e 3 para a terceira.
C2 = 5*4*3 = 60
Multiplicando, temos:
C1*C2 = 1.054.560
Ou seja, 1 milhão de possíveis configurações para a máquina. E tal configuração mudava a cada 24h. Considerando que os Aliados conseguissem testar uma configuração por segundo, apenas 86.400 testes seriam feitos, ou seja, algo como 8,19% de chance de decodificar a mensagem dentro de 24h. Isso sem levar em conta que não existiam tantos Enigmas em posse dos Aliados para que pudesse ser feito um teste a cada segundo; que as mensagens começavam a chegar pela manhã, ou seja, teriam 18h para trabalhar apenas; e, por fim, que de nada adiantava decodificar uma mensagem as 20h, já que o fim do dia estaria muito próximo.
"Aaaah, mas é possível! Se tivessem recursos e gente suficiente, seria possível decodificar a mensagem."
Acontece que a máquina Enigma possuía duas versões: a versão civil (doméstica) e a versão militar. A diferença entre elas era um painel frontal (ilustrada abaixo) onde se poderia embaralhar ainda mais cada letra: faziam-se dez correspondências de uma letra por outra de forma parecida como a Cifra de César. Ou seja, antes da letra passar por todas as engrenagens, ela era transformada "manualmente" em uma outra letra. Portanto, adiciona-se ao nosso cálculo esses pares de letras definidos pelo painel frontal da máquina da seguinte forma:
- Primeiro, temos que verificar quantas possibilidades há de se combinar (arranjar, na verdade), 26 letras: na primeira posição da combinação, tem-se 26 possibilidades. Na segunda, 25. Na terceira, 24. Assim por diante, ou seja, 26*25*24...*3*2*1 = 26!
- Após, devemos lembrar que não são todas as possibilidades possíveis: nossa intenção é formar 10 pares de letras. Ou seja, existem 6 letras que não correspondem a nada. Considerando já o cálculo do passo anterior, temos 26!/6!
- Como a ordem dos pares não importa, ou seja, se definirmos um par A-F, então automaticamente o par F-A é criado, então pode-se dividir pela metade o número de possibilidades, certo? Como temos 10 pares, então podemos dividir por 2^10 (dois elevado a décima potência). Nosso novo número fica: 26!/(6!*2^10)
- Por fim, como a ordem como criamos os pares não importa, ou seja, se criarmos o par A-F antes ou depois do par C-T não importa, para 10 pares temos: 26!/(6!*2^10*10!).
Calculando-se como C3 esse número, temos:
C3 = 26!/(6!*2^10*10!) = 150.738.274.937.250 possibilidades.
Multiplicando-se isso por C1 e C2, já que a mensagem ainda passa por 3 das 5 engrenagens disponíveis em 1 das 26 possíveis para cada engrenagem, tem-se o número definitivo de possíveis configurações da máquina Enigma:
C1*C2*C3 = 17.576 * 60 * 150.738.274.937.250 = 158.962.555.217.826.360.000 (158 quintilhões).
Considerando um cenário (atual) de 6 bilhões de habitantes no planeta Terra, cada um deles testando uma nova configuração a cada segundo, ainda assim a humanidade demoraria 840 anos para ler uma mensagem nazista.
A Bomba de Turing
Esse era o drama vivido por um grupo residindo no sul da Inglaterra, em uma pequena propriedade rural adquirida pelo governo inglês para que pudessem usar como base da inteligência da Rainha que objetivava decodificar as mensagens do Eixo. Nesse grupo, quatro figuras ganham destaque (imagem abaixo): Conel Hugh Alexander, enxadrista, Joan Clarke, prodígia inglesa, a única mulher do grupo, Gordon Welchman, matemático e Alan Turing, também matemático. Abaixo as fotos na ordem como são apresentados no texto.
Depois de muita pesquisa e tentativas fracassadas de decodificar as mensagens alemãs de maneira manual, o grupo decidiu aderir a idéia de Turing, já publicada em artigos anteriores a guerra, de buscar uma solução que pudesse computar as possibilidades de configurações do Enigma de maneira automatizada. Um computador.
A Bomba então foi construída: um enorme dispositivo capaz de testar as variadas configurações da máquina Enigma. O nome surgiu da máquina polonesa homônima, que funcionava de forma mecânica também para decodificação de códigos. O diferencial da versão inglesa era o fator elétrico, que acelerava os cômputos.
Entretanto, mesmo após a construção da Bomba, os 158 quintilhões de possibilidades ainda eram um empecilho. Mesmo testando uma possibilidade a cada 0,000000001s, ou 1 nanosegundo (algo bem distante até para computadores atuais), a máquina levaria 5040 anos para cumprir a tarefa. Qual a solução, então? Seria o Enigma inquebrável?
Não. O Enigma tinha uma fraqueza. Turing observou, através das poucas mensagens que eles haviam decodificado, que uma situação nunca ocorria: uma letra nunca era correspondida por ela mesmo. Ou seja, a codificação da letra "A", por exemplo, nunca era "A". Então, ali, os Aliados ganharam a guerra de inteligência.
"Mas e no que isso ajudava a decodificar o Enigma?!"
Se pensássemos isoladamente, isso não ajudava em muita coisa: diminuiria o número de combinações, mas ainda teríamos algo da grandeza de bilhões de tentativas. No entanto, combinada a outras práticas já usadas em quebras de criptografias, isso poderia ter grande valia. Uma dessas práticas é a busca por palavras comuns no texto. Observou-se que as primeiras comunicações diárias nazistas eram relatórios climáticos e todas elas acabavam com "Heil Hitler". Turing e companhia, então, puseram-se a trabalhar.
Primeiro, temos que entender qual o método. Aqui uma exemplificação resumida de como a falha era a porta de entrada para as mensagens nazis:
- Consideremos que tenhamos a primeira mensagem nazista do dia: o relatório do tempo. Digamos uma parte desse relatório (o início, por exemplo) que seja algo como "...JXATGBGGYWCRYBGVKKL...";
- Conforme explicado anteriormente, estamos esperando encontrar a seguinte frase: "WETTERBERICHT" ("relatório do tempo" em alemão).
- Sabe-se que nenhuma letra é correspondida por ela mesmo. Agora vamos comparar, letra a letra, de forma posicional, a mensagem com o que esperamos (em negrito estão assinalado os problemas):
...- J X A T G B G G Y W C R Y B G V K K L
....W E T T E .R B E R .I. C H T
Deslocando-se a nossa mensagem pela mensagem criptografada:
...- J X A T G B G G Y W C R Y B G V K K L
.......W E T T E .R B E R .I .C H T
Deslocando novamente:
...- J X A T G B G G Y W C R Y B G V K K L
.......W E T T E .R B E R .I C .H T
E achamos o primeiro candidato! É possível que ATGBGGYWCRYBG seja WETTERBERICHT!
Analise o final procurando por "HEIL HITLER" e terás outro ponto de partida para decodificar a mensagem.
Em outras palavras, se acharmos uma configuração para o Enigma a qual digitamos ATGBGGYWCRYBG e recebamos como resposta "WETTERBERICHT", o código está quebrado.
Esse foi o primeiro passo. Agora vou demonstrar como Turing resolveu o problema a partir disso (já que saber disso, por si só, não ajuda a descobrir a configuração da máquina). Primeiro, vamos enxergar o Enigma de maneira simplificada, conforme imagem abaixo:
Como podem ver, a letra era digitada, correspondida no painel frontal através do par que ela se encontrava, após ia para a etapa das engrenagens. O resultado, então, retornava para o painel frontal que iluminava a letra cifrada correspondente.
Portanto, se jogarmos a letra T, a segunda da nossa frase cifrada, teremos a letra E na saída, a segunda da mensagem original. Ou seja:
Supomos, agora, que exista uma conexão T-A no painel frontal.
Jogando essa letra nas engrenagens, considerando uma posição arbitrária qualquer, digamos que tenhamos a letra P. Então, por dedução, podemos dizer que temos o par P-E no painel de controle.
Repetindo esse processo para outras respostas do conjunto de engrenagens, temos as seguintes deduções:
Observando a última situação da imagem anterior, temos a dedução T-G. No entanto, no início partimos do pressuposto de que existe uma conexão T-A, não T-G. Em outras palavras, temos uma contradição. Ou seja, o par de partida escolhido, T-A está errado. Descartemos essa possibilidade e testemos, então, outra, como T-B, por exemplo. Esse processo, então, é repetido até que haja uma solução sem contradição. Caso todas as soluções sejam contraditórias, então a posição arbitrária escolhida nas engrenagens está errada. Troquemos a posição e testemos novamente, tudo de novo!
"Ok, mas continua demorando eternidades até descobrir as posições corretas das engrenagens!"
Na verdade, só aplicando esse método, temos uma redução de 158.962.555.217.826.360.000 possibilidades para 1.054.560. E, note, é possível realizar o método diretamente no Enigma. No entanto, ainda que para 1 milhão, isso torna-se impossível. Na Bomba, aplicando a solução de Gordon Welchman para testar os 5 rotores 3 em 3 de forma simultânea (fazendo todas as conexões físicas/elétricas através de uma modificação na estrutura original da máquina Aliada) temos uma redução de 1.054.560 para 17.576.
De 158.962.555.217.826.360.000 para 17.576. Uma otimização de 99,99999999999998894330807911611% do tempo de cálculo.
Assim, o primeiro código Enigma chegava às 6h e era quebrado às 6h20 pelo mecanismo eletromecânico automático da Bomba.
E foi assim que o pessoal da Hut 8 (a cabana onde se instalavam Turing e seus companheiros) diminuiu a duração da guerra por 2 anos e mudou o rumo da humanidade para sempre, desenvolvendo tecnologias que deram origem as que são usadas hoje para criar esse tópico, por exemplo, e disseminar essa história.
A fonte principal desse texto é o Numberphile. Outros detalhes foram retirados de variados textos disponíveis online (se alguém quiser, posso passar via MP).
AVISO: TÓPICO ANTIGO
Atenção: Este é um tópico criado há mais de 90 dias. Caso não tenha respostas recentes, tenha certeza de que sua resposta é conveniente e útil o suficiente para reativar esta discussão, do contrário você poderá ser advertido/suspenso.
Responder com Citação
Postado originalmente por Ace One
