A Toy Example of RSA Encryption

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.

L2R: Ron Rivest, Adi Shamir, Len Adleman (2003). Image from https://www.usc.edu

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.

Introduction

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 ${P}$ (for plaintext), is encrypted by raising ${P}$ to a high power ${e}$ ( ${e}$ for encryption) and taking the remainder modulo a large number ${n}$ :

$\displaystyle C = P^e\ ( \mod n )$

The resulting number, ${C}$ , is the ciphertext.

The inverse process of decryption is achieved by raising the number ${C}$ to another number ${d}$ and again taking the remainder modulo ${n}$ :

$\displaystyle D = C^d\ ( \mod n)$

The indices ${e}$ and ${d}$ are chosen in such a way that ${D = P}$ corresponds to the plaintext of the original message. The effect of the two operations is to reproduce the original number:

$\displaystyle P = (P^e)^d\ ( \mod n )$

The pair of numbers ${(e, n)}$ comprise the public key. They are openly known. The number ${d}$ 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.

Notation for RSA system, and sample values.

The number ${n}$ is chosen to be a product of two primes. Normally, the factors are huge, making the task of splitting ${n}$ practically impossible. However, for illustration, we choose two small primes, ${p=5}$ and ${q=11}$ so that ${n = p\times q = 55}$ . The quantity ${\phi}$ is Euler’s totient function, given by ${\phi = (p-1)(q-1) = 40}$ .

The encryption index ${e}$ must be coprime with ${\phi}$ , so we choose a small prime value ${e=7}$ . Now comes a tricky bit: the decryption index ${d}$ must be the multiplicative inverse of ${e}$ modulo ${\phi}$ :

$\displaystyle e\times d = 1 \ ( \mod \phi )$

A small amount of experimentation shows that ${7\times 23 = 161 = 4\times 40 + 1}$ so ${d=23}$ is the decryption index.

We are now in possession of the information ${(e,n)}$ required to encrypt a message, and also the information ${(d,n)}$ required to decrypt it. We can make ${(e,n)}$ public but must keep the index ${d}$ 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 ${P = 08}$ .

Now the ciphertext is generated:

$\displaystyle C = P^e\ (\mod n ) = 8^7\ (\mod 55 )$

But ${8^7 = 2^{21} = 2^{10}\times2^{10}\times2 = 1024^2\times 2}$ is easily computed: ${8^7=2\,097\,152}$ . Dividing this by ${n=55}$ we get a remainder ${C = 2}$ .

Decrypting the message

The receiver is the only person in possession of the decryption key index ${d = 23}$ . He or she now decrypts the message by computing

$\displaystyle D = C^d\ ( \mod n) = 2^{23}\ ( \mod 55)$

But ${2^{23} = (2^{10})^2 \times2^3 = 1024^2\times 8 = 8\,388\,608}$ . Dividing by ${n=55}$ , the remainder is ${D = 8}$ , corresponding to the original message “H”.

Final Remark

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’.

Sources
${\bullet}$ Gardner, Martin, 1977: A new kind of cipher that would take millions of years to break. Mathematical Games, Scientific American, 237(2), 120-124.

${\bullet}$ 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.

${\bullet}$ Wikipedia article: RSA (cryptosystem). http://www.wikipedia.org/

ThatsMaths