About the Project
27 Functions of Number TheoryApplications

§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, , 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 p1 or q1. Like n, the prime r is made public. To code a piece x, raise x to the power r and reduce xr modulo n to obtain an integer y (the coded form of x) between 1 and n. Thus, yxr(modn) and 1y<n.

To decode, we must recover x from y. To do this, let s denote the reciprocal of r modulo ϕ(n), so that rs=1+tϕ(n) for some integer t. (Here ϕ(n) is Euler’s totient (§27.2).) By the Euler–Fermat theorem (27.2.8), xϕ(n)1(modn); hence xtϕ(n)1(modn). But ysxrsx1+tϕ(n)x(modn), so ys 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 ys 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).