Hinek Cryptanalysis of RSA and Its Variants

Erscheinungsjahr 2009
ISBN: 978-1-4200-7519-9
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 272 Seiten

Reihe: 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.

Zielgruppe

Researchers and graduate students in cryptography, computer science, and mathematics; electrical engineers.

Autoren/Hrsg.

Hinek, M. Jason

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein

Inhaltsverzeichnis

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.

Über Autor(innen)

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.