Public Key Encryption
Original by Galen Grimes (gag5@psu.edu)
4 May 2000
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
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 = 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
C = M^{e} mod 209
The first character would be encrypted
C = 8^7 mod 209 = 46
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.