Cryptanalysis of Small-Valued Secret Exponents in RSA Cryptosystems Público
Oh, Richard (2010)
Published
Abstract
A vulnerability of the RSA encryption system that uses
small-valued secret
exponents is written here. When small-valued secret exponents are
used, the
encryption system is exposed to an attack via a continued fractions
algorithm.
The original algorithm was discovered by Michael J. Weiner. The
algorithm
is able to use public key information to find the private key
information. The
attack is valuable since it is able to discover the factors of the
modulus and the
secret exponent in polynomial time. This paper expands the analysis
of Wiener's
original paper and implements the algorithm through Python
programming.
Table of Contents
1. Introduction..........................................................................................1
2. Continued Fractions Background..............................................................2
3. Continued Fractions Algorithm................................................................11
4. RSA Encryption System Background........................................................22
5. Continued Fractions Algorithm Applied to RSA...........................................24
6. Polynomial Time...................................................................................27
7. Appendix.............................................................................................30
7.1 Examples...........................................................................................30
Table 1: Example......................................................................................31
7.2 Appendix A.........................................................................................31
7.3 Appendix B.........................................................................................34
7.4 Appendix C.........................................................................................38
7.5 Appendix D.........................................................................................47
Table 2: Time Chart for Algorithm Completion...............................................47
Figure 1: Length of Primes vs. Average Time of Completion in Seconds............48
About this Honors Thesis
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palavra-chave | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
Cryptanalysis of Small-Valued Secret Exponents in RSA Cryptosystems () | 2018-08-28 11:54:50 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|