Git­ter­an­grif­fe auf RSA (DFG Schwer­punkt­pro­gramm 1079)

Bild vergrößern

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.

Be­kann­te An­grif­fe 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.

Un­se­re Er­geb­nis­se

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

Pu­bli­ka­ti­o­nen

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