Factoring with a Hint (Menu Individual Procedures \ RSA Cryptosystem \ Lattice Based Attacks on RSA)

You can execute the attack using the Factoring with a Hint dialog.

With the Factoring-with-a-Hint attack it is possible to factor a RSA-moduls N , if a part of one of the factors p or q is known.

To do that this problem is transformed into a root finding task, which is solved with the method of lattice reduction.

We assume in the following without loss of generality that a part of p is known. We call P the number that matches p in the least significant bits. For the most significant bits the attack is very similar. The polynomial

f(x) = (P + x) mod p
has a root in x0= p-P which can be found using the lattice reduction.

It is an important condition that the known part P of p is big enough. If N is a number with a length of n bit, at least (n/4)+1 bit of p are needed to mount the attack successfully.

Dan Boneh, Glenn Durfee and Nick Howgrave-Graham presented this attack in [BDHG99]. In [Dur02] Durfee showed how to factor N, knowing the most or the least significant bits.

Sources:

[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, 1999, S. 326–337
[Dur02]
Durfee, Glenn: Public Key Cryptanalysis Using Algebraic and Lattice Methods, Stanford University, Diss., 2002