Attacks on the RSA Cryptosystem
Here is a description of my term paper, for the Foundations of Cryptography course (floated as Special Topics in Theoretical Computer Science).
Contents:
Introduction
Elementary Attacks
- Common Modulus Attack
- Low Private Exponent:
- Weiner's Attack
- Continued Fractions
- Avoiding the Attack
- Smart Cards:
- Timing Attacks
- Power Cryptanalysis
Factoring Algorithms
- Quadratic Sieve
- Number Field Sieve
TWINKLE: Breaking 512-bit RSA
- Quadratic Sieve on conventional computers
- The design of TWINKLE
- Conclusion
Time taken by Number Field Sieve
The graph below shows how the time taken by the number field sieve to factorize a number increases with the number of bits of the number. It is assumed that factorization of a 450 bit number (the record before TWINKLE) takes one unit of time.
Presentation
Here are the PowerPoint 95 slides of my presentation to the class. As part of our colloquium course, I gave a talk on TWINKLE, Shamir's optical computing device used to crack 512-bit RSA. Here is Shamir's paper.
References:
-
20 Years of Attack on the RSA Cryptosystem
Dan Boneh, Notices of the AMS (Feb. 1999)
-
A Tale of Two Sieves
Carl Pomerance, Notices of the AMS (Dec. 1996)
-
Factoring Large Numbers with the TWINKLE Device
Adi Shamir
-
An Introduction to the Theory of Numbers
G.H. Hardy & E.M. Wright
Vaibhav Vaish
(csu96173@cse.iitd.ernet.in)