8.1: Cryptography

In this section we discuss some elementary aspects of cryptography, which concerns the coding and decoding of messages. In cryptography, a (word) message is transformed into a sequence $a$ of integers, by replacing each letter in the message by a specific and known set of integers that represent this letter, and thus forming a large integer $a$ by concatenation. Then this integer $a$ is transformed (i.e. coded) into another integer $b$ by using a congruence of the form $b=a^k(mod\ m)$ for some chosen $k$ and $m$, as described below, with $k$ unknown except to the sender and receiver. $b$ is then sent to the receiver who decodes it into $a$ again by using a congruence of the form $a=b^{\bar{k}}(mod\ m)$, where $\bar{k}$ is related to $k$ and is itself only known to the sender and receiver, and then simply transforms the integers in $a$ back to letters and reveals the message again. In this procedure, if a third party intercepts the integer $b$, the chance of transforming this into $a$, even if $m$ and the integers that represent the letters of the alphabet are exactly known, is almost impossible to do (i.e. has a fantastically small probability of being achieved) if $k$ is not known, that practically the transformed message will not be revealed except to the intended receiver.

The basic results on congruences to allow for the above procedure are in the following two lemmata, where $\phi$ in the statements is Euler’s $\phi$-function.

Let $a$ and $m$ be two integers, with $m$ positive and $(a,m)=1$. If $k$ and $\bar{k}$ are positive integers with $k\bar{k}=1(mod\ \phi(m))$, then $a^{k\bar{k}}=a(mod\ m)$.

$k\bar{k}=1(mod\ \phi(m))$ thus $k\bar{k}=q\phi(m)+1$ ($q\geq 0$). Hence $a^{k\bar{k}}=a^{q\phi(m)+1}=a^{q\phi(m)}a$. But by Euler’s Theorem, if $(a,m)=1$ then $a^{\phi(m)}=1(mod\ m)$. This gives that $$(a^{\phi(m)})^qa=1(mod\ m)a=a(mod\ m),$$ and hence that $a^{k\bar{k}}=a(mod\ m)$, and the result follows.

We also need the following.

Let $m$ be a positive integer, and let $r_1, r_2,\cdots, r_n$ be a reduced residue system modulo $m$ (i.e. with $n=\phi(m)$ and $(r_i,m)=1$ for $i=1,\cdots,n$). If $k$ is an integer such that $(k,\phi(m))=1$, then $r_1^k, r_2^k,\cdots, r_n^k$ forms a reduced residue system modulo $m$.

Before giving the proof, one has to note that the above lemma is in fact an if-and-only-if statement, i.e. $(k,\phi(m))=1$ if and only if $r_1^k, r_2^k,\cdots, r_n^k$ forms a reduced residue system modulo $m$. However we only need the if part, as in the lemma.

Assume first that $(k,\phi(m))=1$. We show that $r_1^k, r_2^k,\cdots, r_n^k$ is a reduced residue system modulo $m$. Assume otherwise, i.e. assume that $\exists i,j$ such that $r_i^k=r_j^k(mod\ m)$, in which case $r_i^k$ and $r_j^k$ would belong to the same class and thus $r_1^k, r_2^k,\cdots, r_n^k$ would not form a reduced residue system. Then, since $(k,\phi(m))=1$, $\exists\bar{k}$ with $k\bar{k}=1(mod\ \phi(m))$, and so $$r_i^{k\bar{k}}=r_i(mod\ m)\hspace{0.5cm}and\hspace{0.5cm}r_j^{k\bar{k}}=r_j(mod\ m)$$ by the previous lemma. But if $r_i^k=r_j^k(mod\ m)$ then $(r_i^k)^{\bar{k}}=(r_j^k)^{\bar{k}}(mod\ m)$, and since $r_i^{k\bar{k}}=r_i(mod\ m)$ and $r_j^{k\bar{k}}=r_j(mod\ m)$, then $r_i=r_j(mod\ m)$ giving that $r_i$ and $r_j$ belong to the same class modulo $m$, contradicting that $r_1, r_2,\cdots, r_n$ form a reduced residue system. Thus $r_i\neq r_j$ implies that $r_i^k\neq r_j^k$ if $(k,\phi(m))=1$.

Now to do cryptography, one proceeds as follows. Let $S$ be a sentence given in terms of letters and spaces between the words that is intended to be transformed to a destination with the possibility of being intercepted and revealed by a third party.

1. Transform $S$ into a (large) integer $a$ by replacing each letter and each space between words by a certain representative integer (e.g. three or four digit integers for each letter). $a$ is formed by concatenating the representative integers that are produced.
2. Choose a couple $p_1$ and $p_2$ of very large prime numbers, each (for example) of the order of a hundred digit integer, and these should be strictly kept known only to the sender and receiver. Then form the product $m=p_1p_2$, which is itself a very large number to the point that the chances of someone revealing the prime number factorization $p_1p_2$ of $m$ is incredibly small, even if they know this integer $m$. Now one has, by standard results concerning the $\phi$-function, that $\phi(p_1)=p_1-1$ and $\phi(p_2)=p_2-1$, and that, since $p_1$ and $p_2$ are relatively prime, $\phi(m)=\phi(p_1)\phi(p_2)=(p_1-1)(p_2-1)$. Thus $\phi(m)$ is a very large number, of the order of $m$ itself, and hence $m$ has a reduced residue system that contains a very large number of integers of the order of $m$ itself. Hence almost every integer smaller than $m$, with a probability of the order $1-1/10^{100}$ (almost 1), is in a reduced residue system $r_1, r_2,\cdots, r_{\phi(m)}$ of $m$. Thus almost every positive integer smaller than $m$ is relatively prime with $m$, with probability of the order $1-1/10^{100}$.
3. Now given that almost every positive integer smaller than $m$ is relatively prime with $m$, the integer $a$ itself is almost certainly relatively prime with $m$, and hence is in a reduced residue system for $m$. Hence, by lemma 17 above, if $k$ is a (large) integer such that $(k,\phi(m))=1$, then $a^k$ belongs to a reduced residue system for $m$, and there exists a unique positive $b$ smaller than $m$ with $b=a^k(mod\ m)$.
4. Send $b$ to the destination where $\phi(m)$ and $k$ are known. The destination can determine a $\bar{k}$ such that $k\bar{k}=1(mod\ \phi(m))$, and then finds the unique $c$ such that $c=b^{\bar{k}}(mod\ m)$. Now since, almost certainly, $(a,m)=1$, then almost certainly $c=a$ since $c=b^{\bar{k}}(mod\ m)=(a^k)^{\bar{k}}(mod\ m)=a^{k\bar{k}}(mod\ m)$, and which by lemma 16, is given by $a(mod\ m)$ almost certainly since $(a,m)=1$ almost certainly. Now the destination translates $a$ back to letters and spaces to reveal the sentence $S$. Note that if any third party intercepts $b$, they almost certainly cannot reveal the integer $a$ since the chance of them knowing $\phi(m)=p_1p_2$ is almost zero, even if they know $m$ and $k$. In this case they practically won’t be able to determine a $\bar{k}$ with $k\bar{k}=1(mod\ \phi(m))$, to retrieve $a$ and transform it to $S$.

Contributors and Attributions

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.