Public Key Cryptography

You might like to try putting the ideas in this article into practice using this Public Key Cryptography Interactivity.

Public Key Cryptography, which is also known as asymmetric cryptography, is a system which uses a pair of keys, one to encode messages (which is a public key) and one to decode messages (the private key).

Before reading this article you might like to investigate these problems:

• Clock Arithmetic which introduces the idea of modular arithmetic
• More Adventures with Modular Arithmetic which develops the ideas in Clock Arithmetic further, and also introduces the idea of solving equations of the form $ax \equiv b \text{ mod }n$
• Euler's Totient Function which introduces $\phi(n)$, which is used later in this article

The set-up

1. Bob wants to receive some information from Alice, but doesn't want Eve to get hold of the information, and Bob suspects that Eve is spying on them and reading their messages
2. Bob sends Alice his public key
3. Alice encodes the information using the public key
4. Bob receives the encoded information and decodes the message using his private key
5. Eve can get hold of both the public key and the encoded message but cannot decode the message without the private key.

(Alice, Bob and Eve are the traditional characters used when describing cryptographic systems)

These sorts of systems are called asymmetric as you cannot decode the message by reversing the process of encoding it. They make use of mathematical one-way functions.They are extensively used by everyone who sends any sort of information over the internet!

One of the oldest Public Key Cryptosystems is RSA, named after Ron Rivest, Adi Shamir and Leonard Adleman, who publicised their system in 1977. The same system was developed secretly in 1973 at GCHQ by Clifford Cocks. In 1997 Cocks' system was declassified.

This particular algorithm uses modular arithmetic to create a one-way function. For example, consider encoding the number $2$ by cubing it.

• In normal arithmetic we get the answer $8$, which we can find the cube root of to get back to the original digit $2$
• In arithmetic modulo $5$ we get the answer $3$. There is no easy way to find cube roots in modulo 5, so we need to try cubing all of the digits $ 0 \to 4$ until we find the one that satisfies $x^3 \equiv 3 \text{ mod }5$, where $x$ is smaller than the modulus

When we are working modulo $5$, it doesn't take very long to test all of the cases and "crack the code", but with "real-life" cryptography the modulus will be hundreds (maybe thousands) of digits long, and so testing every value will be impractical.  

RSA cryptography uses the fact that an equation of the form $ax \equiv b \text{ mod }n$ has a unique solution if $a$ is co-prime* to $n$ (this idea is explored in More Adventures with Modular Arithmetic).

It also makes use of the "Fermat Euler theorem" which states that if $x$ and $n$ are co-prime* then:$$x^{\phi(n)} \equiv 1 \text{ mod }n$$

*Co-prime means that they have no common factors except for 1.

If you haven't met $\phi (n)$ or explored the problem Euler's Totient Function, then this might be a good time to do so!

1. Bob chooses two very large (distinct) prime numbers $p$ and $q$
   Bob (unwisely) uses $p=7$ and $q=11$
    
2. Let $n = pq$ and then $\phi(n) = (p-1)(q-1)$
   So $n=7\times 11 = 77$ and $\phi(n) = 6 \times 10 = 60$
    
3. Bob chooses $e$, where $1<e<\phi(n)$ and $e$ is co-prime with $\phi(n)$ 
   $60$ has factors $2, 3$ and 5, so $e$ cannot have any of these factors.  Bob picks $e=13$, but there are other choices he could have made, e.g. $7, 11, 37, 49$
    
4. Bob now tells everyone what $n$ and $e$ are ($n$ and $e$ are the public key) 
   Bob tells everyone that $n=77$ and $e=13$
    
5. Bob keeps $p$, $q$, $\phi(n)$ secret, as well as another number $d$ which we meet in step 8 (the private key)
    
6. Alice wants to send the message $M$ (a single number) where $M$ and $n$ are coprime and $0< M< n$
   In our example we can only send messages up to $77$.  Alice wants to send the message $15$
    
7. Alice finds $Q$, where $Q \equiv M^e \text{ mod } n$, and sends this encoded message $Q$ to Bob
   Alice finds $15^{13} \text{ mod } 77 = 64$, so $Q=64$
   Use the power mod calculator below to check that this is the case.
    
8. Bob finds $d$ so that $e\times d \equiv 1 \text{ mod } \phi(n)$ i.e. $ed=k \phi(n) + 1$ 
   If $e=13$ then $d=37$ (since $e$ is comprime with $\phi(n)$ there is a unique solution of this equation!  This idea is met in More Adventures with Modular Arithmetic)
    
9. Bob receives the message $Q$ from Alice and decodes it by evaluating $Q^d \text{ mod }n$
   Bob finds $64^{37} \text{ mod }77 = 15$
   Use the power mod calculator below to check that this is the case.

Let's think about why this works.  Alice encoded her message $M$ and sent $Q=M^e$ to Bob.
Bob is evaluating $Q^d \text{ mod }n$ which is equal to $(M^e)^d=M^{ed} \text{ mod }n$.
Bob has found the value $d$ so that $ed=k \phi(n) + 1$. 
This means that we have:

\begin{align}
Q^d &\text{ mod } n \\
=M^{ed} &\text{ mod } n \qquad \text{ since } Q=M^e\\
=M^{k \phi(n) + 1} &\text{ mod } n \qquad \text{since } ed=k \phi(n) + 1\\
=M \times M^{k \phi(n)} &\text{ mod } n \qquad \text{ using the laws of indices}\\
=M \times [M^{\phi(n)}]^k &\text{ mod }n \qquad \text{ using the laws of indices}\\
=M \times 1 &\text{ mod }n  \qquad \text{using the Fermat Euler theorem}\\
=M &\text{ mod }n 
\end{align}

In the following example above, and in the one below, we used small primes so that it is easier to follow. In practice the primes would be very big.


Another example

1. Alice wishes to send the message Cat2009 to Bob.  She uses this prearranged code 
   So the message "Cat2009" becomes "20 50 69 3 1 1 10" 
   This code is mostly based on ASCII, shifted down by $47$.
    
2. Bob chooses $p=13$, $q=17$ which gives $n=221$ and $\phi(n)=12\times 16=192$
    
3. Bob chooses an $e$ so that $e$ and $\phi(n)$ are co-prime.  This means that $e$ cannot have a factor of $2$ or $3$.  Bob chooses $e=35$.
    
4. Bob finds $d$ so that $ed=k\phi(n) + 1$, i.e. $ed=192k+1$.
   The value of $d$ that satisfies this is $d=11$ which gives $ed=35 \times 11=385 \equiv 1 \text{ mod }192$.
   The way I did this quickly was to set up a spreadsheet, first column values $1, 2, 3, ...$; second column was $35 \times A1$ etc; and the third column was $(B1 - 1)/192$.  I could then copy down and find the value in the third column which was an integer.
    
5. Bob tells Alice that $n=221$ and $e=35$.
    
6. Alice encodes the message, so C$=20$ becomes $20^{35} \text{ mod }221 = 197$.
   The entire message becomes 197 84 205 61 1 1 82
    
7. Bob decodes the message using $d=11$.  $197$ becomes $197^{11} \text{ mod } 221 = 20$ etc.

To save you scrolling back up, here is the power mod calculator again.

Use the power mod calculator with $d=11$ and $n=221$ to decode 197 84 205 61 1 1 82 to check that you get the original message 20 50 69 3 1 1 10 = Cat2009.

Use the power mod calculator to encode the phrase "Hello" using the values $n=77$ and $e=13$.

Use the power mod calculator to decode the message 62 69 29 4 54 19 using the values $d=37$ and $n=77$.

You might like to try putting the ideas in this article into practice using this Public Key Cryptography Interactivity.

Disclaimer - Encoding letter by letter (as we have done in this article) is a bad idea as the code could then be broken by the use of frequency analysis.  In real life a whole string of characters (i.e. the message) is converted into a long string of numbers without commas and gaps (possibly using ASCII), and then this long number is encoded in one go using the RSA algorithm.

There are a couple of ways in which this code can be "cracked" and how Eve could find the messages. 

One way that Eve could break the code is by factorising $n$ and then finding $\phi(n)$.  This would mean that she could then find the $d$ that solves $ed \equiv 1 \text{ mod }n$.

Alternatively Eve could take all of the values of $ 0<x<n-1$ and evaluate $x^e \text{ mod }n$ and see which matches the code.

The security of the system is based on using very large primes, which make both methods of breaking the code impractical.  Computers can find the product of 2 very large primes quickly, but factorising into the product of two primes is much more difficult. As computers have got faster over the years the size of the primes used in RSA cryptosystems has had to increase. There are some concerns about what the advent of quantum computing might mean for public key cryptosystems.

Using an asymmetric cryptographic system needs quite a lot of computing power, and often it is used as part of a Hybrid Cryptosystem where an asymmetric cryptosystem is used to encode a key for a symmetric cryptosystem, which is used to encode the body of the message. 

Further Reading:

Plus article "Safety in Numbers"

Simon Singh "The Code Book"

Chalkdust article "Clifford Cocks"

We are very grateful to the Heilbronn Institute for Mathematical Research for their generous support for the development of this resource.