Faktorisieren mit teilweise bekanntem p (Menü Einzelverfahren \ RSA-Kryptosystem \ Gitterbasierte Angriffe auf RSA)

Sie können den Angriff über den Dialog Faktorisierung bei teilweise bekanntem p ausführen.

Mit dem Angriff "Faktorisierung bei teilweise bekanntem p" ist es möglich, einen RSA-Modulus N zu faktorisieren, wenn ein Teil eines der beiden Faktoren p oder q bekannt ist.

Dazu wird dieses Problem in eine Nullstellensuche umgeformt und mit dem Verfahren der Gitterreduktion gelöst.

Wir nehmen im folgenden ohne Beschränkung der Allgemeinheit an, dass ein Teil von p bekannt ist. Wir nennen P die Zahl, die p in den niederwertigsten Bits entspricht. Für die höchstwertigen Bits ist das Verfahren sehr ähnlich. Voraussetzung für den Angriff ist, dass der bekannte Teil P groß genug ist. Das Polynom

f(x) = (P + x) mod p
hat in x0= p-P eine Nullstelle, die mit dem Verfahren der Gitterreduktion gefunden werden kann.

Wenn N eine Zahl mit n Bit Länge ist, dann werden mindestens (n/4)+1 Bit von p benötigt, um den Angriff erfolgreich durchzuführen.

Dan Boneh, Glenn Durfee und Nick Howgrave-Graham stellten in [BDHG99] unter anderem dieses Verfahren vor. In [Dur02] wird neben dem hier geschilderten auch die Faktorisierung bei bekannten höchstwertigen Bits gezeigt.

Quellen:

[BDHG99]
Boneh, Dan; Durfee, Glenn; Howgrave-Graham, Nick: Factoring N = pr q for Large r. In: Advances in Cryptology - Crypto’99, Lecture Notes in Computer Science Bd. 1666, Springer Verlag, 1999, S. 326–337
[Dur02]
Durfee, Glenn: Public Key Cryptanalysis Using Algebraic and Lattice Methods, Stanford University, Diss., 2002