cryptofreemedium

bit-leak

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.

$ ls tags/ techniques/
binary_searchrsamultiplicative_homomorphismchosen_ciphertextlsb_oracleparity_oracle
rsa_lsb_oracle_attackbinary_search_interval_narrowingchosen_ciphertext_multiplication

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

bit-leak — TJCTF 2026

Description

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.

Analysis

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

  • If 2m mod n is even → 2m < n → m < n/2
  • If 2m mod n is odd → 2m ≥ n (reduction happened) → m ≥ n/2

Each 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.

Solution

Step-by-step

...

$ grep --similar

Similar writeups