The Math behind RSA
Detailed walk-through of the math behind RSA and its algorithm
We usually find fascinating applications of mathematical results in computer science. RSA is one such application.
RSA is an implementation of asymmetric encryption, also called public key encryption, which was introduced by Diffie and Hellman in New directions in cryptography [1].
The idea behind asymmetric encryption is that each machine A generates two functions f and g such that:
g(f(message)) = messageThe function f is used to encrypt messages and is made public by A. Every machine that wants to send a message to A computes f(message), and sends the result to A.
g is used for decryption and is kept secret by A. Upon receiving the encrypted message f(message), A computes g(f(message)) = message and retrieves the initial message.
For the communication to be secure, it should be computationally infeasible to derive g from f.
Based on this revolutionary idea, RSA was invented. RSA is based on simple but magical mathematical results. In the following sections, we explore the underlying mathematics.
In the following, N is a positive integer greater than 0. Unless otherwise specified, all integers are positive.
Euler’s totient function
Consider φ(N) the number of strictly positive numbers less than N and relatively prime with N.
For example φ(8) = 4, because there are 4 integers less than and coprime with 8 which are 1, 3, 5, and 7.
It can be shown that for any two coprime integers p and q :
Think about it. By knowing how many integers are coprime and less than p, and how many are coprime and less than q, we know how many integers are coprime and less than N=p.q without ever dealing with the integers between p and p.q and between q and p.q.
An example may help highlight this magic equation.
Take the number 72. It is equal to 8x9 which are coprime.
- φ(8) = 4 : Integers coprime with 8 are 1, 3, 5, 7
- φ(9) = 6 : Integers coprime with 9 are 1, 2, 4, 5, 7, 8
The equality above tells us that there are 4x6=24 numbers coprime and less than 72. We didn’t even think about these numbers and how they relate to 72, but we know how many there are that are coprime and less than 72. And this is some of the magic of mathematics.
I will show how the equation works in a future article. For now, we focus on the big picture of all the results behind RSA and how they work together.
Euler’s theorem
Euler’s theorem stipulates that for any positive integer m coprime with N, we have:
Which means that if we raise any positive integer m coprime with N to the power φ(N) then divide by N, the remainder of the division will be equal to 1.
Thus, for any positive integer k we have:
Multiplying each side by m we get:
The formula k.φ(N) + 1 reminds Bezout identity, which states that for every number e coprime with φ(N), there are two integers d and k such that:
Don’t worry if Bezout’s identity is not intuitive for now, we will come back to it in a next article.
By replacing in the formula above, we get:
Which can also be written as:
By considering f the function that maps x to f(x) = x^e mod N,
and g mapping x to g(x) = x^d mod N, where mod returns the remainder of the division, we have g(f(m)) = m for every m < N.
The careful reader will note that the k appearing in Bezout’s equality is an integer that may or may not be positive. However, only a positive k gives m^kφ(N) ≡ 1 mod N. In the case of a negative k, we just move k.φ(N) to the other part of the equation:
We now have two functions f and g which give us the initial integer m when we compute g(f(m)). The integer m will act as the message to send.
f will be made public, and g will be private. Meaning that the integers e and N will be public, and the integer d is private. The couple (e, N) is the public key, and the couple (d, N) is the private key. We need to choose N such that it is infeasible to compute d knowing just e and N.
Choice of N
To derive d from e, an attacker will have to compute φ(N) first.
If we choose N to be a prime number, φ(N) is simply equal to N-1 because all numbers between 1 and N-1 are coprime with N. In this case, because N is public, φ(N) is known with no effort to the attacker.
How about N the square of a prime number p: N = p² ?
Well, It can be easily shown that φ(p²) = p(p-1). Thus, knowing p is enough to know φ(N). p can be obtained in a logarithmic time complexity by performing a binary search between 1 and N.
This can be easily improved by choosing N a product of two different prime numbers p and q: N = p.q. In this case:
One should know p and q in order to compute φ(N). The time complexity to compute p and q is more than linear with respect to N. If the attacker reaches the colossal speed of testing over 10²⁰ numbers per second (imagine 1000 companies in the size of Google, using all their servers for this search, each server performing at a rate of 10 billion numbers per second), it will still take them over 10¹⁹⁰ centuries to derive p and q if p and q are chosen big (for example 2048 bits wide each, which is the size in use today). So choosing N=p.q the product of two primes is enough to secure RSA.
That’s it !
Let’s summarize RSA.
Each machine generates its (public, private) key pair by doing the following:
- Randomly generate two large prime numbers p and q of size 2048 bits each
- Compute N=p.q and φ(N) = (p-1).(q-1)
- Choose a number e coprime with φ(N)
- Using Euclid extended algorithm, compute d the inverse of e modulo φ(N)
- Store (e, N) as the public key, and (d, p, q, N) as the private key.
Then, encryption and decryption of a message between A and B goes as follows:
- A represents the message as an integer m less than N
- A computes c=m^eB mod NB where (eB, NB) is the public key of B. c is the encrypted message.
- A sends c to B
- B computes c^dB mod NB where dB is its private key, and retrieves the initial integer m encrypted by A.
- B converts the integer m to the initial message
That’s it, that’s the basic algorithm of RSA. It’s not difficult to understand, but I still can’t imagine how the inventors came up with the brilliant idea that this math can be used to invent a revolutionary way of encryption.
In a future article, we will have more intuition about each of the mathematical results we have seen. Stay tuned!
References
[1] W. Diffie, M. E. Hellman, New directions in cryptography (1976), IEEE transactions on information theory
[2] R. Rivest, A. Shamir, L. Adleman, A Method for Obtaining digital signatures and public-key cryptosystems (1978), Communications of the ACM
[3] Wikipedia, Euler’s totient function, https://en.wikipedia.org/wiki/Euler%27s_totient_function
[4] Wikipedia, Euler’s theorem, https://en.wikipedia.org/wiki/Euler%27s_theorem
