englishGitterangriffe auf RSA
Das Problem
Sei (N,e) ein öffentlicher RSA-Schlüssel, wobei N = pq. Der geheime
Schlüssel d erfüllt die Gleichung ed = 1 mod (p-1)(q-1). Ziel ist es, entweder den geheimen
Schlüssel d oder die Faktorisierung p, q für spezielle Parameterwahlen in
Polynomialzeit zu berechnen.
Bekannte Angriffe auf RSA
- Wiener ('90) zeigte, dass d aus dem öffentlichen Schlüssel (N,e) mittels Kettenbruchalgorithmus berechnet werden kann, solange d < N 0.25. Boneh und Durfee ('98) verbesserten diese Schranke auf d < N 0.292 mit Hilfe von Gittern.
- Boneh, Durfee und Frankel (1999) zeigten, dass Teilkenntnisse der Bits von d genügen, um den Rest von d in Polynomialzeit zu berechnen, solange e < N 0.5.
Unsere Ergebnisse
- Das Berechnen des geheimen Schlüssels d ist deterministisch Polynomialzeit-äquivalent zum Faktorisieren von N.
- Eine erweiterte Wiener-Attacke: Man kann geheime Schlüssel auch dann in Polynomialzeit berechnen, wenn sie von der Form d = d1/d2 für kleine d1, d2 sind.
- RSA Moduli der Form N=p rq: Neue Angriffe mit Teilkenntnis der Bits von d oder von d mod (p-1).
- Neue Angriffe auf RSA mit Teilkenntnis der Bits von d oder von d mod (p-1) für große Werte von e.
- RSA mit Chinesischem Restsatz: Wenn die Primfaktoren p und q unbalanciert sind und d mod (p-1) klein genug ist, dann kann die Faktorisierung von N in Polynomialzeit gefunden werden.
- Alternative Gitterbasen für die Boneh-Durfee Attacke: Diese führen zu einem vereinfachten Beweis der Schranke d < N 0.292 und in der Praxis zu verbesserten Angriffen.
Publikationen
Johannes Blömer, Alexander May:
A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
In Advances in Cryptology (Eurocrypt 2005), Lecture Notes in Computer Science, vol. 3494, pp. 251-267, Springer-Verlag, 2005.
[BibTeX] [Download]
Matthias Ernst, Ellen Jochemsz, Alexander May, Benne de Weger:
Partial Key Exposure Attacks on RSA up to Full Size Exponents
In Advances in Cryptology (Eurocrypt 2005), Lecture Notes in Computer Science, vol. 3494, pp. 371-386, Springer-Verlag, 2005.
[BibTeX] [Download]
Alexander May:
Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring
In Advances in Cryptology (Crypto 2004), Lecture Notes in Computer Science, vol. 3152, pp. 213-219, Springer Verlag, 2004.
[BibTeX] [Download]
Alexander May:
Secret Exponent Attacks on RSA-type Schemes with Moduli N=p^rq
In Practice and Theory in Public Key Cryptography (PKC 2004), Lecture Notes in Computer Science, vol. 2947, pp. 218-230, Springer-Verlag, 2004.
[BibTeX] [Download]
Johannes Blömer, Alexander May:
A Generalized Wiener Attack on RSA
In Practice and Theory in Public Key Cryptography (PKC 2004), Lecture Notes in Computer Science, vol. 2947, pp. 1-13, Springer-Verlag, 2004.
[BibTeX] [Download]
Alexander May:
New RSA Vulnerabilities Using Lattice Reduction Methods
PhD thesis, University of Paderborn, 2003.
[BibTeX] [Download]
Johannes Blömer, Alexander May:
New Partial Key Exposure Attacks on RSA
In Advances in Cryptology (Crypto 2003), Lecture Notes in Computer Science, vol. 2729, pp. 27-43, Springer Verlag, 2003.
[BibTeX] [Download]
Alexander May:
Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
In Advances in Cryptology (Crypto 2002), Lecture Notes in Computer Science, vol. 2442, pp. 242-256, Springer Verlag, 2002.
[BibTeX] [Download]
Johannes Blömer, Alexander May:
Low Secret Exponent RSA Revisited
In Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science, vol. 2146, pp. 4-19, Springer-Verlag, 2001.
[BibTeX] [Download]
Gefördert durch:
Teil des DFG Schwerpunktprogramms 1079: "Sicherheit in der Informations- und Kommunikationstechnik"