Angriff auf kleine geheime Exponenten (Menü Einzelverfahren \ RSA-Kryptosystem \ Gitterbasierte Angriffe auf RSA)

Sie können den Angriff über den Dialog Angriff auf kleine geheime Exponenten ausführen.

Der Angriff auf kleine geheime Schlüssel ermöglicht es, einen RSA-Modulus N effizient zu faktorisieren, wenn der öffentliche Schlüssel e bekannt ist und der geheime Schlüssel d zu klein gewählt wurde.

Dazu wird diese Aufgabe in eine Nullstellensuche umgeformt und mit dem Verfahren der Gitterreduktion gelöst. Ausgangspunkt für diesen Angriff stellt die folgende elementare Gleichung des RSA-Kryptosystems dar:

e · d ≡ 1 mod Φ(N)
Es existiert also ein k für das
ed + k Φ(N) = 1
über Z gilt. Dabei ist Φ(N) bekanntlich (p-1)(q-1) = pq-p-q+1 = N -(p+q)+1 .
Durch Einsetzen erhält man schließlich:
e · d + k(N + 1 - (p + q)) = 1
Setzt man nun s := -(p + q) und A := N + 1 und reduziert beide Seiten modulo e , so
ergibt sich:
k(A + s) ≡ 1 mod e

Diese Gleichung wird nun mit dem Verfahren der Gitterreduktion gelöst.

Die Größe von d wird im folgenden immer in Abhängigkeit von N angegeben. Dazu wird eine Variable delta eingeführt, so dass folgende Gleichung gilt:
d=Ndelta
Der Angriff funktioniert theoretisch bis zu einem delta der Größe 0,292. Das heißt, dass N nach heutigem Kenntnisstand faktorisiert werden kann, wenn d kleiner ist als N0,292.
Ziel der Forschung ist es, diese Einschränkung zu verringern, so dass die Faktorisierung auch klappt, wenn delta größer als 0,290 ist und damit der geheime Schlüssel auch größer sein kann.

In [BD00] zeigten Boneh und Durfee erstmals Angriffe auf geheime Exponenten d > N¼ mittels Gitterbasenreduktion. Sie konnten die Anwendbarkeit ihres Verfahrens bis zu einer Größe von N0,292 nachweisen. Dabei zeigten sie zunächst die Gültigkeit für d < N0,284 und verbessern anschließend diese Grenze durch Modifikation der Gitterbasis.
In dieser Anwendung wird das Verfahren von Blömer und May [BM01, May03] verwendet, welches auf dem von Boneh und Durfee basiert. Allerdings wird dabei eine andere Strategie zur Modifikation der Gitterbasis verwendet. Dadurch wird die Grenze für d zwar lediglich auf N0,290 erweitert, aber durch die kleinere zu reduzierende Basis können praktisch höhere Werte erreicht werden.

Quellen:

[BD00]
Boneh, Dan; Durfee, Glenn: Cryptanalysis of RSA with private key d less than N0.292. In: IEEE Transactions on Information Theory Bd. 46, 2000. – ISSN 0018–9448, S. 1339–1349
[BM01]
Blömer, Johannes; May, Alexander: Low Secret Exponent RSA Revisited. In: Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Bd. 2146, Springer Verlag, 2001, S. 4–19
[May03]
May, Alexander: New RSA Vulnerabilities Using Lattice Reduction Methods, Universität Paderborn, Diss., 2003