Editorial for DMOJ Capture The Flag '20 C2 - Small RSA
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
At first sight, this problem might look impossible. All these values look like classical RSA values… but are they? Turns out, if we try factoring , it will actually give us both factors, one of which is
. With these 2 factors, we can calculate the secret key,
, and decrypt the ciphertext. With the plaintext number, we can convert it to hexadecimal and subsequently ASCII to retrieve the flag.
This is one of the reasons why it is suggested to use 2 almost equal-length (but NOT equal) primes for RSA encryption, since finding even one of the primes will be enough to decrypt the ciphertext (it is trivial to check if the other factor is a prime).
Comments