# RSA small private key attack: the private key is slightly larger than the bound given by Boneh and Durfee

$$N$$ = 0xf4c548636db62ffcc7ac4a0797952bea9a65bd426175af2435f72657e67ec8194667bfa94ce23c6f1e5baf3201867ab41701f6b8768e71009c41a3d5e9e7c109455341d549c7611f9f52851a2f017906aa9ccbedb95d238468e2c8577d30ecc4f158e3811fd5e2a6051443d468e3506bbc39bba710e34a604ac9e85d0feef8b3;

$$e$$ = 0x16f4b438ba14e05afa944f7da9904f8c78ea52e4ca0be7fa2b5f84e22ddd7b0578a3477b19b7bb4a7f825acc45da2dd10e62dbd94a3386b97d92ee817b0c66c1507514a7860b9139bc2ac3a4e0fe304199214da00a4ca82bfcb7b18253e7e6144828e584dac2dfb9a03fabaf2376ce7c269923fbb60fc68325b9f6443e1f896f;

We are also given the information that $$d \in[2^{299},2^{300}]$$. The ratio $$300/1024=0.293$$ is slightly larger than $$0.292$$. So, what can I do to solve the problem?

Although I'm not stating this will suceed, I'd try the Boneh and Durfee attack (open access) and hope for the best. Their statement is that, for $$e\cdot d\equiv1\pmod{\frac{\phi(N)}2}$$ and $$d=N^\delta$$,

the small inverse problem can be solved for $$\delta<1−1/\sqrt2\approx0.292$$

Here $$(1−1/\sqrt2)\log_2N>299.9$$ thus their statement implies the problem can (most likely) be solved for most $$d$$ in the interval $$[2^{299},2^{300}]$$.

Also, this statement does not exclude that the attack succeeds with some fair probability for $$d$$ slightly above the bound.

OTOH it's entirely possible that the expected method to solve this problem is to factor $$N$$ without the help of $$e$$.

• I have tried Boneh and Durfee attack and it indeed have a output, which however is a wrong answer.(The output d is smaller than 2^299, certainly wrong). So how to adjust the attack？
– Lee
Commented May 12 at 1:24
• @Lee Please try and use your original account for commenting. If you cannot access your account then send the CM team a message so they can merge accounts. Do not use a new account & the answer box to comment. Your comment doesn't seem to have enough details to answer the question stated in it. Commented May 12 at 14:41
• The appropriate way to check a tentative $d$ is to try if $a^{ed-1}\bmod n=1$ for $a\in\{2,3,5\}$.
– fgrieu
Commented May 12 at 16:00