§27.16 Cryptography

Applications to cryptography rely on the disparity in computer time required to find large primes and to factor large integers.

For example, a code maker chooses two large primes $p$ and $q$ of about 400 decimal digits each. Procedures for finding such primes require very little computer time. The primes are kept secret but their product $n=pq$, an 800-digit number, is made public. For this reason, these are often called public key codes. Messages are coded by a method (described below) that requires only the knowledge of $n$. But to decode, both factors $p$ and $q$ must be known. With the most efficient computer techniques devised to date (2010), factoring an 800-digit number may require billions of years on a single computer. For this reason, the codes are considered unbreakable, at least with the current state of knowledge on factoring large numbers.

To code a message by this method, we replace each letter by two digits, say $A=01$, $B=02$, $\mathrm{\dots }$, $Z=26$, and divide the message into pieces of convenient length smaller than the public value $n=pq$. Choose a prime $r$ that does not divide either $p-1$ or $q-1$. Like $n$, the prime $r$ is made public. To code a piece $x$, raise $x$ to the power $r$ and reduce $x^r$ modulo $n$ to obtain an integer $y$ (the coded form of $x$) between $1$ and $n$. Thus, $y\equiv x^r(modn)$ and .

To decode, we must recover $x$ from $y$. To do this, let $s$ denote the reciprocal of $r$ modulo $\varphi \left(n\right)$, so that $rs=1+t\varphi \left(n\right)$ for some integer $t$. (Here $\varphi \left(n\right)$ is Euler’s totient (§27.2).) By the Euler–Fermat theorem (27.2.8), $x^{\varphi \left(n\right)}\equiv 1(modn)$; hence $x^{t\varphi \left(n\right)}\equiv 1(modn)$. But $y^s\equiv x^{rs}\equiv x^{1+t\varphi \left(n\right)}\equiv x(modn)$, so $y^s$ is the same as $x$ modulo $n$. In other words, to recover $x$ from $y$ we simply raise $y$ to the power $s$ and reduce modulo $n$. If $p$ and $q$ are known, $s$ and $y^s$ can be determined (mod $n$) by straightforward calculations that require only a few minutes of machine time. But if $p$ and $q$ are not known, the problem of recovering $x$ from $y$ seems insurmountable.

For further information see Apostol and Niven (1994, p. 24), and for other applications to cryptography see Menezes et al. (1997) and Schroeder (2006).