PtQagain

Attachment:

from secret import p, q
import os
from Crypto.Util.number import bytes_to_long, isPrime

assert isPrime(p) and p.bit_length() <= 512
assert isPrime(q) and q.bit_length() <= 512

with open('flag.txt', 'rb') as f:
    FLAG = f.read()

N = p * q

e1 = 65537
e2 = 65583

m = bytes_to_long(FLAG)
c = pow(m, e1, N)

c1 = pow(p + q, e2, N)

p = str(p)
q = str(q)
c2 = pow(int(p + q), e2, N)

print(f'{N = }')
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{c = }')
print(f'{c1 = }')
print(f'{c2 = }')
N = 8415991046378822808678417368330656853369287762382257778863000234996179456832593823172163438175141897794450973258850755059008064965170892039119019048620633841637561375984016774249397631671121650489315360389403325290330278785155612107593553850666774120554971030956010302235061389242836031692105637093
e1 = 65537
e2 = 65583
c = 5574165375242524333573826610902926393700854735994229967966464169834696611810072076594787795367537651736635669504446868847168099681864093409935801174468222766808668365620150398151512438201199626223130807413078543403236814636420490358773639850910401283271784777683577389622203357416804633487506912900
c1 = 3733372451275945143106630642525005607134287402204217261131967501254130116356869822445109935329406396349828170813887809941457012269457680164427423918812605964033393533444248389803553681873885855742856069057392986629579993551342614294600091763375588208870704928674561853194758243753269168083341300444
c2 = 3733372451275945143106630642525005607134287402204217261131967501254130116356869822445109935329406396349828170813887809941457012269457680164427423918812605964033393533444248389803553681873885855742856069057392986629579993551342614294600091763375588208870704928674561853194758243753269168083341300444

Solved by AI:

TSG CTF 2025 - PtQagain Writeup

Challenge: PtQagain
Category: Crypto
Difficulty: Medium
Author: TSG
Flag: TSGCTF{p+q_4nd_p+q_b3in9_th3_s4me_1s_0bv1ous_ri9h7?aZ3mQ9Lk7P2xB8R}

Challenge Description

I'll give you p + q encrypted twice with the same scheme! It's the same thing anyway, so no problem... right?

We're given a Python script problem.py and its output output.txt. The script encrypts a flag using RSA and also provides some additional encrypted values that leak information about the primes.

Files Provided

  • problem.py - The encryption script
  • output.txt - The output containing public parameters and ciphertexts

problem.py

from secret import p, q
import os
from Crypto.Util.number import bytes_to_long, isPrime

assert isPrime(p) and p.bit_length() <= 512
assert isPrime(q) and q.bit_length() <= 512

with open('flag.txt', 'rb') as f:
    FLAG = f.read()

N = p * q

e1 = 65537
e2 = 65583

m = bytes_to_long(FLAG)
c = pow(m, e1, N)

c1 = pow(p + q, e2, N)

p = str(p)
q = str(q)
c2 = pow(int(p + q), e2, N)

print(f'{N = }')
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{c = }')
print(f'{c1 = }')
print(f'{c2 = }')

output.txt

N = 8415991046378822808678417368330656853369287762382257778863000234996179456832593823172163438175141897794450973258850755059008064965170892039119019048620633841637561375984016774249397631671121650489315360389403325290330278785155612107593553850666774120554971030956010302235061389242836031692105637093
e1 = 65537
e2 = 65583
c = 5574165375242524333573826610902926393700854735994229967966464169834696611810072076594787795367537651736635669504446868847168099681864093409935801174468222766808668365620150398151512438201199626223130807413078543403236814636420490358773639850910401283271784777683577389622203357416804633487506912900
c1 = 3733372451275945143106630642525005607134287402204217261131967501254130116356869822445109935329406396349828170813887809941457012269457680164427423918812605964033393533444248389803553681873885855742856069057392986629579993551342614294600091763375588208870704928674561853194758243753269168083341300444
c2 = 3733372451275945143106630642525005607134287402204217261131967501254130116356869822445109935329406396349828170813887809941457012269457680164427423918812605964033393533444248389803553681873885855742856069057392986629579993551342614294600091763375588208870704928674561853194758243753269168083341300444

Initial Observations

  1. Standard RSA encryption: The flag is encrypted with RSA using e1 = 65537
  2. Interesting leak: Two additional values are encrypted with e2 = 65583:
    • c1 = (p + q)^e2 mod N
    • c2 = (int(str(p) + str(q)))^e2 mod N
  3. Critical observation: c1 = c2 in the output!

The equality c1 = c2 is the key to solving this challenge. It means: 

(p + q)^e2 ≡ (int(str(p) + str(q)))^e2 mod N

Mathematical Analysis

Let's define:

  • x = p + q (integer sum)
  • y = int(str(p) + str(q)) (concatenation of decimal representations)
  • len_q = number of decimal digits in q

Then: 

y = p * 10^len_q + q

From c1 = c2, we have: 

x^e2 ≡ y^e2 mod N

Since N = p * q, we can analyze this modulo q:

  1. x ≡ p + q ≡ p (mod q)
  2. y ≡ p * 10^len_q + q ≡ p * 10^len_q (mod q)
  3. Therefore: p^e2 ≡ (p * 10^len_q)^e2 ≡ p^e2 * (10^len_q)^e2 (mod q)
  4. Assuming p ≠ 0 (mod q) (true since p and q are distinct primes), we can divide by p^e2: 
    (10^len_q)^e2 ≡ 1 (mod q)
  5. Which gives us: 
    10^(len_q * e2) ≡ 1 (mod q)

This is the key insight: q divides 10^(len_q * e2) - 1.

Attack Strategy

Since we know q divides 10^(len_q * e2) - 1, we can try to find q by computing: 

gcd(10^(k * e2) - 1, N)
for reasonable values of k (the candidate for len_q).

We need to estimate len_q: - q is ≤ 512 bits - Number of decimal digits ≈ bits * log10(2) ≈ 512 * 0.3010 ≈ 154 - But N is 990 bits, so p and q are roughly 495 bits each - 495 * log10(2) ≈ 149 decimal digits

So we should search k in the range 140-160.

Exploit Implementation

from Crypto.Util.number import long_to_bytes, GCD

N = 8415991046378822808678417368330656853369287762382257778863000234996179456832593823172163438175141897794450973258850755059008064965170892039119019048620633841637561375984016774249397631671121650489315360389403325290330278785155612107593553850666774120554971030956010302235061389242836031692105637093
e1 = 65537
e2 = 65583
c = 5574165375242524333573826610902926393700854735994229967966464169834696611810072076594787795367537651736635669504446868847168099681864093409935801174468222766808668365620150398151512438201199626223130807413078543403236814636420490358773639850910401283271784777683577389622203357416804633487506912900

# Search for the correct digit length of q
for k in range(140, 160):
    value = pow(10, k * e2, N) - 1
    g = GCD(value, N)

    if g > 1 and g < N:
        q = g
        p = N // q

        # Decrypt the flag
        phi = (p - 1) * (q - 1)
        d = pow(e1, -1, phi)
        m = pow(c, d, N)
        flag = long_to_bytes(m)

        print(f"Found with k={k}: {flag}")
        break

Results

The exploit finds a factor when k = 144:

  • q = 899718757349577828631761341730093220713822770643140264600436229195941807849819816835925771559643276518390048146301688389176642719947087961896703
  • q has 479 bits and 144 decimal digits
  • p = N // q has 512 bits and 154 decimal digits

Decrypting the flag gives: 

TSGCTF{p+q_4nd_p+q_b3in9_th3_s4me_1s_0bv1ous_ri9h7?aZ3mQ9Lk7P2xB8R}

Why This Works

The challenge creator made a subtle but critical mistake: they assumed that encrypting p+q and the concatenation of p and q as strings would produce different ciphertexts. However, when these values are encrypted with the same exponent e2 modulo N, and the resulting ciphertexts are equal, it reveals a mathematical relationship between p, q, and N.

The equality c1 = c2 implies that (p+q)^e2 ≡ (p*10^len_q + q)^e2 mod N. When analyzed modulo q, this simplifies to 10^(len_q * e2) ≡ 1 mod q, which means q divides 10^(len_q * e2) - 1. Since len_q is the decimal digit length of q (which we can estimate), we can find q by checking gcd(10^(k*e2) - 1, N) for reasonable k values.

Lessons Learned

  1. Never reuse encryption keys/schemes for different values: Even if values seem different (like p+q vs. string concatenation), encrypting them with the same parameters can leak information.

  2. Mathematical relationships matter: The equality of ciphertexts reveals algebraic relationships that can be exploited.

  3. Estimation is key: Knowing approximate sizes (bit lengths, digit lengths) helps narrow down brute-force searches.

  4. Modular arithmetic is powerful: Analyzing equations modulo the unknown factors (p and q) can simplify complex relationships.

Flag

TSGCTF{p+q_4nd_p+q_b3in9_th3_s4me_1s_0bv1ous_ri9h7?aZ3mQ9Lk7P2xB8R}