§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 and of about 400 decimal digits each. Procedures for finding such primes require very little computer time. The primes are kept secret but their product , 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 . But to decode, both factors and 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 , , , , and divide the message into pieces of convenient length smaller than the public value . Choose a prime that does not divide either or . Like , the prime is made public. To code a piece , raise to the power and reduce modulo to obtain an integer (the coded form of ) between 1 and . Thus, and .

To decode, we must recover from . To do this, let denote the reciprocal of modulo , so that for some integer . (Here is Euler’s totient (§27.2).) By the Euler–Fermat theorem (27.2.8), ; hence . But , so is the same as modulo . In other words, to recover from we simply raise to the power and reduce modulo . If and are known, and can be determined (mod ) by straightforward calculations that require only a few minutes of machine time. But if and are not known, the problem of recovering from 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).