RSA

2024-12-10

Introduction

RSA is a popular scheme used for asymmetric encryption. This post is intended as a primer on the mathematics behind RSA, how it works, and why it is secure. We will not focus on the history of RSA or why it is used. There are plenty of resources available that explain this already.

Asymmetric encryption uses two separate keys to encrypt and decrypt messages. Imagine using one key to lock a door, and another to unlock it. The key used to encrypt (lock) data is called the public key. The other key is used to decrypt the encrypted messages, and is called the private key. When using RSA, or other asymmetric schemes, the public key can be shared widely, but private key is kept secret.

Kyber, ElGamal and Diffie-Hellman Key Exchange are other examples of asymmetric schemes. Generally, their security depends on one-way functions. RSA’s security depends on the difficulty of factoring large numbers.

Mathematics required for RSA

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value. The modulus is the value that numbers wrap around when reaching it. For example, in modulo 12 arithmetic, $5 + 8 \equiv 1 \pmod{12}$ because $5 + 8 = 13$ , and $13 \equiv 1 \pmod{12}$ . Similarly $5 \times 8 \equiv 4 \pmod{12}$ because $40 \equiv 4 \pmod{12}$ . (12 goes into 40 three times with a remainder of 4).

Greatest Common Divisor

The greatest common divisor (gcd) of two integers is the largest integer that divides both numbers without leaving a remainder. For example, the gcd of 8 and 12 is 4 (gcd(8, 12) = 4) because 4 is the largest number that divides both 8 and 12 without leaving a remainder. What is gcd(10, 5), or gcd(7, 9)? A gcd of 1 means two numbers have no common factors, except 1.

Euler's Totient Function

If two numbers have no common factors except 1, we say they are coprime - or that their gcd is 1. Euler's totient function, φ(n), counts the number of positive integers less than n that are coprime to n. For example, φ(8) = 4 because {1, 3, 5, 7} are coprime to 8, but {2, 4, 6} each have common divisors with 8.

How RSA works - overview

Choose two prime numbers, p and q. These are kept private.
Compute n = p * q. n is used as the modulus for both the public and private keys. Making n a very large number and it being difficult to factor into p and q makes RSA secure.
Compute φ(n). φ(n) is simply (p - 1) * (q - 1) - see proof below.
Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. e is released as part of the public key.
Compute d such that e * d ≡ 1 (mod φ(n)). d is kept private.
The public key is (n, e) and the private key is (n, d).

How RSA works - in detail

Step 1 - Generating large primes

The first step in RSA is to generate sufficiently large primes p and q. In order for n to be 2,048-bits long, p and q must each be around 1,024-bits long.

Generating primes this large is non-trivial and computationally expensive. One common method to generate large primes is as follows:

Select σ, a random x-bit number (e.g 1,024-bits). This number should be odd as 2 is the only even prime number. Thus we select an odd number in the range $[2^{x-1}, 2^{x}-1]$ . We call σ the prime candidate.
We perform an initial test to check if σ is prime, called a low-level primality test. We start with a precomputed list of the first k prime numbers. The value of k should be as large as possible. If σ is divisible by any of the first k primes, then σ is composite and not prime and we pick a new σ. If σ is not divisible by any of the first k primes, then σ remains our prime candidate.
Once we find a σ that passes this low-level primality test, we perform a high-level primality test, the Miller–Rabin primality test. This is a probabilistic method. It is not feasible to use a deterministic method to check the primality of extremely large numbers because of the computation required.
The Miller-Rabin method repeatedly tests the prime candidate, σ, for primality. With each iteration that the candidate passes, we increase our confidence in the candidate being prime by 75%. By performing many iterations, we can achieve high confidence that the candidate is prime. For example, after 10 tests, the probability of primality is $1 - \frac{1}{4}^{10} = 0.99999904632$ . We test for primality until the chance of σ being composite is less than $2^ \frac{1}{128}$ , which is ~64 iterations. We then assume we have found a prime number and can move on to the next step. Otherwise we return to step 1.

We now have an algorithm for generating p and q. The next step is to compute n = p * q.

Step 2 - Computing the modulus `n`

Once we have p and q, computing n is trivial. We simply multiply p and q together to get n. This is known as a one way, easy to do one way (multiply two numbers together) but computationally hard to reverse (find the prime factors of a really large composite number). This is ultimately what makes RSA secure.

Step 3 - Computing Euler's totient function `φ(n)`

As mentioned earlier, φ(n) is simply a case of computing (p - 1) * (q - 1).

The proof for this is as follows:

Let n = p * q. Where p and q are prime numbers.
Let φ(n) be the number of positive integers less than n that are coprime to n.
We can write φ(n) as φ(p * q).
We know that if two numbers are coprime, then their greatest common divisor is 1. Thus, gcd(p, q) = 1 because p and q are prime numbers.
We can write φ(p * q) as φ(p) * φ(q) because p and q are coprime.
We can write φ(p) as p - 1 because all numbers less than p are coprime to p except for p itself.
We can write φ(q) as q - 1 because all numbers less than q are coprime to q except for q itself.
Thus, φ(p * q) = (p - 1) * (q - 1).
Therefore, φ(n) = (p - 1) * (q - 1).

Step 4 - Choosing the public exponent `e`

The public exponent e must be chosen such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. In practice, e is often chosen to be 65537 because it is a prime number and it makes the encryption process faster.

Why is 65537 commonly used for e?

65537 is commonly used as the public exponent e because it strikes a balance between efficiency and security. 65537 is prime and small, so it is compatible with the requirement that gcd(e, φ(n)) = 1. Its binary representation, 10000000000000001, has only two 1-bits, making modular exponentiation computationally efficient due to the reduced number of multiplications required. 65537 is large enough to avoid vulnerabilities that can arise from using smaller values, e.g. 3 or 17, but is small enough to still enable fast encryption. 65537 is known as a Fermat Prime.

Step 5 - Computing the private exponent `d`

The private exponent d is computed such that e * d ≡ 1 (mod φ(n)). This is called the modular multiplicative inverse of e modulo φ(n). You might think of it as the modular arithmetic equivalent of a reciprocal, or 1/e. d is generally computed using the Extended Euclidean Algorithm.

Step 6 - Generating the public and private keys

The public key is (n, e) and the private key is (n, d).

Encryption and Decryption

Encryption

To encrypt a message m using the public key (n, e), we compute $c = m^e \mod n$ .

c is the resulting ciphertext, or the garbled version of the original message. If m is larger than n, then the message must be split into smaller blocks and each block must be encrypted separately and then concatenated together.

Decryption

To decrypt a ciphertext c using the private key (n, d), we compute $m = c^d\mod n$

Where m is the resulting plaintext. If c is larger than n, then the ciphertext must be split into smaller blocks and each block must be decrypted separately and then concatenated together.

Why is RSA secure?

The security of RSA relies on the fact that it is easy to multiply large prime numbers together (p * q = n), but it is extremely difficult to factor the product of two large prime numbers (n = ? * ?).

Breaking RSA

If an attacker was to learn any one of p, q, φ(n) , or d they can fully break the cipher.

If they learn p or q it is trivial to calculate the other values given n = p * q and n is public. From here they can work out all remaining secret values.
If they were to learn φ(n) they can solve for p and q given they know the function φ(n) = (p - 1)(q - 1) and that n = p * q . This is a case of solving two unknowns from two equations (note that n is public).
If they learn d, the private key, the entire cipher is clearly broken instantly.

If we assume that all private values (p, q, φ(n) , d) remain private, then the security of RSA relies on an attacker being unable to factorize n into p and q . This is the problem of prime factorization.

Prime factorization - how hard is it to factor `n`?

Within RSA, two common key sizes are 2048 and 4096 bits. Key size refers to the length of n which we normally measure in bits . A 2048-bit key will produce an integer between $2^{2047}$ to $2^{2048}$ , or roughly $3 \times 10^{616}$ . That’s 617 decimal digits. For RSA 4096, this doubles to an integer roughly 1,235 digits long.

Factoring large numbers is hard. Very very hard. The most efficient known algorithm for factoring large numbers is the general number field sieve and the largest number that’s been factored in public is roughly $10^{250}$ or 829 bits. That’s $10^{366}$ smaller than an RSA 2048 key. How much harder would it be to factor a 2048-bit key? Here’s a rough estimate: The factoring difficulty doubles with every 5 (decimal) digits. A 617 digit number requires $\frac{617 - 250}{5} = 73.4$ doublings in computational power, or $2^{73.4} \approx 10^{21}$ more computation. The 829-bit result effectively took 2700 years on a single CPU core. Then, factoring a 2048-bit number would require $2700 \times 10^{21} \approx 3 \cdot 10^{24}$ years on a single CPU core. The universe is $10^{14}$ years old. Keep in mind these are rough figures.

What if we replaced the CPU with a supercomputer? The Argonne exascale computer can do $\sim10^{18}$ operations per second. That’s a $10^9$ improvement on a single CPU core, so it might take approx $3 \cdot 10^{15}$ years on the Argonne computer to factor a 2048-bit number. That’s still longer than the universe’s lifetime. Suppose you could apply 1 billion Argonne computers to the sole task of factoring a single 2048-bit number. You should expect it to take 3 million years.

RSA