# rsa special private key attack

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!

• 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$.
– fgrieu
Commented May 15 at 14:35