Colossus foi um conjunto de computadores desenvolvidos por decifradores britânicos nos anos de 1943 a 1945 para ajudar na criptoanálise da cifra de Lorenz. A Colossus usava válvulas termiônicas (tubos a vácuo) para realizar operações booleanas e de contagem. Colossus é, portanto, considerado o primeiro computador digital programável, eletrônico, embora tenha sido programado por interruptores e plugues e não por um programa armazenado.
O Colossus foi projetado pelo engenheiro de pesquisa de telefone da General Post Office (GPO) Tommy Flowers para resolver um problema apresentado pelo matemático Max Newman na Escola de Código do Governo e Cypher (GC&CS) em Bletchley Park. O uso de probabilidade de Alan Turing na criptoanálise (ver Banburismus) contribuiu para seu projeto. Algumas vezes foi erroneamente declarado que Turing projetou o Colossus para ajudar na criptoanálise da máquina Enigma.Golden, Frederic (29 de março de 1999), "Who Built The First Computer?", Time, vol. 153 no. 12, arquivado do original em 6 de janeiro de 2006 A máquina de Turing que ajudou a decodificar o Enigma foi a Bomba Eletromecânica, não a Colossus.
O protótipo, Colossus Mark 1, foi mostrado para funcionar em dezembro de 1943 e estava em uso em Bletchley Park no início de 1944. Já o Colossus Mark 2 aprimorado, que usava registradores de deslocamento para quintuplicar a velocidade de processamento, trabalhou pela primeira vez em 1 de junho de 1944, bem a tempo para os desembarques na Normandia no Dia D.T. H. Flowers, "The Design of Colossus (foreword by Howard Campaigne)," in Annals of the History of Computing, vol. 5, no. 3, pp. 239-252, July-Sept. 1983, doi: 10.1109/MAHC.1983.10079. Dez Colossi estavam em uso até o final da guerra e um décimo primeiro estava sendo comissionado. O uso dessas máquinas em Bletchley Park permitiu aos Aliados obter uma vasta quantidade de inteligência militar de alto nível a partir de mensagens de radiotelegrafia interceptadas entre o Alto Comando Alemão (OKW) e seus comandos do exército em toda a Europa ocupada.
A existência das máquinas Colossus foi mantida em segredo até meados da década de 1970.Preneel, Bart, ed. (2000), "Colossus and the German Lorenz Cipher – Code Breaking in WW II" (PDF), Advances in Cryptology - EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium May 14-18, 2000, Proceedings, Lecture Notes in Computer Science, Springer, p. 417, doi:10.1007/3-540-45539-6_29, ISBN 978-3540675174 Todas as máquinas, exceto duas, foram desmontadas em peças tão pequenas que não foi possível inferir seu uso. As duas máquinas retidas foram eventualmente desmontadas na década de 1960. A reconstrução funcional de um Mark 2 Colossus foi concluída em 2008 por Tony Sale e uma equipe de voluntários; Hoje em dia, está em exibição no Museu Nacional de Computação em Bletchley Park.
Objetivo e origens miniaturadaimagem|Uma máquina de criptografia Lorenz SZ42 com suas tampas removidas no Museu Nacional de Computação em Bletchley Park Os computadores Colossus foram usados para ajudar a decifrar mensagens de rádio teletipo interceptadas que foram criptografadas usando a Lorenz, que até então era desconhecida. Informações de inteligência revelaram que os alemães chamavam os sistemas de transmissão de teleimpressora sem fio de "Sägefisch" (peixe-serra). Isso levou os britânicos a chamarem o tráfego criptografado do teleprinter alemão de "Fish",Good, Michie & Timms 1945, 1 Introduction: 11 German Tunny, 11A Fish Machines, (c) The German Ciphered Teleprinter, p. 4. e a máquina desconhecida e suas mensagens interceptadas de "Tunny" (atum).Hinsley, F. H.; Stripp, Alan (2001). "PART THREE: Fish". Codebreakers: The Inside Story of Bletchley Park. Oxford University Press. ISBN 978-0-19-280132-6. Retrieved 26 October 2017 – via Google Books.
Antes que os alemães aumentassem a segurança de seus procedimentos operacionais, os criptoanalistas britânicos diagnosticaram como a máquina invisível funcionava e construíram uma imitação dela chamada "British Tunny".
Foi deduzido que a máquina tinha doze rodas e usava uma técnica de cifragem Vernam em caracteres de mensagem no código telegráfico padrão ITA2 de 5 bits. Ele fez isso combinando os caracteres de texto simples com um fluxo de caracteres-chave usando a função booleana XOR para produzir o texto cifrado. miniaturadaimagem|Pinos nas rodas 9 e 10 mostrando suas posições levantadas (ativas) e abaixadas (inativas). Um pino ativo reverteu o valor de um bit (0 → 1 e 1 → 0) Em agosto de 1941, um erro cometido por operadores alemães levou à transmissão de duas versões da mesma mensagem com configurações de máquina idênticas. Estes foram interceptados e trabalhados em Bletchley Park, em uma mansão vitoriana chamada Station X, a qual estava prestes a ser demolida, porém devido a sua localização geográfica próxima a ferrovia e grandes centros educacionais, tornou-se o centro onde Colossus fora construído. Primeiro, John Tiltman, um criptoanalista GC&CS, derivou um fluxo de chave de quase 4.000 caracteres.Budiansky, Stephen (2006), Colossus, Codebreaking, and the Digital Age, pp. 52–63 in Copeland (2006) Em seguida, Bill Tutte, um membro recém-chegado da Seção de Pesquisa, usou esse fluxo-chave para descobrir a estrutura lógica da máquina Lorenz. Ele deduziu que as doze rodas consistiam em dois grupos de cinco, que ele chamou de rodas χ (chi) e ψ (psi), as duas restantes ele chamou de rodas μ (mu) ou "motoras". As rodas chi pisavam regularmente com cada letra criptografada, enquanto as rodas psi pisavam irregularmente, sob o controle das rodas motoras.Tutte, William T. (2006), Appendix 4: My Work at Bletchley Park, pp. 352–369 miniaturadaimagem|As máquinas Lorenz SZ tinham 12 rodas, cada uma com um número diferente de cames (ou "pinos"). Número da roda123456789101112Nome da roda BPψ1ψ2ψ3ψ4ψ5μ37μ61χ1χ2χ3χ4χ5Número de cames (pinos)434751535937614131292623 |491x491px Com um fluxo de chaves suficientemente aleatório, uma cifra de Vernam remove a propriedade de linguagem natural de uma mensagem de texto simples de ter uma distribuição de frequência desigual dos diferentes caracteres, para produzir uma distribuição uniforme no texto cifrado. A máquina Tunny fez isso bem. No entanto, os criptanalistas descobriram que, ao examinar a distribuição de frequência das mudanças caractere a caractere no texto cifrado, em vez dos caracteres simples, houve um desvio da uniformidade que forneceu um caminho para o sistema. Isso foi alcançado por "diferenciação" em que cada bit ou caractere foi XOR-ed com seu sucessor.Good, Michie & Timms 1945, 1 Introduction: 11 German Tunny, 11C Wheel Patterns, (b) Differenced and Undifferenced Wheels, p. 11. Depois que a Alemanha se rendeu, as forças aliadas capturaram uma máquina Tunny e descobriram que era a máquina de criptografia em linha eletromecânica Lorenz SZ (Schlüsselzusatzgerät, cipher attach).
Para descriptografar as mensagens transmitidas, duas tarefas tiveram que ser executadas. O primeiro foi "quebra de roda", que foi a descoberta dos padrões excêntricos para todas as rodas. Esses padrões foram configurados na máquina Lorenz e então usados por um período fixo de tempo para uma sucessão de mensagens diferentes. Cada transmissão, que geralmente continha mais de uma mensagem, era codificada com uma posição inicial diferente das rodas. Alan Turing inventou um método de quebra de roda que ficou conhecido como Turingery.Copeland "Turingery" 2006, pp. 378–385. A técnica de Turing foi posteriormente desenvolvida em "Retângulo", para o qual Colossus poderia produzir tabelas para análise manual. Colossi 2, 4, 6, 7 e 9 tinham um dispositivo para ajudar neste processo.Good, Michie & Timms 1945, 24 – Rectangling: 24B Making and Entering Rectangles pp. 114–115, 119–120.
A segunda tarefa era "configuração da roda", que calculava as posições iniciais das rodas para uma mensagem específica e só poderia ser tentada depois que os padrões do came fossem conhecidos.Good, Michie & Timms 1945, 1 Introduction: 11 German Tunny, 11E The Tunny Network, (b) Wheel-breaking and Setting, p. 15. Foi para essa tarefa que o Colossus foi inicialmente projetado. Para descobrir a posição inicial das rodas chi para uma mensagem, o Colossus comparou dois fluxos de caracteres, contando estatísticas da avaliação de funções booleanas programáveis. Os dois fluxos eram o texto cifrado, que era lido em alta velocidade em uma fita de papel, e o fluxo de chave, gerado internamente, em uma simulação da máquina alemã desconhecida. Após uma sucessão de diferentes corridas do Colossus para descobrir as prováveis configurações da roda do chi, elas foram verificadas examinando a distribuição de frequência dos caracteres no texto cifrado processado.Small, Albert W. (December 1944), The Special Fish Report O Colossus produziu essas contagens de frequência.
Processos de descriptografia As mensagens da "Tunny" eram decodificadas a mão por Alan Turing, usando seu método de dedução. O método de Turing, foi por alguns meses o único mecanismo de decodificação, todavia a decodificação era feita a mão, o que se provou muito lento. O Colossus 1, em média 1 ano para ser criado mas depois que o primeiro foi lançado, a produção foi acelerada rapidamente.
Usando a diferenciação e sabendo que as rodas psi não avançavam com cada caractere, Tutte concluiu que tentar apenas dois bits diferenciados (impulsos) do fluxo de chi contra o texto cifrado diferenciado produziria uma estatística não aleatória. Isso ficou conhecido como "invasão 1 + 2" de Tutte. Envolveu o cálculo da seguinte função booleana:
Contando o número de vezes que resultou "falso" (zero). Se esse número exceder um valor limite predefinido conhecido como "total definido", ele será impresso. O criptoanalista examinaria a impressão para determinar qual das posições iniciais putativas era mais provável de ser a correta para as rodas chi-1 e chi-2.Carter, Frank (2008), Codebreaking with the Colossus Computer, Bletchley Park Reports, 1 (New ed.), Bletchley Park Trust, ISBN 978-1-906723-00-2
Essa técnica seria então aplicada a outros pares de impulsos, ou únicos, para determinar a provável posição inicial de todas as cinco rodas chi. A partir daí, o de-chi (D) de um texto cifrado pode ser obtido, a partir do qual o componente psi pode ser removido por métodos manuais. Se a distribuição de frequência de caracteres na versão de-chi do texto cifrado estava dentro de certos limites, a "configuração da roda" das rodas chi foi considerada alcançada, e as configurações de mensagem e de-chi foram passadas para o "Testery". Esta foi a seção em Bletchley Park liderada pelo Major Ralph Tester, onde a maior parte do trabalho de descriptografia foi feito por métodos manuais e linguísticos.Roberts, Jerry (2009). Capt. Jerry Roberts: My Top Secret Codebreaking at Bletchley Park 1941 to 45: Lecture on 11 March 2009. University College London. 34 minutes in – via YouTube.
O Colossus também podia derivar a posição inicial das rodas do motor e psi, mas isso não foi muito feito até os últimos meses da guerra, quando havia muitos Colossi disponíveis e o número de mensagens Tunny havia diminuído. +NotaçãoGood, Michie & Timms 1945, 1 Introduction: 12 Cryptographic Aspects, 12A The Problem, (a) Formulae and Notation, p. 16.texto simpleschave - a sequência de caracteres usados no XOR binário com o texto simples para dar o texto cifradocomponente chi da chavecomponente psi da chavepsi estendido - a sequência real de caracteres adicionados por