InfoSec 3001 — Information Security from the Offensive Perspective

Step 229. RSA Attacks 1: Small e, Common Modulus — The Moment Implementation Mistakes Become Mathematical Weaknesses

Step 229. RSA Attacks 1: Small e, Common Modulus — The Moment Implementation Mistakes Become Mathematical Weaknesses

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★☆☆ | Estimated time: 4 hours

Prerequisites: Step 228 (full RSA implementation) — today you break the "textbook RSA" you built in that chapter.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

  • What you need: Python 3 (measured: 3.12.14), the prime-generation code from Step 228. Standard library only.
  • Caution: today’s attacks target only keys you generated yourself. Running this code against someone else’s key and knowing how your own key breaks are entirely different things.

In Step 228 you built the RSA castle. Today you find and pull out two of its weak stones. First, if the public exponent e is small and the message is also small, m^e never exceeds n, so the mod operation never even engages — the integer cube root of the ciphertext is the plaintext. Second, if the same n is reused to encrypt the same message under different e values, the extended Euclidean algorithm (Step 227) alone recovers the plaintext. Both are vulnerabilities made not by math but by "implementation habits," and both are staple material for CTF Crypto problems.

1. Learning Objectives

By the end of this chapter, you will be able to:

  • Recover plaintext via the integer cube root when e=3 and m^3 < n
  • Extend the attack with c + k·n search when m^e slightly exceeds n
  • Recover plaintext from two ciphertexts encrypted under the same n with different e values, using the extended Euclidean algorithm (common modulus attack)
  • State precisely the conditions under which these attacks work, and explain why padding (OAEP) defends against them

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

Category Details
Language/environment Python 3 (measured: 3.12.14) — standard library only, nothing to install
Today’s commands pow(c, a, n) (including negative exponents), a hand-rolled iroot() (integer k-th root), egcd()
Concepts needed Step 227 (extended Euclidean algorithm, inverses) + all of Step 228 (RSA key structure)
Today’s deliverable A small-e attacker + a common-modulus attacker — both recovering plaintext in live runs

2-1. The Small-e Attack — If mod Never Engages, It Isn’t Encryption

RSA encryption is c = m^e mod n. But if m^e < n, taking the remainder changes nothing — c = m^e, period. The attacker just computes the integer e-th root of c. Encrypt a short message (say, a 30-byte flag) with e=3 and no padding, and against a 1024-bit n this condition holds easily.

The attack extends even when m^3 barely exceeds n. If the k in c = m^3 - k·n is small, add c + k·n repeatedly and find the k where the cube root comes out an integer. If k is a few hundred or less, it’s milliseconds of work.

2-2. The Common Modulus Attack — Two Keys on the Same Lock

Suppose two recipients (or two systems) sharing the same n each encrypted the same message m with their own e:

c1 = m^e1 mod n
c2 = m^e2 mod n

If gcd(e1, e2) = 1, the extended Euclidean algorithm gives integers a, b with a·e1 + b·e2 = 1. Then:

c1^a × c2^b ≡ m^(a·e1 + b·e2) ≡ m^1 ≡ m  (mod n)

Out comes m — no private key d, nothing but public information. The egcd you learned in Step 227 becomes attack code as-is.

2-3. Why This Doesn’t Break in Practice — Padding

Production RSA never raises the raw plaintext to the exponent. OAEP padding mixes random bits into the plaintext, making m a large number close to n, and a different value every time. The m^e < n condition becomes physically impossible, and the premise "the same message" itself disappears. Today’s attacks work only against "padding-free textbook RSA" and "design mistakes" — and CTF turns exactly those mistakes into problems.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14. Keys are regenerated at random every run, so your numbers will differ.

3-1. Setup: Key Generation and the Integer k-th Root

Bring over is_probable_prime and gen_prime from Step 228 as-is. As an attack tool, build one integer k-th root function — floating-point c ** (1/3) loses precision on large numbers (Wall 1), so use binary search.

def iroot(c, k):
    # integer k-th root via binary search. Returns (root, exact?)
    lo, hi = 1, 1 << ((c.bit_length() + k - 1) // k + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** k <= c:
            lo = mid
        else:
            hi = mid - 1
    return lo, lo ** k == c

p, q = gen_prime(512), gen_prime(512)
n = p * q
print("n bits:", n.bit_length())

n bits: 1024

3-2. Attack 1: e=3, Recovering Plaintext via Cube Root

e = 3
msg = b"flag{tiny_e}"
m = int.from_bytes(msg, "big")
c = pow(m, e, n)
print("m^3 == c (equal without mod?):", m**3 == c)   # below n, so mod never engaged

root, exact = iroot(c, 3)
print("integer cube root exact?:", exact)
rec = root.to_bytes((root.bit_length() + 7)//8, "big")
print("recovered plaintext:", rec)

m^3 == c (equal without mod?): True
integer cube root exact?: True
recovered plaintext: b'flag{tiny_e}'

How to read the output: m^3 == c being True means the mod n operation never applied even once — the ciphertext is literally the plaintext cubed. Take the cube root and the flag pops out. No key needed, no factoring of n needed. This isn’t cryptology; it’s arithmetic.

3-3. Attack 1b: Barely Over n — The c + k·n Search

Grow the message a bit so m^3 exceeds n (measured: a 43-byte message), and the cube root no longer comes out exact. In that case, search while adding k.

msg2 = b"A" * 26 + b"a tiny bit longer"   # 43 bytes
m2 = int.from_bytes(msg2, "big")
print("m2^3 < n ?", m2**3 < n, " / m2^3 // n =", m2**3 // n)
c2 = m2**3 % n
for k in range(200):
    root, exact = iroot(c2 + k*n, 3)
    if exact:
        print("found k:", k)
        print("recovered:", root.to_bytes((root.bit_length()+7)//8, "big"))
        break

m2^3 < n ? False  / m2^3 // n = 7
found k: 7
recovered: b'AAAAAAAAAAAAAAAAAAAAAAAAAAa tiny bit longer'

How to read the output: m^3 was just over 7 times n, and an exact cube appeared at k=7. Since m^3 = c + k·n, this attack is practical only "when k is small" — when m^3 // n is a few hundred or less, as measured. As the message approaches n, k grows astronomically and this method goes limp.

3-4. Attack 2: Common Modulus

Assume you intercepted two ciphertexts of the same message, encrypted under the same n with e1=3 and e2=65537.

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

e1, e2 = 3, 65537
m3 = int.from_bytes(b"same message, same n", "big")
c1 = pow(m3, e1, n)
c2 = pow(m3, e2, n)

g, a, b = egcd(e1, e2)
print("gcd(e1,e2) =", g, "| a =", a, "| b =", b)
print("a*e1 + b*e2 =", a*e1 + b*e2)

m3r = (pow(c1, a, n) * pow(c2, b, n)) % n   # b<0 → pow handles the inverse automatically
print("common modulus recovery:", m3r.to_bytes((m3r.bit_length()+7)//8, "big"))
print("matches original:", m3r == m3)

gcd(e1,e2) = 1 | a = 21846 | b = -1
a*e1 + b*e2 = 1
common modulus recovery: b'same message, same n'
matches original: True

How to read the output: a·e1 + b·e2 = 21846×3 + (-1)×65537 = 1 — Step 227’s extended Euclidean algorithm verbatim. Note b is negative; Python 3.8+’s pow(c2, -1, n) computes the modular inverse automatically (version requirement, Wall 2). The plaintext was recovered from public values (n, e1, e2, c1, c2) alone.

3-5. Defense Check — Why Practice Doesn’t Break

Summarize the two attacks’ shared premises: ① no padding (small m), ② n reuse, ③ the same message repeated. OAEP padding turns the plaintext into a large, near-n value that’s different every time, breaking all three at once. The defense isn’t "a bigger key" — it’s "an implementation that follows the rules."

4. Missions & Exercises

Mission — The RSA Attack Toolbox rsa_attacks.py

  1. Organize today’s two attacks into functions — small_e_attack(c, e, n, max_k=1000) (merging 3-2 and 3-3; returns None if not found) and common_modulus_attack(c1, c2, e1, e2, n) (returns the recovered m)
  2. Give each function clear failure conditions via assert or return values — with comments on which conditions fail and why
  3. Write a demonstration script: generate a vulnerable key, print scenes where both attacks succeed, and a scene where small_e_attack returns None for a large m
  4. (Optional) Measure each attack’s runtime with time and attach it to the output — the point is that both come in under a second

Exercises

Exercise 1. With e=3, how many bits or fewer must the plaintext m be for m^3 < n (1024-bit n) to hold? Convert it to bytes.

Exercise 2. In the common modulus attack, what if gcd(e1, e2) is not 1 but 3? Instead of m, what power of m gets recovered? Explain.

Exercise 3. Why does n-sharing happen at all? Apart from the common modulus attack, point out one more fundamental problem with the design "the whole company shares one n, and each employee is issued a different (e, d)" (hint: what an employee who knows d can do).

Exercise 4. Explain by what mechanism OAEP padding blocks each of today’s two attacks, pairing each with the attack’s precondition.

5. Model Answers & Completion Criteria

Mission Model Answer

def small_e_attack(c, e, n, max_k=1000):
    """Find k such that c + k*n is an exact e-th power; return m. None if not found."""
    for k in range(max_k):
        root, exact = iroot(c + k * n, e)
        if exact:
            return root
    return None

def common_modulus_attack(c1, c2, e1, e2, n):
    g, a, b = egcd(e1, e2)
    if g != 1:
        return None          # if gcd isn't 1, only m^g can be recovered
    return (pow(c1, a, n) * pow(c2, b, n)) % n

Grading criteria: ① both attacks match the original under == on a vulnerable key ② small_e_attack returns None for a large m (reporting failure rather than silently returning a wrong value is the key) ③ the comments’ failure conditions match the text’s conditions (m^e size, gcd(e1,e2)).

How to verify: generate a fresh key, run twice, and check the success/failure judgments are the same both times. Judgments that stay stable over random keys mean the attacker implemented the conditions precisely.

Exercise Answers

Answer 1. For m^3 < 2^1024, you need m < 2^(1024/3) ≈ 2^341.3, i.e., about 341 bits or fewer. In bytes, 42 bytes (336 bits) is roughly the ceiling — in measurement, the 43-byte message had already left the condition at m^3 // n = 7. Short flags and session keys (16–32 bytes) are unconditionally inside this range at e=3.

Answer 2. Since a·e1 + b·e2 = 3, what gets recovered is c1^a × c2^b ≡ m^3 (mod n). If m is small enough that m^3 < n, you can go on to m via cube root as in 3-2; if not, you stop with just m^3 mod n. That these two attacks chain like this is the charm of Crypto problems.

Answer 3. Any single employee who knows n and their own (e, d) can factor n using the fact that e·d - 1 is a multiple of φ(n) (a known probabilistic technique). In other words, sharing n equals "everyone who knows their own private key holding a master key that opens the whole company’s secrets." The common modulus attack needs only ciphertexts, but this problem means one leaked key collapses everything — both stem from reusing n.

Answer 4. The small-e attack’s premise is m^e < n; OAEP attaches a random seed and padding before the plaintext, making the encoded m near-n in size, so the premise can’t hold. The common modulus attack’s premise is "both ciphertexts encode the same m"; OAEP’s random seed makes even identical plaintexts encode to a different m each time, so c1^a × c2^b becomes meaningless. Padding doesn’t "change the math" — it "removes the attacks’ premises."

Completion Criteria Checklist

  • [ ] I implemented iroot() with binary search and can explain why c ** (1/3) is dangerous
  • [ ] I recovered plaintext via cube root under e=3, m^3 < n
  • [ ] I recovered the slightly-over-n case too via c + k·n search
  • [ ] I found a, b with egcd and succeeded at the common modulus attack in a live run
  • [ ] I know pow(x, negative, n) auto-handles inverses in Python 3.8+
  • [ ] I can state each attack’s working condition in one sentence
  • [ ] I can explain which premise OAEP breaks for each attack
  • [ ] Mission: rsa_attacks.py complete, both success and failure judgments confirmed in output

6. Common Pitfalls & Fixes

Wall 1. Computing the cube root with c </strong> (1/3) gives a wrong value**

Symptom: int(10<strong>60 </strong> (1/3)) yields 99999999999999737856 — the trailing digits are off (measured 2026-09-09).
Cause: Python floats have 53-bit precision and can’t hold integers with dozens of digits. The result isn’t an integer, so the lo ** k == c check fails forever or you get a wrong plaintext.
Fix: use integer binary search like 3-1’s iroot(). Floating point is forbidden in cryptology.

Wall 2. ValueError: base is not invertible for the given modulus from pow(c2, b, n)

Symptom: ValueError: base is not invertible for the given modulus (measured 2026-09-09).
Cause: when b is negative, pow(c2, b, n) first computes the inverse via pow(c2, -1, n) — if c2 and n aren’t coprime, this error fires. Or on Python 3.7 and below, negative exponents aren’t supported at all.
Fix: in proper RSA the odds of c2 and n sharing a factor are negligible, so if this error appears, check your Python version first (3.8+ required). Manually, it’s the same as pow(pow(c2, -1, n), -b, n).

Wall 3. The common-modulus recovery is weird bytes

Symptom: to_bytes on the recovered m gives something other than the original.
Cause: mostly, the two ciphertexts didn’t come from the same m — if one side alone was padded, or the messages differ slightly, the attack fails silently. Notably, this attack has no "it failed" signal.
Fix: verify by whether the recovery reads as human-legible text. In real CTFs, the problem hands you the hint that the two ciphertexts are "the same plaintext."

Wall 4. small_e_attack exhausts k without finding it

Symptom: it loops to max_k and returns None.
Cause: m^e // n is larger than max_k — the message is longer than you thought. In measurement a 43-byte message was k=7, but at 50 bytes k jumps into the thousands.
Fix: compute the attackability condition first — how much m.bit_length() * e exceeds n’s bit length. If it’s far over, this isn’t a target for this attack.

Wall 5. Direction mistakes with int.from_bytes and to_bytes

Symptom: converting the recovered integer to bytes gives a garbled front or reversed order.
Cause: mixing "big" / "little", or skipping the byte-count computation.
Fix: the Step 228 rule as-is — always convert with "big", and the byte count is (m.bit_length() + 7) // 8. All of today’s attack code runs on top of this conversion.

7. Summary

Today’s Concepts

Concept One-line explanation
Small-e attack If m^e < n, mod never engages and the e-th root of the ciphertext is the plaintext
c + k·n search Extension that adds k to find an exact power when m^e barely exceeds n
Common modulus attack Same n, different e, same m → c1^a × c2^b ≡ m (extended Euclidean)
Integer k-th root iroot — no floating point, binary search mandatory
OAEP padding Makes plaintext large and different every time, removing both attacks’ premises

Today’s Commands & Code

Command What it does
iroot(c, k) Integer k-th root (binary search) — the small-e attack’s core tool
egcd(e1, e2) Compute a, b of a·e1 + b·e2 = gcd — the key to common modulus
pow(c, a, n) Auto-handles inverses for negative a (3.8+) — combines c1^a × c2^b mod n
m.bit_length() Check the attackability condition (size comparison of m^e vs n)
(m.bit_length()+7)//8 Byte-length computation for integer → bytes conversion

An Instinct More Important Than Commands

What broke today isn’t RSA-the-mathematics but "implementations that ignored the math’s premises." One line checking m^e < n, one rule forbidding n reuse, and both attacks are fully blocked. When a CTF hands you an RSA problem, the first questions are always the same — "Is e small? Is n shared? Is m small?" This checklist is today’s real deliverable.

Once every box is checked, Step 229 is complete. Click the checkbox in the sidebar to save your progress.

← 이전 스텝
다음 스텝 →