Attack on Small Secret Keys (Menu Individual Procedures \ RSA Cryptosystem \ Lattice Based Attacks on RSA)

You can execute the attack using the Attack on Small Secret Keys dialog.

The attack on short secret keys allows to factor a RSA-Modulus N efficiently, if the public key e is known and the secret key d is selected too small.

For this purpose this task is transformed into a root-finding problem, which is solved with the method of Lattice reduction.
We start with the following equation of the RSA Cryptosystem:

e · d ≡ 1 mod Φ(N)
There exists a k for which
ed + k Φ(N) = 1
holds in Z. Here Φ(N) is (p-1)(q-1) = pq-p-q+1 = N -(p+q)+1.
Combining both equations we get:
e · d + k(N + 1 - (p + q)) = 1
Now setting s := -(p + q) and A := N + 1 and reducing both sides modulo e, we get:
k(A + s) ≡ 1 mod e

This Equation is now solved with the method of Lattice reduction.

The size of d is in the following alway expressed relative to N. We introduce the variable delta so, that the following equation holds:
d=Ndelta
The attack is theoretically mountable for up to 0.292. That means, that N can be factored, if d is less than N0.292. To increase the upper limit on d, allowing to factor N for delta greater than 0.292, is the subject of research.

In [BD00] for the first time Boneh and Durfee show attacks on d > N¼ using Lattice reduction. They were able to prove the usability of their method for d up to N0,292. At first they show an approach for d < N0,284 and improve this result by modifying the lattice base.
In this application the algorithm of Blömer and May[BM01, May03] is used, which is based on the approach of Boneh and Durfee. By using a different strategy of modifying the lattice base the theoretical boundary on d is is slightly worse (d<N0,290). However because of the smaller lattice base practically higher values can be achieved.

Sources:

[BD00]
Boneh, Dan; Durfee, Glenn: Cryptanalysis of RSA with private key d less than N0.292. In: IEEE Transactions on Information Theory Bd. 46, 2000. – ISSN 0018–9448, S. 1339–1349
[BM01]
Blömer, Johannes; May, Alexander: Low Secret Exponent RSA Revisited. In: Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Bd. 2146, Springer, 2001, S. 4–19
[May03]
May, Alexander: New RSA Vulnerabilities Using Lattice Reduction Methods, University of Paderborn, Diss., 2003