1st Edition

Cryptanalysis of RSA and Its Variants

By M. Jason Hinek Copyright 2009
    286 Pages 19 B/W Illustrations
    by Chapman & Hall

    Thirty years after RSA was first publicized, it remains an active research area. Although several good surveys exist, they are either slightly outdated or only focus on one type of attack. Offering an updated look at this field, Cryptanalysis of RSA and Its Variants presents the best known mathematical attacks on RSA and its main variants, including CRT-RSA, multi-prime RSA, and multi-power RSA.

    Divided into three parts, the book first introduces RSA and reviews the mathematical background needed for the majority of attacks described in the remainder of the text. It then brings together all of the most popular mathematical attacks on RSA and its variants. For each attack presented, the author includes a mathematical proof if possible or a mathematical justification for attacks that rely on assumptions. For the attacks that cannot be proven, he gives experimental evidence to illustrate their practical effectiveness.

    Focusing on mathematical attacks that exploit the structure of RSA and specific parameter choices, this book provides an up-to-date collection of the most well-known attacks, along with details of the attacks. It facilitates an understanding of the cryptanalysis of public-key cryptosystems, applications of lattice basis reduction, and the security of RSA and its variants.

    PRELIMINARIES

    The RSA Cryptosystem

    Public-Key Cryptography

    The RSA Cryptosystem

    The Security of RSA

    Efficiency of RSA

    RSA Signature Scheme

    Variants of RSA

    Some Notation, Mathematics, and Techniques

    Some Notation

    Some Mathematics Results

    Integer Factorization

    Continued Fractions

    Lattices

    Solving Linear Equations

    Coppersmith’s Methods

    On Attacks and Proofs

    CRYPTANALYSIS OF RSA

    Some Early Attacks

    Common Modulus Attack

    Håstad’s Broadcast Attack

    Cycling Attacks

    Small Public Exponent Attacks

    Stereotyped Message Attack

    Related Message Attacks

    Random Padding Attack

    Leaking Information

    Small Private Exponent Attacks

    Wiener’s Continued Fraction Attack

    Boneh and Durfee’s Lattice Attacks

    Effectiveness of the Attacks

    Partial Key Exposure Attacks

    Factoring with a Hint

    Partially Known Private Exponent: MSBs

    Partially Known Private Exponent: LSBs

    Partially Known Primes

    Key Reconstruction with Random Errors

    More Small Private Exponent Attacks

    Common Modulus Attack

    Common Private Exponent Attack

    CRYPTANALYSIS OF VARIANTS OF RSA

    CRT-RSA

    CRT-RSA

    Small CRT-Exponent Attacks

    Partial Key Exposure Attacks

    Key Reconstruction with Random Errors

    Multi-Prime RSA

    Multi-Prime RSA

    Factoring the Modulus

    Small Private Exponent Attacks

    Partial Key Exposure Attacks

    Common Modulus Attacks

    CRT Attacks

    Multi-Power RSA

    Takagi’s Scheme

    Factoring the Modulus

    Small Private Exponent Attacks

    Partial Key Exposure Attacks

    Common Modulus Attack

    Multi-Exponent RSA

    Common Prime RSA

    Common Prime RSA

    Factoring the Modulus

    Small Private Exponent Attacks

    Small CRT-Exponent Attacks

    Dual RSA

    Dual RSA

    Small Public Exponent

    Small Private Exponent

    Dual CRT-RSA

    Efficiency and Comparison

    Appendix A: Distribution of g = gcd(p – 1, q – 1)

    Appendix B: Geometrically Progressive Matrices

    Appendix C: Some AlgorithmsFurther Reading

    Bibliography

    Index

    Additional Notes appear at the end of each chapter.

    Biography

    M. Jason Hinek is an adjunct research fellow in the iCORE Information Security Lab at the University of Calgary. He earned his Ph.D. in computer science from the University of Waterloo, where his research focused on the security of variants of RSA.

    I enjoyed reading the book because the author is always caring about the different references that he used to write the text. This allows the reader to go further in his understanding of what is presented. … I was pleased by the way the author presented all the different attacks and variant of RSA. I would recommend this book for people who would like to know more about the RSA and more precisely about the difficulties of attacking this cryptosystem with mathematical techniques. … this book can be used as a base for building a complete course on RSAs cryptanalysis.
    —Antoine Rojat, SIGACT News, December 2011

    I can honestly recommend this book. It is written straightforward and is therefore easy to read. Every step is explained and original sources are given, so if you want to look deeper into the background of a certain problem, you can easily do that. … a substantiated overview over the current state of cryptanalysis of RSA. …
    —IACR book reviews, January 2010