We use RSA extensively in our everyday life, in web browsers, in computer servers, in cell phones, and pretty everywhere else where authentication is required. But how does RSA encryption actually works? I came across an article in Zhihu in Chinese to explain RSA and I think it is the best article that I ever read about this topic: simple, straightforward and intuitive description for layman such as myself. The author self-declare as a high school student. I decided to re-write it in English to help English readers with limited mathematics skills understand how RSA encryption actually works.
And of course, I will use a set of Python scripts to illustrate some fun examples to help readers understand this better, and play it yourself. While I write this article, I also put in some extra information that I learned online (such as the origin of Alice and Bob). Additionally, while writing this article, I also decided to write another section specifically dedicated to applications of Euler's theorem due to the use of this theorem in RSA formulation.
RSA is a public-key cryptosystem that is widely used for secure data transmission. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the encryption algorithm in 1977. Before the paper, people typically call a message sender as A and receiver as B. As a fun fact, in the paper, the authors first use Alice and Bob as the sender and receiver, so most cryptography papers after this paper began to adopt the name Alice and Bob. But anyway, they initially sent the paper to a low impact journal and was rejected and they are probably not very happy about it, but later it is still published in a decent journal Communications of the ACM. In 2002 they also won a prestiguous ACM Turing Award for the invention of RSA.
I know I am a little off-topic here, but whether or not the original paper was rejected by a low-impact journal (and which journal) is up to debate. I also do want to draw your attention to a webpage maintained by Merkle about his idea in a 1974 CS244 class at UC Berkeley, which he dropped because the professor does not like his project. He did submit to Communications of the ACM but the paper was rejected, and he is obviously upset with it. I quote his words: "The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability." I am not trying to imply anything here, and I do not think Merkle is trying to imply anything obvious either. Move on.
RSA uses asymmetric encryption. Here two keys are used: the Public Key is used for encryption and the Private Key is for decryption. This is different from symmetric encryption which consists of one key for encryption and decryption.
In this case, Alice wants to send a message to Bob. Bob then creates a pair of keys in RSA and gives the public key to Alice. Alice then encrypts the message using the public key and sends the encrypted message to Bob. Bob then decrypts the message using private key. If somebody named Eve gets the public key and the encrypted message, Eve still cannot decrypt the message within a reasonable amount of time. This is how asymmetric encryption works.
The various steps are detailed below. Before going to step 1, we need to review several basic concepts:
$\varphi(n)$ is Euler's totient function, which counts the positive integers up to a given integer n that are relatively prime to n. Say for example, if we want to calculate $\varphi(10)$, we can count the numbers that are co-prime with 10, which will be [1, 3, 7, 9], so $\varphi(10) = 4$.
To calculate power and modulus, we can use the property $(a * b) \pmod{m} = [(a \pmod{m}) * (b \pmod{m}] \pmod{m}$. Additionally, we can use binary representation of the exponent, for example, decompose 13 to 8+4+1. Now, if we want to calculate $c = a^e \% n$, the calculation uses Binary Exponentiation, which moves bit by bit (the code is written in C implementation via right-shift of bit for every cycle), so it can be very fast. You do not actually calculate the a^e number then calculate the modulus. Python has the built-in pow(a,b,n) function that is already written in C, which calculate (a ^ b) % n directly. The computational complexity is O(n) only.
Bob uses random number generator to find two large prime numbers $p_1$ and $p_2$. He checks that these two numbers are actually prime using Miller-Rabin test. The time complexity is O(n) for both random number generation and primality test. I copied the code from a website. You can run the code below to find all prime numbers below a specific integer.
#@title
# Python3 program Miller-Rabin primality test
import random
# Utility function to do
# modular exponentiation.
# It returns (x^y) % p
def power(x, y, p):
# Initialize result
res = 1;
# Update x if it is more than or
# equal to p
x = x % p;
while (y > 0):
# If y is odd, multiply
# x with result
if (y & 1):
res = (res * x) % p;
# y must be even now
y = y>>1; # y = y/2
x = (x * x) % p;
return res;
# This function is called
# for all k trials. It returns
# false if n is composite and
# returns false if n is
# probably prime. d is an odd
# number such that d*2<sup>r</sup> = n-1
# for some r >= 1
def miillerTest(d, n):
# Pick a random number in [2..n-2]
# Corner cases make sure that n > 4
a = 2 + random.randint(1, n - 4);
# Compute a^d % n
x = power(a, d, n);
if (x == 1 or x == n - 1):
return True;
# Keep squaring x while one
# of the following doesn't
# happen
# (i) d does not reach n-1
# (ii) (x^2) % n is not 1
# (iii) (x^2) % n is not n-1
while (d != n - 1):
x = (x * x) % n;
d *= 2;
if (x == 1):
return False;
if (x == n - 1):
return True;
# Return composite
return False;
# It returns false if n is
# composite and returns true if n
# is probably prime. k is an
# input parameter that determines
# accuracy level. Higher value of
# k indicates more accuracy.
def isPrime( n, k):
# Corner cases
if (n <= 1 or n == 4):
return False;
if (n <= 3):
return True;
# Find r such that n =
# 2^d * r + 1 for some r >= 1
d = n - 1;
while (d % 2 == 0):
d //= 2;
# Iterate given nber of 'k' times
for i in range(k):
if (miillerTest(d, n) == False):
return False;
return True;
# Driver Code
# Number of iterations
k = 4;
print("All primes smaller than 100: ");
for n in range(1,100):
if (isPrime(n, k)):
print(n , end=" ");
# This code is contributed by mits
All primes smaller than 100: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Bob calculates the product of $p_1$ and $p_2$ as $n$. Complexity is O(n).
Bob calculates $\varphi(n)$ = ($p_1$ - 1)($p_2$ - 1). This equation is intuitive to prove. Complexity is O(n).
Because complexity for integer factorization is exponential (or at least some form of NP), when $p_1$ and $p_2$ are very large, it is impossible for anybody to factorize $n$. There is some explanation here why it is not polynomial: basically the size of the problem is the bits to represent an integer, not the integer itself.
First we do some simple explanation: if $a=b+km$, then we write it as $a \equiv b \pmod{m}$. For example, 14=2+3*4, so $14 \equiv 2 \pmod{3}$.
Bob then finds another integer $d$, such that $ed \equiv 1 \pmod{\varphi(n)}$. In practice this needs to be calculated by Extended Euclidean algorithm with O(n) complexity. We just need one relatively large (say 2048 bits) $d$ value, even though many possible suitable $d$ values may exist.
The detailed derivation of recovering a^e^d to a is given below:
Remember that Euler's Theorem states that if $gcd(a,n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.
$\because a^{\varphi(n)} \equiv 1 \pmod{n}$
$\therefore a^{k\varphi(n)} \equiv 1 \pmod{n}$
$\therefore a^{k\varphi(n)+1} \equiv a \pmod{n}$
$\therefore a^{ed} \equiv a \pmod{n}$
$\therefore$ if $c \equiv a^e \pmod{n}$ then $c^d \equiv a^{ed} \equiv a \pmod{n}$
So now the private/public key pair is done. The public key is $(n, e)$, and private key is $(n, d)$. Of course, there is no mathematical reason why they cannot be switched; but since people typically use a value such as 65537 as the value of e, it is by default used as public key rather than private key. Additionally, think about this: the public key is only 32 bit, yet the private key is typically 2048 or even 4096 bit, so it is a lot harder to crack a private key in this case. If the public/private keys are too close to each other, then there are algorithms to crack them, so it is best to keep public key short yet private key long.
Now Alice can do encryption using the public key $(n,e)$. With a given number $a$, she only needs to calculate $c = a^e \% n$ which is O(n) as I mentioned above. The pow() function in Python can do this easily.
Alice sends c to Bob. Then Bob can recover a because a = c^d \% n which has O(n) complexity. Nobody can break the code even if they steal n and e (as I mentioned, it is too hard to factorize n to two prime numbers).
However, if we think about this problem more carefully, we can see that a hacker does not have to factorize n. If there is a fast algorithm that calculates $\varphi(n)$ instead, RSA can also be cracked.
Whether quantum algorithm can speed up RSA craking, either through n factorization or through $\varphi(n)$ calculation, is up to debate right now.
# you can see that the code below runs very fast, because Python does not actually calculate 1234567890**6789012345 which is a huge value!!!
pow(3,4,5), pow(2,3,4), pow(12345,67890,13579), pow(1234567890,6789012345,13579)
(1, 0, 545, 1405)
So in the above section we describe how RSA algorithm actually works. Next we use a numerical example to show the procedure: suppose we have two prime number 11 and 59, and we pick a e=3. Then $\varphi(n)$ is 10*58=580. We then select a $d = (k*\varphi(n)+1)/e$=(2*580+1)/3=387.
p1 = 11
p2 = 59
e = 3
n = p1*p2
phin = (p1-1)*(p2-1)
for k in range(100):
if (k*phin+1) % e == 0:
print ("We found a good d value: ", int ((k*phin+1)/e), " at k=", k)
break
We found a good d value: 387 at k= 2
# next we use a as input message, and show how we can recover the message using e (public key) and d (private key)
a = 345
c = a**e % n
c
d = 387
newa = c**d % n
print ("a=", a, "c=", c, "newa=", newa)
a= 345 c= 97 newa= 345
# next we repeat the same procedure but using pow() function
a = 345
c = pow(a,e,n)
c
d = 387
newa = pow(c,d,n)
print ("a=", a, "c=", c, "newa=", newa)
a= 345 c= 97 newa= 345
The examples above show how to encrypt a single number. Obviously this does not apply to real world, when we need to encrypt a much longer message or file.
In real world applications, we had to rely on symmetric key (such as a 128 bit AES key) and encrypting the message or file with that key. Then that key is further encrypted by RSA.
So when a receipient get an encrypted file, first use private key of the RSA to decrypt the AES key, then use the symmetric AES key to decrypt the actual file.
If you are viewing this webpage via https://mathinpython.wglab.org in your web browser, then you can click the little "lock" icon in the URL bar to examine security certificate. The website is directly hosted at GitHub, which uses Let's Encrypt to issue keys. It seems that 2048-bit RSA is used for the encryption. However, if you are viewing this webpage in Google Colab, you will see that 256-bit ECC keys are actually used instead of RSA keys. More explanations are here. It seems that Chrome browser support both RSA and ECC, based on their documentation. I do not know enough on this topic to dig it further.
Let's consider another fun question: prove $n^5 \equiv n \pmod{10}$.
Solution I, let's use a brute force approach to prove that this is indeed the case:
# this is a very nice piece of code but it does not generalize to infinitely large numbers of n
all(pow(i, 5, 10) == i for i in range(10))
True
Solution II, we can apply Euler's Theorem here to prove this equation:
if gcd(n,10)=1, or if n and 10 are co-prime (relatively prime), then we have $n ^ {\varphi(10)} = n^4 \equiv 1 \pmod{10}$. Then $n^5 \equiv n \pmod{10}$.
Otherwise, then n either has 2 or 5 as a factor, and the solution is self-evident given $n^5-n = n(n-1)(n+1)(n^2+1)$. If $n$%5=0 or 4 or 1 then obviously $n$ or $n+1$ or $n-1$ is multiples of 5. If $n$%5=2 or 3 then it is also obvious by replacing $n=2k+2$ or $n=2k+3$ and then expand it to see that it is multiples of 5.
Solution III, we can try another approach that can be generalized further. This solution is given by a middle school student:
Because $n^5-n = n(n-1)(n+1)(n^2+1)$, it can be divided by 2. Because 5 is prime, so $n^5-n$ can be divided by 5 with Fermat's little theorem. So it is proved.
Solution IV, we try to generalize this to all prime numbers, not just 5. Again we will use Fermat's little theorem, but let's actually prove the Fermat's little theorem first. For a prime number $p$, with binomial expansion, we have:
$(n+1)^p = \displaystyle\sum_{i=0}^{p} C_p^i n^i$
Because $p$ is prime, we have $C_p^i = \frac{p!}{i!(p-i)!} \equiv 0 \pmod{p}$, so
$(n+1)^p = \displaystyle\sum_{i=0}^{p} C_p^i n^i \equiv n^p + 1 + \displaystyle\sum_{i=1}^{p-1} C_p^i n^i \equiv n^p + 1 \pmod{p}$
So we proved Fermat's little theorem. Now using this theorem, we just need to re-write n to n-1+1:
$n^p \equiv (n-1)^p+1 \pmod{p} \equiv (n-2)^p+2 \pmod{p} \equiv ... \equiv 1^p+(n-1) \pmod{p} \equiv n \pmod{p}$
So it is proved and generalized to all prime numbers.