Cryptology III.2 Cryptanalysis of RSA

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The prime number theorem [PDF]
2. Computing the key and factoring [PDF]
3. The probability of flops [PDF]
4. Factoring algorithms (overview) [PDF]
5. Iteration attack [PDF]
6. Breaking single ciphertexts [PDF]
7. Re-use of a module [PDF]
8. Small exponents [PDF]
9. The signature trap [PDF]
10. More attacks (overview) [PDF]

Overview

»Cryptanalysis of RSA« doesn't break the cipher—except in a few exceptional situations—but traces out the framework for applying it in a secure way according to our best judgment. In particular it helps avoiding some traps.

We want answers to the questions:

• Do there exist sufficiently many keys to evade an exhaustion attack?
• Which mathematical results might lead to breaking an RSA ciphertext? Or to a computation of the private key?
• How to choose the parameters in order to avoid weaknesses?

A summary of the results is

There is a good overview in:

• D. Boneh: Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society 46 (1999), 203-213.
  Online unter http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html.