In PKCS#1 standard, (p,q,d,dp,dq,qp) is used as a private-key of RSA. Heninger and Shacham showed a method which can reconstruct SK=(p,q,d,dp,dq) from a random δ fraction of their bits. It succeeds with high probability for small e when δ≥0.27. In this paper, we show how to reduce the search range of a certain parameter k, which is a bottleneck of Heninger–Shacham attack. The bigger δ, the better our method is. More precisely, the search range of k is reduced from e to View the MathML source.