$ cat writeup.md…
$ cat writeup.md…
tjctf
Task: RSA parity oracle — server decrypts chosen ciphertexts and returns only the LSB (even/odd). Solution: exploit RSA multiplicative homomorphism to perform binary search on plaintext via repeated multiplication by 2^e mod n, recovering the exact message in ~512 queries.
$ cat /etc/rate-limit
Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.
our security monitor only ever tips us off about the parity of RSA decryptions. turns out "even or odd" isn't much of a secret. can you recover the message one bit at a time?
The server generates RSA with two 256-bit primes (512-bit modulus), e=65537. It encrypts the flag and provides n, e, and the ciphertext. The user gets up to 2100 parity oracle queries: send any ciphertext, receive pow(ciphertext, d, n) & 1 — the least significant bit (parity) of the decrypted value.
This is a classic RSA LSB (Parity) Oracle scenario. The key insight is that RSA's multiplicative homomorphism allows us to manipulate the underlying plaintext without knowing it:
RSA Homomorphism: Given ciphertext c = m^e mod n, if we compute c' = c * 2^e mod n, then decrypting c' yields 2m mod n.
Parity reveals range information: Since n is odd (product of two odd primes):
2m mod n is even → 2m < n → m < n/22m mod n is odd → 2m ≥ n (reduction happened) → m ≥ n/2Each query eliminates half the candidate range, giving us a binary search over [0, n).
Query budget: With a 512-bit modulus, we need exactly 512 queries. The server allows 2100, giving ample margin.
Precision: Floating-point arithmetic would lose precision over 512 iterations. The solve script tracks bounds as integer numerators with a shared power-of-2 denominator (lower_num/2^k, upper_num/2^k), maintaining exact arithmetic throughout.
...
$ grep --similar