Related Messages picoCTF 2026 Solution

Description

1. Step 1

   Identify the Franklin-Reiter attack

   Observation

   I noticed that chall.py encrypts two related messages under the same RSA key with a small exponent (e = 17) and explicitly prints the difference between them, which are exactly the conditions for the Franklin-Reiter related-message attack where the two plaintexts share a known linear relationship.

   chall.py uses one RSA public key (N, e) with e = 0x11 = 17 to encrypt two related messages: the original Message and the typo-fixed Message_fixed. It prints the two ciphertexts, then the known difference (Message - Message_fixed), then N. So m1 and m2 satisfy m1 = m2 + k for a known constant k, and Franklin-Reiter's related-message attack recovers both via a polynomial GCD over Z/NZ. The GCD path works for any small exponent, so it applies directly to e = 17.

   Learn more

   The Franklin-Reiter related-message attack (1995) exploits RSA with a small public exponent when the same key encrypts two messages with a known linear relationship. If m1 = m2 + k (here a single-character typo correction, and k is printed by chall.py), an attacker recovers both plaintexts without factoring N. This challenge uses e = 17, so the closed-form trick written for e = 3 does not apply; the polynomial-GCD form does, for any small e.

   The intuition is algebraic: c1 = m1^e mod N and c2 = m2^e = (m1 - k)^e mod N, so m1 is a common root of the two known polynomials f1(x) = x^e - c1 and f2(x) = (x - k)^e - c2 over Z/NZ. Their GCD is the degree-1 factor x - m1.

   Why the GCD reveals the plaintext. If f1 and f2 share the 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 over Z/NZ runs in O(e^2) ring operations - perfectly fast for e = 17 - and the final degree-1 remainder is x - m1, whose negated constant term is the plaintext.

   Polynomial-GCD setup, any small e (here e = 17), m1 = m2 + k:
     f1(x) = x^e - c1            (root x = m1)
     f2(x) = (x - k)^e - c2      (root x = m2 + k = m1)
   
   Run the Euclidean polynomial GCD over Z/NZ:
     while b != 0:  a, b = b, a mod b
     return a.monic()
   
   Each step makes the divisor monic (multiply by the inverse of its
   leading coefficient mod N) so the division is well-defined, then
   takes the remainder. The chain terminates at a degree-1 polynomial
   gcd(f1, f2) = x - m1. Read the plaintext directly:
      m1 = -gcd.constant_coefficient()   in SageMath.
   
   This is the general method and is what you should use for e = 17.
   
   (Aside, e = 3 ONLY) When e = 3 the GCD collapses to a one-line
   closed form, m1 = k*(c2 + 2*c1 - k^3) / (c2 - c1 + 2*k^3) mod N.
   This does NOT generalise to e = 17 - do not use it here. It is
   listed only to flag that some related-message writeups assume e = 3.

   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 two related messages under raw RSA with a small exponent 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 2

   Extract the values from output.txt

   Observation

   I noticed that the attack requires four concrete values (c1, c2, the constant k, and N), and chall.py prints all of them to output.txt while the exponent e = 0x11 = 17 is hardcoded in the script, so reading these values was the necessary prerequisite before any computation could begin.

   output.txt holds, in order: the two ciphertexts (c1 of the original message, c2 of the fixed message), then the difference Message - Message_fixed (this is the known constant k = m1 - m2), then the modulus N. The exponent e = 0x11 = 17 is read from chall.py. So you have c1, c2, k, N, and e = 17 - everything the GCD attack needs.

   bash

   cat output.txt

   Copied!

   bash

   grep -n 'e =' chall.py   # confirms e = 0x11 (17)

   Copied!

   What didn't work first

   Tried: Assume e = 65537 (the common default) without checking chall.py, then complain the attack is too slow.

   The polynomial GCD Euclidean chain runs in O(e^2) ring operations, so e = 65537 would be computationally infeasible. chall.py explicitly sets e = 0x11 = 17, which is the whole reason Franklin-Reiter is fast here. Always verify the exponent from the source file rather than assuming the production default.

   Tried: Treat the printed difference as m2 - m1 (subtraction in the other order), plugging in the wrong sign for k.

   chall.py outputs Message - Message_fixed, so k = m1 - m2 where m1 is the original typo message. If you reverse the sign, f2 = (x + k)^e - c2 instead of (x - k)^e - c2, and the GCD will not terminate at a degree-1 factor. The recovered integer will be garbage. Flip the sign of k in the polynomial and re-run if the output bytes are not valid ASCII.

   Learn more

   In RSA, the public key is the modulus N (product of two large primes) and the public exponent e. Common choices are 3, 17, or 65537. This challenge uses e = 17 (0x11 in chall.py), which is small enough that the related-message attack works but large enough that the e = 3 closed-form shortcut does not apply.

   The constant k = m1 - m2 is the difference between the two messages - the single-character typo correction - and chall.py prints it directly, so it is fully known. A known linear offset is exactly what Franklin-Reiter requires. (Even an unknown offset could be attacked with Coppersmith short-pad methods, but that is unnecessary here since the difference is given.)

3. Step 3

   Apply the Franklin-Reiter attack (polynomial GCD, e = 17)

   Observation

   I noticed that both ciphertexts produce polynomials sharing the common root m1 over Z/NZ (specifically f1 = x^e - c1 and f2 = (x - k)^e - c2), and the polynomial Euclidean GCD directly extracts that shared root as the degree-1factor x - m1 without requiring factorization of N.

   Construct f1 = x^e - c1 and f2 = (x - k)^e - c2 over Z/NZ with e = 17 and k = m1 - m2 (the printed difference), then compute their polynomial GCD. The result is x - m1; read m1 as the negated constant coefficient and convert it to bytes for the flag.

   python

   # Franklin-Reiter via polynomial GCD - works for e = 17
   sage << 'EOF'
   N  = YOUR_N
   e  = 17                 # 0x11 from chall.py
   c1 = YOUR_C1            # ciphertext of the original message
   c2 = YOUR_C2            # ciphertext of the fixed message
   k  = YOUR_K             # printed difference: m1 - m2
   
   R.<x> = Zmod(N)['x']
   f1 = x^e - c1
   f2 = (x - k)^e - c2     # m2 = m1 - k, so its root is also m1
   
   def gcd_poly(a, b):
       while b:
           a, b = b, a % b
       return a.monic()
   
   g = gcd_poly(f1, f2)
   m1 = int(-g.constant_coefficient())
   print(bytes.fromhex(hex(m1)[2:]))
   # (m2 = m1 - k recovers the second message if you need it.)
   EOF

   Copied!

   Expected output

   picoCTF{fr4nkl1n_r31t3r_...}

   What didn't work first

   Tried: Apply the e = 3 closed-form shortcut: m1 = k*(c2 + 2*c1 - k^3) / (c2 - c1 + 2*k^3) mod N.

   The closed form is a special case derived by fully expanding the e = 3 GCD and solving analytically. It does not generalise - when e = 17, the polynomial has degree 17 and the cancellation that collapses it to a single fraction no longer holds. You will get a nonsense integer that does not decode to readable bytes. Use the iterative polynomial GCD loop, which works for any small e.

   Tried: Use plain Python integers for the polynomial arithmetic instead of SageMath's Zmod(N) ring, computing remainders with Python's % operator.

   Python's % for integers works on the coefficients individually but does not automatically reduce a polynomial remainder modulo N at each division step. Without the ring structure, intermediate coefficients grow to thousands of digits and the algorithm either hangs or produces wrong remainders. SageMath's Zmod(N)[] ring reduces every coefficient mod N after each operation, keeping the computation tractable and mathematically correct.

   Learn more

   Note the sign of k: chall.py prints Message - Message_fixed, so with m1 the original and m2 the fixed message, k = m1 - m2 and m2 = m1 - k. That is why f2 = (x - k)^e - c2. If your recovered bytes look wrong, flip the sign of k (i.e. try (x + k)^e - c2) to match which ciphertext you labelled c1 vs c2.

   SageMath is the standard computer algebra system for these challenges. The ring syntax R.<x> = Zmod(N)[] creates polynomials over the integers mod N, reducing modulo N at every step - essential for working in Z/NZ where plain Python arithmetic would not reduce correctly.

   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.

Flag

The flag is recovered with the Franklin-Reiter related-message attack on RSA with e = 17 (0x11 in chall.py). Use the polynomial-GCD form, which works for any small e; the e = 3 closed-form shortcut does not apply here.