# Cryptanalysis of RSA and Its Variants

#### By **M. Jason Hinek**

#### Series Editor: **Douglas R. Stinson**

Chapman and Hall/CRC – 2009 – 272 pages

**Series:** Chapman & Hall/CRC Cryptography and Network Security Series

Chapman and Hall/CRC – 2009 – 272 pages

**Series:** Chapman & Hall/CRC Cryptography and Network Security Series

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.

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

*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.*

**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.

Name: Cryptanalysis of RSA and Its Variants (Hardback) – Chapman and Hall/CRC

Description: By M. Jason HinekSeries Editor: Douglas R. Stinson. 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...

Categories: Intelligent Systems, Cryptology, Combinatorics, Discrete Mathematics