AC, Antes dos Computadores 12 Cifras

AC, Antes dos Computadores: Sobre a Tecnologia da Informação, da Escrita à Era do Dado Digital

Por Stephen Robertson

Capítulo anterior

[131]12 Cifras

É fácil pensar nos computadores como calculadoras gigantes, e de fato a tarefa de cálculo e sua mecanização contribuíram tanto para a ideia da construção de tal máquina quanto para o conceito das tarefas às quais ela poderia ser endereçada. Tarefas difíceis de cálculo tais como aquelas envolvidas em balística (particularmente em tempos de guerra) proveram parte do estímulo na direção do desenvolvimento pós-Segunda Guerra Mundial dos computadores. Mas nós vimos há pouco, no capítulo anterior, como um tipo bastante diferente de tarefa estimulou uma forma diferente de mecanização que nos trouxe próximos da era do computador. O estímulo principal para a invenção atual dos computadores novamente veio de outro domínio.

O desafio era quebrar os códigos usados pelos inimigos a fim de ser capaz de ler as mensagens supostamente secretas, no viveiro tecnológico que foi a Segunda Guerra Mundial. Para vermos como isso aconteceu, nós novamente começamos muito antes.

Códigos e cifras

Através da história, as pessoas sentiram a necessidade de escrever mensagens (mensagens ponto a ponto, nos termos de nossa discussão anterior) que seriam ilegíveis por qualquer outro exceto o destinatário pretendido, especialmente por qualquer um que poderia interceptá-las na rota. Comandos militares, relatórios de inteligência, instruções para agentes, cartas de amor, arranjos para encontros, planos para qualquer tipo de ação ou atividade que poderiam levar a contramedidas de qualquer tipo por qualquer terceiro – tudo isso e muito mais poderia ser considerado pelo emissor como necessário de encriptação.

Uma vez que a palavra código (code) está um pouco sobrecarregada no uso atual, eu usarei a palavra encriptação (encryption) para indicar a colocação de alguma mensagem em código, de uma maneira que ela somente possa ser lida por uma pessoa que tenha a chave para o código, e [132]cifra (cipher) como o método ou regras para o fazer. A mensagem original é texto puro (plain) e a criptografia resulta na mensagem encriptada ou cifrada. A recuperação do texto simples (dada a chave) é decriptação (decryption). A descoberta da chave, ou até do completo sistema de cifra, eu ainda posso referir como quebra de código (code-breaking), em deferência ao uso popular, o assunto inteiro, de design das cifras e de as quebrar, e do estudo de suas propriedades (tais como se, em princípio, elas são quebráveis) é a criptografia.

Um livro com uma explicação maravilhosa dos diferentes tipos de cifras que têm sido usadas ao longo da história, e os esforços dos oponentes para as quebrar, é The Code Book, de Simon Singh. Muito do resto deste capítulo é extraído do livro de Singh.

O alfabeto e encriptação

Desde o começo e até o dia de hoje tem havido algum uso de sistemas de código baseados em palavras. Uma notícia em um jornal de hoje sobre minha mesa descreve um caso no qual algum alegado conspirador terrorista “usou palavras codificadas” para algumas palavras que possivelmente soam suspeitas, como armas de fogo. Mas tais sistemas são planejados para disfarçar e camuflar uma mensagem codificada, tornando-a menos suspeita e portanto menos provável de atrair atenção. Outra abordagem é ocultar completamente a existência de uma mensagem.

Contudo, a maioria da criptografia trata da questão de como tornar uma mensagem ilegível até quando o adversário está de posse do que ele ou ela suspeita ou sabe ser uma mensagem cifrada. Mais uma vez, é difícil conceber muito da história da criptografia sem o alfabeto. A maioria dos sistemas encriptados através da história têm sido baseados em alfabeto. As cifras tipicamente envolvem um ou ambos de: rearranjo das letras da mensagem, e/ou substituição de diferentes caracteres para essas na mensagem. Mesmo no Japão e na China, nós vemos evidência do uso de alfabetos ou de conjuntos de símbolos semelhantes a alfabeto para encriptação. Cifras japonesas tendem a ser baseadas em um dos alfabetos fonéticos (kana), enquanto que uma cifra chinesa poderia usar, por exemplo, ou um alfabeto fonético ou o assim chamado método dos Quatro Cantos para encriptação de cada caractere em quatro ou cinco números, o qual também é usado como um tipo de substituto para ordem alfabética, para ordenação e, em seguida, exame dos caracteres.

Dado um alfabeto, um dos tipos mais simples de encriptação é substituir para cada letra em uma mensagem a letra três posições adiante no alfabeto [133](essa era a cifra usada por Júlio César). Se eu fizer isso para o título desta seção¹, eu obtenho:

Wkh doskdehw dqg hqfubswlrq.

Ou eu poderia escolher uma troca diferente, ou eu poderia rearranjar o alfabeto cifrado de alguma maneira. Meu destinatário pretendido precisa saber que sistema de cifra eu usei, uma chave que o ou a capacitará a decriptar a mensagem: tanto o princípio (‘troca alfabética’, por exemplo) quanto o número de caracteres trocas.

Mas, como nós deveremos ver em um minuto, tais cifras, nas quais um texto puro (plaintext) e é sempre representado pelo mesmo símbolo na mensagem cifrada (nesse caso um h)² normalmente são fáceis de quebrar. Para fazer uma cifra mais forte, nós poderíamos usar todas as 26 trocas possíveis do alfabeto, e uma chave que nos diz que troca usar para cada letra. A chave é uma palavra, a primeira letra da qual nos diz qual troca usar para a primeira letra da mensagem, a segunda para a segunda, e assim por diante. Quando nós alcançamos o final da palavra-código (codeworld), nós retornamos ao começo. Essa é a base para a cifra de Vigenère, inventada por Blaise de Vigenère no século XVI.

A cifra de Vigenère faz uso do quadrado de Vigenère, mostrando todas as trocas possíveis do alfabeto (ver figura 18). Suponha novamente que você queira encriptar o título desta seção, e a palavra-código é revolução. Nós escrevemos nosso texto puro e, sob ele, a palavra-código, repetida tantas vezes quanto necessário para corresponder a cada letra do texto simples. Então nós examinamos cada letra do texto simples na linha do topo do quadrado de Vigenère, e encriptamo-la com a letra correspondente na linha identificada pela letra da palavra-código. O primeiro resultado (coluna T, linha R) é circulado na figura. Dada a palavra-código, a decriptação é igualmente simples – mas você necessita da palavra-código.

THE ALPHABET AND ENCRYPTION texto puro

REV OLUTIONR EVO LUTIONREVO palavra-código repetida

KLZ OWJAIPRK EIR PHVZMCKMJB texto cifrado

[134]Figura 18: Quadrado de Vigenère. Diagrama: o autor.

A cifra de Vigenère é muito mais forte do que a simples substituição por troca alfabética, e considerava-se ser inquebrável. No exemplo, você pode ver que os dois As em alfabeto são representados por letras diferentes no texto cifrado. Mas ela pode ser quebrada – o homem que estabeleceu esse fato foi [134]alguém que nós já encontramos no capítulo 10: o matemático e inventor do século XIX Charles Babbage.

Quebra de código

Suponha que eu esteja de posse de uma mensagem cifrada, ou de um conjunto de tais mensagens de uma única fonte – mas eu não sou o destinatário pretendido, e não conheço a cifra. Se eu tiver qualquer razão para acreditar que a cifra é uma simples troca alfabética, ou de fato qualquer simples substituição um para um, então deveria ser fácil para eu descobrir a chave e, desse maneira, decriptá-la. Em particular, o número de ocorrências de cada letra fornecerá uma pista clara de quais letras foram substituídas, digamos, E ou T ou A (as letras mais comuns em inglês). Quão mais longa a mensagem mais fácil será, mas na curta mensagem acima, eu tenho três de cada E e T, e também N, e somente dois As.

Mesmo assim, nós imediatamente vemos que a quebra é um tipo diferente de tarefa da [135]encriptação e decriptação. Tanto a encriptação, quanto a decriptação para o destinatário de posse da chave, envolvem um conjunto muito simples de regras. A quebra da cifra, contudo, é um pouco mais complexa. O quebrador de código (code-breaker) pode ter de fazer alguma contabilidade e estatística, e então tentar um número de possibilidades.

O método de Babbage para quebra da cifra de Vigenère envolve procurar por sequências repetidas de caracteres na mensagem cifrada. A distância entre tais sequências dar-nos-á boas pistas quanto ao tamanho da palavra-chave usada, após a que, uma extensa forma de análise da estatística da ocorrência de letras, como usada para quebrar simples cifras de substituição, é provável de ser efetiva.

Contudo, usar uma chave mais longa (por exemplo, uma frase ou poema inteiro) torna-a mais difícil de quebrar. O estágio final desse desenvolvimento era construção de uma série inteira de longas chaves aleatórias, cada uma impressa em uma folha separada de papel, formando um bloco (pad), do qual emissor e receptor teriam cada um uma cópia. O emissor encriptaria uma mensagem usando a primeira folha, e em seguida descartaria a primeira folha de maneira que ela nunca fosse usada novamente. O destinatário decripta-la-ia também usando a primeira folha, e em seguida descartaria a folha. Essa cifra, o bloco de uso único (one-time pad), foi inventada por Joseph Mauborgne para o exército dos EUA ao final da Primeira Guerra Mundial, e conhecida como inquebrável por qualquer um que não esteja de possa do bloco de uso único. Sua principal limitação é a necessidade de produzir e seguramente distribuir o bloco.

De fato, o processo de invenção de melhores cifras (por aqueles tentando enviar e receber mensagens seguras) e a invenção de novas maneiras de as quebrar (por seus inimigos) é um jogo que muitas pessoas jogaram por milênios.

Métodos e máquina

Dado que os processos de encriptação e de decriptação são normalmente baseados em regras bem definidas, é um pouco surpreendente que o uso de auxílios mecânicos fosse lento para iniciar. Simples cifras de substituição não requerem mais do que tabelas de duas linhas: letras do texto puro na linha do topo e substitutas abaixo. A cifra de Vigenère requer uma tabela quadrada, com cada das 26 trocas alfabéticas possíveis em sua própria linha. Mesmo o bloco de uso único é essencialmente baseado em papel.

Contudo, também é possível construir um simples aparelho mecânico para ajudar [136]ou a encriptação e decriptação por substituição ou no estilo Vigenère, na forma de um par de discos um dentro do outro. As letras do alfabeto são escritas em volta das extremidades de cada disco, e o dico interior é rodado em relação ao disco exterior para estabelecer uma única tabela de substituição. Se ele for adicionalmente rodado durante a encriptação, uma cifra do estilo Vigenère é produzida.

Um disco semelhante foi inventado por Leon Alberti no século XV, e aparelhos similares estiveram em uso por um longo tempo, incluindo a Guerra Civil Americana. Talvez surpreendentemente, não foi antes do século XX que o uso de maquinário para encriptação e decriptação avançou muito além. Contudo, a aplicação de um complexo sistema de cifra realmente sugere ou até exige maquinaria: quão mais complexas as regras a serem aplicadas, tanto mais importante é delegar a operação das mesmas a uma máquina, da qual se poderia esperar não cometer erros.

A mecanização de encriptação e decriptação não decolou realmente até a invenção da máquina Enigma. As forças armadas alemãs famosamente usaram o Enigma como seu aparelho de cifra preferido durante a Segunda Guerra Mundial, com mudanças diárias de chaves; e os britânicos, igualmente famosamente, tinham em Bletchley Park um estabelecimento dedicado à leitura das mensagens cifradas alemãs, o qual de fato repetida e exitosamente quebrava essas cifras diárias.

Enigma

A Enigma gera uma substituição letra por letra da mensagem limpa, mas a tabela de substituição efetivamente muda com cada letra. Mas, diferentemente do original sistema Vigenère baseado em palavras-chave, a tabela não se repete a cada poucas letras. É mais comparável ao bloco de uso único.

É uma máquina fascinante no seu próprio direito. Desenvolvida em 1918 por Arthur Scherbius, ela parece muito com uma máquina de escrever – de fato, o teclado é baseado estritamente no teclado de Sholes descrito no capítulo 5 (o qual, por 1918, estava bem estabelecido como a forma padrão de teclados para máquinas de escrever). Mas, em vez de papel, a parte traseira da máquina tinha uma réplica do teclado em uma placa de lâmpadas (lampboard), um arranjo de discos com letras cada um com uma lâmpada atrás – ver figura 19. (Você pode notar de passagem que esse teclado difere um pouco do teclado da máquina de escrever de Sholes (capítulo 5), embora obviamente derivado dele. Em particular, os deslocamentos (offsets) diferem – tendo apenas três linhas, [137]os deslocamentos são um terço da largura da tecla. Digitadores (touch-typist) teriam notado isso!)

[137]A letra L é pressionada, e a lâmpada D é ligada. Figura 19: Máquina Enigma.https://commons.wikimedia.org/wiki/File:Enigma_Machine_A16672_open,_letter_L_pressed.agr.jpg CC BY-SA 4.0.

A mensagem limpa é digitada, como poderia ser uma máquina de escrever, mas a cada pressionamento de tecla, em vez de impressão, uma dessas lâmpadas é iluminada, indicando uma nova letra – o código cifrado para ser usado para a letra recém-teclada. A letra iluminada então tem de ser registrada de alguma maneira – escrita ou digitada ou transmitida diretamente.

Os mecanismos que permitem a continuamente mutável tábua de substituições são vários e engenhosos, e eu não tentarei descrevê-los aqui. Eles dependiam das configurações iniciais, as quais eram mudadas diariamente; uma vez em uma mensagem, as configurações eram mudadas automaticamente pelo processo de digitação da mensagem. Quer dizer, cada pressionamento de tecla resultava não apenas na codificação de uma letra da mensagem, mas também no rearranjo da tabela de correspondências para o próximo pressionamento de tecla.

A cifra resultante era extremamente complexa e difícil de quebrar, mas [138]a complexidade não surgia tanto de regras complexas, mas sim a partir da combinação das múltiplas aplicações de regras simples. Essa é exatamente a província da maquinaria à época, e não é surpreendente que encriptação e decriptação deveriam ter sucumbido a alguma forma semelhante de mecanização, não muito depois da máquina de escrever e do comptômetro.

Quebrando a Enigma

Como eu indiquei, a quebra de código é uma ordem completamente diferente de tarefa. Quase inevitavelmente, dada uma séria de mensagens cifradas, a quebra de um sistema de cifra, envolve uma combinação de conhecimento ou conjectura (guesswork) dos mecanismos envolvidos na cifra (ou melhor, das regras que eles mecanizam), conhecimento ou conjectura sobre configurações de chave, tentativa e erro. Há uma sensação muito forte de que a quebra de código é uma forma de arte. Como qualquer forma de arte ela tem sua tecnologia suportante (tanto na forma da maquinaria quanto na forma da habilidade (know-how), métodos e maneiras de fazer as coisas, conjuntos de regras que podem ser aplicadas), mas ele também necessita de inspiração. Isso certamente não é verdadeiro da encriptação ou decriptação. Poderia ser dito verdadeiro da invenção de novos sistemas de cifras – e de fato há algumas invenções do final do século XX que parecem verdadeiramente inspiradas – mas como um viveiro para o desenvolvimento de novas maneiras de pensar, é difícil superar Bletchley Park.

Bletchley Park era o estabelecimento do governo do Reino Unido, durante a Segunda Guerra Mundial, encarregado das tentativas de ler quaisquer mensagens inimigas cifradas interceptadas. Muitas das mensagens de ou para unidades militares de todos os tipos, da Alemanha e outros poderes do Eixo, foram interceptadas e enviadas a Bletchley Park. E por grande parte da guerra, muitas dessas mensagens foram exitosamente decriptadas. Sempre havia um desafio no começo do dia, porque as chaves eram mudadas e a nova chave tinha de ser descoberta a partir de algumas das mensagens anteriores interceptadas. Então, por alguns longos intervalos, semanas ou meses, uma cifra particular poderia tornar-se ilegível por causa de uma mudança em alguma parte do procedimento de encriptação pelos alemães – até que as pessoas em Bletchley Park descobrissem como lidar com essa nova variante.

[139]Criptografia no pós-guerra

Na subsequente história da criptografia, seguindo-se ao final da Segunda Guerra Mundial, o computador agigantou-se. A maioria dos sistemas modernos de cifra são baseados em computador, no sentido de que programas de computador são usados para encriptação e decriptação assim como pelos quebradores de código. De fato, a maioria dos sistemas faz uso do fato de que uma mensagem em um computador (necessariamente em um dos códigos binários discutidos no capítulo 5) parece muito com um número, ao qual operações aritméticas podem ser aplicadas. É claro, ela não é realmente um número, mas com certas ressalvas nós podemos fingir que é. Nós podemos encriptá-la ao aplicar operações aritméticas a ela, tais como adição e multiplicação; a decriptação então significa o inverso dessas operações.

Uma das grandes descobertas da criptografia nesse período é o princípio de assimetria. Ele é baseado no fato de que algumas operações aritméticas são fáceis de realizar em uma direção, mas muitos difíceis em outra (é fácil multiplicar dois grandes números primos; é muito mais difícil fatorar o produto e redescobrir os dois primos originais). O sistema de cifra resultante é conhecido como Criptografia de Chave Pública (Public Key Cryptography). Ele permite à pessoa que quer receber uma mensagem cifrada tornar pública uma chave de encriptação; qualquer um que queira enviar a uma mensagem a ele / ela pode usar essa chave para a encriptar. Contudo, a chave de decriptação é diferente. Apenas o destinatário da mensagem conhece essa chave de decriptação – ela precisa nunca ser tornada pública para outros. Em princípio, isso constitui uma configuração muito mais segura – em quase todos os sistemas anteriores de cifra, emissor e receptor teriam de compartilhar uma chave, e a necessidade de compartilhamento é uma fonte principal de insegurança.

Bletchley Park e seu legado

A despeito do fato de que a criptografia realmente entrou na era da máquina apenas após a Primeira Guerra Mundial, o desafio de criptoanálise e quebra de código precisa ser realmente creditado com o pontapé inicial da revolução em TI da segunda metade do século XX. No final, nós não inventamos computadores para controlar maquinário, como Jacquard poderia ter feito; nós não inventamos computadores para realizar cálculos numéricos repetitivos, como Babbage tentou fazer. Nós não os inventamos para analisar censos; nem para organizar nossas contabilidades ou folhas de pagamento (payroll); nem para fazer previsão do tempo; nem para fazer processamento de texto; nem para [140]facilitar telecomunicações; nem para tocar nossa música ou para procurar nossas fotografias – embora eles sejam muito úteis para todas essas coisas e mais. Nós inventamos computadores para quebrar códigos.

A operação do Bletchley Park dependia pesadamente de pessoas: coletando, transcrevendo, analisando as mensagens cifradas interceptadas. Inicialmente, toda a análise era realizada inteiramente por pessoas, usando especialmente lápis e papel, e o esforço humano permanecia central para a tarefa de quebra de código. Contudo, cedo na guerra, o grande Alan Turing projetou uma máquina chamada de bombe, a qual grandemente ajudou na eliminação de muitas configurações iniciais possíveis (dada uma dica (crib), um humano poderia advinhar a versão em texto puro de uma seção particular do texto cifrado). Essa invenção possibilitou ao Bletchley Park, por grande parte da guerra, descobrir as novas configurações de chave cedo no dia, possibilitando a decriptação de quaisquer mensagens adicionais daquele dia, tão cedo quanto elas fossem recebidas.

Posteriormente durante a guerra, o esforço de Bletchley Park teve sérias dificuldades com outro sistema alemão, a cifra de Lorenz. Essa era similar à Enigma mas muito mais complexo, e tipicamente requeria semanas para quebrar as mensagens de um dia. Max Newman, outro matemático em Bletchley Park, começou a desenvolver planos para uma nova máquina que seria muito mais adaptável do que a bombe – de fato, ela era o que nós agora descrevemos como programável. Essa era muito mais difícil de construir do que a bombe, mas eventualmente, ao final de 1943, o engenheiro Tommy Flowers projetou e construiu uma versão funcional, usando válvulas termiônicas (como as usadas em rádios antigos). Ela foi chamada de Colossus e com sua ajuda, as chaves para as mensagens cifradas em Lorentz poderiam ser rapidamente descobertas.

O Colossus foi o claro precursor do computador moderno. Ele era eletrônico, digital, e em algum sentido programável, e usava muitas das ideias e princípios e métodos que um cientista da computação consideraria como essencialmente aqueles de um computador.

Um ato de vandalismo

Então, ao final da guerra, o conjunto do que fora a operação em Bletchley Park foi eliminado. Winston Churchill, quem fora o arrimo-chefe de Bletchley Park, assegurando financiamento para ele contra a oposição de algumas áreas, exigiu que toda a evidência das habilidades criptográficas do Reino Unido fosse apagada. Não apenas o Colossus mesmo foi destruído, mas [141]todas os diagramas para ele foram queimados. Todos o pessoal em Bletchely foi requerido de manter silêncio sobre absolutamente tudo que ocorreu ali.

A despeito de meu título, vandalismo é uma palavra pobre para descrever a ação de Churchill. Isso foi um retrocesso de 2000 anos ao primeiro imperador da China, no segundo século a.C. - a queima da biblioteca, para suprimir o conhecimento subversivo guardado ali.

A próxima fase

Mas é difícil matar uma ideia como essa. Nos anos de 1940, fora do Bletchley Park, algumas das ideias necessárias já estavam combinando-se. Um projeto entre a IBM e a Universidade de Harvard, planejado por Howard Aiken, desenvolveu o Harvard Mark 1, uma gigantesca calculadora programável com muitas características semelhantes às de um computador, a qual funcionou primeiro em 1943. A destruição de Bletchley Park deixou para trás, em adição a um punhado de excêntricos que acreditavam na possibilidade de construção de um computador, outro punhado que realmente o viram em operação. Dentro de um ano ou dois, imediatamente se seguindo a guerra, acadêmicos no Reino Unido (em Manchester e Cambridge) e nos EUA (em Pennsylvania e outros lugares) começaram a construir computadores. Dentro muitos poucos anos, a era do computador decolara.

Mas essa é outra história.

Epilogo

ORIGINAL:

Robertson, Stephen, B C, Before Computers: On Information Technology from Writing to the Age of Digital Data. Cambridge, UK: Open Book Publishers, 2020. p.131-141. Disponível em: <https://doi.org/10.11647/OBP.0225>

TRADUÇÃO:

EderNB do Blog Mathesis

Licença: CC BY 4.0

1Nota do anterior: Conforme o original em inglês: “The alphabet and encryption”.

2Nota do tradutor: Novamente, segundo original em inglês (ver nota anterior), onde o “e” de “The” corresponde ao “h” de “Wkh”.