Diffie–Hellman: um segredo combinado em público

Alice envia gᵃ mod p, Bob envia gᵇ mod p e ambos chegam a gᵃᵇ mod p sem que nenhum deles o tenha transmitido. Eve vê todos os números que passam pela linha. Avance passo a passo pela troca e pelo ataque, e varie p e g para descobrir o que lhe encurta o trabalho.

Exemplo resolvido — Diffie–Hellman: um segredo combinado em público

Número público de Alice	8
Número público de Bob	19
O segredo partilhado	2
Valores possíveis do segredo partilhado	22 de 22
Tentativas por força bruta para este A	7 (no pior caso 22)
Tentativas por Pohlig–Hellman para este A	8 (no pior caso 13)
Segredo obtido por Eve a partir de x	2

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Diffie–Hellman: um segredo combinado em público

Numa troca de chaves de Diffie–Hellman, duas partes combinam um número secreto através de um canal aberto a qualquer observador. Fixam publicamente um primo p e uma base g. Cada interveniente escolhe um expoente privado, publica g elevado a essa potência mod p e eleva depois o número público do outro ao seu próprio expoente privado: (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Desfazer este processo exige resolver um logaritmo discreto: dado A = gᵃ mod p, encontrar x tal que gˣ ≡ A (mod p). Diffie e Hellman observaram em 1976 que não viam forma de extrair o segredo partilhado dos números públicos sem resolver este problema, embora não tivessem prova formal de que tal atalho não existisse. A ordem de g é o menor n ≥ 1 com gⁿ ≡ 1 (mod p); e g diz-se um gerador quando a sua ordem é p − 1.

O que significa cada símbolo

p: o módulo primo, público
g: a base, pública
a, b: os expoentes privados de Alice e de Bob
A, B: os seus números públicos, gᵃ mod p e gᵇ mod p
x: o expoente descoberto por Eve; qualquer x com gˣ ≡ A serve, pelo que ela encontra a mod a ordem de g
ord(g): a ordem de g: quantos valores distintos o segredo partilhado pode assumir

Pressupõe: p é um número primo entre 5 e 1.999; g é qualquer base entre 2 e p − 2; e a e b variam de 1 a p − 2. Uma tentativa corresponde a comparar uma potência calculada com o alvo, incluindo-se em ambas as contagens a tentativa bem-sucedida. Cada dígito em Pohlig–Hellman é determinado testando os candidatos por ordem, exatamente como os autores propõem para fatores pequenos; para fatores grandes, descrevem também uma busca que troca memória por tempo, não implementada nesta página. O exemplo original de Diffie e Hellman usava um primo com cerca de 200 bits, estimando o cálculo do logaritmo em cerca de 2¹⁰⁰ operações.

Em 257, a base 2 deixa apenas dezasseis segredos possíveis 🖖

Prima Um ciclo de 16. Como 257 é primo, A e B parecem à primeira vista poder ser qualquer um de 256 números. Mas 2⁸ = 256, que é −1 mod 257, logo 2¹⁶ = 1; as potências de 2 fecham-se num ciclo de 16 valores: 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129. São essas as células sombreadas. Quaisquer que sejam a e b, gᵃᵇ será um deles, e aqui é 129. A força bruta de Eve para ao fim de 14 tentativas e nunca precisará de mais de 16. O valor de x encontrado, 13, não é o 77 de Alice, mas coincide com ele mod 16 — e o expoente não guarda mais informação do que essa. Um módulo primo não nos protege disto. Das 254 bases entre 2 e 255, 126 não são geradores, e duas delas, 16 e 241, deixam apenas quatro segredos possíveis. Em 263, onde p − 1 = 2 × 131, a ordem de qualquer base entre 2 e 261 é 131 ou 262.

Primos gémeos: 811 tentativas contra 21 🖖

Prima p − 1 em blocos pequenos. 1621 é primo e 1620 = 2² · 3⁴ · 5, pelo que Pohlig–Hellman nunca precisa de percorrer as 1.620 potências de g. Determina a mod 4 testando dois candidatos de cada vez, a mod 81 três de cada vez e a mod 5 entre cinco possibilidades, reunindo depois os blocos pelo teorema chinês dos restos: no pior caso, 2·2 + 4·3 + 5 = 21 tentativas, e aqui apenas 15, onde a força bruta exigiria 1.235. Escolha agora 1619 na tabela de primos vizinhos de p. Fica apenas duas unidades abaixo, mas 1618 = 2 × 809: um único bloco de 809 candidatos, no pior caso 811 tentativas, e 427 para o mesmo a. O esforço de Eve depende do maior fator primo de p − 1, e não do tamanho de p. Nos 301 primos aceites por esta página, o pior caso de Pohlig–Hellman nunca excede esse fator por mais de 25; em 172 deles fica abaixo de um décimo da força bruta, e em 146 das 300 transições de um primo para o seguinte o custo até diminui. Em 1978, Pohlig e Hellman afirmaram-no sem rodeios: quando p − 1 tem apenas fatores primos pequenos, a exponenciação mod p «não é uma boa função unidirecional».

A base mais segura não é um gerador 🖖

Prima Uma base de ordem prima. Para o primo 263, a base 2 não é um gerador: as suas potências repetem-se ao fim de 131 passos, pelo que só 131 segredos são possíveis. Escreva g = 5, um gerador, e o total duplica. Repare no pior caso de Pohlig–Hellman para esta base: 133 tentativas, duas delas no último dígito binário de a, porque A¹³¹ vale 1 se a for par e 262 (ou seja, −1) se a for ímpar. Um gerador entrega esse dígito de mão beijada para qualquer primo ímpar, pois p − 1 é sempre par. Volte a g = 2. A sua ordem, 131, é prima; Pohlig–Hellman não tem por onde decompor o problema e o seu pior caso fica-se pelas 131 tentativas, tal como a força bruta. O gerador duplicou o leque de segredos possíveis, mas ofereceu a Eve um bit a troco de nada: apenas a partir de A e B, ela consegue deduzir se o segredo é um quadrado mod 263. Como todas as potências de 2 são quadrados, com g = 2 não há nada a denunciar.

Problema resolvido na íntegra

Recuperar o segredo de Alice para p = 101 5 passos
Alice e Bob utilizam p = 101 e g = 2. Eve observa A = 12 e B = 53. Encontre um x com 2ˣ ≡ 12 (mod 101) através de Pohlig–Hellman, conte as tentativas e use x para obter o segredo partilhado. Diga depois quanto custaria o mesmo ataque com p = 65.537.

Abrir este problema na ferramenta
1. Como 100 = 2² · 5², x fica determinado por x mod 4 e x mod 25. A ordem de 2 tem de dividir 100; sendo 2⁵⁰ = 100 e 2²⁰ = 95 ambos diferentes de 1, a ordem só pode ser o próprio 100, o que faz de 2 um gerador.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Mod 4, temos γ = 2⁵⁰ = 100, equivalente a −1. Para o primeiro dígito binário: 12⁵⁰ = 100, logo d = 1, à segunda tentativa. Descontando esse contributo: 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6. Como 6²⁵ = 100, o dígito seguinte também é 1, outra vez à segunda tentativa. Daqui resulta x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Mod 25, γ = 2²⁰ = 95, com potências 1, 95, 36, 87, 84. Primeiro dígito na base 5: 12²⁰ = 95, dando d = 1 à segunda tentativa. Eliminando-o: 6⁴ = 1.296 ≡ 84, pelo que o dígito seguinte é 4, à quinta tentativa. Logo, x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. Os números inferiores a 100 congruentes com 21 mod 25 são 21, 46, 71 e 96; destes, apenas 71 é congruente com 3 mod 4. Conclui-se que x = 71, ao fim de 2 + 2 + 2 + 5 = 11 tentativas (no pior caso seriam 2·2 + 2·5 = 14). A força bruta teria percorrido de 0 a 71, totalizando 72 tentativas. O segredo partilhado é 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65.537 = 2¹⁶ + 1 é primo e p − 1 = 2¹⁶. Pohlig–Hellman resolve os seus dezasseis dígitos binários um a um, com dois candidatos cada: no pior cenário são 32 tentativas, enquanto a força bruta poderia exigir 65.536. Pohlig e Hellman analisaram especificamente este caso, p = 2ⁿ + 1, antes de passarem ao método geral.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Resposta

x = 71, ao fim de 11 tentativas (no pior caso 14), sendo o segredo partilhado 35. Para p = 65.537, o ataque exige no máximo 32 tentativas. A página termina em 1.999, pelo que esse valor resulta da aritmética e não de uma execução.

$x = 71, 11 tries, s = 35$

Percurso de aprendizagem

Como se quebram os códigos

Referências (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.