-1
$\begingroup$

$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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Lee
    Commented May 12 at 1:24
  • $\begingroup$ @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. $\endgroup$
    – Maarten Bodewes
    Commented May 12 at 14:41
  • $\begingroup$ The appropriate way to check a tentative $d$ is to try if $a^{ed-1}\bmod n=1$ for $a\in\{2,3,5\}$. $\endgroup$
    – fgrieu
    Commented May 12 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.