Converse Results to the Wiener Attack on RSA

摘要: A well-known attack on RSA with low secret-exponent d was given by Wiener about 15 years ago. showed that using continued fractions, one can efficiently recover the from public key (N,e) as long 0? We answer this question in negative proving a converse to Wiener's result. Our result shows that, for any fixed e > 0 and all sufficiently large modulus lengths, succeeds negligible probability over random choice of 1/4 + e. Thus success bound 1/4. The known attacks class (by Verheul Van Tilborg Dujella) run exponential time, so it is natural ask whether there exists an subexponential run-time. second answers also negative.