The RSA system has been presented many times, following the excellent expository article of Martin Gardner in the August 1977 issue of Scientific American. There is no need for yet another explanation of the system; the essentials are contained in the Wikipedia article RSA (cryptosystem), and in many other articles.
The purpose of this note is to give an example of the method using numbers so small that the computations can easily be carried through by mental arithmetic or with a simple calculator.
The RSA encryption system is the earliest implementation of public key cryptography. It has played a crucial role in computer security since its publication in 1978. The essential idea is simple: a message, represented by a number (for plaintext), is encrypted by raising to a high power ( for encryption) and taking the remainder modulo a large number :
The resulting number, , is the ciphertext.
The inverse process of decryption is achieved by raising the number to another number and again taking the remainder modulo :
The indices and are chosen in such a way that corresponds to the plaintext of the original message. The effect of the two operations is to reproduce the original number:
The pair of numbers comprise the public key. They are openly known. The number is the private key, known only to the recipient of the message.
Example with Small Numbers
Before continuing, let us review the short list of important numbers required to implement the RSA system. The notation is summarised in the Table below.
The number is chosen to be a product of two primes. Normally, the factors are huge, making the task of splitting practically impossible. However, for illustration, we choose two small primes, and so that . The quantity is Euler’s totient function, given by .
The encryption index must be coprime with , so we choose a small prime value . Now comes a tricky bit: the decryption index must be the multiplicative inverse of modulo :
A small amount of experimentation shows that so is the decryption index.
We are now in possession of the information required to encrypt a message, and also the information required to decrypt it. We can make public but must keep the index private.
Encrypting the message
With this toy example, the message must be broken into very short blocks. For simplicity, we consider a message comprising a single letter. The letters A to Z are represented by numbers from 01 to 26. We consider the message “H” corresponding to the numerical plaintext .
Now the ciphertext is generated:
But is easily computed: . Dividing this by we get a remainder .
Decrypting the message
The receiver is the only person in possession of the decryption key index . He or she now decrypts the message by computing
But . Dividing by , the remainder is , corresponding to the original message “H”.
The original paper of Rivest, Shamir and Adleman gives an excellent account of the RSA system. It is available online. The prescience of the paper is illustrated by the opening sentence: `The era of “electronic mail” may soon be upon us’.
Gardner, Martin, 1977: A new kind of cipher that would take millions of years to break. Mathematical Games, Scientific American, 237(2), 120-124.
R.L. Rivest, A. Shamir, and L. Adleman, 1978: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Comm. ACM, 21(2), 120-126.
Wikipedia article: RSA (cryptosystem). http://www.wikipedia.org/