This is a level 3 challenge in Mystery Twister. https://mysterytwister.org/media/challenges/add/mtc3-kitrub-04-speciald-paramter.txt https://mysterytwister.org/media/challenges/pdf/mtc3-kitrub-04-speciald-en.pdf

The private key has 400 bits. The 90 lsbs are random but the 310 msbs have a low hamming weight. Besides the topmost bit, only 3 bits are 1. Some comments on the website hint me to use lattice, but I do not know how to relate the information of d with lattice. Actually it is feasible to list all the possible 310 msbs (dm) within minutes, but if I implement some algorithm related to lattice for all the possible dm(i even do not know how to do it), the cost of time will be intolerable. So I think this may not be the proper approach.Anyone help me pls. i will be very grateful!

  • $\begingroup$ Some remarks: Wiener's bound is $\log(d)<0.25\log(N)$, not $d<0.25\log(N)$ as in your ref. It has been improved to $\log(d)<0.292\log(N)$. But here a 400-bit $d$ is way above these bounds. Thus indeed, you must use the special form of $d$. I can't think of a better way than solving the few million problems involving knowledge of $(N,e)$ and all except the 90 low-order bits of $d$. $\endgroup$
    – fgrieu
    Commented May 15 at 14:35


Your Answer

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

Browse other questions tagged or ask your own question.