Until about 1970, cryptography wasprivate key cryptography: a secret of some kind (typically astring of letters and numbers) was used both to encrypt and decrypt amessage, and so both the sender and receiver had to know the secretkey.
For example, all textual messages can be encoded as a sequence of 0sand 1s (bits), and so can the key. Here is a simple way to encrypt such amessage: 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 thekey in the same way, and recovers the message. If the message islonger than the key, the key can be repeated as many times asrequired, though there are techniques that can be used to break thissystem. The only provably secure method is to use a key as long as themessage, and never to reuse a key.
In public key cryptography, there are two keys. Suppose Alicewishes to receive encrypted messages; she publishes one of the keys,the public key, and anyone, say Bob, can use it to encrypt a messageand send it to her. When Alice gets the encrypted message, sheuses 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, orcryptosystem, called RSA,after Ron Rivest, Adi Shamir and Leonard Adleman.
Alice chooses two prime numbers, $p$ and $q$, and publishes theproduct $n=pq$ together with an integer $c$ that is relatively prime toboth $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 ofintegers, each smaller than both $p$ and $q$. For each of thesenumbers $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$, weknow 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 relativelyprime to $n$, so $[x]\in \U_n$.
Now consider $[x]^L\in\U_n$. From sections3.7 and3.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 theremainder when $r^d$ is divided by $n$, that is, $x=r^d\pmod{n}$, asclaimed.
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 Bobcomputes $33^5\pmod{2701}= 604$ and sends $604$ to Alice. Alicecomputes $604^{29}\pmod{2701}=33$, the original number in Bob'smessage.Here's the computation in Sage:
This is a bit tedious if we want to deal with an entire message. Bydefining 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 factorvery large numbers in a reasonable length of time. In practice each of$p$ and $q$ would be prime numbers with hundreds of digits so thatfactoring $n=pq$ is not feasible. Also, individual characters are notsuitable for encrypting, since then it is possible to attack the codebased on the frequency of different characters. Many characters shouldbe grouped together, giving a large number to be encrypted as ablock.
Finally, while the necessary operations for encrypting and decryptingcan be performed fairly quickly with modern computers, there are goodprivate key cryptosystems that are much faster. Instead of encryptingthe entire message with RSA, it can be used to encrypt and exchange asecret key, and this key is then used with another cryptosystem toencrypt the message. This secret key can be generated at random andused only once.
Exercises 3.11
Use this code to turn symbols into integers: A through Z arerepresented by 1 through 26, a period is 27, a comma is 28, anexclamation point is 29, a space is 30. (This is used in the Sageworksheet, which you may want to use to do the exercises.)
Ex 3.11.1Use $p=101$, $q=103$, and $c=121$ to encrypt "MEET ME AT NOON.''
Ex 3.11.2Use the values for $p$, $q$, and $c$ from the previousproblem to decrypt this message: [1403, 6884, 8311, 8311, 7466, 438,1106, 2589, 7466, 4239, 8311, 1457, 5381].
