Cryptanalysis of RSA and Its Variants (Hardcover)

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 Hastad’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.