Solve for z3kapig R3CTF 2026

Solve for z3kapig by aresinheaven

Let's do a quick recap of what I understood for this challenge.

First thing the server acts as party 1 while we control party 0, so we get to choose every message sent from the party-0 side of the protocol. second thing our job isn't just to produce a valid signature. After we complete one successful sign-and-verify round, the server unlocks another endpoint:

{"action":"guess_key","data":{"guess":123}}

If guess matches party 1's secret share $x_i$ , the server returns the flag...

Plan to solve the challenge

During the aux phase, we can provide a crafted 2048-bit Paillier modulus $N_0$ that is not the product of two RSA primes.
But since ProofMod.verify never requires $W$ to be invertible, this malformed modulus still passes the modulus proof even though we know its complete factorization.
ProofEnc.verify and ProofLogstar.verify only remain sound if the plaintext is interpreted modulo a valid Paillier modulus. If the Fiat–Shamir challenge $e$ is divisible by a hidden small factor $p \mid N_0$ , then an encryption of $k + N_0/p$ is accepted as an encryption of $k$ .
Then I decided to hide the secp256k1 group order $q$ inside $N_0$ . Since $N_0/p$ is a multiple of $q$ , the extra term disappears modulo $q$ , so every elliptic-curve check still sees the same nonce scalar.
The server then uses our shifted nonce ciphertext during mta i.e. $M = x_i \cdot (k_0 + N_0/p) + \beta_{\text{neg}} \pmod{N_0}$ and from the server's honest affg proof we will get this $Z_2 = e \cdot \beta_{\text{neg}} + \beta$ . where $0 < \beta < N_0$ . This gives us a good approximation of $\beta_{\text{neg}}$ .
brute force the values of $x_i \pmod p$ will give a match it was exactly one
then I repeated the same trick for roughly 15 different small primes and combining the results with CRT recovers the unique scalar $x_i$ in $[1, q)$
I validated everything locally with a 2048-bit Paillier modulus. My exploit recovers $x_i$ , verifies that $x_i \cdot G = X_j$ , and finally makes guess_key return correct: true

Math 1 Math 2 Math 3 Math 4 Math 5 Math 6 Math 7 Math 8

this was my Math for the challenge

Final output

[$] round 14: recovered xi mod 262331 = 118076
    logstar grind p=262331: 64784 attempts
[$] CRT modulus bits=271
[$] recovered xi = 95401058553176690993657320772652702378918272643766567159124468810038960643453
{
  "status": "ok",
  "action": "guess_key",
  "result": {
    "correct": true,
    "flag": "r3ctf{p3op1E_5h0ULD_M0Ve_To-bEtT3r_on3_tH@n-cGgMp21....6a}"
  }
}
(ctf-env) manavhowal@manavs-MacBook-Air attachment 3 %

Flag: r3ctf{p3op1E_5h0ULD_M0Ve_To-bEtT3r_on3_tH@n-cGgMp21....6a}