The Mathematics of RSA

Primes and coprimes

Before we learn how to ‘divide’ in modular arithmetic, we need to explore the concept of division in a bit more detail.

Primes

A divisor of a number is any number that divides into another number neatly with no remainder left over. For example, 3 is a divisor of 6, 5 is a divisor of 145, and 17 is a divisor of 187. Note that 46 is a divisor of 46, and 1 is a divisor of 10,023. Indeed, every number has at least two divisors: the number itself and 1. Most numbers have more divisors than this.

A prime is a number with no divisors other than itself and 1. For example, 17 is prime because 17 and 1 are the only numbers dividing into 17. 2 is also a prime, and so are 3, 5, and 7. On the other hand, 18 is not a prime because 2, 3, 6, and 9 are also divisors of 18.

1 is not a prime number.

Primes have many special mathematical properties, so they form the basis for so many different cryptographic algorithms.

Greatest common divisors

The greatest common divisor (GCD) of two numbers is the largest whole number dividing neatly into both numbers without leaving a remainder. In other words, the GCD of $a$ and $b$ is the largest number that is a divisor of both $a$ and $b$.

For example, the GCD of 14 and 21 is 7, since 7 is the largest divisor of both 14 and 21. We normally write this as:

$$gcd(14, 21) = 7$$

Similarly, $gcd(6, 8) = 2$, because 2 is the largest divisor of both 6 and 8.

Every pair of numbers has a greatest common divisor. Since 1 is a divisor of every number, there is always at least one common divisor. In some cases, 1 is the greatest common divisor, but many pairs of numbers have a common divisor that is larger than 1.

Coprimes

We say two numbers are coprime if their GCD is 1. In other words, two numbers are coprime if the only divisor they have in common is the number 1. Or, using our GCD notation, two numbers $a$ and $b$ are coprime if $gcd(a, b) = 1$. For example, 42 and 55 are coprime. But 42 and 56 are not coprime, since 2 divides into 42 and 56 (as do many other numbers).

Primality and coprimality are different concepts. Primality is a measure applied to a single number on its own. Coprimality is a measure applied to two numbers to compare them. However, it is true that two different primes are always coprime to one another.

Multiplicative inverses

Before considering division in modular arithmetic, we must reconsider what division means in normal arithmetic.

Definition of multiplicative inverse

The multiplicative inverse is a number we multiply a chosen number by to get 1. In other words:

$$3\times \space'\space the \; multiplicative \; inverse \; of \; 3' = 1$$

So what is the multiplicative inverse of 3 in our normal number system? The answer is one-third, since:

$$3 \times \frac{1}{3} = 1$$

Similarly, the multiplicative inverse of 127 is $\frac{1}{127}$. The multiplicative inverse of a number is indicated by raising the number to the power –1. Thus, for example:

$$3^{-1} \times \frac{1}{3} = 1$$

An important issue is that not every number has a multiplicative inverse. For example, in our normal number system, the number 0 does not have a multiplicative inverse because there is no number that, when multiplied by 0, results in the answer 1.

Division using multiplicative inverses

Division by a number is the same as multiplication with the multiplicative inverse of the number. For example, dividing by 10 is just the same as multiplying by $\frac{1}{10}$, the multiplicative inverse of 10. In other words, division by 10 is the same as multiplying by $10^{–1}$. Similarly, division by 127 is the same as multiplying by $127^{-1} = \frac{1}{127}$.

This might sound like we are just playing with words, but we are not. Considering division as multiplication using multiplicative inverses is very helpful when we return to the problem of how to divide in modular arithmetic.

Modular inverses

We’ll now consider the multiplicative inverse of one number modulo another, sometimes called a modular inverse. We’ll see that, in contrast to our normal number system:

• Many numbers other than $0$ do not have a multiplicative inverse modulo another number.

• There exist numbers other than $1$, which are their multiplicative inverse modulo another number.

We’ll begin with an example. Let’s try to find the multiplicative inverse of 2 modulo 7. In other words, we need to find a number that, when multiplied by 2, results in 1 mod 7. Recall that when working mod 7, the only numbers are 0, 1, 2, 3, 4, 5, and 6, so $\frac{1}{2}$ cannot be the answer.

It is not obvious what the answer is, or indeed if there is an answer at all. One rather crude way of finding a solution is to try out all of the numbers mod 7 until we find out if there is an answer:

$$2 \times 0 = 0 \; mod \; 7$$

$$2 \times 1 = 2 \; mod \; 7$$

$$2 \times 2 = 4 \; mod \; 7$$

$$2 \times 3 = 6 \; mod \; 7$$

$$2 \times 4 = 1 \; mod \; 7$$

$$2 \times 5 = 3 \; mod \; 7$$

$$2 \times 6 = 5 \; mod \; 7$$

So the modular inverse of 2 is 4. In other words, $2^{-1} = 4 \; mod \; 7$. We can also search for the multiplicative inverse of 6 modulo 10:

$$6 \times 0 = 0 \; mod \; 10$$

$$6 \times 1 = 6 \; mod \; 10$$

$$6 \times 2 = 2 \; mod \; 10$$

$$6 \times 3 = 8 \; mod \; 10$$

$$6 \times 4 = 4 \; mod \; 10$$

$$6 \times 5 = 0 \; mod \; 10$$

$$6 \times 6 = 6 \; mod \; 10$$

$$6 \times 7 = 2 \; mod \; 10$$

$$6 \times 8 = 8 \; mod \; 10$$

$$6 \times 9 = 4 \; mod \; 10$$

So, there is no multiple of 6 equal to 1 mod 10. Thus, 6 does not have an inverse mod 10. In other words, the modular inverse $6^{-1} \; mod \; 10$ does not exist.

The previous examples raise the interesting question: when does a number have a multiplicative inverse modulo another number? In other words: when can we divide in modular arithmetic? It turns out that a number has an inverse modulo another number precisely when the two numbers are coprime. Thus, for example, since $gcd(2, 7) = 1$, which means that 2 and 7 are coprime, and thus $2^{-1} \; mod \; 7$ exists. Similarly, $gcd(5, 17) = 1$, which means that 5 and 17 are coprime, and thus $5^{-1} \; mod \; 17$ exists. On the other hand, $gcd(6, 10) = 2$, which means that 6 and 10 are not coprime, and thus $6^{-1} \; mod \; 10$ does not exist.

The extended Euclidean algorithm

We need to find modular inverses to set up key pairs for the RSA cryptosystem. RSA works with modular numbers, which are very large, so the idea of exhaustively trying out all the possible numbers less than our modulus is not going to be a practical method of finding modular inverses.

Fortunately, a process known as the Extended Euclidean Algorithm can be used to calculate modular inverses. Refer to Extended Euclidean Algorithm to learn more about this process.

RSA key pair setup

We’ll now explain how all the simple ideas we have just discussed come together in the RSA cryptosystem.

Four basic steps are involved in setting up an RSA public and private key pair. Let’s reiterate this concept from earlier using the mathematical terms just explained:

1. Generating the modulus. Choose two primes $p$ and $q$, and let $n = p \times q$.

2. Generating $e$. Choose $e$ to be a number smaller than $(p - 1) \times (q - 1)$ coprime to $(p - 1) \times (q - 1)$. The reason we require this is because we want $e$ to have a modular inverse.

3. Forming the public key. Let the public key be $(n, e)$.

4. Generating the private key. The private key $d$ is the unique modular inverse of $e$ modulo $(p - 1) \times (q - 1)$. This number $d$ can be calculated using the extended Euclidean algorithm by anyone who knows $p$ and $q$.