Public Key Encryption Demo

In the late 1970s a number of researchers realized that a public-key encryption scheme could be created using certain difficult mathematical problems. For example a few public key systems are based on the knapsack problem (see wikipedia.org/wiki/Knapsack_problem). A number of researchers came up with another scheme, based on the difficulty of factoring large numbers. Once such scheme that became very popular was invented by three mathematicians: Rivest, Shamar, and Adleman (A Method for Obtaining Digital Signatures and Public-key Systems, Comm. of the ACM, Feb. 1970, Vol. 21 no. 2, pp. 120-126).

Over the years RSA became refined to impove the protection offered. Eventually RSA obtained a patent on this method (which has since expired). Today this is the type of public key system used in PGP, GnuPG, SSH, SSL, and TLS (although others are used too).

RSA public key encryption can be understood by using a simple example. However note that in a real RSA system, the numbers used are much larger and need to satisfy other constraints to ensure maximum security.

Example Encryption:

Convert some text into a large number.
Normally the ASCII text file is first compressed and the message is considered one huge number. It is possible to break a long message into blocks and encrypt each block separately. For ASCII text you can encrypt each character individually, however this is useless for real security (it becomes a simple cryptoquote type cypher, where one letter stands for another). Is is also possible (for digital signatures) to compute a message digest of the message and encrypt that number.
```
The ASCII string"ABCD" = 1145258561 (as a 4 byte unsigned integer). 
However to keep the math simpler we will encrypt this as 4 numbers,
Using a=1, B=2, C=3, etc., our message becomes this series of
messages:  1 2 3 4.
```
Generate a pair of keys.
1. Pick a pair of large prime numbers at random (that satisfy various constraints). Here we pick the (poor) prime numbers of p=3 and q=11.
2. Computer the product of these values:
```
 n = p × q = 3 × 11 = 33 
```
  (This is the step that is supposedly hard to reverse!)
3. Compute the value of Euler's totient function of n: φ(n):
```
φ(n) = (p-1) × (q-1) = 2 × 10 = 20
```
4. Pick any number less than and relatively prime to φ(n), in this case any prime number except 2 or 5 will do. This is one of your two keys, say the public or encryption key e. Let's pick e = 7.
5. Finally compute the matching private or decryption key d, as the inverse of e modulus φ(n). In this case the inverse means a number such that e × d mod φ(n) = 1:
```
d = inv of e mod φ(n) = inv(7) mod 20 = 3
```
The two keys are: (7,33) and (3,33). Without factoring n (33) you can't easily compute φ(n), and thus even knowing one key you can't easily compute the other.

Encrypt the messages using one of the keys (the public key):

cyphertext = plaintext^key mod n
           = 1⁷ mod 33 =     1 mod 33 =  1    for 'A'
           = 2⁷ mod 33 =   128 mod 33 = 29    for 'B'
           = 3⁷ mod 33 =  2187 mod 33 =  9    for 'C'
           = 4⁷ mod 33 = 16384 mod 33 = 16    for 'D'

The resulting cyphertext can be converted back to ASCII, say by adding "64" to each number (ASCII for 'A' = 65, 'B' = 66, ...).

Decrypt the messages using the other key (the private key):

plaintext = cyphertext^key mod n
           =  1³ mod 33 =     1 mod 33 = 1    for 'A'
           = 29³ mod 33 = 24389 mod 33 = 2    for 'B'
           =  9³ mod 33 =   729 mod 33 = 3    for 'C'
           = 16³ mod 33 =  4096 mod 33 = 4    for 'D'

A C program that demonstrates this can be found on Yborstudent, in ~wpollock/bin/rsa. You can also view/download rsa.c source code.

Another version of RSA written in bc, "rsa.bc", can also be found on Yborstudent, in ~wpollock/bin/rsa.bc. You can also view/download rsa.bc source code.