03 — Criptografia Clássica

Cifras desde a Antiguidade até 1949 (artigo de Shannon). Substituição, transposição, polialfabéticas, máquinas eletromecânicas. Toda cifra desta seção é broken; apresentada para entender evolução e ataques.

1. Esteganografia (não é criptografia, mas relacionada)

Esconder a existência da mensagem, não seu conteúdo. Histórica:

2. Cifras de substituição monoalfabética

Cada letra mapeada para outra letra fixamente.

Atbash (hebraica, ~600 a.C.)

\(A \to Z, B \to Y, C \to X, \dots\) Substituição reversa. Aparece no Tanakh (Jeremias).

Cifra de César (~50 a.C.)

Shift fixo \(k\) (clássico \(k=3\)): $\(c_i = (p_i + k) \mod 26\)$

ROT13 (\(k=13\)) é caso especial — sua própria inversa, usada em Usenet para spoilers.

Quebra: 25 possibilidades; brute force trivial.

Substituição genérica monoalfabética

Mapa arbitrário \(\pi: \mathcal{A} \to \mathcal{A}\). Espaço de chaves \(26! \approx 4 \times 10^{26}\) — parece grande.

Quebra: análise de frequência (al-Kindi, ~850). Frequência de letras em texto típico:

Letras dobradas (LL, SS, EE), n-gramas (TH, HE, IN no inglês; QUE, NTE, COM no pt-BR), padrões de palavras curtas (THE, AND, OF; QUE, COM, DE) — destroem qualquer monoalfabética em minutos.

Cifras nomenclator (séc. XV–XVIII)

Substituição + lista de homofones (várias substituições para letras frequentes) + códigos para palavras frequentes (cidades, nomes, verbos). Mais difícil que monoalfabética pura mas ainda quebrável com texto suficiente.

Grande Chiffre de Luís XIV (Antoine + Bonaventure Rossignol, ~1670): nomenclator com 587 entradas, ~códigos para sílabas. Permaneceu inquebrado até Étienne Bazeries em 1893. Famoso por desvendar identidade do Homem da Máscara de Ferro.

3. Cifras de substituição polialfabética

Usa vários alfabetos ciclicamente. Reduz padrões estatísticos.

Cifra de Alberti (1466)

Disco rotativo com alfabeto interno embaralhado. Rotação a cada N letras (controlada por letras maiúsculas indicadoras). Primeira cifra polialfabética ocidental.

Cifra de Vigenère (Bellaso 1553, mal-atribuída a Vigenère 1586)

Chave \(K = k_1 k_2 \dots k_m\) repetida ciclicamente.

$\(c_i = (p_i + k_{(i \mod m)}) \mod 26\)$

Decifrar com tabula recta (tabela 26×26 de Trithemius).

Quebra:

1. Teste de Kasiski (Friedrich Kasiski 1863; Babbage independentemente em 1854): repetições no ciphertext em distâncias múltiplas de \(m\) indicam tamanho da chave.
2. Índice de coincidência (William Friedman 1922): \(\text{IC} \approx 0.067\) para inglês monoalfabético, \(\approx 0.038\) para texto uniformemente aleatório; usa pra estimar \(m\).
3. Sabendo \(m\), separar ciphertext em \(m\) "fluxos" monoalfabéticos, atacar cada um por frequência.

Autokey (Vigenère 1586, original)

A chave é a própria palavra-chave seguida do plaintext: \(K = k_1 k_2 \dots k_m p_1 p_2 p_3 \dots\). Mais forte que Vigenère puro mas ainda quebrável.

Beaufort (Francis Beaufort, ~1857)

\(c_i = (k_i - p_i) \mod 26\) — sua própria inversa. Usada em comércio do séc. XIX.

Running-key cipher

Chave = trecho de livro escolhido. Sem repetição cíclica. Mais forte mas ainda atacável porque chave é texto natural (não aleatório) — atacante explora estatística de duas linguagens sobrepostas.

4. One-Time Pad (OTP)

Conceito: Frank Miller (1882) propõe; Gilbert Vernam patenteia em 1917 (US 1,310,719) usando fita de papel furada com XOR; Joseph Mauborgne insiste em chave aleatória de uso único.

$\(c_i = p_i \oplus k_i\)$

com \(|K| = |P|\), \(K\) uniformemente aleatório, usado uma única vez.

Prova de Shannon (1949)

OTP tem perfect secrecy: para todo \(P, P', C\): $\(\Pr[E_K(P) = C] = \Pr[E_K(P') = C] = \frac{1}{|K|}\)$

Ciphertext não dá nenhuma informação sobre plaintext além do tamanho.

Limitações práticas (devastadoras)

• Chave do tamanho da mensagem.
• Distribuição da chave: precisa canal seguro com largura de banda igual ao tráfego.
• Reutilização é catastrófica (two-time pad).
• Geração de aleatoriedade verdadeira em escala é difícil.

Two-time pad attack

Se \(C_1 = P_1 \oplus K\) e \(C_2 = P_2 \oplus K\), então: $\(C_1 \oplus C_2 = P_1 \oplus P_2\)$

E \(P_1 \oplus P_2\) tem estatística de texto natural, decifrável manualmente com crib-dragging.

Uso real

• Venona (1943–1980): operação NSA/GCHQ que decifrou ~3000 mensagens KGB criptografadas com OTP, porque os soviéticos reutilizaram pads devido a apuro logístico em 1942–1945.
• Hotline Washington-Moscou desde 1963 usa OTP.
• Espionagem moderna: numbers stations (estações de números em rádio shortwave) ainda transmitem OTP-encrypted messages.

5. Cifras de transposição

Reorganizam letras sem substituir.

Cítale espartana (~500 a.C.)

Fita enrolada em bastão de diâmetro fixo \(d\). Mensagem escrita ao longo do eixo; desenrolada, letras embaralhadas. Atacante com bastão de mesmo diâmetro reconstrói.

Rail fence (zigzag)

Escreve em zigzag \(n\) linhas, lê linha por linha.

plaintext: HELLO WORLD
n=3:
H . . . O . . . R . .
. E . L . W . O . L .
. . L . . . . . . . D
ciphertext: HOR ELWOL LD

Columnar transposition

Escreve em matriz \(r \times c\), lê colunas em ordem dada por palavra-chave.

Single columnar: quebrável por anagrama. Double columnar: aplica duas vezes com chaves distintas; usada como ADFGVX (Alemanha WWI).

ADFGVX (1918)

Cifra alemã WWI, autoria Fritz Nebel. Combina substituição (5×5 Polybius) + double columnar transposition. Usa apenas letras A, D, F, G, V, X (escolhidas porque morse delas é distintivo).

Quebra: Georges Painvin (criptanalista francês) em jun/1918. Considerada uma das maiores realizações criptanalíticas da WWI.

6. Cifras de bigramas e poligramas

Playfair (Wheatstone 1854)

Cifra por bigramas. Quadrado 5×5 derivado de palavra-chave (I=J).

Regras para cifrar bigrama \((a, b)\):

1. Se na mesma linha: cada letra → letra à direita.
2. Se na mesma coluna: cada letra → letra abaixo.
3. Caso geral: letras formam diagonal de retângulo; trocam para os cantos da mesma linha.

Bigramas idênticos (LL) separados por X.

Uso: britânicos na 2ª Boer War, WWI tático, WWII costeiro. Considerada inquebrável por décadas; quebrável com ~600 letras de ciphertext via análise de frequência de bigramas.

Hill cipher (Lester Hill 1929)

Primeira cifra algébrica. Plaintext em blocos de \(n\) letras vetor \(\mathbf{p} \in \mathbb{Z}_{26}^n\). Chave matriz invertível \(K \in \mathbb{Z}_{26}^{n \times n}\).

$\(\mathbf{c} = K \mathbf{p} \mod 26\)$

Decryption com \(K^{-1} \mod 26\).

Vulnerabilidade: linearidade. Conhecendo \(n\) pares \((\mathbf{p}, \mathbf{c})\) linearmente independentes, resolve \(K\).

Importante historicamente: inspira S-boxes lineares modernas (que precisam ser quebradas com não-linearidade — daí AES MixColumns + S-box).

7. Máquinas eletromecânicas (1918–1945)

Enigma (Scherbius 1918; militar 1926–1945)

Componentes:

• 3 (depois 4) rotores escolhidos de set de 5 (M3) ou 8 (M4 naval). Cada rotor implementa permutação fixa de 26 letras.
• Plugboard (Steckerbrett): 10 cabos formam permutação fixa adicional, simétrica.
• Refletor: permutação fixa simétrica no final.
• Ring settings (Ringstellung): deslocamento entre rotor e indicador.
• Avanço de rotor: a cada tecla, rotor rápido avança; rotor médio avança a cada 26 do rápido (com "double-stepping" quirk).

Sinal: tecla → plugboard → rotor 1 → 2 → 3 → refletor → 3 → 2 → 1 → plugboard → lâmpada.

Propriedade matemática crítica: por causa do refletor, encrypt = decrypt (involução), mas nenhuma letra cifra para si mesma — exploited por Bletchley.

Espaço de chaves teórico: ~\(1.59 \times 10^{20}\) (rotores escolhidos × ring × Stecker × posição inicial).

Quebras:

1. Marian Rejewski + Jerzy Różycki + Henryk Zygalski (Biuro Szyfrów, Polônia, 1932–1939): exploram indicator system (dupla cifração da chave da mensagem). Rejewski deriva fiação dos rotores usando teoria de permutações (teorema sobre número de ciclos em permutações conjugadas). Constroem Bomba kryptologiczna (replica de 6 Enigmas em paralelo).
2. Bletchley Park (1939–1945): Turing redesenha Bomba pra explorar cribs (plaintext-ciphertext pairs prováveis, como "wetterbericht" em mensagens da Luftwaffe às 6 da manhã). Gordon Welchman adiciona diagonal board. Centenas de Bombas. Banbury sheets, Hut 6, Hut 8 (naval). Bletchley empregou ~10.000 pessoas no pico.
3. Operações de captura: U-110 (mai1941) — Royal Navy captura M3 Enigma e codebook. U-559 (out1942) — short signal codebook do M4. Sem essas capturas, Bletchley não teria entrado no M4 a tempo.

Estimativa: a quebra de Enigma encurtou WWII em ~2 anos e salvou ~14 milhões de vidas (estimativa Hinsley, British Intelligence in the Second World War).

Lorenz SZ40/SZ42 ("Tunny")

Máquina alemã para comunicação estratégica (não tática) — Hitler ↔ generais. Cifra de fluxo binária Vernam pseudo-OTP com 12 rotores (5 chi + 5 psi + 2 motor). Mais forte que Enigma.

Quebra: Bill Tutte deriva estrutura completa olhando apenas ciphertext (jan/1942) — feita matemática considerada uma das maiores da história. Tommy Flowers constrói Colossus (1943) — primeiro computador eletrônico programável, 1500–2400 válvulas, especificamente pra quebrar Lorenz. 10 Colossi operacionais até fim da guerra.

Type B / Purple (Japão WWII)

Máquina japonesa de cifras diplomáticas — substituição em alfabeto Latin via stepping switches (rotativos elétricos de telefone). Não rotores como Enigma.

Quebra: William Friedman + Frank Rowlett (US SIS) por engenharia reversa pura sem captura de máquina — apenas análise de tráfego (1940). Codinome Magic. Permitiu ler tráfego diplomático japonês incluindo a véspera de Pearl Harbor (mas mensagem chegou tarde ao comando do Pacífico).

M-209 (Hagelin)

Máquina americana portátil (Boris Hagelin, Crypto AG). Mecânica pura (sem eletricidade). 6 rotores com pinos, mais lugs em drum. Quebrável pelos alemães em horas em comunicações táticas; usada para C2 de baixo nível porque cifras militares estratégicas usavam outras.

SIGABA (ECM Mark II)

Máquina americana high-end (Friedman + Rowlett 1939–1941). 15 rotores em três bancos com avanço pseudo-aleatório. Nunca quebrada durante WWII. Aposentada nos 1950s.

Crypto AG / Hagelin pós-WWII

Boris Hagelin emigra para Suíça pós-WWII. Funda Crypto AG (CAG). Vende máquinas a governos do mundo todo. Décadas depois (revelado 2020 via Washington Post + ZDF): empresa foi secretamente comprada pela CIA + BND alemã em Operação Rubicon / Thesaurus / Minerva, e máquinas vendidas a 130+ países tinham backdoors deliberadas. NSA e BND lendo tráfego "criptografado" da Argentina, Irã, Líbia, Vaticano, Brasil… até 2018.

8. Cifras de papel da Guerra Fria

VIC cipher

Cifra usada pelo agente soviético Reino Häyhänen e descoberta por Hans Stuhmüller. Combinação de substituição straddling checkerboard + dois transposition tableaux + chave derivada de data + ID pessoal. Manual mas muito forte; quebrada pela NSA apenas após desertor entregar manual.

Solitaire (Schneier, 1999)

Bruce Schneier projeta para Neal Stephenson usar em Cryptonomicon. Stream cipher baseado em baralho de 52 cartas + 2 jokers. Quebra demonstrada por Crowley em 1999: sequência tem viés estatístico detectável.

Numbers stations

Estações de rádio shortwave transmitem strings de números em voz sintética. OTP-encrypted instruções para agentes. Ainda ativas em 2026: "Lincolnshire Poacher" (UK, desativada 2008), "The Buzzer" (UVB-76, Rússia, ativa desde 1982), Cuban "Atención" stations.

9. Linha do divisor: Shannon 1949

Communication Theory of Secrecy Systems (BSTJ 28, out 1949):

1. Define perfect secrecy matematicamente.
2. Prova teorema \(|K| \geq |M|\).
3. Propõe product cipher alternando substituição (S-boxes não-lineares) e transposição (P-boxes lineares).
4. Introduce confusion e diffusion.
5. Estabelece modelo de adversário formal.

Após Shannon, criptografia clássica termina; criptografia moderna começa. Tudo após (Feistel, DES, AES, RSA) deriva desta fundamentação.

Resumo: vulnerabilidades das cifras clássicas

Lição: nenhuma cifra clássica (exceto OTP perfeitamente usada) sobrevive a criptanálise sistemática. Modernidade começa quando prova de segurança formal substitui confiança intuitiva.