Revised 22/9/00 FER

In 1976 three MIT researchers — Ron Rivest, Ad Shamir, and Len Adleman (hence RSA encryption) — developed a public key encryption system. Their work was one of the first algorithms to be patented, apperently as as a non-mathematical formula (go figure). The system is based on modular exponentiation modulo of the products of 2 large prime numbers. Each person using the system to send a message has an encryption key consisting of a modulus

n = pq,

where p and q are large prime numbers (usually with at least 200 digits each) and an exponent e that is relatively prime to

gcd(e,) = gcd(13,42*58) = 1

Encryption is performed using

C = M^e mod n

Where

M is the original (un-encrypted text)

C is the encrypted message

Here’s how it is done.

1. To encrypt the message GO NITTANY LIONS you first want to convert each letter in the message using the system 1 = space, 2 = A, 3 = B, and so on (see table below) , such that

GO NITTANY LIONS becomes

8 16 1 15 10 21 21 2 15 26 1 13 10 16 15 20

2. Encrypt this message using the RSA encryption system with p = 11 and q = 19, so that phi= 10*18= 180, E= 7, D =?

(NOTE: We are using much smaller prime numbers than you would normally use only to illustrate the RSA system.)

3. We encrypt each character using

The first character would be encrypted

C = 8^7 mod 209 = 46

Homework

1. Encrypt the remaining characters of the message.

2. Research in your book or on the Internet how to decrypt RSA encryption (i.e., find D), and show that your encryption/decryption works.

3. What are some of the things wrong with this algorithm as an encryption algorithm as it currently used here?

Possible resource talk: How to compute A*B mod N effeciently.