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