Cryptanalysis of Small-Valued Secret Exponents in RSA Cryptosystems 公开

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	Emory College
Department	Mathematics
Degree	BS
Submission	Honors Thesis
Language	English
Research Field	Mathematics Computer Science
关键词	Cryptosystems Cryptanalysis Small Secret Exponents RSA
Committee Chair / Thesis Advisor	Garibaldi, Skip, Emory University
Committee Members	Brussel, Eric, Emory University Soria, Jose, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Cryptanalysis of Small-Valued Secret Exponents in RSA Cryptosystems ()	2018-08-28 11:54:50 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions