Analyze this challenge fully in depth please and h...

Here’s the core idea in one sentence:
you have to deliberately give the server “valid-looking” RSA parameters that PyCryptodome rejects as an invalid key, 32 times in a row.

The trick is a subtle bug/limitation in RSA.construct’s factor-recovery algorithm, and you exploit it by choosing special primes q matched to the printed p so that the library cannot recover p and q from (n, e, d) and throws an exception instead.

I’ll walk through all the moving pieces and then show what the attack actually looks like.

---

1. What the challenge code actually does

The loop

py
with open("flag.txt", "r") as f:
    FLAG = f.read()

for _ in range(32):
    p = getPrime(1024)
    print("p =", p)

    q = int(input("q: "))
    assert p != q
    assert q.bit_length() >= 1024
    assert isPrime(q)

    n = p * q
    e = getPrime(64)
    d = pow(e, -1, (p - 1) * (q - 1))

    try:
        cipher = RSA.construct((n, e, d))
    except:
        print("error!")
        continue
    print("key setup successful")
    exit()

print(FLAG)

Per connection:

1. For up to 32 rounds:

   • Server picks a random 1024-bit prime p and prints it.

   • You send a prime q (≥1024 bits, q != p).

   • It builds n = p*q, chooses a random 64-bit prime e, and sets
     d = e^{-1} mod (p-1)(q-1) (a correct RSA private exponent).

   • Then it calls RSA.construct((n, e, d)) inside a try:

     • If RSA.construct succeeds:
       it prints "key setup successful" and immediately exits.
       → You fail (no flag).

     • If RSA.construct raises (any exception):
       it prints "error!" and goes to the next round.

2. Only if you cause an exception for all 32 rounds does the loop finish and print the flag.

So your job is:

For each printed p, choose a prime q so that
RSA.construct((n, e, d)) throws an exception.

If you ever accidentally give a “normal” q (where RSA.construct works), the program exits early and you don’t see the flag.

---

2. What RSA.construct((n, e, d)) does under the hood

PyCryptodome’s RSA.construct accepts tuples like:

• (n, e) – public key only, or
• (n, e, d) – private key, where it must recover p and q from these.citeturn1search1turn1search15

The relevant internal logic is:

py
if not hasattr(input_comps, 'd'):
    key = RsaKey(n=n, e=e)
else:
    d = input_comps.d
    if hasattr(input_comps, 'q'):
        p = input_comps.p
        q = input_comps.q
    else:
        # Compute factors p and q from the private exponent d.
        ktot = d * e - 1
        t = ktot
        while t % 2 == 0:
            t //= 2

        spotted = False
        a = Integer(2)
        while not spotted and a < 100:
            k = Integer(t)
            while k < ktot:
                cand = pow(a, k, n)
                if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
                    p = Integer(n).gcd(cand + 1)
                    spotted = True
                    break
                k *= 2
            a += 2
        if not spotted:
            raise ValueError("Unable to compute factors p and q from exponent d.")

        q = n // p
        ...
        # Then it checks p,q are prime etc. and builds RsaKey

Key points:

• ktot = d*e - 1 is a multiple of φ(n) = (p−1)(q−1).
• They write ktot = 2^s * t with t odd.
• For a = 2, 4, 6, ..., 98, they look at powers a^k (mod n) for k = t, 2t, 4t, ..., < ktot.
• They’re searching for a non-trivial square root of 1 mod n (an element whose square is 1 but isn’t ±1). If they find one, gcd(cand+1, n) is a factor.
• If they fail for all a < 100, they throw:

py
ValueError("Unable to compute factors p and q from exponent d.")

…and your challenge code catches that and prints "error!".

So the exploitable behaviour is:

Even if (n, e, d) is mathematically a valid RSA key,
PyCryptodome gives up and throws ValueError if this particular factoring algorithm can’t find p and q using bases a=2,4,...,98.

Your influence is only through q (and therefore n and φ(n)).
The challenge’s secret e is random 64-bit prime, but the failing condition we’ll use does not depend on which e ends up being chosen.

---

3. When does this factoring algorithm succeed or fail?

Let’s denote:

• n = p*q with odd primes p, q.
• φ(n) = (p−1)(q−1).
• A base a with gcd(a, n) = 1.

Rough idea of Rabin’s algorithm from (n, e, d):citeturn1search2turn1search16

1. Because d is the inverse of e mod φ(n), we know
   k_tot = d*e - 1 is a multiple of φ(n).
2. Write k_tot = 2^s * t, t odd.
3. For some base a:
   • Consider the sequence x_i = a^{t*2^i} mod n for i = 0..s.
   • If for some i:
     • x_i is not ±1, but
     • x_i^2 ≡ 1 (mod n),
     • then x_i is a non-trivial square root of 1, and gcd(x_i - 1, n) yields a factor.

So success for a given a happens exactly when one of those powers is a non-trivial square root of 1.

Quadratic residues & Legendre symbols

Over a prime modulus p, the group (ℤ/pℤ)* is cyclic of order p−1. An element a is:

• a quadratic residue (QR) mod p if some x has x² ≡ a (mod p);
• a non-residue (QNR) otherwise.

The Legendre symbol (a/p) is:

• +1 if a is a QR mod p,
• −1 if a is a QNR mod p.

And Euler’s criterion says:

text
a^((p-1)/2) ≡  1 (mod p)  iff  (a/p) = +1
a^((p-1)/2) ≡ -1 (mod p)  iff  (a/p) = -1

Similarly mod q.

Now, very important fact for this attack (this is exactly what that CISCN writeup uses):citeturn2search0

For a composite n = p*q, a non-trivial square root of 1 mod n appears iff the Legendre symbols of some base g disagree modulo p and modulo q:

• (g/p) = +1, (g/q) = −1, or
• (g/p) = −1, (g/q) = +1.

Intuitively:
if g “behaves differently” in the two prime fields, some exponent exposes that mismatch and gives a square root of 1 that’s 1 mod one prime and −1 mod the other, hence non-trivial mod n.

If the Legendre symbols match for both primes:

• (g/p) = (g/q) = +1 or (g/p) = (g/q) = −1,

then every square root of 1 mod n looks the same modulo each prime and the Rabin procedure never gets that “mixed-sign” square root it needs, at least for that base g.

So:

• For a base g, factoring via this algorithm succeeds if (g/p) ≠ (g/q);
• It fails for that base if (g/p) = (g/q).

For a random prime q, and fixed prime p and base g, the Legendre symbol (g/q) is basically random ±1, so:

• Pr[(g/p) = (g/q)] = 1/2 → “bad” base
• Pr[(g/p) ≠ (g/q)] = 1/2 → “good” base

---

4. How to make all PyCryptodome bases “bad” at once

PyCryptodome doesn’t choose random bases; it deterministically uses:

py
a = 2, 4, 6, 8, ..., 98

All of these are products of small primes (no prime factor > 49). So if we control the Legendre symbols for those small primes, we control Legendre symbols for every a it will ever try.

This is exactly what the CISCN “badkey2” writeup does; they pick the small primes:citeturn2search0

py
Y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

For each y in Y, we define the “pattern”:

py
σ_p(y) = +1  if pow(y, (p-1)//2, p) == 1
σ_p(y) = -1  if pow(y, (p-1)//2, p) == p-1

Now, if we can find a q such that for every y in Y,

text
σ_q(y) = σ_p(y)

then:

• For any product g of primes from Y (like 2 * 3 * 7 = 42, etc.), the Legendre symbols multiply, so:

  text
  (g/p) = ∏ (y/p) = ∏ σ_p(y)
  (g/q) = ∏ (y/q) = ∏ σ_q(y) = ∏ σ_p(y) = (g/p)

• So for every such g, (g/p) = (g/q).

And all the PyCryptodome bases a = 2, 4, ..., 98 are products of those primes, so for all of them:

(a/p) = (a/q) → every base the library tries is “bad” for Rabin’s algorithm.

When that happens, the while not spotted and a < 100: loop never finds a factor and hits this path:

py
if not spotted:
    raise ValueError("Unable to compute factors p and q from exponent d.")

Exactly what we want.

How likely is such a q to exist?

For a random prime q:

• For each y, (y/q) is independent ±1, so chance that (y/q) = σ_p(y) is 1/2.
• For 15 independent y’s, probability that all 15 match is 2^-15 ≈ 1/32768.

So for each p, we expect to find a suitable q after sampling on the order of ~30–40k primes. That’s exactly what the Chinese writeup estimates and observes in practice.citeturn2search0

On your own machine, generating ~30k 1024-bit primes with gmpy2.next_prime (or similar) is completely doable, and the remote challenge doesn’t care how long you take to answer since its time limit is CPU time inside the jail, not your wall-clock time.

---

5. Concrete construction of a “bad” q for a given p

So for each p that the challenge prints, you do this locally:

Step 1 – Precompute the Legendre pattern of p

Pick the set Y of small primes:

python
Y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Given the server’s prime p:

python
pattern = []
for y in Y:
    val = pow(y, (p - 1)//2, p)
    pattern.append(1 if val == 1 else -1)   # p is prime, so val is ±1

This pattern is just the list [σ_p(y) for y in Y].

Step 2 – Search for q with matching pattern

We need a prime q such that:

• q.bit_length() >= 1024

• q != p

• for all y in Y:

  python
  val = pow(y, (q - 1)//2, q)
  σ_q(y) == σ_p(y)

You can do a simple sequential search using something like gmpy2.next_prime to make it fast:

python
import gmpy2

def legendre_pattern(modulus, Y):
    patt = []
    for y in Y:
        v = pow(y, (modulus - 1)//2, modulus)
        patt.append(1 if v == 1 else -1)  # for odd primes, v is ±1
    return patt

def find_bad_q_for_p(p, bits=1024):
    Y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    patt_p = legendre_pattern(p, Y)

    # Start around 2^(bits-1)
    q = gmpy2.next_prime(1 << (bits - 1))

    while True:
        if q == p:
            q = gmpy2.next_prime(q + 2)
            continue

        # (Optional, as in the writeup) enforce q ≡ 3 mod 4
        if (q - 1) % 4 == 0:       # q ≡ 1 (mod 4), skip
            q = gmpy2.next_prime(q + 2)
            continue

        patt_q = legendre_pattern(int(q), Y)
        if patt_q == patt_p:
            return int(q)          # Found a candidate

        q = gmpy2.next_prime(q + 2)

In practice you’ll find such a q after on the order of 30k iterations.

Step 3 – (Optional but reassuring) Verify locally that it actually breaks RSA.construct

Just to convince yourself before sending it to the remote:

python
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime

def is_bad_pair(p, q, trials=5):
    n = p * q
    for _ in range(trials):
        e = getPrime(64)    # same distribution as server
        phi = (p-1)*(q-1)
        d = pow(e, -1, phi)
        try:
            RSA.construct((n, e, d))
            # If it ever succeeds, this (p,q) won't work for our challenge
            return False
        except ValueError as ex:
            # Should be "Unable to compute factors p and q from exponent d."
            continue
    return True

For a “good bad” pair (p, q) generated as above, you should consistently see the ValueError in your local tests, independent of e.

---

6. Putting it all together for the 32-round challenge

Remember the control flow: as soon as any RSA.construct succeeds, the program exits and you lose.

So your exploit must never send a “normal” q.

A typical attack script (using pwntools) looks like:

python
from pwn import *
from Crypto.Util.number import isPrime
# + your gmpy2-based search code above

def solve_one_connection():
    r = remote('host', 15809)

    for round_idx in range(32):
        # Read "p = <number>"
        line = r.recvline().decode().strip()
        assert line.startswith("p = ")
        p = int(line.split("=", 1)[1].strip())
        print(f"[round {round_idx}] got p, computing bad q...")

        q = find_bad_q_for_p(p, bits=1024)
        assert isPrime(q)

        # Optionally, check locally is_bad_pair(p, q) before sending
        # assert is_bad_pair(p, q)

        r.sendline(str(q).encode())

        # After sending q, if we did it right, the server prints "error!" and moves on.
        # If we messed up, it will print "key setup successful" and close.
        reply = r.recvline(timeout=5).decode().strip()
        print("[server]", reply)
        assert reply == "error!"   # sanity check

    # After 32 rounds of "error!", the server prints the flag
    flag = r.recvline().decode().strip()
    print("[FLAG]", flag)

    r.close()

Flow:

1. For each of the 32 p values the server gives you:

   • Compute a matching-pattern prime q as in section 5.
   • Optionally sanity-check locally that RSA.construct((p*q, e, d)) fails.
   • Send that q to the remote.
   • The remote sees the ValueError, prints "error!", and continues to the next round.

2. After 32 failures, the loop ends and print(FLAG) runs.

---

7. Summary of the “why”

Conceptually, this challenge is about understanding both:

1. How PyCryptodome reconstructs p and q from (n, e, d) – via Rabin’s factorization algorithm with a fixed, small set of bases ({2, 4, …, 98}); and
2. How to construct RSA moduli where that specific factoring algorithm consistently fails, by controlling quadratic residue behaviour (Legendre symbols) of those bases modulo p and q.

You’re not breaking RSA itself; you’re breaking a particular implementation detail of one library’s key import:

• The key is mathematically valid: d really is the inverse of e mod φ(n).
• But PyCryptodome’s recovery algorithm can’t rediscover p and q from (n, e, d), so it throws and your challenge counts that as “bad key”.

Do that 32 times in a row, and you get the flag.

---

If you want, I can next:

• help you shrink this into an actual exploit script ready to run, or
• walk through a smaller-bit-size toy example step-by-step so you can see the Legendre-symbol / quadratic-residue logic numerically.