Dimensione della chiave privata Diffie-Hellman

Question

Attualmente sto scrivendo la mia implementazione di Diffie-Hellma n (questo non è per uso effettivo. Questo è strettamente per me per ottenere una migliore comprensione del DH facendolo da solo.)

Per il primo e il generatore, sto usando RFC 3526 , più specificamente il primo a 4096 bit.

La mia domanda è: esiste una generazione di interi segreti standard specifici per Diffie-Hellman? Poiché la sicurezza dei numeri interi segreti (comunemente due, ma DH supporta più di una comunicazione 1-1) è piuttosto cruciale per la sicurezza dello scambio di chiavi.

Answer 1

DHKE

In un Diffie-Hellman esponenziale , indicato con DHKE, si prende un gruppo$G$ con un generatore $g$ con il suo ordine $n$.

Alice e Bob, durante lo scambio di chiavi, generano un numero casuale $a$ e $b$ nell'intervallo $a,b\in (1,n)$ e trasmette $g^a$ e $g^b$ e infine, stabiliscono la chiave come $g^{ab}$ quindi utilizzare un KDF per derivare una chiave simmetrica e IV / nonce.

Esiste anche la versione con curva ellittica di DHKE ed è indicata con ECDH ed è più utilizzata rispetto alla versione esponenziale classica.

Prime

In DHKE, scegliamo primo per essere un numero primo sicuro, cioè $p = 2 \cdot q + 1$ con $q$è anche un primo. Il$q$si chiama Sophie Germain prime .

Questa è una contromisura contro l' algoritmo di Pohlig-Hellman che beneficia del piccolo fattore di$p-1$. Se viene utilizzato un numero primo sicuro, i fattori lo sono$2$ e $q$. Avere un grande fattore è una contromisura contro il Pohlig-Hellman.

C'è anche il gruppo Schnorr con$p = r\,q + 1$. Questo può essere considerato come una generalizzazione dei primi saggi. La sage prime è ottimale.

Prime Generating

L'approccio ingenuo genera un primo $q$ quindi controlla la primalità di $2 \, q +1$( Menezes: Algorithm 4.86 ). In pseudocodice;

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

Esistono metodi più veloci

• Safe Prime Generation a doppia velocità di David Naccache, 2003

  come suggerisce il titolo, questo accelera di circa un fattore due testando entrambi $2q + 1$ e $(q − 1)/2$ per la primalità.

  L'idea sta usando il numero primo casuale $p$ come safe prime o Sophie Germain prime;

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

• Safe Prime Generation con un setaccio combinato di Michael J. Wiener, 2003.

  Hanno proposto di setacciare piccoli numeri primi fino a $2^{16}$. Questo fornisce$15x$ più veloce dell'algoritmo ingenuo.

  L'idea parte da questa osservazione; tutti e due$q$ e $q=2p+1$ deve essere congruente a $2$ modulo $3$. Quindi si possono eliminare i candidati con cui sono$0$ modulo $3$ e $1$ modulo $3$.

  Questo può essere generalizzato a qualsiasi numero primo dispari $r$. Eliminare$q$è che sono convenzionati a $(r-1)/2$ modulo $r$ poiché in questo caso $p$ è divisibile $r$.

  Prendi un set $S$ tutto dispari primo $<B$. Poi$\prod_{r\in S}(r-2)/r$ dei candidati sopravviverà al setaccio.

  Se $B=2^{16}$ si stima che possa produrre $\approx \times 15$ accelerare.

Collisione

Ora esamineremo la probabilità di arrivare lo stesso numero casuale se ce ne sono $k$persone che utilizzano lo stesso modulo DHKE. Supponiamo che il file$k$persone che utilizzano lo stesso generatore di numeri casuali sicuro (imprevedibile) per generare le proprie chiavi casuali. Per semplificare, possiamo supporre che ci sia una persona che genera numeri casuali. In questo caso, questo è completamente il paradosso del compleanno e in Cryptography guardiamo questo è l' attacco del compleanno per trovare una collisione con il 50%. Questo è un modo comune per esaminare la collisione delle funzioni hash.

Permettere $H$ essere l'intervallo del generatore di numeri casuali e il $p$ rappresenta la probabilità che vogliamo, quindi $n(p; H)$ essere il numero più piccolo di valori che dobbiamo scegliere;

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

Nel classico caso di collisione hash, impostiamo $p=1/2$ e questo si avvicina

$$n(0.5;H) \approx 1.1774 \sqrt H$$ e di solito rappresentiamo come $\mathcal{O}(\sqrt{H})$

Ora, diamo un'occhiata ad alcuni numeri reali.

• Prime a 2048 bit

  Assumilo $n$ è un numero di 2048 bit, ricorda $n$ era l'ordine del generatore $g$. Poi

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

  Con il 50% di probabilità $$n(0.5;2^{2048})\approx 2^{1204}$$

  Di conseguenza, devi generare $2^{1204}$numeri casuali per colpire di nuovo uno con il 50%. Non fattibile.

• 4096 bit prime

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

  Con il 50% di probabilità $$n(0.5;2^{4096})\approx 2^{2048}$$

  Di conseguenza, devi generare $2^{2048}$numeri casuali per colpire di nuovo uno con il 50%. Non fattibile. Pre-calcola la tabella dlog.

---

Poiché i moduli sono predeterminati dagli standard, si può sostenere che alcune organizzazioni con superpoteri hanno costruito alcune tabelle DLog per il modulo.

Anche questo non è un pericolo. Supponiamo che possano costruire una tabella fino a$2^{64}$ allora la probabilità del tuo colpo casuale è $$\frac{\ell \, 2^{64}}{2^{2048}}$$ con $\ell$provare. Inserisci il possibile numero di generazione della chiave del tuo gruppo in$\ell$. Quindi, 2048 bit è un numero davvero grande da affrontare.