Recent Advances in RSA Cryptography

1. Mathematical Background.- 1 1 Divisibility and the residue class ring ?n.- 1.2 Polynomials.- 1.3 Euler’s totient function and ?n*.- 1.4 Polynomial congruences and systems of linear congruences.- 1.5 Quadratic residues.- 2. Computational Complexity.- 2.1 Turing machines.- 2.2 Deterministic and nondeterministic machines.- 2.3 Decision problems and complexity classes.- 2.4 Reductions, completeness and oracle computations.- 2.5 co—NP.- 2.6 Efficient computation and randomized complexity classes.- 3. Public Key Cryptography.- 3.1 Public key cryptography.- 3.2 Permutation polynomials and RSA-type cryptosystems.- 3.3 Efficient implementation of RSA.- 3.4 One-way functions.- 3.5 On the complexity of an attack against RSA.- 4. Factorization Methods.- 4.1 Trial division and Fermat factorization.- 4.2 Monte-carlo factorization.- 4.3 Factor base methods.- 4.4 The continued fraction method.- 4.5 Quadratic sieve.- 4.6 Other Factorization Methods.- 5. Properties of the RSA Cryptosystem.- 5.1 Computing the decryption exponent.- 5.2 Partial decryption.- 5.3 Cycling attacks and superencryption.- 5.4 Incorrect keys.- 5.5 Partial information on RSA and hard-core predicates.- 6. Low-Exponent RSA.- 6.1 Wiener’s attack.- 6.2 Lattice basis reduction.- 6.3 The attack of Boneh and Durfee.- 6.4 Low public exponents.- 6.5 Polynomially related messages.- 6.6 Partial key exposure.- 7. Protocol and Implementation Attacks.- 7.1 Simple protocol attacks against RSA.- 7.2 Håstad’s broadcast attack.- 7.3 Effective security of small RSA messages.- 7.4 Optimal Asymmetric Encryption.- 7.5 Faulty encryption.- 7.6 Timing attacks.- 8. RSA Signatures.- 8.1 Attacks on RSA signatures with redundancy.- 8.2 Security of hash-and-sign signatures.- 8.3 Provably secure RSA signatures.- 8.4 Undeniablesignatures.- 8.5 Threshold signatures.- References.