#!/usr/bin/env python3 from Crypto.PublicKey impo...

Short answer: with the code exactly as you pasted it, there isn’t a “clever” deterministic way to force 32 failures of RSA.construct just by choosing q. The usual CTF tricks that use RSA.construct don’t apply in the same way here – they all assume you can also influence d (or at least n,d), which you can’t in this script.

I’ll walk you through why, what similar challenges do, and what a solver would look like for that kind of challenge. You’ll probably find that either:

• the code you have is incomplete / slightly different on the server, or
• the intended task is something else (e.g. exploit after “key setup successful”).

---

1. What this script actually does

python
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)

Behavior:

• 32 rounds:
  • server chooses a random 1024-bit prime p, prints it.
  • you send a q that must be:
    • different from p
    • at least 1024 bits
    • isPrime(q) according to Crypto.Util.number.isPrime
  • server picks a random 64-bit prime e
  • computes d = e^{-1} mod (p-1)(q-1) using Python’s pow(e, -1, ...)
  • calls RSA.construct((n, e, d)) with just (n, e, d)
• If RSA.construct throws any exception → prints "error!" and goes to the next round.
• If it doesn’t throw → prints "key setup successful" and exit()s.
• Only if all 32 rounds end with "error!" (i.e. RSA.construct fails every time) do you get to print(FLAG).

So to see the flag, you need to make RSA.construct fail on all 32 iterations.

And your only knob is: the choice of q for each random p.

---

2. What can actually make RSA.construct((n, e, d)) fail?

From the PyCryptodome source for Crypto.PublicKey.RSA.construct (not quoting the whole thing for copyright, but summarizing), these are the relevant checks when you pass only (n, e, d):

1. It tries to recover p and q from (n, e, d) using the classic “factor N from (N,e,d)” algorithm – essentially the standard ed − 1 = k·φ(N) trick.
   • If this fails →
     ValueError("Unable to compute factors p and q from exponent d.")
2. After it finds p,q, it runs a consistency check:
   • gcd(n, e) == 1 (public exponent coprime to modulus)
   • gcd(n, d) == 1 (private exponent coprime to modulus)
   • n odd
   • p*q == n
   • p and q are (probable) primes
   • e*d ≡ 1 (mod lcm(p-1, q-1))
   • CRT coefficient u sane, etc.
   • Violations give errors like
     • "Invalid RSA public exponent"
     • "RSA public exponent is not coprime to modulus"
     • "Invalid RSA private exponent"
     • "RSA private exponent is not coprime to modulus"
     • "RSA factors do not match modulus"
     • "RSA factor p/q is composite"
     • "Invalid RSA condition"

So the only way your choice of q can force "error!" is by arranging that one of those checks fails.

Given how p,q,e,d are generated in your script:

• p is a true 1024-bit prime (getPrime(1024)).
• You are forced to send a q that:
  • passes isPrime(q) and has bit_length ≥ 1024.
• e is a true 64-bit prime (getPrime(64)).
• d = e^{-1} mod φ(n) with φ(n) = (p-1)(q-1) computed by Python’s built-in modular inverse.

For almost all such choices, (n,e,d) is a perfectly normal RSA key, and RSA.construct is designed to accept exactly that.

---

3. Can you break each check by choosing q?

Let’s go through the possible failure modes and see whether you can force them with just q, knowing that e is chosen after your q.

3.1 RSA factor p/q is composite

Idea: send a composite q that isPrime(q) misclassifies as prime, but RSA.construct’s own primality test rejects.

• isPrime in Crypto.Util.number is a Miller–Rabin test with enough rounds to guarantee false positives ≤ 10⁻⁶, using random bases.
  The number of rounds is ceil(-log(fpp)/log(4)) = 10 for the default fpp=1e-6.
• The bases are chosen randomly each time you call isPrime, so for a fixed composite q, each call succeeds (i.e. wrongly returns True) with probability ≤ 10⁻⁶, and fails (returns False) otherwise.

Now in your code:

• assert isPrime(q) is called once per round on your q.
• You need this to pass 32 times in the same run.
• If you reuse the same composite q on all 32 rounds, you need 32 independent false positives, so the probability is at most:

$$(10^{-6})^{32} = 10^{-192}$$

That’s effectively “never” in a CTF environment.

So relying on isPrime’s false positives is not a viable intended trick.

3.2 RSA public exponent is not coprime to modulus

This happens if gcd(e, n) ≠ 1, i.e. e shares a factor with p or q.

• e is a random 64-bit prime.
• p and q are ~1024-bit primes, so the chance p == e or q == e is astronomically close to 0.
• You cannot choose q small (like setting q = e) because you must have q.bit_length() ≥ 1024.

So you can’t realistically force this either.

3.3 RSA private exponent is not coprime to modulus

This is the interesting one from write-ups like CISCN 2023 “badkey1”, where people deliberately construct d so that p | d (or q | d) and trigger this error.

In your script, however:

• You don’t control d directly.
• You only control q, while:
  • e is chosen randomly after you pick q.
  • d is uniquely determined by e and φ(n) via d = e^{-1} mod φ(n).

For a fixed pair (p, q):

• Consider the mapping from e (coprime to φ(n)) to d = e^{-1} mod φ(n). This is a bijection on the multiplicative group modulo φ(n).
• The set of d that are multiples of, say, p is extremely sparse: density about 1/p, and p is ~2¹⁰²⁴.
• A random 64-bit prime e corresponds to a pseudo-random d modulo φ(n); the probability that it lands in “multiples of p” or “multiples of q” is negligible – on the order of 2⁻¹⁰²⁴.

So for any reasonable choice of q, the chance that this condition triggers is essentially 0.

And you’d need it to trigger every iteration to see the flag.

3.4 Unable to compute factors p and q from exponent d

This is the factor-from-(n,e,d) algorithm failing.

For valid RSA parameters, this algorithm is proven to succeed with overwhelming probability using a small number of random bases. It’s exactly the algorithm from DI Management’s write-up “RSA: how to factorize N given d”.

You can’t “spoof” this by your choice of q because:

• n = p*q with p,q both primes.
• d actually satisfies e d ≡ 1 (mod φ(n)) by construction (modular inverse via pow).
• Under these conditions RSA.construct’s recovery of p,q always works for practical purposes.

Trying to sabotage it by making q weird (huge, special form, etc.) just makes the computation slower, not incorrect, and there’s no separate bound that would throw a Python exception in the normal code path.

---

4. What similar CTF challenges actually do

There are challenges on the web that look a lot like this and use RSA.construct as the vulnerability, but the structure is a bit different.

Example: [CISCN 2023 初赛] badkey

The core idea (see e.g. Luino’s write-up) is:

• The service builds an RSA key from n, e, d, p, q via RSA.construct([n, e, d, p, q]).

• If RSA.construct raises a ValueError, you get the flag.

• By studying the construct source, they find the check:

  python
  if Integer(n).gcd(d) != 1:
      raise ValueError("RSA private exponent is not coprime to modulus")

• There, you do control d (or have enough control over n,e,d) so you can deliberately choose d that shares a factor with n and force the exception.

Your snippet is missing that degree of freedom: you never choose d, and d is computed from e and φ(n) in a way that’s essentially guaranteed to satisfy all of RSA.construct’s conditions.

So the “badkey” trick doesn’t port over as-is.

---

5. Why a “fast solver for all 32 checks” probably doesn’t exist for this exact code

Putting it all together:

• The only place that can throw inside the try is RSA.construct((n, e, d)).
• For any valid primes p,q and exponent e with d = e^{-1} mod (p-1)(q-1), the triple (n,e,d) is a correct RSA private key as far as PyCryptodome is concerned.
• The set of bad triples for which:
  • the factor-from-(n,e,d) algorithm fails, or
  • gcd(n, e) ≠ 1, or
  • gcd(n, d) ≠ 1 is so vanishingly small that you can’t hit it on purpose with only q and a random 64-bit prime e.

If you try to “solve” this literally:

• Random choice of 1024-bit prime q → RSA.construct succeeds almost every time on the very first round → the script exits and NEVER reaches print(FLAG).
• Trying to game isPrime via pseudoprimes is statistically hopeless because:
  • You’d need 32 independent false positives in a row on the same composite q (probability ≤ 10⁻¹⁹²).
• Trying to force gcd(n,d) ≠ 1 for all choices of random 64-bit prime e is mathematically impossible given how d is defined.

So unless:

• the real remote code is slightly different (e.g. uses inverse from Crypto.Util.number with no try/except, or lets you choose e / d), or
• there is some implementation bug in the specific PyCryptodome version used by the server that we don’t see here,

there is no clean, deterministic “trick” that gives you 32 guaranteed error!s.

---

6. What a solver would look like for a similar badkey-style challenge

Even though this exact script doesn’t give you enough leverage, here’s how a solver usually looks when the challenge is:

“Cause RSA.construct to throw by giving it a bad private key.”

Typical pattern (like CISCN badkey1)

1. Study Crypto.PublicKey.RSA.construct source.
2. Pick a failure mode that you can control (e.g. force gcd(n, d) ≠ 1).
3. Algebraically construct parameters so the server’s computed d is a multiple of p or q but still satisfies the modular inverse condition.

In those challenges, the actual game is:

• You are given a random p.
• You get to produce some integers q and d (or n and d, etc.).
• The server checks with RSA.construct and gives you the flag if it throws.

Then a solver looks like (pseudo-Python):

python
from Crypto.Util.number import getPrime, isPrime
from Crypto.PublicKey import RSA
from Crypto.Math.Numbers import Integer
from pwn import remote

def pick_bad_d(p, q, e):
    phi = (p-1)*(q-1)
    # Start from a 'good' inverse d0
    d0 = pow(e, -1, phi)
    # Add a multiple of n to make d share a factor with n
    # For example, force p | d:
    # solve d ≡ 0 (mod p) and d ≡ d0 (mod phi)
    # via Chinese Remainder Theorem, etc.
    # (Details depend on the exact challenge.)
    ...

io = remote(HOST, PORT)

for _ in range(32):
    p = int(io.recvline().split(b"=")[1])
    q = construct_q_that_works(p)    # problem-specific
    io.sendline(str(q).encode())
    # read "error!" or success, handle accordingly

But note: In your script, the server is the one computing d internally, and you never see or control it, so you can’t do the step marked pick_bad_d.

---

7. So what should you do with this?

If you’re the one designing or analyzing this challenge, I’d strongly suggest:

1. Double-check the real remote source:
   • Is d really computed exactly as pow(e, -1, (p-1)*(q-1))?
   • Do they maybe let you influence e or d elsewhere?
   • Is there additional logic after "key setup successful" that you didn’t paste?
2. Compare with documented challenges like CISCN 2023 badkey to see how they give the attacker enough control.

If you can share the full remote script (or at least the part after "key setup successful"), then we could actually try to design a real solver: either one that:

• makes RSA.construct fail on purpose (badkey-style), or
• leverages the constructed key to decrypt/sign something and get the flag.

But with only this snippet and PyCryptodome’s actual behavior, the honest answer is:

There is no practically feasible “trick” that guarantees 32 failures of RSA.construct just by choosing q under those constraints. Any solver would have to rely on astronomically unlikely random accidents, not a clever deterministic strategy.