RSA security, attacks, padding and hybrid encryption

Why factoring is the whole game, the five attack classes the lecture names against RSA, why textbook RSA is malleable, and how padding and hybrid encryption fix RSA's two practical weaknesses.

State why factoring n is the foundation of RSA's security, and why key sizes below 2048 bits are no longer considered safe.
Explain why p and q must be large and must not be close together.
Name the five classes of attack the lecture identifies against RSA.
Reproduce the lecture's malleability derivation and explain why it defeats semantic security.
Explain what OAEP padding adds to RSA and why hybrid encryption exists.

20 min read

Intuition

The previous page showed RSA working correctly: choose keys, encrypt, decrypt, get the right answer back. None of that says the scheme is safe to actually deploy. RSA’s security rests on one hard problem, factoring, and even a mathematically sound choice of $p$ , $q$ and $e$ can still be broken if the ciphertext is used carelessly. This page covers both halves: what makes the numbers themselves hard to attack, and what makes naive RSA unsafe even when the numbers are fine.

Mechanism

Why factoring is the whole game. Recovering $d$ without permission means either finding the $e$ -th root of $C$ directly, which is believed infeasible, or factoring $n$ back into $p$ and $q$ , which lets an attacker reconstruct $\varphi(n)$ and then $d$ exactly as the key holder did. Both are believed hard. Factoring is the one that fails first as $n$ shrinks, so RSA’s key-size recommendation is set by how large $n$ needs to be before factoring is out of reach.

Two conditions on $p$ and $q$ keep factoring hard:

$p$ and $q$ must be very large. The lecture states RSA key lengths of 2048 bits and above are needed for $n$ today; the Week 5 practice quiz is explicit that key sizes below 2048 bits are no longer considered secure.
$p$ and $q$ must not be close together. If they are, $n = pq$ sits close to $\sqrt{n}^2$ , and searching near $\sqrt{n}$ finds the factors quickly, a much cheaper search than factoring in general.

The lecture is blunt about the rest: there are further constraints on what makes a good key beyond these two, and the guidance is simply never implement RSA yourself for production use.

Mechanism

Five ways to attack RSA, as the lecture names them:

Brute force. Try every possible private key. Feasible only against small keys, which is the attack the 2048-bit recommendation defends against.
Mathematical attacks. Several distinct approaches exist, but all of them are equivalent in effort to factoring $n$ .
Timing attacks. Measure how long decryption takes. Variation in running time can leak information about $d$ .
Hardware fault-based attacks. Deliberately induce a fault in the processor computing a signature, then use the faulty output to extract key material.
Chosen ciphertext attacks. Exploit a structural property of RSA itself, with malleability as the lecture’s example, rather than attacking the key.

The rest of this page is about the fifth one, because it is the attack that motivates everything RSA does in practice beyond raw key generation.

Threat

Malleability. Textbook RSA preserves multiplicative structure: if you have two ciphertexts, their product decrypts to the product of the two plaintexts, and nobody needs to know either plaintext or the private key to produce that product. An attacker who can get a chosen ciphertext decrypted (a chosen ciphertext attack) turns this into a way to recover a plaintext they never directly saw.

Worked example

AnswerEve turns c = E(3) into a product with E(5) = 146, gets 15 back from decryption, and divides by 5 to recover the original 3, without ever learning d.

Using the key from the previous page: $p=17$ , $q=11$ , $n=187$ , $e=7$ , $d=23$ .

Eve intercepts $c = m^e \bmod n$ for some plaintext $m$ she has not seen. Say $m = 3$ : $c = 3^7 \bmod 187$ . By repeated squaring: $3^1 = 3$ , $3^2 = 9$ , $3^4 = 81$ . $7 = 4+2+1$ , so $3^7 = 81 \times 9 \times 3 \bmod 187$ : $81 \times 9 = 729 \bmod 187 = 168$ , then $168 \times 3 = 504 \bmod 187 = 130$ . So $c = 130$ .
The general trick, from the lecture: pick any $r$ , compute $c' = c \cdot r^e \bmod n$ , and get it decrypted. Since $(c')^d \equiv (c \cdot r^e)^d \equiv m^{ed} \cdot r^{ed} \equiv m \cdot r \pmod n$ , the decrypted value is $m \cdot r$ , not $m$ , but $m \cdot r$ is enough to recover $m$ once $r$ is known.
Eve doesn’t need to pick $r$ out of thin air. If she has already seen another ciphertext $c_2 = r^e \bmod n$ for a known $r = 5$ (say $c_2 = 5^7 \bmod 187$ ), she can use it directly as her multiplier. Computing $c_2$ : $5^1 = 5$ , $5^2 = 25$ , $5^4 = 625 \bmod 187 = 64$ . $5^7 = 64 \times 25 \times 5 \bmod 187$ : $64 \times 25 = 1600 \bmod 187 = 104$ , then $104 \times 5 = 520 \bmod 187 = 146$ . So $c_2 = 146$ .
Eve computes $c' = c \cdot c_2 \bmod n = 130 \times 146 \bmod 187$ . $130 \times 146 = 18980$ , and $18980 \bmod 187 = 93$ . She submits $c' = 93$ for decryption. This is the chosen ciphertext attack step.
The decryption oracle returns $(c')^d \bmod n = 93^{23} \bmod 187$ . By repeated squaring: $93^1 = 93$ , $93^2 = 47$ , $93^4 = 152$ , $93^8 = 103$ , $93^{16} = 137$ . $23 = 16+4+2+1$ , so $93^{16} \times 93^4 \times 93^2 \times 93^1 \bmod 187$ : $137 \times 152 \bmod 187 = 67$ , then $67 \times 47 \bmod 187 = 157$ , then $157 \times 93 \bmod 187 = 15$ . The oracle returns $15$ .
$15 = m \cdot r = m \times 5$ , and Eve knows $r = 5$ , so $m = 15 \div 5 = 3$ : the original plaintext, never once decrypted directly, with $d$ never exposed. (In general $m$ is recovered as $15 \times r^{-1} \bmod n$ ; here plain division works because $m \cdot r = 15$ is smaller than $n$ .)

Control

OAEP, Optimal Asymmetric Encryption Padding, is what the lecture names as today’s fix. Padding adds randomness to the message before it is raised to the power $e$ , so encrypting the same plaintext twice under the same key produces two different ciphertexts. That randomness breaks the algebra above: an attacker who multiplies two OAEP-padded ciphertexts together does not get a padded encryption of the product, because the padding does not survive the multiplication cleanly. Malleability is a property of the raw mathematical function; OAEP changes what gets fed into that function.

Mechanism

Why textbook RSA has no semantic security. A cryptosystem is semantically secure when a ciphertext leaks only a small amount of information about its plaintext. Plain RSA is deterministic: the same plaintext under the same public key always produces the same ciphertext. An attacker facing a small or guessable message space can encrypt candidate plaintexts under the known public key and compare the results to the target ciphertext. This is a chosen plaintext attack, and it works precisely because RSA has no randomness of its own. OAEP’s padding is also what supplies the randomness semantic security needs; the fix for malleability and the fix for missing semantic security are the same padding scheme, because both problems trace back to the same cause.

Mechanism

Hybrid encryption. Public-key cryptography solves key distribution but has two practical problems: it can only encrypt numbers, so non-numeric data needs an extra mapping step, and it is slow: the lecture states RSA runs 100 to 1000 times slower than AES. Almost every real system avoids encrypting bulk data with RSA directly. Instead:

Generate a random symmetric key $k$ .
Encrypt the actual message with a symmetric cipher: $c_m = \mathrm{Enc}_k(m)$ .
Encrypt $k$ itself with the receiver’s public key: $c_k = \mathrm{Enc}_{PU}(k)$ .
Send both $(c_k, c_m)$ .

The receiver decrypts $c_k$ with their private key to recover $k$ , then uses $k$ to decrypt $c_m$ with the fast symmetric cipher. RSA’s job shrinks to moving one short key; the symmetric cipher, covered on the AES page, carries everything else.

Aside

The lecture frames this as two separate roles working together, not RSA being replaced: the public key still solves the problem symmetric cryptography cannot (agreeing on a secret with no prior shared key), while the symmetric cipher solves the problem RSA is bad at (encrypting a lot of data quickly).

Exam detail

Three numbers are worth having cold: 2048 bits as the minimum RSA key length the unit treats as secure, the five named attack classes in order (brute force, mathematical, timing, hardware fault, chosen ciphertext), and the malleability identity itself: $c' \equiv c \cdot r^e \pmod n$ decrypts to $m \cdot r$ . A question that gives you a ciphertext and asks what an attacker who never saw the plaintext can still produce is testing this identity directly.

Pitfall

“Textbook RSA is insecure” does not mean the RSA problem itself is broken. Factoring is still believed hard, and a well-chosen key pair is still safe to use. The vulnerability is in using raw, unpadded RSA directly on a message. Padding does not touch key generation at all; it changes what gets encrypted, not how $n$ , $e$ or $d$ are chosen.

Recall

An attacker has two ciphertexts, c1 = E(3) and c2 = E(5), under the same RSA key, and can get any ciphertext decrypted. How do they recover 3 without ever seeing it decrypted directly?

Multiply the ciphertexts: $c' = c_1 \cdot c_2 \bmod n$ . Because RSA preserves multiplicative structure, decrypting $c'$ returns $m_1 \cdot m_2 = 15$ . Since the attacker already knows $m_2 = 5$ from their own ciphertext, they recover $m_1 = 15 \div 5 = 3$ , the plaintext behind $c_1$ , without the private key and without ever submitting $c_1$ itself for decryption.

Source

Week 5 notes PDF