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 é *roken* apresentada para entender evolução e ataques.

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

Esconder a *xistê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\)$

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

*uebra* 25 possibilidades; *rute 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.

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

Letras dobradas (LL, SS, EE), ngramas (TH, HE, IN no inglês; QUE, NTE, COM no ptBR), 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 *omofones*(várias substituições para letras frequentes) + *ódigos*para palavras frequentes (cidades, nomes, verbos). Mais difícil que monoalfabética pura mas ainda quebrável com texto suficiente.

*rande 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 *á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). *rimeira 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 *abula recta*(tabela 26×26 de Trithemius).

*uebra*

1. *este 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; *ilbert Vernam*patenteia em 1917 (US 1,310,719) usando fita de papel furada com XOR; *oseph Mauborgne*insiste em chave aleatória de uso único.

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

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

Prova de Shannon (1949)

OTP tem *erfect 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 *o tamanho da mensagem*
• Distribuição da chave: precisa canal seguro com largura de banda igual ao tráfego.
• *eutilizaçã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, *ecifrável manualmente*com crib-dragging.

Uso real

• *enona*(1943–1980): operação NSA/GCHQ que decifrou ~3000 mensagens KGB criptografadas com OTP, *orque os soviéticos reutilizaram pads*devido a apuro logístico em 1942–1945.
• *otline Washington-Moscou*desde 1963 usa OTP.
• *spionagem 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.

*ingle columnar* quebrável por anagrama. *ouble 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).

*uebra* 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 *igramas* 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.

*so* 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 *lgé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\).

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

Importante historicamente: *nspira Sboxes lineares modernas*(que precisam ser quebradas com nãolinearidade — daí AES MixColumns + S-box).

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

Enigma (Scherbius 1918; militar 1926–1945)

*omponentes*

• 3 (depois 4) *otores*escolhidos de set de 5 (M3) ou 8 (M4 naval). Cada rotor implementa permutação fixa de 26 letras.
• *lugboard (Steckerbrett)* 10 cabos formam permutação fixa adicional, simétrica.
• *efletor* permutação fixa simétrica no final.
• *ing settings (Ringstellung)* deslocamento entre rotor e indicador.
• *vanç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).

*inal* tecla → plugboard → rotor 1 → 2 → 3 → refletor → 3 → 2 → 1 → plugboard → lâmpada.

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

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

*uebras*

1. *arian Rejewski + Jerzy Różycki + Henryk Zygalski*(Biuro Szyfrów, Polônia, 1932–1939): exploram *ndicator system*(dupla cifração da chave da mensagem). Rejewski deriva *iação dos rotores*usando teoria de permutações (teorema sobre número de ciclos em permutações conjugadas). Constroem *omba kryptologiczna*(replica de 6 Enigmas em paralelo).
2. *letchley Park*(1939–1945): Turing redesenha Bomba pra explorar *ribs*(plaintext-ciphertext pairs prováveis, como "wetterbericht" em mensagens da Luftwaffe às 6 da manhã). Gordon Welchman adiciona *iagonal board* Centenas de Bombas. *anbury sheets* *ut 6* *ut 8*(naval). Bletchley empregou ~10.000 pessoas no pico.
3. *perações de captura* U110 (mai/1941) — Royal Navy captura M3 Enigma e codebook. U559 (out/1942) — short signal codebook do M4. Sem essas capturas, Bletchley não teria entrado no M4 a tempo.

*stimativa* 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 *straté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.

*uebra* *ill Tutte*deriva estrutura completa olhando apenas ciphertext (jan/1942) — feita matemática considerada uma das maiores da história. *ommy Flowers*constrói *olossus*(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.

*uebra* *illiam Friedman + Frank Rowlett*(US SIS) por *ngenharia reversa pura*sem captura de máquina — apenas análise de tráfego (1940). Codinome *agic* 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. *uebrá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 highend (Friedman + Rowlett 1939–1941). 15 rotores em três bancos com avanço pseudoaleatório. *unca quebrada*durante WWII. Aposentada nos 1950s.

Crypto AG / Hagelin pós-WWII

Boris Hagelin emigra para Suíça pós-WWII. Funda *rypto AG (CAG)* Vende máquinas a governos do mundo todo. Décadas depois (revelado 2020 via Washington Post + ZDF): empresa foi *ecretamente comprada pela CIA + BND alemã*em *peração Rubicon / Thesaurus / Minerva* e máquinas vendidas a 130+ países tinham *ackdoors 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; *uebrada*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. *uebra*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. OTPencrypted instruções para agentes. Ainda ativas em 2026: "Lincolnshire Poacher" (UK, desativada 2008), "The Buzzer" (UVB76, 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 *erfect secrecy*matematicamente.
2. Prova teorema \(|K| \geq |M|\).
3. Propõe *roduct cipher*alternando substituição (Sboxes nãolineares) e transposição (P-boxes lineares).
4. Introduce *onfusion*e *iffusion*
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

*ição* nenhuma cifra clássica (exceto OTP perfeitamente usada) sobrevive a criptanálise sistemática. Modernidade começa quando *rova de segurança formal*substitui *onfiança intuitiva*