zer0pts CTF 2021
crypto
This is the very simple warmup-level RSA challenge. We're given public key and ciphertext .
Considering . This is from RSA's multiplicative homomorphism. If is even, . This looks unsolvable. However, if is odd value, since .
Then we get two cipheretexts and a difference of their plantexts. As is small[1], we can apply the Franklin-Reiter's Related Message Attack.
Only the problem is is even or odd. We have 1/2 chance of win. Additionally, as is the flag, we can guess it ends with }
. It is odd value, then and is odd value highly probability.
The plagiarism challenge in diceCTF 2021 introduces us the Half-GCD method which solves polynomial GCD faster than euclidean method. So we can solve this challenge if even is not so small. I didn't know such a great way when I've created this challenge. ↩︎