Simplified Proof for Small Secret Key Attack on RSA and its Extension

摘要

For RSA, Boneh and Durfee proved that if d < N~(0.292), N can be factored in polynomial time. Their proof is rather complicated and limited to small secret key attack. So, it is difficult to apply their proof to other similar problems. First, we give a simplified proof for small secret key attack on RSA. Second, we extend the proof technique to more general problems. As a result, we can easily obtain the proof of small secret key attack on Takagi's variant of RSA.