RSA encryption is a public-key cryptosystem that relies on the mathematical difficulty of factoring large numbers.
Let’s see it in action. Imagine Alice wants to send a secret message to Bob.
First, Bob generates a pair of keys: a public key and a private key. His public key is something he can share with anyone, like Alice. His private key he keeps secret.
Bob’s public key is a pair of numbers $(n, e)$. His private key is another pair of numbers $(n, d)$. The number $n$ is the same for both keys.
Here’s how Bob generates them:
- He picks two large prime numbers, $p$ and $q$. Let’s use small ones for illustration: $p=11$ and $q=13$.
- He calculates $n = p \times q$. So, $n = 11 \times 13 = 143$. This $n$ will be part of both his public and private keys.
- He calculates Euler’s totient function, $\phi(n) = (p-1)(q-1)$. So, $\phi(143) = (11-1)(13-1) = 10 \times 12 = 120$.
- He chooses an integer $e$ such that $1 < e < \phi(n)$ and $e$ is coprime to $\phi(n)$ (their greatest common divisor is 1). Let’s pick $e=7$. $\text{gcd}(7, 120) = 1$, so this is valid. This $e$ is the public exponent.
- He calculates $d$, the modular multiplicative inverse of $e$ modulo $\phi(n)$. This means $d \times e \equiv 1 \pmod{\phi(n)}$. We need to find $d$ such that $7d \equiv 1 \pmod{120}$. Using the extended Euclidean algorithm, we find $d=103$ because $7 \times 103 = 721$, and $721 \pmod{120} = 1$ ($721 = 6 \times 120 + 1$). This $d$ is the private exponent.
So, Bob’s public key is $(n, e) = (143, 7)$ and his private key is $(n, d) = (143, 103)$.
Now, Alice wants to send the message "HI" to Bob. First, she needs to convert "HI" into a number. Let’s say 'A' is 01, 'B' is 02, and so on. So, 'H' is 08 and 'I' is 09. She can represent "HI" as a single number, say $M=809$. For RSA, the message $M$ must be less than $n$. If the message is larger than $n$, it’s split into blocks. For simplicity, let’s assume $M$ is small enough, say $M=15$ (representing a character or a small number).
Alice uses Bob’s public key $(n, e) = (143, 7)$ to encrypt her message $M=15$. The encryption formula is $C = M^e \pmod{n}$. $C = 15^7 \pmod{143}$. $15^7 = 170,859,375$. $170,859,375 \pmod{143}$. To calculate this, we can use modular exponentiation. $15^2 \equiv 225 \equiv 82 \pmod{143}$ $15^4 \equiv 82^2 \equiv 6724 \equiv 76 \pmod{143}$ ($6724 = 47 \times 143 + 23$, wait, $6724 = 47 \times 143 + 23$ not 76. $143 \times 40 = 5720$, $143 \times 7 = 1001$, $143 \times 47 = 6721$. So $6724 \pmod{143} = 3$. My manual calculation is off, let’s use a calculator for this intermediate step. $82^2 = 6724$. $6724 / 143 \approx 47.02$. $47 \times 143 = 6721$. $6724 - 6721 = 3$. So $15^4 \equiv 3 \pmod{143}$.) $15^7 = 15^4 \times 15^2 \times 15^1 \equiv 3 \times 82 \times 15 \pmod{143}$ $3 \times 82 = 246 \equiv 103 \pmod{143}$ $103 \times 15 = 1545 \equiv 115 \pmod{143}$ ($1545 = 10 \times 143 + 115$) So, the ciphertext $C = 115$.
Alice sends the ciphertext $C=115$ to Bob.
Bob receives $C=115$ and uses his private key $(n, d) = (143, 103)$ to decrypt it. The decryption formula is $M = C^d \pmod{n}$. $M = 115^{103} \pmod{143}$.
This is where the math behind RSA shines. Because of the relationship between $e$, $d$, and $\phi(n)$, we know that $M^{ed} \equiv M \pmod{n}$ for any message $M$. Let’s verify for our example: $115^{103} \pmod{143}$. We know $115 \equiv -28 \pmod{143}$. $(-28)^{103} \pmod{143}$. This calculation is still complex, but the core principle is that $C^d \pmod{n}$ will recover the original message $M$. $115^{103} \pmod{143}$ using a computational tool yields $15$. And indeed, $15$ was the original message Alice sent.
The security of RSA hinges on the fact that it is computationally infeasible to compute $d$ from $n$ and $e$ without knowing the prime factors $p$ and $q$. Factoring a large number $n$ into its prime factors $p$ and $q$ is the hard problem. If an attacker could factor $n$, they could then compute $\phi(n)$ and subsequently $d$, thereby compromising Bob’s private key. The larger the primes $p$ and $q$, the larger $n$ becomes, and the more computationally expensive factoring becomes.
The key generation process relies on the Chinese Remainder Theorem (CRT) for efficiency when decrypting with the private key. While the decryption formula is $M = C^d \pmod n$, for performance, it’s often computed as: $d_p = d \pmod{p-1}$ $d_q = d \pmod{q-1}$ $q_{inv} = q^{-1} \pmod p$
Then, calculate: $m_1 = C^{d_p} \pmod p$ $m_2 = C^{d_q} \pmod q$ $h = (q_{inv} \times (m_1 - m_2)) \pmod p$ $M = m_2 + h \times q$
This is faster because the modular exponentiations are done with smaller moduli ($p$ and $q$) instead of the larger modulus $n$. For instance, if $p$ and $q$ are 1024 bits, $n$ is 2048 bits. Computing modulo $p$ and $q$ is significantly faster than modulo $n$. This optimization is crucial for real-world RSA performance.