Rozmiar klucza prywatnego Diffie-Hellman
Obecnie piszę własną implementację Diffie-Hellma n (to nie jest do rzeczywistego użytku. Jest to wyłącznie dla mnie, aby lepiej zrozumieć DH, robiąc to samodzielnie).
W przypadku liczby pierwszej i generatora używam RFC 3526 , a dokładniej 4096-bitowej liczby pierwszej.
Moje pytanie brzmi, czy istnieje określone standardowe generowanie tajnych liczb całkowitych dla Diffie-Hellman? Ponieważ bezpieczeństwo tajnych liczb całkowitych (zwykle dwóch, ale DH obsługuje więcej niż komunikację 1-1) jest dość istotne dla bezpieczeństwa wymiany kluczy.
Odpowiedzi
DHKE
W wykładniczym Diffie-Hellman , oznaczonym przez DHKE, bierze się grupę$G$ z generatorem $g$ z jego kolejnością $n$.
Alicja i Bob podczas wymiany kluczy generują losową liczbę $a$ i $b$ w zasięgu $a,b\in (1,n)$ i przekazuje $g^a$ i $g^b$ i wreszcie ustalają klucz jako $g^{ab}$ następnie użyj KDF do wyprowadzenia klucza symetrycznego i IV / nonce.
Istnieje również wersja DHKE z krzywą eliptyczną i jest oznaczona przez ECDH i jest częściej używana niż klasyczna wersja wykładnicza.
główny
To znaczy w DHKE wybieramy liczbę pierwszą jako bezpieczną liczbę pierwszą $p = 2 \cdot q + 1$ z $q$jest również liczbą pierwszą. Plik$q$nazywana jest liczbą pierwszą Sophie Germain .
Jest to środek zaradczy przeciwko algorytmowi Pohliga-Hellmana, który korzysta z niewielkiego współczynnika$p-1$. Jeśli używana jest bezpieczna liczba pierwsza, to są współczynniki$2$ i $q$. Posiadanie dużego czynnika jest środkiem zaradczym przeciwko Pohlig-Hellmanowi.
Jest też grupa Schnorr z$p = r\,q + 1$. Można to uznać za uogólnienie liczb pierwszych mędrców. Szałwia pierwsza jest optymalna.
Generowanie Prime
Naiwne podejście generuje liczbę pierwszą $q$ następnie sprawdź pierwotność $2 \, q +1$( Menezes: Algorytm 4.86 ). W pseudokodzie;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
Są szybsze metody
Double-Speed Safe Prime Generation , David Naccache, 2003
jak sugeruje tytuł, przyśpiesza to około dwukrotnie, testując oba $2q + 1$ i $(q − 1)/2$ dla prymatu.
Pomysł polega na użyciu losowej liczby pierwszej $p$ jako bezpieczna liczba pierwsza lub liczba pierwsza Sophie Germain;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Safe Prime Generation with a Combined Sieve Michael J.Wiener, 2003.
Zaproponowali przesiewanie małych liczb pierwszych do $2^{16}$. To zapewnia$15x$ przyspieszyć niż naiwny algorytm.
Pomysł zaczyna się od tej obserwacji; obie$q$ i $q=2p+1$ musi być zgodny $2$ modulo $3$. Dlatego można wyeliminować kandydatów, z którymi są$0$ modulo $3$ i $1$ modulo $3$.
Można to uogólnić na dowolną nieparzystą liczbę pierwszą $r$. Wyeliminować$q$to jest zgodne z $(r-1)/2$ modulo $r$ ponieważ w tym przypadku $p$ jest podzielna $r$.
Weź zestaw $S$ wszystkie dziwne liczby pierwsze $<B$. Następnie$\prod_{r\in S}(r-2)/r$ kandydatów przetrwa sito.
Gdyby $B=2^{16}$ szacuje się, że może produkować $\approx \times 15$ przyśpieszyć.
Kolizja
Teraz przyjrzymy się prawdopodobieństwu uzyskania tej samej liczby losowej, jeśli istnieje $k$ludzie używający tego samego modułu DHKE. Zakładamy, że$k$osoby używające tego samego bezpiecznego (nieprzewidywalnego) generatora liczb losowych do generowania losowych kluczy. Aby to uprościć, możemy założyć, że jest jedna osoba, która generuje liczby losowe. W tym przypadku jest to całkowicie paradoks urodzinowy, a w kryptografii patrzymy na to, że jest to atak urodzinowy, aby znaleźć kolizję z 50%. Jest to typowy sposób patrzenia na kolizję funkcji skrótu.
Pozwolić $H$ być zakresem generatora liczb losowych, a $p$ reprezentuje zatem prawdopodobieństwo, którego chcemy $n(p; H)$ być najmniejszą liczbą wartości, jakie mamy do wyboru;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
W klasycznym przypadku kolizji hash, ustawiamy $p=1/2$ i to się zbliża
$$n(0.5;H) \approx 1.1774 \sqrt H$$ i zwykle reprezentujemy jako $\mathcal{O}(\sqrt{H})$
Spójrzmy teraz na rzeczywiste liczby.
2048-bitowy prime
Zakładać, że $n$ jest liczbą 2048-bitową, pamiętaj $n$ była kolejność generatora $g$. Następnie
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
Z prawdopodobieństwem 50% $$n(0.5;2^{2048})\approx 2^{1204}$$
W rezultacie musisz wygenerować $2^{1204}$losowe liczby, aby ponownie trafić w jedną z 50%. Niewykonalny.
4096-bitowa pierwsza
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
Z prawdopodobieństwem 50% $$n(0.5;2^{4096})\approx 2^{2048}$$
W rezultacie musisz wygenerować $2^{2048}$losowe liczby, aby ponownie trafić w jedną z 50%. Niewykonalny. Oblicz wstępnie tabelę dlog.
Ponieważ moduły są z góry określone przez standardy, można argumentować, że niektóre organizacje z supermocarstwami zbudowały jakąś tablicę DLog dla modułu.
To też nie jest zagrożenie. Załóżmy, że potrafią zbudować tabelę do$2^{64}$ to prawdopodobieństwo przypadkowego trafienia wynosi $$\frac{\ell \, 2^{64}}{2^{2048}}$$ z $\ell$próbować. Umieść możliwy numer generowania klucza swojej grupy w$\ell$. Tak więc 2048-bit to naprawdę duża liczba, z którą trzeba sobie poradzić.