//X_O (Crypto / RSA)

>TL;DR

We abuse the special structure of the primes (bitwise complement plus constant) to factor n, then notice the public exponent is a Mersenne number (2^k - 1) with gcd(e, φ) = 7. We divide the exponent by 7, invert it modulo φ/7, get m^7, take 7th roots modulo each prime, combine with CRT, and recover the flag: nexus{2f13a9d896297558e7c986}.

>Challenge artifacts

• Provided: challenge.py plus printed n and ciphertext.

• Flag format: nexus{...}

>Given code (essentials)

• p = getPrime(L) where L is the bit length (1024-ish).

• q = bitwise_complement_mask(p) + 31337 where bitwise_complement_mask(x) = (2^{bitlen(x)}-1) ^ x (bitwise NOT within the bit-length) and the same +31337 shift.

• n = p * q

• e = 2^k - 1 (unknown k, but a Mersenne form is forced by the assert (e+1) & e == 0).

• ciphertext = m^e mod n for m = flag.

>Observations

1. Complementary primes: With q = (2^L - 1 - p) + 31337, we know p + q = 2^L + 31336. This gives a direct handle to factor n.

2. Bit length: The provided n has 2046 bits, so L ≈ 1024.

3. Mersenne exponent: e = 2^k - 1 for some k. The assertion only enforces the Mersenne shape; k is unknown.

>Factoring n (deterministic)

Let c = 2^L + 31336. Then p + q = c and pq = n. Solve the quadratic:

$$x^2 - c x + n = 0$$

The roots are:

$$p, q = \frac{c \pm \sqrt{c^2 - 4n}}{2}$$

Scanning L near 1024, L = 1024 makes the discriminant a perfect square, yielding 1024- and 1023-bit primes p and q. This instantly factors n.

>Totient and exponent structure

Compute φ = (p-1)(q-1). Testing gcd(2^k - 1, φ) for k ≡ 3 (mod 6) shows gcd = 7. Hence the actual public exponent satisfies:

$$e = 2^k - 1 = 7 \cdot t \quad\text{with}\quad gcd(t, φ) = 1$$

So encryption was c = m^{7t} mod n.

>Turning it into a 7th-power problem

If e = 7t, then:

$$c = m^{7t} \equiv (m^t)^7 \pmod{n}$$

Let d = t^{-1} mod (φ/7) (since we divided both e and φ by the same factor 7). Then:

$$m^7 \equiv c^{d} \pmod{n}$$

So one modular exponentiation gives m^7.

>Extracting 7th roots

• Because gcd(7, p-1) = 1, the 7th root modulo p is unique: root_p = (m^7)^{7^{-1} mod (p-1)} mod p.

• Because gcd(7, q-1) = 7, there are 7 possible roots modulo q. We find a primitive 7th root of unity ζ mod q; then all candidates are root_q * ζ^i for i = 0..6.

• Use CRT to combine each (root_p, root_q * ζ^i) into a full plaintext candidate mod n.

• Check which candidate contains nexus{.

The correct combination appears; decoded plaintext is nexus{2f13a9d896297558e7c986}.

>Reference exploit snippet

from math import isqrt, gcd

from Crypto.Util.number import long_to_bytes

from sympy import mod_inverse

from sympy.ntheory.modular import crt

  

# n, c from the challenge statement (omitted here for brevity)

# reconstruct p, q using L = 1024

L = 1024

cconst = (1 << L) + 31336

s = isqrt(cconst * cconst - 4 * n)

p = (cconst + s) // 2

q = (cconst - s) // 2

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

  

# search k ≡ 3 mod 6 where gcd(2^k - 1, φ) = 7

for k in range(3, 200000, 6):

    r = pow(2, k, phi)

    if (r - 1) % 7:  # need divisible by 7

        continue

    t = (r - 1) // 7

    if gcd(t, phi // 7) != 1:

        continue

    d = mod_inverse(t, phi // 7)

    m7 = pow(c, d, n)             # m^7 mod n

    # unique 7th root mod p

    rp = pow(m7 % p, mod_inverse(7, p - 1), p)

    # 7 roots mod q

    inv7_q = mod_inverse(7, (q - 1) // 7)

    base_q = pow(m7 % q, inv7_q, q)

    # primitive 7th root of unity mod q

    def root_unity(mod, order):

        exp = (mod - 1) // order

        g = 2

        while True:

            cand = pow(g, exp, mod)

            if pow(cand, order, mod) == 1 and cand != 1:

                return cand

            g += 1

    z7 = root_unity(q, 7)

    roots_q = [base_q * pow(z7, i, q) % q for i in range(7)]

    for rq in roots_q:

        m = int(crt([p, q], [rp, rq])[0])

        pt = long_to_bytes(m)

        if b"nexus{" in pt:

            print("flag:", pt)

            raise SystemExit

>Final flag

nexus{2f13a9d896297558e7c986}

>Key takeaways

• Structuring primes with a complement relation makes p + q known; factoring reduces to solving a quadratic.

• Mersenne exponents can share small factors with φ; if gcd(e, φ) > 1, you may reduce the problem to extracting roots instead of full RSA decryption.

• When gcd(k, p-1) = 1 but gcd(k, q-1) = k, you get a small set of candidates modulo one prime and a unique root modulo the other; CRT plus format checks quickly picks the right plaintext.