RSA book

In the mid 1990's, a series of letter bomb attacks, motivated by racist reasons, struck Austria. The recipients of these bombs were people engaged in multi-cultural activities or who were known as supporters of refugee organizations. Several people were injured seriously. Some months later the perpetrator sent a letter of confession to the Austrian authorities, encrypted in the RSA system using the RSA modulus



The author(s) believed that the factorization of this number would require tremendous efforts, even on a modern supercomputer, and (perhaps) speculated that their letter would be safe for a long period of time. In a cynical statement they mentioned that supercomputers were built for solving this academic, simple-looking ``Highschool''-like problem. However, this number can be factored immediately by using Fermat's factoring method. Consequently, the letter of confession could be read by the authorities within some weeks. Does this incident allow to draw the conclusion that the RSA system as a whole is insecure? As RSA is perhaps one of the most frequently used public key cryptosystems, this would have enormous consequences. Luckily, the authors of the letter simply chose an instance of the RSA cryptosystem that can be broken easily.

Ever since the RSA cryptosystem was published in 1978 by Rivest, Shamir and Adleman, it has attracted numerous researchers with various backgrounds (number theorists, complexity theorists and computer security experts to name but a few) because of its elegance and practicability. RSA is perhaps today the most well-known public key cryptosystem; accordingly, many theoretical results regarding the security of RSA are known. Many of them are ``bad news'' for a cryptanalyst, stating that breaking RSA is still likely to be intractable; however, some weaknesses have been found recently in special instances of the RSA system.

The book S. Katzenbeisser, Recent Advanves in RSA Cryptography, volume 3 of Advances in Information Security, Kluwer Academic Publishers, 2001 (140 pages, ISBN 0-7923-7438-X) surveys the most important achievements of the last years of research in a unified way.

Homepage of the book at Kluwer
The book can easily be ordered through amazon.com!



Contents of the book:

1. Mathematical background: Divisibility and the residue class ring Zn; Polynomials; Euler's totient function and Zn*; Polynomial congruences and systems of linear congruences; Quadratic residues
2. Computational complexity: Turing machines; Deterministic and nondeterministic machines; Decision problems and complexity classes; Reductions; completeness and oracle computations; co-NP; Efficient computation and randomized complexity classes
3. Public key cryptography: Public key cryptography; Permutation polynomials and RSA-type cryptosystems; Efficient implementation of RSA; One-way functions; On the complexity of an attack against RSA
4. Factorization methods: Trial division and Fermat factorization; Monte-carlo factorization; Factor base methods; The continued fraction method; Quadratic sieve; Other Factorization Methods
5. Properties of the RSA cryptosystem: Computing the decryption exponent; Partial decryption; Cycling attacks and superencryption; Incorrect keys; Partial information on RSA and hard-core predicates
6. Low-exponent RSA: Wiener's attack; Lattice basis reduction; The attack of Boneh and Durfee; Low public exponents; Polynomially related messages; Partial key exposure
7. Protocol and implementation attacks: Simple protocol attacks against RSA; Hastad's broadcast attack; Effective security of small RSA messages; Optimal Asymmetric Encryption; Faulty encryption; Timing attacks
8. RSA Signatures: Attacks on RSA signatures with redundancy; Security of hash-and-sign signatures; Provably secure RSA signatures; Undeniable signatures; Threshold signatures
9. References
10. Index