Public Key Cryptography

The idea of Public Key Cryptography is to send messages in such a way that only the person who receives them can understand them even if the method of encryption is discovered by 'an enemy' who intercepts the messages. The person who sends the message encodes it; the person who receives the message decodes it (puts it back into a readable form). Public Key Cryptography was discovered (or invented?) by R. Rivest, A. Shamir and L.Adleman about 1970. This method has been widely used to ensure security and secrecy in electronic communication and particularly where financial transactions are involved.

The method depends on the fact that while it is easy to calculate the product of two large prime numbers (particularly with the help of a computer) it is, for all practical purposes, impossible to find the factors of a large number if it has only very large prime factors. This is because all methods of finding such factors would take many many thousands of years by even the fastest modern computers.

In order to understand this article you need to know that two numbers are said to be congruent in modulus arithmetic if their difference is divisible by the modulus. For example 23 is congruent to 2 modulus 7 because the difference between 2 and 23 is divisible by 7. Another way of expressing this is to say $a\equiv b \pmod{m}$ if and only if $a=pm+b$ where $p$ is an integer. Everything else you need to know is explained in the article.

The Basic Idea

• Bob wants to receive a coded message from Alice
• EVERYBODY knows how to write the message in code.
• Bob is the ONLY person who knows how to decode the coded message.

1. Bob chooses two very large (distinct) prime numbers $p$ and $q$;
2. $n = pq$, $\quad m =$ $lcm$ {$p-1$, $q-1$} (lcm is the least common multiple );
3. Bob chooses $r$, where $r > 1$ and $r$ is coprime with $m$ (i.e. $r$ and $m$ have no factors in common);
4. Bob then finds the unique $s$ such that $rs \equiv 1 \pmod{m}$
5. Bob now tells everyone what $n$ and $r$ are, but does NOT say what $p$, $q$ or $s$ are.
6. Alice wants to send the message $M$ (a single number) where $M$ and $n$ are coprime and $0< M< n$.
7. Alice finds $M_c$, where $M_c \equiv M^r \pmod{n}$, and sends the message $M_c$ to Bob.
8. Bob receives the message $M_c$ from Alice and decodes it.

Now Bob knows $p,q,m,n,r,s$, and he uses these to decode the message $M_c$ from Alice so as to find $M$. To do this Bob uses the theorem that $(M_c)^s \equiv M \pmod n$

In the following example we use small numbers so that you can work through it using a calculator. In practice the numbers would be very big.

An example

(1) Alice wishes to send the message $M$ to Bob

(2) Bob chooses $p=17$, $q=23$; so $n=391$, $m=176$, $r=3$ and $s=59$.

(3) Bob then tells Alice that $n=391$ and $r=3$.

(4) Note: It does not matter how many people have this information, they still won't be able to find $s$.

(5) Alice computes $M_c$ and finds that $M_c=180$.

(5) Bob receives the coded message $180$ from Alice

(6) Bob now calculates $M \equiv 180^{59} \pmod {391}$, and finds Alice's secret message $M$. Can you find it?

In order to find Alice's message you may need some help from the following section.

Working with modulus arithmetic

You need to use the following facts:

(1) If $a\equiv b \pmod n$ then $a c\equiv b c \pmod n$

(2) If $a\equiv b \pmod n$ then $a^k\equiv b^k \pmod n$.
The proofs of these results are simple.

(1) If $a\equiv b \pmod n$ then $n$ divides $a-b$ and if $n$ divides $a-b$ then $n$ divides $(a-b)c=a c-b c$ which is the same as saying $a c\equiv b c \pmod n$.

(2) As $a^k-b^k$ always has a factor $a-b$ for all k it follows that if $n$ divides $a-b$ then $n$ divides $a^k-b^k$ so if $a\equiv b \pmod n$ then $a^k\equiv b^k \pmod n$.

In order to find the secret number that Alice sent to Bob as described above you will need to use the same sort of method as in the following example. Suppose you want to find $x$ where ($0\leq x\leq 100$) and $17^{13}\equiv x \pmod {101}$. As $17^{13}$ is too large for most calculators to show exactly we start with $17^6=24137569$ and, first dividing this by 101, we find that $17^6=(238985)(101)+84$ so we now know that $17^6\equiv 84 \pmod{101}.$ The next step is to use this to tackle $17^{13}$. $$\eqalign{ 17^{13}&=(17^6)^2 \times 17 \\ &\equiv 84^2 \times 17 \equiv 119952 \pmod {101} \\ 119952 &=1187\times 101 + 65 \\ &\equiv 65 \pmod{101}.}$$ Hence $x=65$.

Finally we prove the theorem that $(M_c)^s = M^{rs} \equiv M \pmod n$, where $M$ and $n$ are coprime, given that \+(i) $rs\equiv 1 \pmod m$ \\ \+(ii) $m= {\rm lcm}\ [(p-1), (q-1)]$ \\ \+(iii) $n=pq$ \\

Proof

As $M$ and $n$ are coprime we know that $M$ and $p$ are coprime and $M$ and $q$ are coprime. By Fermat's Little Theorem it follows that $$\eqalign{ M^{p-1}&\equiv 1 \pmod p \\ M^{q-1}&\equiv 1 \pmod q }.$$ Also $(p-1)$ and $(q-1)$ divide $m$ so say $m=j(p-1)=k(q-1)$, then $$M^m={(M^{p-1})}^j\equiv 1^j \equiv 1 \pmod p.$$ Similarly $$M^m={(M^{q-1})}^k\equiv 1^k \equiv 1 \pmod q.$$ So both $p$ and $q$ divide $M^m-1$ and, as $n=p q$, it follows that $M^m\equiv 1 \pmod n$. We know that $rs\equiv 1 \pmod m$ so $rs=1+mt$ for some integer $t$. Putting all this together we have $$M^{r s}=(M^1)(M^{m t})\equiv M \pmod{n}.$$

For Further Reading
Singh, Simon (1999) 'The Code Book - The Science of Secrecy from Ancient Egypt to Quantum Cryptography', The Fourth Estate, London ISBN 1 85702 879 1
Flannery, Sarah (2000) 'In Code - A Mathematical Journey' Profile Books, ISBN 1 86197 222 9 This is a unique book, written by a teenager, and highly recommended for all young people interested in mathematics.