RSA CryptographyFermat's little theorem was used by Rivest, Shamir, and Adelman to design a fascinating encryption algorithm, in which you can tell anyone you like how the encryption works, although this knowledge is not sufficient to be able to decrypt; decryption is only possible for the chosen few who have extra information. Let's see how this works on a simple example. Let's assume that the text we want to encrypt is: WHATEVER First we have to translate this text into numbers. To do this, we shall use a hash code, which replaces every character by an integer. (We'll see more examples on the next page.) For the word whatever this gives: 23 8 1 20 5 22 5 18 To encrypt this text, we will replace every number x by another number y, according to a simple rule. The key to this encryption rule is given by two numbers n and r. The number n is chosen in a very particular way: n is the product of two primes p and q. Suppose we choose n = 29 * 37 = 1073. Let's take r = 25. To encrypt x we just compute: To decrypt y we need a decryption key, which takes the form of a number s. In this particular case, with this choice of n and r, the choice s = 121 is an appropriate decryption key. The decryption then works via a simple formula, analogous to the encryption: we compute and this gives us x back again! (We'll come back below to why this happens.)
