Gitterangriffe auf RSA (DFG Schwerpunktprogramm 1079)

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.

• 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.

• 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 = d₁/d₂ für kleine d₁, d₂ 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.

• Johannes Blömer, Alexander May
  A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
  In: Advances in Cryptology (Eurocrypt '05), 2005, [DOI], [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 '05), 2005, [DOI]
• Johannes Blömer, Alexander May
  A Generalized Wiener Attack on RSA
  In: Practice and Theory in Public Key Cryptography (PKC '04), 2004, [DOI], [Download]
• Alexander May
  Secret Exponent Attacks on RSA-type Schemes with Moduli N=p^rq
  In: Practice and Theory in Public Key Cryptography (PKC '04), 2004, [DOI]
• Alexander May
  Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring
  In: Advances in Cryptology (Crypto 2004), 2004, [DOI]
• Johannes Blömer, Alexander May
  New Partial Key Exposure Attacks on RSA
  In: Advances in Cryptology (Crypto '03), 2003, [DOI]
• Alexander May
  New RSA Vulnerabilities Using Lattice Reduction Methods
  PhD Thesis, Paderborn University, 2003, [Download]
• Alexander May
  Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
  In: Advances in Cryptology (Crypto '02), 2002, [DOI]
• Johannes Blömer, Alexander May
  Low Secret Exponent RSA Revisited
  In: Cryptography and Lattice Conference (CaLC '01), 2001, [DOI]