Related Messages picoCTF 2026 Solution

Description

1. Step 1Identify the Franklin-Reiter attack
   The same RSA public key (n, e) is used to encrypt two related messages m1 and m2 where m2 = m1 + k for some small known constant k (a typo correction). With e=3 and a linear relation between the plaintexts, Franklin-Reiter's related-message attack can recover both messages.
   Learn more

   The Franklin-Reiter related-message attack (1995) exploits a fundamental weakness in RSA with small public exponents when the same key is used to encrypt two messages with a known linear relationship. If m2 = a*m1 + b for known constants a and b, an attacker can recover both plaintexts without factoring n. The attack is most devastating with e=3 because the polynomials involved remain small and manageable.

   The intuition is algebraic: since c1 = m1^3 mod n and c2 = (m1+k)^3 mod n, both ciphertexts are roots of known polynomials over Z/nZ. Specifically, f1(x) = x^3 - c1 and f2(x) = (x+k)^3 - c2 share a common root x = m1. Computing their GCD over the polynomial ring recovers a degree-1 polynomial whose root is the plaintext.

   Why the GCD reveals the plaintext. If two polynomials f1(x) and f2(x) share a single common root x = m1, then (x - m1) divides both, so gcd(f1, f2) = (x - m1) up to a constant factor. The Euclidean polynomial GCD algorithm computes this in O(e^2) ring operations. With e = 3, the algorithm performs only a handful of polynomial divisions, and the final remainder is a degree-1 polynomial of the form x - m1. The constant term is the plaintext.

   Polynomial-GCD trace, e = 3, m2 = m1 + k:
     f1(x) = x^3 - c1
     f2(x) = (x + k)^3 - c2
           = x^3 + 3k*x^2 + 3k^2*x + k^3 - c2
   
   Step 1: f2 - f1 (cancels the x^3 term)
     r1(x) = 3k*x^2 + 3k^2*x + (k^3 - c2 + c1)        [degree 2]
   
   Step 2: make r1 monic. Multiply r1 by (3k)^(-1) mod n:
     r1_monic(x) = x^2 + k*x + (k^3 - c2 + c1) * (3k)^(-1)
   
     Why monic? Euclidean polynomial division over Z/nZ requires the
     divisor's leading coefficient to be invertible (and conventionally
     normalised to 1) so the quotient is well-defined. Without monic
     normalisation, dividing f1 by r1 leaves a leading-coefficient term
     that obscures the constant we are after.
   
   Step 3: divide f1 = x^3 - c1 by r1_monic.
     Polynomial long division: x^3 / x^2 = x. Subtract x*r1_monic:
       f1 - x*r1_monic = -k*x^2 - alpha*x - c1
     where alpha = (k^3 - c2 + c1) * (3k)^(-1) mod n.
   
     Continue dividing -k*x^2 - alpha*x - c1 by r1_monic.
     -k*x^2 / x^2 = -k.  Subtract -k * r1_monic:
       remainder r2(x) = (-alpha + k^2)*x + (-c1 + k*alpha)
   
     r2 is degree 1: r2(x) = A*x + B.
   
   Step 4: divide r1_monic by r2. After making r2 monic
     (multiply by A^(-1) mod n), the next remainder is constant.
     At that point gcd(f1, f2) = x - m1 (after dividing through
     by the trailing constant). Read m1 directly:
        m1 = -gcd.constant_coefficient()  in SageMath.
   
   Closed-form shortcut for e = 3 (use this first):
      m1 = k * (c2 + 2*c1 - k^3) / (c2 - c1 + 2*k^3)  (mod n)
     This is what falls out of Steps 1-4 once you simplify symbolically.
     One modular inverse and a few multiplications, milliseconds even
     for 2048-bit n.
   
   Fallback: if the denominator (c2 - c1 + 2*k^3) is not invertible
   mod n (gcd with n != 1), pick a different relation constant k or
   fall back to the full polynomial GCD - the GCD path doesn't need
   that specific inverse.

   SageMath idiom: R.<x> = Zmod(n)[] creates the polynomial ring, .monic() normalises after each division, and -poly.constant_coefficient() reads m1 from the final degree-1 polynomial.

   Encrypting the same message twice under raw RSA is always dangerous. OAEP padding randomises every encryption and kills related-message attacks in one stroke. See RSA attacks for CTF for the full attack catalogue.

2. Step 2Extract the values from output.txt
   Parse output.txt to get n, e, c1 (ciphertext of m1), and c2 (ciphertext of m2), and the relationship constant k.
   bash

   cat output.txt

   Copied!
   Learn more

   In RSA, the public key consists of the modulus n (the product of two large primes p and q) and the public exponent e. Common choices for e are 3, 17, or 65537 (2^16 + 1). Small values like e=3 are computationally efficient but create vulnerabilities when used without proper padding, as demonstrated by this challenge.

   The relationship constant k represents the difference between the two messages - in this scenario, a single character typo correction. This small, known offset is exactly what the Franklin-Reiter attack requires. Even a completely unknown offset could be recovered using the Coppersmith small roots method, making related-message attacks a broad class of RSA weaknesses for small exponents.

3. Step 3Apply the Franklin-Reiter attack
   Try the closed-form shortcut first; it's one line of modular arithmetic. If the denominator is not invertible mod n, switch the relation constant or fall back to polynomial GCD over Z/nZ in SageMath.
   python

   # Fast path: closed-form for e = 3
   python3 << 'EOF'
   n  = YOUR_N
   c1 = YOUR_C1
   c2 = YOUR_C2
   k  = YOUR_K   # m2 = m1 + k
   
   num = k * (c2 + 2*c1 - pow(k, 3, n)) % n
   den = (c2 - c1 + 2 * pow(k, 3, n)) % n
   m1 = (num * pow(den, -1, n)) % n
   print(bytes.fromhex(hex(m1)[2:]))
   EOF

   Copied!

   python

   # Fallback: polynomial GCD in SageMath
   sage << 'EOF'
   n  = YOUR_N
   e  = 3
   c1 = YOUR_C1
   c2 = YOUR_C2
   k  = YOUR_K
   
   R.<x> = Zmod(n)['x']
   f1 = x^e - c1
   f2 = (x + k)^e - c2
   
   def gcd_poly(a, b):
       while b:
           a, b = b, a % b
       return a.monic()
   
   g = gcd_poly(f1, f2)
   m1 = -g.constant_coefficient()
   print(bytes.fromhex(hex(int(m1))[2:]))
   EOF

   Copied!
   Learn more

   SageMath is an open-source computer algebra system built on Python that is the standard tool for cryptographic CTF challenges involving number theory and polynomial arithmetic. Its polynomial ring syntax R.<x> = Zmod(n)[] creates a polynomial ring over the integers mod n, where arithmetic naturally reduces modulo n at every step. This is essential for working in Z/nZ where standard Python integer arithmetic would overflow or give incorrect results.

   The polynomial GCD algorithm over Z/nZ works analogously to the Euclidean algorithm for integers: repeatedly replace (a, b) with (b, a mod b) until b = 0, then return a normalized to be monic (leading coefficient = 1). The result is a degree-1 polynomial x - m1, whose constant term (negated) is the plaintext. The .monic() call normalizes the result so the constant term can be directly read as the root.

   The message is recovered as a large integer, then converted back to bytes using bytes.fromhex(hex(int(m1))[2:]). This strips the 0x prefix and decodes the hex representation into the original message bytes - the standard way to convert between Python big integers and byte strings in cryptographic challenges.

Alternate Solution

Flag

The flag is recovered using the Franklin-Reiter related-message attack on RSA with e=3.