Tags: partial-private-key lsb-oracle wiener
Rating: 5.0
4 RSA challenges, each with specific vulnerabilities:
- big e, vulnerable to Wiener attack (small d). Lot of libraries to solve this.
- sexy primes used for the modulus (`p = q-6`). Just compute `sqrt(N+9)` to find `(p+q)/2`
- LSB oracle: given a ciphertext c, an oracle returns the parity of p the plaintext for c. This allows to perform a binary search on the plaintext by sending ciphertexts for `2^kP` for all k.
- partial key exposure attack: given half of the private key (LSBs), we can find an approximation d' of d such that `|d' - d| <= 3sqrt(N)`. Because `3sqrt(N)` is only a little bit more than half of d bits, we can just replace the LSB of d' with the known value and brute force the 3 or 4 bits that are still uncertain.
Full explanation and Python code in the original writeup.
