Public Key Encryption

Galen Grimes (gag5@psu.edu)

4 May 2000

In 1976 three MIT researchers — Ron Rivest, Ad Shamir, and Len Adleman (hence RSA encryption) — developed a public key encryption system. 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 = Me 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

8161151021212152611310161520

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

2. Encrypt this message using the RSA encryption system with p = 43 and q = 59, so that n = 43 * 59 = 2537, and with e = 13

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

3. You might also find it easier if you group the above integer into blocks of four, so that

8161151021212152611310161520

becomes

8161 1510 2121 2152 6113 1016 1520

4. We encrypt each block of four using

C = Me mod 2537

The first block of four would be encrypted

C = 816113 mod 2537

Homework

1. Encrypt the remaining blocks of the message.

2. Research in your book or on the Internet how to decrypt RSA encryption and test whether your encryption works.