//The Strongest Exponent

Challenge summary

• Files provided: problem.py, output.txt.

• Goal: Recover the original flag (format TSGCTF{...}) which was converted to an integer m via int.from_bytes(flag.encode(),'big') and encrypted as c = pow(m, e, n).

>TL;DR

• The bug: e = (p ^ q) % phi uses ^ (bitwise XOR) instead of exponentiation; hence the published e equals p XOR q (call it x).

• Using n = p * q and x = p ^ q, we can recover p (and q) bit-by-bit with a small DFS (enforcing p*(p^x) ≡ n (mod 2^k)).

• After factoring, because gcd(e, p-1) = gcd(e, q-1) = 2 (no modular inverse), we invert the exponent by doing successive modular square-root steps until the exponent becomes invertible, then use CRT to recombine candidates.

Recovered flag: TSGCTF{Wait,_caret_is_XOR,_not_power!}

>Files & initial inspection

problem.py (the relevant lines):

p = getPrime(1024)

q = getPrime(1024)

n = p * q

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

e = (p ^ q) % phi

m = int.from_bytes(flag.encode(), 'big')

c = pow(m, e, n)

print(f"n = {n}")

print(f"e = {e}")

print(f"c = {c}")

Note the ^ operator: that is bitwise XOR in Python, not exponentiation. So e is not a normal public exponent but p ^ q reduced modulo phi (in this case, it equals p ^ q).

output.txt contains the triple (n, e, c) published by the challenge. Example (truncated for readability):

I also ran a few quick inspections in the terminal to guide the attack:

Observation: e is about 1020 bits long — roughly the length of p or q — consistent with p ^ q.

>Key idea 1 — Factor from p ^ q and n (bit-by-bit)

If we let x = p ^ q, then q = p ^ x. Since n = p * q = p * (p ^ x), the bits of p are constrained by the congruence modulo powers of two:

For each k, (p * (p ^ x)) mod 2^k must equal n mod 2^k. This allows a branching search where at step k we try setting the k-th bit of p (0/1) and prune if the congruence fails.

This is a standard Hensel-like bit-reconstruction technique and is very efficient (the search is pruned heavily and completes in linear-time in practice for 1024-bit primes because only a few choices remain valid at each bit).

I implemented a recursive DFS which maintains p modulo 2^k and tests the congruence. When all bits are recovered, we verify p * q == n.

Terminal verification included:

>Key idea 2 — Decrypt when exponent is not invertible

After we recovered p and q, we saw:

So e is not invertible modulo φ(n) and we cannot directly compute m = c^{d} mod n in the usual way. However, note:

• Let e = 2^v * t where t is odd (v = v2(e)).

• If gcd(e, p-1) = g (>1), one approach is to take successive modular square roots of c until the reduced exponent e' = e / 2^r is invertible modulo p-1. For each prime modulus, this yields up to 2^r roots from which we compute m modulo p (and modulo q) and then combine via CRT.

In our instance,

• v2(e) = 2 (so e divisible by 4)

• v2(p-1) = v2(q-1) = 1

We need r = minimal integer with gcd(e/2^r, p-1) = 1. That gives r = 2; therefore we take two successive square roots:

1. Find z with z^2 ≡ c (mod p) — so z ≡ m^{2t}.

2. For each such z find w with w^2 ≡ z (mod p) — so w ≡ m^{t}.

3. Because t is odd and gcd(t, p-1) = 1, compute m ≡ w^{t^{-1} (mod p-1)}.

Repeat the same process modulo q. Then combine all pairs using CRT. Check candidates by verifying pow(m_candidate, e, n) == c and by checking ASCII/flag format.

I used Tonelli–Shanks to find modular square roots (it works for any odd prime), then CRT (using modular inverse) to recombine.

Terminal output when solving roots and recombining:

>Reproducible solver (all code)

I included a single solver.py below that does everything: parse output.txt, recover p,q, compute modular roots and CRT, then print the flag.

#!/usr/bin/env python3

# solver.py — Solve 'The Strongest Exponent' by factoring using x = p ^ q and decrypting via successive sqrt + CRT

from Crypto.Util.number import inverse

import math

  

# --- utility: tonelli-shanks (square roots mod prime) ---

  

def tonelli_shanks(a, p):

    a %= p

    if a == 0:

        return 0

    if pow(a, (p - 1) // 2, p) != 1:

        return None

    if p % 4 == 3:

        return pow(a, (p + 1) // 4, p)

    # Factor out powers of 2 from p-1

    q = p - 1

    s = 0

    while q % 2 == 0:

        s += 1

        q //= 2

    z = 2

    while pow(z, (p - 1) // 2, p) != p - 1:

        z += 1

    m = s

    c = pow(z, q, p)

    t = pow(a, q, p)

    r = pow(a, (q + 1) // 2, p)

    while t != 1:

        i = 1

        t2i = (t * t) % p

        while i < m and t2i != 1:

            t2i = (t2i * t2i) % p

            i += 1

        b = pow(c, 1 << (m - i - 1), p)

        r = (r * b) % p

        t = (t * b * b) % p

        c = (b * b) % p

        m = i

    return r

  
  

def all_square_roots(a, p):

    r = tonelli_shanks(a, p)

    if r is None:

        return []

    return list({r, (-r) % p})

  

# --- parse output.txt ---

  

def parse_output(path='output.txt'):

    txt = open(path).read()

    n = int(txt.split('n = ')[1].split('\n')[0])

    e = int(txt.split('e = ')[1].split('\n')[0])

    c = int(txt.split('c = ')[1].split('\n')[0])

    return n, e, c

  

# --- factor p from x = p ^ q and n using bitwise DFS ---

  

def recover_primes_from_xor(n, x, bitlen=None):

    if bitlen is None:

        bitlen = x.bit_length()

    sys.setrecursionlimit(10000)

    mask = lambda k: (1 << (k + 1)) - 1

  

    def dfs(k, p_low):

        # k is number of bits placed so far (next bit index to place)

        if k == bitlen:

            p = p_low

            q = p ^ x

            if p * q == n:

                return p, q

            return None

        m = mask(k)

        x_low = x & m

        n_low = n & m

        for pb in (0, 1):

            p2 = p_low | (pb << k)

            q2 = p2 ^ x_low

            if (p2 * q2) & m == n_low:

                res = dfs(k + 1, p2)

                if res:

                    return res

        return None

  

    # Start with LSB of p being 1 (odd prime)

    assert x & 1 == 0 or x & 1 == 1  # just fine

    start = 1

    return dfs(1, start)

  

# --- compute roots modulo prime given non-invertible exponent e ---

  

def invert_exponent_using_sqrts(c, prime, e):

    # find minimal r >= 0 so that gcd(e//(2**r), prime-1) == 1

    r = 0

    while math.gcd(e >> r, prime - 1) != 1:

        r += 1

    # perform r successive sqrt operations

    cur = {c % prime}

    for _ in range(r):

        nxt = set()

        for v in cur:

            roots = all_square_roots(v, prime)

            for root in roots:

                nxt.add(root)

        cur = nxt

    # Now e' = e//(2**r) is invertible mod prime-1

    e_odd = e >> r

    inv = inverse(e_odd, prime - 1)

    return [pow(w, inv, prime) for w in cur]

  

# --- CRT combine and test ---

  

def crt_combine(ap, aq, p, q):

    inv_p_mod_q = inverse(p, q)

    t = ((aq - ap) % q) * inv_p_mod_q % q

    return ap + t * p

  

# --- helper to test and decode flag candidate ---

  

def try_candidates(cands, n, e):

    for m in cands:

        if pow(m, e, n) != c:

            continue

        b = m.to_bytes((m.bit_length() - 1) // 8 + 1, 'big')

        try:

            s = b.decode()

        except Exception:

            continue

        if s.startswith('TSGCTF{') and s.endswith('}'):

            return s

    return None

  

# --- main ---

if __name__ == '__main__':

    import sys

    n, e, c = parse_output(sys.argv[1] if len(sys.argv) > 1 else 'output.txt')

    print('n bits', n.bit_length())

    print('e bits', e.bit_length())

  

    # x is p^q because of the bug

    x = e

    print('assuming x=p^q (XOR)')

  

    p, q = recover_primes_from_xor(n, x, bitlen=(x.bit_length() or 1024))

    print('found p bits', p.bit_length(), 'q bits', q.bit_length())

  

    # compute candidates modulo each prime

    mp = invert_exponent_using_sqrts(c, p, e)

    mq = invert_exponent_using_sqrts(c, q, e)

    print('solutions mod p', len(mp))

    print('solutions mod q', len(mq))

  

    cands = []

    for ap in mp:

        for aq in mq:

            m = crt_combine(ap, aq, p, q)

            cands.append(m)

    print('crt candidates', len(cands))

  

    flag = try_candidates(cands, n, e)

    if flag:

        print('FLAG', flag)

    else:

        print('No valid flag found among candidates')

Usage:

>Why this approach?

• The immediate giveaway was the ^ operator in problem.py. In Python ^ is XOR, not exponentiation. Since p and q are ~1024-bit primes, p ^ q is also ~1024 bits and when used modulo phi it remained unchanged in the provided instance.

• If we know x = p ^ q and n = p*q, then p and q satisfy simple bitwise congruences mod powers of two. Recovering p bit-by-bit is an application of modular lifting (Hensel type) and works well in practice because at each bit only a few choices survive.

• Once factors are known, the exponent's gcd with p−1 caused the usual modular inverse to fail, but the number-theoretic trick of taking modular square roots enough times until the remaining exponent is odd (invertible) allowed us to recover m modulo each prime and assemble the final message.

>References & further reading

• Tonelli–Shanks algorithm — Wikipedia: https://en.wikipedia.org/wiki/Tonelli–Shanks

• Chinese Remainder Theorem — Wikipedia: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

• Crypto.SE discussion on factoring with XOR knowledge (example discussion thread): https://crypto.stackexchange.com/questions/3089/factorization-given-p-xor-q-and-n

• Practical examples of bit-by-bit recovery (Hensel-lifting style) are common in CTF writeups and blog posts (search for "recover p from p xor q" or "factoring given xor" ).

>Final notes and lessons learned

• Small coding mistakes (using the wrong operator) can completely break cryptographic assumptions.

• Always sanity-check what the published public exponent actually is: is it small (like 65537), or is it suspiciously similar in size to p/q? If the latter, inspect the code carefully.

• When the exponent is not invertible, remember that repeated square roots + modular inversion of the odd part can recover the plaintext when the exponent's power-of-two part is not too large and relevant inverses exist.