THE GARDEN

Franklin-Reiter Related Message Attack

Updated 13 Sep 2026

• •

  What it is

  • •

    If the same RSA key is used to encrypt two messages related by a known, public affine relationship — $m_2 = \alpha \cdot m_1 + \beta$ for known $\alpha, \beta$ — an attacker who sees both ciphertexts can recover both messages without factoring $N$ or knowing the private key. Both $f_1(X) = X^e - c_1$ and $f_2(X) = (\alpha X + \beta)^e - c_2$ have $m_1$ as a root modulo $N$; computing their polynomial GCD over the ring $\mathbb{Z}_N[X]$ generically collapses to a single linear factor $(X - m_1)$, directly revealing $m_1$ — exactly analogous to ordinary integer GCD, just one polynomial ring up.

• •

  When to apply

  • •

    The same plaintext gets encrypted more than once under the same key with different, but affinely-related, "padding" (e.g. random linear padding $a \cdot m + b$ re-rolled on every request) — the "relatedness" is that both encrypted values are affine functions of the same underlying secret, exactly what Franklin-Reiter needs.

• •

  Math

  • •

    Given $c_1 = m^e \bmod N$ and $c_2 = (\alpha m+\beta)^e \bmod N$, define $f_1(X) = X^e - c_1$, $f_2(X) = (\alpha X+\beta)^e - c_2$ over $\mathbb{Z}_N[X]$; $\gcd(f_1,f_2)$ generically equals $(X-m)$ up to a scalar, so making it monic and negating the constant term gives $m$ directly.

• •

  Worked example

  • •

    A hand-rolled polynomial GCD (no Sage) over $\mathbb{Z}_N[X]$ for $e=11$ and two random affine pads of the same secret message correctly reduced to a degree-1 polynomial, and negating its constant term recovered the exact original message.

• •

  Python

  • •

    # polynomial arithmetic needs to be done mod N at every coefficient step;
    # Sage's native polynomial rings handle this far more cleanly than hand-rolled
    # lists (see below) -- shown here only to confirm the technique works without it
    def poly_gcd(f1, f2):
            a, b = f1, f2
            while not is_zero(b):
                _, r = poly_divmod(a, b)
                a, b = b, r
            return poly_monic(a)   # coefficients reduced mod N throughout
    

• •

  SageMath

  • •

    R.<X> = Zmod(N)[]
    f1 = X**e - c1
    f2 = (alpha*X + beta)**e - c2
    g = f1.gcd(f2)              # Sage's polynomial rings support gcd() natively over Zmod(N)[X]
    m = -g.monic()[0]
    

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Coppersmith's Method for Stereotyped-Partially-Known Messages

◌ Explore connections in Graph view