Public Key Encryption

Galen Grimes (gag5@psu.edu)

4 May 2000

In 1976 three MIT researchers — Ron ** R**ivest, Ad

*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

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 = M^{e} mod 2537

The first block of four would be encrypted

*C = 8161 ^{13} 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.