Tamanho da chave privada Diffie-Hellman

Question

No momento, estou escrevendo minha própria implementação de Diffie-Hellma n (não é para uso real. É estritamente para eu obter uma melhor compreensão do DH fazendo isso sozinho).

Para o primo e o gerador, estou usando o RFC 3526 , mais especificamente o primo de 4096 bits.

Minha pergunta é: existe uma geração de inteiros secretos padrão específica para Diffie-Hellman? Uma vez que a segurança dos números inteiros secretos (normalmente dois, mas o DH suporta mais de 1-1 comunicação) é crucial para a segurança da troca de chaves.

Answer 1

DHKE

Em um Diffie-Hellman exponencial , denotado por DHKE, toma-se um grupo$G$ com um gerador $g$ com seu pedido $n$.

A Alice e o Bob, durante a troca da chave, geram número aleatório $a$ e $b$ no intervalo $a,b\in (1,n)$ e transmite $g^a$ e $g^b$ e, finalmente, eles estabelecem a chave como $g^{ab}$ em seguida, use um KDF para derivar uma chave simétrica e IV / nonce.

Também existe a versão Curva Elíptica de DHKE e é denotada por ECDH e é mais usada do que a versão exponencial clássica.

Prime

Na DHKE, escolhemos o primo para ser um primo seguro, ou seja, $p = 2 \cdot q + 1$ com $q$também é um primo. o$q$é chamado de Sophie Germain primo .

Esta é uma contramedida contra o algoritmo Pohlig-Hellman que se beneficia do pequeno fator do$p-1$. Se um primo seguro for usado, então os fatores são$2$ e $q$. Ter um grande fator é uma contramedida contra o Pohlig-Hellman.

Há também o grupo Schnorr com$p = r\,q + 1$. Isso pode ser considerado uma generalização dos números primos do sábio. O princípio do sábio é ótimo.

Geração primária

A abordagem ingênua gera um primo $q$ em seguida, verifique a primalidade de $2 \, q +1$( Menezes: Algoritmo 4,86 ). Em pseudocódigo;

do
   p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)

Existem métodos mais rápidos

• Double-Speed ​​Safe Prime Generation de David Naccache, 2003

  como o título sugere, isso acelera em cerca de um fator de dois, testando ambos $2q + 1$ e $(q − 1)/2$ para a primalidade.

  A ideia é usar o primo aleatório $p$ como safe prime ou Sophie Germain prime;

  do 
    p = randomPrime(k-bit integer)
  while ((p − 1)/2 and 2p + 1 are composite)
  

• Safe Prime Generation with a Combined Sieve de Michael J. Wiener, 2003.

  Eles propuseram peneirar pequenos primos até $2^{16}$. Isso fornece$15x$ acelerar do que o algoritmo ingênuo.

  A ideia começa com esta observação; ambos$q$ e $q=2p+1$ deve ser congruente com $2$ modulo $3$. Portanto, pode-se eliminar os candidatos com os quais são$0$ modulo $3$ e $1$ modulo $3$.

  Isso pode ser generalizado para qualquer primo ímpar $r$. Eliminar$q$que são conguruentes com $(r-1)/2$ modulo $r$ já que neste caso $p$ é divisível $r$.

  Pegue um conjunto $S$ tudo estranho $<B$. Então$\prod_{r\in S}(r-2)/r$ dos candidatos sobreviverão à peneira.

  E se $B=2^{16}$ estima-se que pode produzir $\approx \times 15$ acelerar.

Colisão

Agora vamos olhar para a probabilidade de chegarmos ao mesmo número aleatório se houver $k$pessoas usando o mesmo módulo DHKE. Estamos assumindo que o$k$pessoas usando o mesmo gerador de números aleatórios seguro (imprevisível) para gerar suas chaves aleatórias. Para simplificar, podemos assumir que existe uma pessoa que gera números aleatórios. Neste caso, este é completamente o paradoxo do aniversário e na Criptografia olhamos para este é o ataque de aniversário para encontrar uma colisão com 50%. Essa é uma maneira comum de observar a colisão das funções hash.

Deixei $H$ ser o intervalo do gerador de números aleatórios, e o $p$ representa a probabilidade que queremos, então $n(p; H)$ ser o menor número de valores que temos que escolher;

$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$

No caso clássico de colisão de hash, definimos $p=1/2$ e isso se aproxima

$$n(0.5;H) \approx 1.1774 \sqrt H$$ e geralmente representamos como $\mathcal{O}(\sqrt{H})$

Agora, vamos examinar alguns números reais.

• 2048 bits primos

  Assuma isso $n$ é um número de 2048 bits, lembre-se $n$ foi a ordem do gerador $g$. Então

  $$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$

  Com 50% de probabilidade $$n(0.5;2^{2048})\approx 2^{1204}$$

  Como resultado, você precisa gerar $2^{1204}$números aleatórios para acertar um novamente com 50%. Não é viável.

• 4096 bits primos

  $$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$

  Com 50% de probabilidade $$n(0.5;2^{4096})\approx 2^{2048}$$

  Como resultado, você precisa gerar $2^{2048}$números aleatórios para acertar um novamente com 50%. Não é viável. Pré-calcule a tabela dlog.

---

Uma vez que os módulos são pré-determinados pelos padrões, pode-se argumentar que algumas organizações com superpoderes construíram alguma tabela DLog para o módulo.

Isso também não é um perigo. Vamos supor que eles possam construir uma mesa até$2^{64}$ então a probabilidade do seu acerto aleatório é $$\frac{\ell \, 2^{64}}{2^{2048}}$$ com $\ell$experimentar. Coloque o possível número de geração de chave de seu grupo em$\ell$. Portanto, 2048 bits é um número muito grande para se lidar.