Diffie-Hellman Private Key Size
Ich schreibe gerade meine eigene Implementierung von Diffie-Hellma n (Dies ist nicht für den tatsächlichen Gebrauch. Dies ist ausschließlich für mich, um ein besseres Verständnis von DH zu erlangen, indem ich es selbst mache.)
Für die Primzahl und den Generator verwende ich RFC 3526 , genauer gesagt die 4096-Bit-Primzahl.
Meine Frage ist, gibt es eine bestimmte Standardgeneration für geheime Ganzzahlen für Diffie-Hellman? Da die Sicherheit der geheimen Ganzzahlen (normalerweise zwei, aber DH unterstützt mehr als 1-1-Kommunikation) für die Sicherheit des Schlüsselaustauschs ziemlich entscheidend ist.
Antworten
DHKE
In einem exponentiellen Diffie-Hellman , der mit DHKE bezeichnet wird, nimmt man eine Gruppe$G$ mit einem Generator $g$ mit seiner Bestellung $n$.
Alice und Bob generieren während des Schlüsselaustauschs eine Zufallszahl $a$ und $b$ im Bereich $a,b\in (1,n)$ und überträgt $g^a$ und $g^b$ und schließlich legen sie den Schlüssel als fest $g^{ab}$ Verwenden Sie dann ein KDF, um einen symmetrischen Schlüssel und IV / Nonce abzuleiten.
Es gibt auch eine Elliptic Curve-Version von DHKE, die mit ECDH bezeichnet wird und häufiger verwendet wird als die klassische Exponentialversion.
Prime
In DHKE wählen wir prime als sichere Primzahl $p = 2 \cdot q + 1$ mit $q$ist auch eine Primzahl. Das$q$wird Sophie Germain Prime genannt .
Dies ist eine Gegenmaßnahme gegen den Pohlig-Hellman-Algorithmus , der von dem kleinen Faktor des profitiert$p-1$. Wenn eine sichere Primzahl verwendet wird, sind die Faktoren$2$ und $q$. Einen großen Faktor zu haben, ist eine Gegenmaßnahme gegen den Pohlig-Hellman.
Es gibt auch Schnorr Gruppe mit$p = r\,q + 1$. Dies kann als Verallgemeinerung der Salbei-Primzahlen angesehen werden. Die Salbei-Primzahl ist optimal.
Prime Generating
Der naive Ansatz erzeugt eine Primzahl $q$ Überprüfen Sie dann die Primalität von $2 \, q +1$( Menezes: Algorithmus 4.86 ). Im Pseudocode;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
Es gibt schnellere Methoden
Double-Speed Safe Prime Generation von David Naccache, 2003
Wie der Titel schon sagt, beschleunigt dies dies um etwa den Faktor zwei, indem beide getestet werden $2q + 1$ und $(q − 1)/2$ für die Ursprünglichkeit.
Die Idee ist die Verwendung der zufälligen Primzahl $p$ als sicherer Prime oder Sophie Germain Prime;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Sichere Prime Generation mit einem kombinierten Sieb von Michael J. Wiener, 2003.
Sie schlugen vor, kleine Primzahlen bis zu sieben $2^{16}$. Dies bietet$15x$ beschleunigen als der naive Algorithmus.
Die Idee beginnt mit dieser Beobachtung; beide$q$ und $q=2p+1$ muss kongruent sein zu $2$ Modulo $3$. Daher kann man die Kandidaten eliminieren, mit denen$0$ Modulo $3$ und $1$ Modulo $3$.
Dies kann auf jede ungerade Primzahl verallgemeinert werden $r$. Beseitigen$q$Das ist konguruent zu $(r-1)/2$ Modulo $r$ da in diesem Fall $p$ ist teilbar $r$.
Nimm einen Satz $S$ alles ungerade Prime $<B$. Dann$\prod_{r\in S}(r-2)/r$ der Kandidaten wird das Sieb überleben.
Wenn $B=2^{16}$ es wird geschätzt, dass es produzieren kann $\approx \times 15$ beschleunigen.
Kollision
Nun werden wir die Wahrscheinlichkeit untersuchen, dass dieselbe Zufallszahl ankommt, wenn es welche gibt $k$Menschen mit dem gleichen DHKE-Modul. Wir gehen davon aus, dass die$k$Personen, die denselben sicheren (unvorhersehbaren) Zufallszahlengenerator verwenden, um ihre Zufallsschlüssel zu generieren. Um dies zu vereinfachen, können wir davon ausgehen, dass es eine Person gibt, die Zufallszahlen generiert. In diesem Fall ist dies vollständig das Geburtstagsparadoxon und in der Kryptographie sehen wir uns an, dass dies der Geburtstagsangriff ist , um eine Kollision mit 50% zu finden. Dies ist eine gängige Methode, um die Kollision der Hash-Funktionen zu betrachten.
Lassen $H$ sei der Bereich des Zufallszahlengenerators und der $p$ repräsentiert dann die Wahrscheinlichkeit, die wir wollen $n(p; H)$ sei die kleinste Anzahl von Werten, die wir wählen müssen;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
Im klassischen Hash-Kollisionsfall setzen wir $p=1/2$ und das nähert sich
$$n(0.5;H) \approx 1.1774 \sqrt H$$ und wir repräsentieren normalerweise als $\mathcal{O}(\sqrt{H})$
Schauen wir uns nun einige tatsächliche Zahlen an.
2048-Bit-Primzahl
Annehmen, dass $n$ ist 2048-Bit-Nummer, denken Sie daran $n$ war die Reihenfolge des Generators $g$. Dann
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
Mit 50% Wahrscheinlichkeit $$n(0.5;2^{2048})\approx 2^{1204}$$
Als Ergebnis müssen Sie generieren $2^{1204}$Zufallszahlen, um eine mit 50% erneut zu treffen. Nicht durchführbar.
4096-Bit-Primzahl
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
Mit 50% Wahrscheinlichkeit $$n(0.5;2^{4096})\approx 2^{2048}$$
Als Ergebnis müssen Sie generieren $2^{2048}$Zufallszahlen, um eine mit 50% erneut zu treffen. Nicht durchführbar. Berechnen Sie die dlog-Tabelle vorab.
Da der Modul durch die Standards vorbestimmt ist, kann man argumentieren, dass einige Organisationen mit Superkräften eine DLog-Tabelle für den Modul erstellt haben.
Auch dies ist keine Gefahr. Nehmen wir an, dass sie eine Tabelle bis zu erstellen können$2^{64}$ dann ist die Wahrscheinlichkeit Ihres zufälligen Treffers $$\frac{\ell \, 2^{64}}{2^{2048}}$$ mit $\ell$Versuchen. Geben Sie die mögliche Schlüsselgenerierungsnummer Ihrer Gruppe ein$\ell$. 2048-Bit ist also eine wirklich große Zahl.