Taille de la clé privée Diffie-Hellman

Question

J'écris actuellement ma propre implémentation de Diffie-Hellma n (Ce n'est pas pour une utilisation réelle. C'est strictement pour moi d'obtenir une meilleure compréhension de DH en le faisant moi-même.)

Pour le premier et le générateur, j'utilise RFC 3526 , plus précisément le premier 4096 bits.

Ma question est la suivante: existe-t-il une génération d'entiers secrets standard spécifique pour Diffie-Hellman? Étant donné que la sécurité des entiers secrets (généralement deux, mais DH prend en charge plus de communications 1-1) est assez cruciale pour la sécurité de l'échange de clés.

Answer 1

DHKE

Dans un Diffie-Hellman exponentiel , noté DHKE, on prend un groupe$G$ avec un générateur $g$ avec sa commande $n$.

Alice et Bob, lors de l'échange de clés, génèrent un nombre aléatoire $a$ et $b$ dans le périmètre $a,b\in (1,n)$ et transmet $g^a$ et $g^b$ et enfin, ils établissent la clé comme $g^{ab}$ puis utilisez un KDF pour dériver une clé symétrique et IV / nonce.

Il existe également une version à courbe elliptique de DHKE et elle est désignée par ECDH et elle est plus utilisée que la version exponentielle classique.

Premier

Dans DHKE, nous choisissons prime pour être une prime sûre, c'est-à-dire $p = 2 \cdot q + 1$ avec $q$est également une prime. le$q$s'appelle un prime de Sophie Germain .

Il s'agit d'une contre - mesure contre l' algorithme de Pohlig-Hellman qui bénéficie du petit facteur de$p-1$. Si un nombre premier sûr est utilisé, les facteurs sont$2$ et $q$. Avoir un facteur important est une contre-mesure contre le Pohlig-Hellman.

Il y a aussi le groupe Schnorr avec$p = r\,q + 1$. Cela peut être considéré comme une généralisation des nombres premiers de sage. Le sage prime est optimal.

Génération principale

L'approche naïve génère une prime $q$ puis vérifiez la primalité de $2 \, q +1$( Menezes: algorithme 4.86 ). En pseudocode;

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

Il existe des méthodes plus rapides

• Génération Safe Prime à deux vitesses par David Naccache, 2003

  comme le titre l'indique, cela accélère environ un facteur de deux en testant les deux $2q + 1$ et $(q − 1)/2$ pour la primalité.

  L'idée utilise le premier aléatoire $p$ comme safe prime ou Sophie Germain prime;

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

• Safe Prime Generation avec un tamis combiné par Michael J.Wiener, 2003.

  Ils ont proposé de tamiser de petits nombres premiers jusqu'à $2^{16}$. Cela fournit$15x$ accélérer que l'algorithme naïf.

  L'idée part de cette observation; tous les deux$q$ et $q=2p+1$ doit être congru à $2$ modulo $3$. On peut donc éliminer les candidats avec lesquels$0$ modulo $3$ et $1$ modulo $3$.

  Cela peut être généralisé à tout premier impair $r$. Éliminer$q$qui sont compatibles avec $(r-1)/2$ modulo $r$ puisque dans ce cas $p$ est divisible $r$.

  Prenez un ensemble $S$ tous les premiers impairs $<B$. ensuite$\prod_{r\in S}(r-2)/r$ des candidats survivront au tamis.

  Si $B=2^{16}$ on estime qu'il peut produire $\approx \times 15$ accélérer.

Collision

Nous allons maintenant regarder la probabilité d'arriver au même nombre aléatoire s'il y a $k$les personnes utilisant le même module DHKE. Nous supposons que le$k$les personnes utilisant le même générateur de nombres aléatoires sécurisé (imprévisible) pour générer leurs clés aléatoires. Pour simplifier cela, nous pouvons supposer qu'il y a une personne qui génère des nombres aléatoires. Dans ce cas, c'est complètement le paradoxe de l' anniversaire et dans Cryptography nous regardons c'est l' attaque d'anniversaire pour trouver une collision à 50%. C'est une façon courante de regarder la collision des fonctions de hachage.

Laisser $H$ être la plage du générateur de nombres aléatoires, et le $p$ représente la probabilité que nous voulons, alors $n(p; H)$ être le plus petit nombre de valeurs que nous devons choisir;

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

Dans le cas de collision de hachage classique, nous définissons $p=1/2$ et cela approche

$$n(0.5;H) \approx 1.1774 \sqrt H$$ et nous représentons généralement comme $\mathcal{O}(\sqrt{H})$

Maintenant, regardons quelques chiffres réels.

• Premier 2048 bits

  Suppose que $n$ est un nombre de 2048 bits, rappelez-vous $n$ était l'ordre du générateur $g$. ensuite

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

  Avec 50% de probabilité $$n(0.5;2^{2048})\approx 2^{1204}$$

  En conséquence, vous devez générer $2^{1204}$nombres aléatoires pour frapper à nouveau un avec 50%. Pas faisable.

• 4096 bits prime

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

  Avec 50% de probabilité $$n(0.5;2^{4096})\approx 2^{2048}$$

  En conséquence, vous devez générer $2^{2048}$nombres aléatoires pour frapper un à nouveau avec 50%. Pas faisable. Pré-calculez la table dlog.

---

Puisque les modules sont prédéterminés par les normes, on peut soutenir que certaines organisations dotées de superpuissances ont construit une table DLog pour le module.

Ce n'est pas non plus un danger. Supposons qu'ils puissent construire une table jusqu'à$2^{64}$ alors la probabilité de votre coup aléatoire est $$\frac{\ell \, 2^{64}}{2^{2048}}$$ avec $\ell$essayer. Mettez le numéro de génération de clé possible de votre groupe dans$\ell$. Donc, 2048 bits est un très grand nombre à traiter.