Cryptanalysis of Small-Valued Secret Exponents in RSA Cryptosystems Open Access

Oh, Richard (2010)

Permanent URL: https://etd.library.emory.edu/concern/etds/d217qp81k?locale=en
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

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files