Related Messages picoCTF 2026 Solution

Description

1. Step 1Identify the Franklin-Reiter attack

   Observation

   chall.py encrypts two related messages under one RSA key with a small exponent, and prints the difference between them. Those are exactly the conditions for the Franklin-Reiter attack: two plaintexts with 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) / (c1 - c2 + 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 solutions 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 2Extract the values from output.txt

   Observation

   The attack needs four values: both ciphertexts, the constant difference, and the modulus. output.txt has all of them, and the exponent is hardcoded in the script.

   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 GCD chain costs on the order of e squared ring operations, so the usual 65537 would be hopeless. chall.py sets the exponent to 17, which is the entire reason this runs fast. Read the exponent from the source 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.

   The script prints the first message minus the corrected one, which fixes the sign of the constant. Get it backwards and the second polynomial is wrong, the GCD never lands on a degree-one factor, and the recovered integer is garbage. If the bytes are not ASCII, flip the sign and run again.

   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 3Apply the Franklin-Reiter attack (polynomial GCD, e = 17)

   Observation

   Each ciphertext gives a polynomial, and both share the first plaintext as a root over the ring modulo N. A polynomial GCD pulls that root out as a degree-one factor, with no factoring of N anywhere.

   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:
           b = b.monic()       # divisor must be monic for % to be well-defined
           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{m3ssage_w1th_...}

   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.

   That closed form comes from expanding the exponent-3 case by hand, and it does not generalize: at degree 17 the cancellation that collapses everything to one fraction no longer happens, so you get a nonsense integer. Use the iterative GCD loop, which works for any small exponent.

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

   Python's modulo works on individual integers and does not reduce a polynomial remainder at each division step. Without the ring, intermediate coefficients grow to thousands of digits and the algorithm hangs or returns wrong remainders. Sage's polynomial ring over the integers mod N reduces after every operation, which keeps it both tractable and 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.