//PtQagain — Writeup

>TL;DR

Recovered the RSA plaintext (the FLAG) by exploiting a leak in the problem where two different expressions are exponentiated with the same exponent and modulus. The equality of the two ciphertexts implies a multiplicative relation that yields a nontrivial factor of N via gcd. With the factor, we recover the private key and decrypt the flag.

Flag: TSGCTF{p+q_4nd_p+q_b3in9_th3_s4me_1s_0bv1ous_ri9h7?aZ3mQ9Lk7P2xB8R}

>Files in this challenge

• problem.py — provided; performs the (vulnerable) computations and prints results.

• output.txt — result of running problem.py (contains N, e1, e2, c, c1, c2).

• solve.py — solver I wrote to automatically recover the flag.

• writeup.md — this file.

>What the challenge does (essential parts of problem.py)

Relevant code (short):

So the program prints N, e1, e2, the ciphertext c = m^e1 mod N, and two values c1 and c2:

• c1 = (p + q)^e2 mod N (sum of primes, exponentiated)

• c2 = int(str(p) + str(q))^e2 mod N (concatenation of decimal representations, exponentiated)

In the provided output.txt we observe c1 == c2.

>Key observation (the exploitation idea)

Let k be the number of decimal digits of q. The concatenation int(str(p) + str(q)) equals p * 10^k + q.

Consider these values modulo q:

• p + q ≡ p (mod q)

• p * 10^k + q ≡ p * 10^k (mod q)

Raising both sides to the power e2 (mod q) gives:

(p + q)^{e2} ≡ p^{e2}  (mod q)

(p * 10^k + q)^{e2} ≡ p^{e2} * 10^{k*e2}  (mod q)

Given c1 == c2 (mod N), these two are also equal modulo q, so

p^{e2} * (10^{k*e2} - 1) ≡ 0  (mod q)

Because p is not divisible by q (distinct primes), p^{e2} is invertible modulo q, so we must have

10^{k*e2} ≡ 1  (mod q)

Hence q divides 10^{k*e2} - 1.

Therefore, for the correct k, gcd(10^{k*e2} - 1, N) will reveal a non-trivial factor of N (either p or q). Brute-force k over a reasonable range (digit lengths or small numbers) and compute that gcd to get a factor.

>Reproducing the exploit (commands and terminal output) 🖥️

1. Inspect the provided output.txt (shows the important values):

Note: c1 and c2 are equal in the output.

1. Brute-force k and compute gcd(pow(10, k*e2, N) - 1, N) until a non-trivial factor is found. Example run (I used a small script):

After finding the factor g we set p=g and q=N//p and continue to RSA-decrypt c using d = inverse(e1, (p-1)*(q-1)) and m = c^d mod N.

1. I also created solve.py to automate the process; running it prints the flag:

(Exact terminal snippets above were captured during solving and are reproduced here for clarity.)

>The solver code

The full solver (also in this folder as solve.py):

#!/usr/bin/env python3

from math import gcd, isqrt

from Crypto.Util.number import long_to_bytes, inverse

  

# Values from output.txt

N = 84159910463788228086784...5637093

  

e1 = 65537

e2 = 65583

c = 55741653752425243335738266109...06912900

  
  

def recover_factor_via_decimal_concat_property(N: int, e2: int) -> int:

    """Exploit c1 == c2 from problem.py.

  

    From c1 == c2 we get 10^(k*e2) == 1 (mod q) for some decimal digit-length k,

    hence q | (10^(k*e2)-1). Brute-force k and compute gcd(10^(k*e2)-1, N).

    """

    approx_digits = len(str(isqrt(N)))

    for k in range(max(1, approx_digits - 200), approx_digits + 201):

        g = gcd(pow(10, k * e2, N) - 1, N)

        if 1 < g < N:

            return g

    raise RuntimeError("No factor found; widen k search range")

  
  

def main() -> None:

    p = recover_factor_via_decimal_concat_property(N, e2)

    q = N // p

    phi = (p - 1) * (q - 1)

    d = inverse(e1, phi)

    m = pow(c, d, N)

    print(long_to_bytes(m).decode(errors="replace"))

  
  

if __name__ == "__main__":

    main()

(Replace truncated numeric literals above with the full values from output.txt if you copy/paste.)

>Why this worked / intuition

• The program leaks two exponentiations where one is the arithmetic sum p + q and the other is the decimal concatenation int(str(p) + str(q)).

• Working modulo one of the primes (say q) reduces these to different expressions that differ by a multiplicative factor of 10^{k*e2}.

• Because the two exponentiations are equal mod q (due to c1 == c2), that multiplicative factor must be 1 modulo q, giving the congruence used to compute a gcd-based factor.

• This is a classic example of using small algebraic relationships and modular arithmetic to turn a leak into a factorization.

>Notes & references

• The short book-style text on modular arithmetic and RSA: Boneh & Shoup, A Graduate Course in Applied Cryptography (useful for understanding modular orders and gcd tricks). 🔧

• Crypto StackExchange and many CTF writeups show similar tricks of forming gcds of (a^k - 1) with N to get factors when a has small order modulo a factor.

>Final remarks

• This challenge is a great example where careful reading of the code and observation of equal outputs (c1 == c2) suggests a modular property to exploit.

• Keep an eye out for places where values are represented differently (sum vs concatenation) — the representation itself can leak useful algebraic structure!