- Home
- Documents
*RSA CRYPTOSYSTEM: AN ANALYSIS AND PYTHONSIMULATOR Ciscily Spring 2017.pdf¢ the entire RSA...*

prev

next

out of 41

View

0Download

0

Embed Size (px)

RSA CRYPTOSYSTEM: AN ANALYSIS AND PYTHON SIMULATOR

by

Cescily Nicole Metzgar

Honors Thesis

Appalachian State University

Submitted to the Department of Mathematical Sciences

and The Honors College

in partial fulfillment of the requirements for the degree of

Bachelor of Science

May, 2017

Approved by:

Rick Klima, Ph.D., Thesis Director

Dee Parks, Ph.D., Second Reader

Vicky Klima, Ph.D., Honors Director, Department of Mathematical Sciences

Ted Zerucha, Ph.D., Interim Director, The Honors College

Abstract

This project involves an exploration of the RSA cryptosystem and the mathematical con-

cepts embedded within it. The first goal is to explain what the cryptosystem consists of,

and why it works. Additional goals include detailing some techniques for primality test-

ing, discussing integer factorization, modular exponentiation, and digital signatures, and

explaining the importance of these topics to the security and efficiency of the RSA cryp-

tosystem. The final goal is to implement all of these components into a full simulation of

the entire RSA cryptosystem using the Python programming language.

Contents

1 Background 1

2 How RSA Works 1

3 Why RSA Works 10

4 Why RSA is Public-Key 11

5 Primality Testing 13

6 Integer Factorization 17

7 Modular Exponentiation 21

8 Digital Signatures 23

9 Python Simulator Description 26

10 Python Simulator Code 30

References 38

1 Background

The RSA cryptosystem was created by three MIT professors, Ron Rivest, Adi Shamir, and Len

Adleman and published in an article named A Method for Obtaining Digital Signatures and

Public-Key Cryptosystems in 1978. While the cryptosystem is named for this trio of mathe-

maticians, it is less widely known that a man named Clifford Cocks had actually discovered

the algorithm first while working in a classified environment for the British cryptologic agency

GCHQ. Clifford Cock’s discovery of the RSA algorithm was revealed more than two decades

after the publication by Rivest, Shamir and Adleman [Klima, Sigmon].

RSA was the world’s first public-key cryptosystem, which is part of why the algorithm is so

well-known and popular. Being a public-key cryptosystem stems from being asymmetric. This

means that the encryption key is made public knowledge and does not in any way give clues

to an outsider or even the person sending the message about how to obtain the decryption key.

In a more formalized assertion, a public key cryptosystem is a system in which the encryption

function f can be public knowledge without revealing f−1. This inability to determine f−1

from the encryption function f comes from the practical difficulty of factoring large primes

[Klima, Sigmon]. This factorization problem allows RSA to be an extremely secure cryptosys-

tem. Because of its security it is most widely used today to provide privacy and ensure the

authenticity of digital data. RSA is implemented by web servers and browsers to secure web

traffic, it is used to ensure privacy and authenticity of email, and it is frequently used in elec-

tronic credit card payment systems. These are all applications in which security of digital data

is of extreme importance, which exemplifies the high level of security RSA can provide. While

RSA is extremely secure, the mathematics that underlie the system are fairly simple as will be

shown.

2 How RSA Works

It is important to note that RSA depends on the numerical conversion of a message. To do

this, one can map the letters of the alphabet to a corresponding element in the ring Z26. This

mapping can be outlined as follows: A 7→ 0, B 7→ 1, C 7→ 2, . . . , Z 7→ 25 [Klima, Sigmon].

The only setback to this method is that only capital letters can be used in creating messages to

1

send. To improve upon this method, ASCII representations of letters, symbols and spaces can

be used. With ASCII, lower and upper case letters have different numerical representations, so

messages converted using ASCII are able to use upper and lower case letters as well as spaces

and symbols. All of these elements within a message are preserved throughout the encryption

and decryption process. In the Python program included as part of this thesis, this is the

method used to convert strings of text to their numerical representations. Any way you do

it, you must convert the string of characters that make up your messages into a numerical

equivalent. We let this numerical message be x. To get started with the RSA encryption

algorithm, we must first choose two distinct prime numbers p and q. We then must determine

n = pq as well as m = (p−1)(q−1). Next we would need to determine an encryption exponent

a ∈ Z∗m which satisfies gcd(a,m) = 1. A decryption exponent b ∈ Z∗m will also need to be found

that satisfies ab = 1 mod m. We cannot choose any number as our a because in order for RSA

to work, a must be relatively prime to m. This in turn allows us to be able to find a value of

b that when multiplied by a yields the value 1 mod m. These two conditions on a and b are

extremely important. When met, they force the following equation to be true: xab = x mod n.

This equation shows that once we raise a plaintext message to the encryption exponent, we

can raise the resulting ciphertext to the decryption exponent then reduce mod n and the same

plaintext message x will be the end result [Klima, Sigmon].

Finding an encryption exponent a that is relatively prime to a chosen m is fairly straightfor-

ward. Once an a is found, finding the decryption exponent b requires the use of the Euclidean

algorithm. The Euclidean algorithm can also be used to confirm that your choice of a is indeed

relatively prime to m as well. So, knowing the Euclidean algorithm and how to implement it is

fairly important when looking for parameters that will allow the RSA algorithm to work.

Suppose you want to receive RSA encrypted messages, so you must first generate the keys.

For the sake of this first example very small numbers will be used to show how the Euclidean

algorithm works to help choose the encryption and decryption exponents. Suppose you select

primes p = 47 and q = 61. This would give n = pq = 47 · 61 = 2867. You must then calculate

m = (p−1)(q−1), which is (47−1) ·(61−1), or 46 ·60 = 2760. Now you would need to establish

an a such that a and 2760 have no common divisors greater than 1. Suppose you choose a = 67.

Now you can use the Euclidean algorithm to prove that this choice of a is actually relatively

2

prime to m as follows. Begin by dividing m by a, while noting the quotient and remainder.

This process will then be repeated, each time using the divisor from the previous step and then

dividing that by the remainder from the previous step. The last nonzero remainder in this

process is the gcd of a and m:

2760 = 67(41) + 13

67 = 13(5) + 2

13 = 2(6) + 1

2 = 1(2) + 0.

Because the last nonzero remainder is 1, the gcd of 67 and 2760 is 1, and so the two numbers are

relatively prime, which justifies the choice of a. Now we can find a valid decryption exponent.

We are looking for a value of b that satisfies ab = 1 mod m. In other words we need a value of b

such that 67b = 1 mod 2760. The Euclidean algorithm equations used to validate our choice of

a can also be used to find b as well. The Euclidean algorithm equations can be rewritten in a

way that allows us to work backwards to find the multiplicative inverse of our a mod m. This

can be done as follows:

1 = 13− 2(6)

= 13− (67− 13(5))(6)

= −67(6) + 13(31)

= −67(6) + (2760− 67(41))(31)

= 2760(31) + 67(−1277).

The last line gives 2760(31)+67(−1277) = 1, which can be reduced mod 2760, giving the result

67(−1277) = 1 mod 2760. This tells us that −1277 is a multiplicative inverse of 67 mod 2760.

However, we do not want to use a negative number for b, but since we are working mod 2760,

we can see that −1277 mod 2760 = 1483. This means that 1483 can work as our decryption

exponent b. Now that we have determined valid encryption and decryption exponents, we have

3

obtained all the information we need to make the encryption exponent and modulus n public

and begin receiving encrypted messages that only our decryption exponent b can decrypt. We

can now do some examples using RSA with our parameters n = 2867, encryption exponent

a = 67, and decryption exponent b = 1483.

Example 1: Encryption

Suppose someone wants to send us a message, specifically the message URGENT: Meet at dusk!.

First, the sender must convert their message into its numerical equivalent. This can be done

using the ASCII correspondences shown in Table 1. Using this method, the message URGENT:

Meet at dusk! converts into the following string of numbers:

085082071069078084058032077101101116032097116032100117115107033.

At this point, the sender will use the encryption calculation to encrypt the messa