1. Asymmetric Cryptography: The Core Concept of Public/Private Keys

1.1 The Secure Channel Problem

Suppose Alice wants to send a secret message to Bob. Under symmetric encryption, they must first meet in person to agree on a shared secret key. If they cannot meet, any channel they use to share the key (like email or chat) can be intercepted by an eavesdropper, compromising all future encrypted messages. Asymmetric cryptography resolves this by providing Bob with two keys: a Public Key, which he distributes to the world, and a Private Key, which he keeps secret. Anyone can use Bob's public key to encrypt a message, but only Bob's private key can decrypt it. The public key is like an open padlock: anyone can snap it shut, but only the owner of the key has the combination to open it.

For this model to work, the public key and private key must be mathematically linked. However, it must be computationally impossible to calculate the private key from the public key. Achieving this requires a mathematical **one-way function with a trapdoor**: a function that is easy to calculate in one direction, but virtually impossible to reverse unless you possess a specific piece of auxiliary data (the trapdoor/private key). In RSA, this trapdoor function is built using modular arithmetic and prime factorization.

1.2 The Trapdoor Function

A trapdoor function is a function $y = f(x)$ that is easy to compute, but given $y$, computing $x = f^{-1}(y)$ is extremely difficult unless a "trapdoor" $d$ is known. When $d$ is known, $x = g(y, d)$ can be computed easily. In RSA, the one-way function is modular exponentiation:

Given $m$, $e$, and $n$, computing the ciphertext $c$ is extremely fast. However, given $c$, $e$, and $n$, finding $m$ requires calculating modular roots, which is computationally intractable unless you know the prime factors of $n$. The prime factors are the trapdoor $d$, allowing Bob to decrypt the message instantly.

Common Misconception — Public Keys are kept secret: A common misconception among beginners is that both public and private keys must be protected. In reality, the public key is designed to be shared openly. You can publish it on your website, include it in email signatures, or store it in public directories. The security of the system relies entirely on keeping the *private key* secure; public key exposure does not compromise security.

2. Modular Arithmetic: The Clock Arithmetic Foundation

2.1 Clock Arithmetic Intuition

Modular arithmetic is the arithmetic of remainders, often called "clock arithmetic". On a standard 12-hour clock, if it is 9 o'clock, and we add 4 hours, it becomes 1 o'clock, not 13 o'clock. We express this mathematically using the modulo operator:

Two integers $a$ and $b$ are congruent modulo $n$ if their difference $a - b$ is an integer multiple of $n$. This means they leave the same remainder when divided by $n$. We write this congruence as:

Modular arithmetic is highly useful in computer science because it defines a finite field of numbers. When you perform operations (addition, multiplication, exponentiation) within a modulo $n$, the result always wraps around to stay within the range $[0, n-1]$. This prevents values from bloating, keeping variables within predictable boundaries.

3. The Math Engine: Prime Numbers and Euler's Totient Function

3.1 Prime Factorization Complexity

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers. If we choose two massive prime numbers $p$ and $q$ (each hundreds of digits long) and multiply them to get $n = p \times q$, calculating $n$ takes microseconds. However, if a third party is given $n$, finding $p$ and $q$ requires checking astronomical numbers of factors, which would take supercomputers thousands of years to compute. This asymmetry is the core shield of RSA.

3.2 Euler's Totient Function

To link the public and private keys, RSA uses **Euler's Totient Function**, represented by the Greek letter $\phi$ (phi). For any integer $n$, $\phi(n)$ is defined as the count of positive integers less than or equal to $n$ that are coprime (share no common factors other than 1) to $n$. For a prime number $p$, all numbers less than it are coprime, so:

Because the totient function is multiplicative, if we have $n = p \times q$ where $p$ and $q$ are distinct primes, we can calculate $\phi(n)$ easily as:

Crucially, calculating $\phi(n)$ is only possible if you know the prime factors $p$ and $q$. If you only know $n$, calculating $\phi(n)$ is just as hard as factoring $n$. $\phi(n)$ is the secret mathematical link used to generate the private key from the public key.

4. Key Generation Step-by-Step

4.1 The Generation Algorithm

To generate a pair of RSA keys, Bob follows these mathematical steps:

1. Choose two distinct, large prime numbers $p$ and $q$.
2. Compute the modulus $n = p \times q$. The length of $n$ (usually 2048 or 4096 bits) is the key size.
3. Compute the totient $\phi(n) = (p - 1)(q - 1)$.
4. Choose an integer $e$ (the public exponent) such that $1 < e < \phi(n)$ and $e$ is coprime to $\phi(n)$. In practice, the value $65537$ ($2^{16}+1$) is almost always chosen because it is prime and has a binary representation ($10000000000000001$) that makes modular exponentiation fast.
5. Determine the private exponent $d$ (the private key) by calculating the modular multiplicative inverse of $e$ modulo $\phi(n)$. This means $d$ satisfies the congruence:

Once $d$ is calculated, Bob publishes the **Public Key** $\langle e, n \rangle$ and keeps the **Private Key** $d$ secret. He can discard $p$, $q$, and $\phi(n)$ safely, or store them securely alongside $d$.

Mermaid Diagram: The logical dependency flow of RSA Key Generation.

5. The Encryption and Decryption Math

5.1 Encryption

Suppose Alice wants to send a message $m$ (represented as an integer less than $n$) to Bob. She retrieves Bob's public key $\langle e, n \rangle$ and calculates the ciphertext $c$ as:

Alice sends the encrypted integer $c$ to Bob over the network. Even if an eavesdropper intercepts $c$, they cannot retrieve $m$ because calculating the $e$-th root of $c$ modulo $n$ is computationally impossible without knowing the private exponent.

5.2 Decryption

When Bob receives $c$, he uses his private key $d$ and modulus $n$ to recover the message $m$ using modular exponentiation:

By raising the ciphertext $c$ to the power of the private key $d$ modulo $n$, Bob recovers the original message $m$ instantly. We will prove why this decryption step always works in Section 6.

Pitfall — Processing Messages Larger than the Modulus $n$: Since RSA calculations are modulo $n$, the message $m$ must be represented as an integer strictly less than $n$ ($m < n$). If you attempt to encrypt a message larger than $n$, the modulo operation will truncate the value, making it impossible to recover during decryption. In practice, we never encrypt large files directly with RSA; instead, we use a hybrid model where RSA is only used to encrypt a small AES key, which is then used to encrypt the large file.

6. Mathematical Proof: Why Decryption Recovers the Message

6.1 The Mathematical Verification

To prove that $c^d \equiv m \pmod n$, we substitute the encryption formula $c \equiv m^e \pmod n$ into the decryption equation:

Since we chose $d$ as the modular inverse of $e$ modulo $\phi(n)$, we know that $ed \equiv 1 \pmod{\phi(n)}$, which means $ed = k \cdot \phi(n) + 1$ for some integer $k$. We can rewrite the exponent as:

According to **Euler's Theorem**, if $m$ is coprime to $n$, then $m^{\phi(n)} \equiv 1 \pmod n$. Substituting this in, we get:

Thus, the decryption operation recovers the original message $m$ perfectly. This proof holds even if $m$ is not coprime to $n$ (by applying the Chinese Remainder Theorem), guaranteeing that the mathematical decryption contract is always valid.

7. Advanced: The Extended Euclidean Algorithm

7.1 Calculating Modular Inverses

To calculate the private key $d$, we must find the modular inverse of $e$ modulo $\phi(n)$. This requires solving the linear Diophantine equation $e \cdot d + \phi(n) \cdot y = 1$ for integers $d$ and $y$. We do this efficiently using the **Extended Euclidean Algorithm**. The standard Euclidean algorithm calculates the Greatest Common Divisor (GCD) of two integers by repeated division. The extended version tracks the coefficients of each step, allowing us to express the GCD as a linear combination of the inputs, returning the modular inverse in logarithmic time:

7.2 Bezout's Identity and the Step-by-Step Coefficient Trace

The mathematical foundation of the Extended Euclidean Algorithm is **Bézout's Identity**. It states that for any non-zero integers $a$ and $b$, there exist integers $x$ and $y$ such that:

In RSA, because we select $e$ to be coprime to the totient $\phi(n)$, their GCD is guaranteed to be 1. Thus, Bézout's Identity simplifies to $e \cdot x + \phi(n) \cdot y = 1$. The coefficient $x$ is the modular multiplicative inverse of $e$ modulo $\phi(n)$ — which is Bob's private exponent $d$. If the algorithm returns a negative value for $x$, we add $\phi(n)$ to wrap it back into a positive integer within the range $[1, \phi(n)-1]$.

To illustrate how the coefficients are calculated recursively, let us trace the algorithm for $e = 7$ and $\phi(n) = 40$. We want to find $d$ such that $7d \equiv 1 \pmod{40}$:

1. Step 1: $40 = 5 \times 7 + 5$ (Remainder 5). We express the remainder: $5 = 40 - 5 \times 7$.
2. Step 2: $7 = 1 \times 5 + 2$ (Remainder 2). We express the remainder: $2 = 7 - 1 \times 5$. Substituting Step 1: $2 = 7 - 1 \times (40 - 5 \times 7) = 6 \times 7 - 1 \times 40$.
3. Step 3: $5 = 2 \times 2 + 1$ (Remainder 1). We express the remainder: $1 = 5 - 2 \times 2$. Substituting previous equations: $1 = (40 - 5 \times 7) - 2 \times (6 \times 7 - 1 \times 40) = 3 \times 40 - 17 \times 7$.

Looking at the final equation, we have $-17 \times 7 + 3 \times 40 = 1$. Thus, the modular inverse of 7 modulo 40 is $-17$. Wrapping this modulo 40 gives: $d = -17 + 40 = 23$. We verify this: $7 \times 23 = 161 = 4 \times 40 + 1 \equiv 1 \pmod{40}$. The algorithm computes this sequence in logarithmic time, enabling instant key generation even for 4096-bit primes.

Pitfall — Exponent Coprimality Failures: If you select an exponent $e$ that is not coprime to $\phi(n)$ (for example, if they share a common divisor like 2), the Greatest Common Divisor will be greater than 1. In this case, no modular multiplicative inverse $d$ exists, and the key generation will crash. Always verify that $\gcd(e, \phi(n)) == 1$ before running the Extended Euclidean steps.

8. Advanced: Common Attacks and Padding

8.1 Vulnerabilities of Raw RSA

Raw RSA (also known as textbook RSA) is mathematically correct but highly insecure in practice. It is a deterministic encryption algorithm: encrypting the same message $m$ with the same public key always yields the same ciphertext $c$. An attacker intercepting traffic can build a database of encrypted common words (like "Yes", "No") and decrypt messages by matching ciphertexts. Furthermore, raw RSA is vulnerable to mathematical exploits like the Coppersmith attack if the public exponent $e$ is set too small.

To secure RSA, we must make it non-deterministic (probabilistic). Before encrypting, we apply a padding scheme called **Optimal Asymmetric Encryption Padding (OAEP)**. OAEP uses cryptographic hash functions and random noise to pad the message, ensuring that encrypting the same message multiple times yields completely different ciphertexts, blocking dictionary attacks and mathematical structure exploits.

9. Complete Python RSA Implementation from Scratch

9.1 Implementation Code

The following code implements Extended GCD, modular exponentiation, key generation, encryption, and decryption from scratch in Python:

10. Interactive: RSA Handshake Simulator

Click "Encrypt & Send" to watch the asymmetric encryption handshake. Observe how Alice uses Bob's public key to encrypt the message, sending the scrambled ciphertext over the network, and how Bob recovers the text using his secret private key:

RSA Overhead: Key Size vs Performance

The chart below compares the time taken (in milliseconds) to generate keys and encrypt messages using different RSA key bit-lengths:

12. Frequently Asked Questions