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