Security Analysis of RSA-type Cryptosystems

PhD. thesis in Cryptography, UCL, October 1997 (118 pages)
Committee: J.-J. Quisquater (Supervisor), F. Borceux, J.-M. Couveignes, and A. Magnus
Jury: P. Sobieski (Chair), F. Borceux, J.-M. Couveignes, A. Magnus, D. Naccache, J.-J. Quisquater, and J. Stern

Abstract. In 1978, Rivest, Shamir and Adleman introduced the public-key cryptosystem RSA. Thereafter, it was extended to Lucas sequences and elliptic curves. This thesis analyses the security of these cryptosystems in given contexts. In particular, all major known attacks against RSA-type systems (including some attacks due to the author) are reviewed. We also see how these attacks can be avoided.

Contents

• Preface
• Mathematical Backdround
  • Baic facts
  • Eisenstein and Gaussian integers
    • The ring Z[w]
    • The ring Z[i]
  • Lucas sequences
    • Definitions and properties
    • Dickson polynomials
  • Elliptic curves
    • Elliptic curves over a field
    • Elliptic curves over a ring
    • Division polynomials
  • Lattice basis reduction
• RSA-type Cryptosystems
  • RSA
  • LUC
  • Elliptic curve systems
    • KMOV
    • Demytko's system
• Security Analysis
  • Polynomial attacks
    • Hastad attack
    • GCD attack
    • Garbage-man-in-the-middle attack
  • Homomorphic attacks
    • Chosen-message attack
    • Garbage-man-in-the-middle attack II
    • Common modulus attack
  • Other attacks
    • Wiener's attack
    • Lenstra's attack
    • (Transient) faults based attack
• Summary and Conclusions

Homepage