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 .%Boneh らは，RSA 暗号において，d＜N~(0.292)の時に，解読が可能であることを証明している．彼らの証明は複雑であり，他の同種の問題の証明へ適用することは困難である．本稿では，まず，d＜N~(0.292)のときに多項式時間で素因数分解ができることの簡単な証明を与える．ついで，同種の問題に対しても，容易に適用可能な証明技法を与える．例えば Itoh らにより与えられている，Takngi's wiant of RSA に対するsmall secret attack に対する証明も容易に導くことができる．