Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD

Two ciphertexts of RSA-encrypted messages that satisfy a *known* linear relation m2 = a·m1 + b, under the same modulus N and exponent e, leak m1 directly as the root of a degree-1 polynomial GCD — no factoring of N required.

The signal that gives it away

- Two ciphertexts c1, c2 under the same `N` and the same `e`, and the challenge (or its framing) tells you or lets you derive the messages are related — a counter increment, a fixed known offset, two messages that differ only in one known field, "encrypt the flag twice with a one-byte-different prefix," and similar. The relation has to be *known* to you as concrete numbers a, b, not just suspected to exist. - e is small — the classic case is e = 3, and the technique still works for larger e but the polynomial-GCD computation gets more expensive as e grows, so it stops being practical well before e gets large. If e is large (e.g. 65537) this is essentially never the intended path. - Don't confuse this with Common Modulus Attack — same n, two coprime exponents on the same message: that one has the same message encrypted under two different exponents; Franklin–Reiter is the mirror image — different (but related) messages under the same exponent. If the challenge gives you two exponents on one plaintext, you want common-modulus, not this. - If the relation between the two messages is only *partially* known (you know the padding scheme and its length, but not the exact random pad value), that's not this attack — that's Coppersmith's short-pad attack, which needs Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction and a bound on the unknown part rather than an exact known relation.

How it's exploited

The mechanism: build two polynomials over Zmod(N)[x] that both vanish at the unknown message. g1(x) = x^e - c1 has m1 as a root (since c1 = m1^e mod N). g2(x) = (a·x + b)^e - c2 has m1 as a root too, because a·m1 + b = m2 and c2 = m2^e mod N. Both polynomials therefore share the factor (x - m1), and computing their GCD isolates it.

``python # SageMath P.<x> = PolynomialRing(Zmod(N)) g1 = x^e - c1 g2 = (a*x + b)^e - c2 g = g1.gcd(g2) # expect degree 1: g = x - m1 m1 = int(-g.monic().constant_coefficient()) m2 = (a * m1 + b) % N # derive the second message once you have the first ``

- Expect a linear result. A degree-1 GCD is the success condition — it factors as x - m1, and reading off -constant_coefficient (after making the polynomial monic) gives m1 straight away. See Polynomial GCD — the Euclidean algorithm on polynomials, and the trick that recovers a shared root for the underlying Euclidean-algorithm mechanics. - A useful failure mode, not just a dead end: running the Euclidean algorithm on polynomials over Zmod(N) occasionally needs to invert a leading coefficient mod N during a division step. If that coefficient isn't invertible — i.e. it shares a nontrivial factor with N — the GCD step itself throws or breaks down. That failure is informative: taking gcd(that coefficient, N) factors N on the spot. Treat a GCD crash as a lead, not just noise, before assuming your relation is wrong. - Cost scales with `e`. This is the reason the attack is described as an e = 3 technique first and foremost — the field notes and the public sources agree it "works more generally, with increasing cost as e grows." Budget for it only when e is small (roughly single digits to low tens); don't reach for it against RSA with a standard large e. - Once you recover m1, deriving m2 is free (a·m1 + b mod N) — you never need to attack the second ciphertext independently, and you never need to factor N or recover the private exponent d.

What does NOT work

- Assuming the wrong relation and expecting the GCD to "mostly work." If a/b are off — wrong sign, off-by-one on the offset, wrong byte position for the assumed padding — the two polynomials generically share no common root at all, and the GCD comes back as a constant (degree 0), not something close to linear. A non-degree-1 GCD is a hard signal that the assumed relation is wrong, not that the attack needs tuning; go back and re-derive a, b rather than retrying the same computation. - Reaching for this when the relation is unknown, only bounded. If all you know is that two messages differ by *some* short, random padding of a known maximum length — not an exact numeric relation — polynomial GCD alone won't isolate a root. That's the regime for Coppersmith's short-pad attack: it needs the full lattice machinery of Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction (bounding the unknown by N^{1/d} and running LLL), not this direct GCD. Franklin–Reiter is the special case where the relation is fully pinned down as numbers you can write down. - Applying it across different exponents. Two ciphertexts of related messages encrypted with two *different* e values don't share the algebraic structure this attack needs — the polynomials wouldn't have compatible degree in the right variable. If the exponents differ, look at whether the *message* is actually the same one (then it's Common Modulus Attack — same n, two coprime exponents on the same message) or treat it as a fresh problem; don't try to force Franklin–Reiter onto mismatched exponents. - Expecting it to work for large `e`. Nothing about the math forbids a bigger e in principle, but the polynomial-GCD computation (effectively degree-e polynomial arithmetic mod N) gets expensive fast, and by the time e reaches typical real-world values (65537) it is no longer a practical CTF technique — that large an e on related messages is not the intended path; look elsewhere (padding oracle, exponent misuse, a leaked bit) instead of trying to brute the GCD through it.

Related

Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction Common Modulus Attack — same n, two coprime exponents on the same message Polynomial GCD — the Euclidean algorithm on polynomials, and the trick that recovers a shared root RSA Fundamentals — the routing hub: which artifact points to which attack