Until about 1970, cryptography was private key cryptography: a secret of some kind (typically a string of letters and numbers) was used both to encrypt and decrypt a message, and so both the sender and receiver had to know the secret key.

For example, all textual messages can be encoded as a sequence of 0s and 1s (bits), and so can the key. Here is a simple way to encrypt such a message: line up the message and the key, and add the bits modulo 2:

$$\matrix{\hbox{message:}&1100101100011011101010011\cr \hbox{key:}\hskip20pt&1011011100101100100011010\cr \hbox{sum:}\hskip16pt&0111110000110111001001001\cr }$$

The sender transmits the sum; the receiver then adds the sum to the key in the same way, and recovers the message. If the message is longer than the key, the key can be repeated as many times as required, though there are techniques that can be used to break this system. The only provably secure method is to use a key as long as the message, and never to reuse a key.

In public key cryptography, there are two keys. Suppose Alice wishes to receive encrypted messages; she publishes one of the keys, the public key, and anyone, say Bob, can use it to encrypt a message and send it to her. When Alice gets the encrypted message, she uses the private key to decrypt it and read the original message. If Alice needs to reply to Bob, Bob will publish his own public key, and Alice can use it to encrypt her reply.

We will describe one method of public key cryptography, or cryptosystem, called RSA, after Ron Rivest, Adi Shamir and Leonard Adleman.

Alice chooses two prime numbers, $p$ and $q$, and publishes the product $n=pq$ together with an integer $c$ that is relatively prime to both $p-1$ and $q-1$, that is, to $[p-1,q-1]=L$. Alice also computes $[c]^{-1}=[d]$ in $\U_L$.

To send Alice a message, Bob represents his message as a sequence of integers, each smaller than both $p$ and $q$. For each of these numbers $x$, Bob computes $x^c$, and then the remainder of $x^c$ mod $n$, so $x^c = nQ+r$. Bob sends $r$ to Alice.

For each number $r$ that Alice receives, she computes $r^d\bmod{n}$; this is the original $x$. Here's why: Since $[c][d]=[1]$ in $\U_L$, we know that $cd\equiv 1\pmod{L}$, or $cd=1+tL$. Now $r^d\equiv (x^c)^d\pmod{n}$, since $r\equiv x^c\pmod{n}$, and $x^{cd}=x^{1+tL}=x(x^L)^t$. Since $x< p$ and $x< q$, $x$ is relatively prime to $n$, so $[x]\in \U_n$.

Now consider $[x]^L\in\U_n$. From sections 3.7 and 3.8, we know this is matched with $([x]^L,[x]^L)\in \U_p\times\U_q$. Now $$L={(p-1)(q-1)\over (p-1,q-1)}=(p-1)A=(q-1)B,$$ where $A$ and $B$ are integers. Then $$ [x]^L = ([x]^{p-1})^A=([x]^{\phi(p)})^A=[1]^A=[1] $$ in $\U_p$, using Euler's Theorem (3.10.5), and $$ [x]^L = ([x]^{q-1})^B=([x]^{\phi(q)})^B=[1]^B=[1] $$ in $\U_q$. Hence $[x]^L$ is paired with $([1],[1])$ in $\U_p\times\U_q$, and since $[1]$ is also paired with $([1],[1])$, $[x]^L=[1]$ in $\U_n$, that is, $x^L\equiv 1\pmod{n}$.

Now, modulo $n$, $r^d\equiv x(x^L)^t\equiv x$. Since $x< n$, $x$ is the remainder when $r^d$ is divided by $n$, that is, $x=r^d\pmod{n}$, as claimed.

Suppose we use $p=37$, $q=73$, and $c=5$. Then $n=2701$, $d=29$ and $L=[36,72]=72$. Suppose one number in a message is 33. Then Bob computes $33^5\pmod{2701}= 604$ and sends $604$ to Alice. Alice computes $604^{29}\pmod{2701}=33$, the original number in Bob's message. Here's the computation in Sage:

This is a bit tedious if we want to deal with an entire message. By defining a couple of Python functions we can make life easier.
Now we can encrypt a whole string of characters at once:
and decrypt:

It is possible to break this code by factoring the published number $n$. While this is in principle easy, there is no known way to factor very large numbers in a reasonable length of time. In practice each of $p$ and $q$ would be prime numbers with hundreds of digits so that factoring $n=pq$ is not feasible. Also, individual characters are not suitable for encrypting, since then it is possible to attack the code based on the frequency of different characters. Many characters should be grouped together, giving a large number to be encrypted as a block.

Finally, while the necessary operations for encrypting and decrypting can be performed fairly quickly with modern computers, there are good private key cryptosystems that are much faster. Instead of encrypting the entire message with RSA, it can be used to encrypt and exchange a secret key, and this key is then used with another cryptosystem to encrypt the message. This secret key can be generated at random and used only once.

Exercises 3.11

Use this code to turn symbols into integers: A through Z are represented by 1 through 26, a period is 27, a comma is 28, an exclamation point is 29, a space is 30. (This is used in the Sage worksheet, which you may want to use to do the exercises.)

Ex 3.11.1 Use $p=101$, $q=103$, and $c=121$ to encrypt "MEET ME AT NOON.''

Ex 3.11.2 Use the values for $p$, $q$, and $c$ from the previous problem to decrypt this message: [1403, 6884, 8311, 8311, 7466, 438, 1106, 2589, 7466, 4239, 8311, 1457, 5381].