Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

AG Codes and Kryptographie Show image information

AG Codes and Kryptographie

Gitterangriffe auf RSA (DFG Priority Programme 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.

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.

Publications

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

The University for the Information Society