There are 3 challenges in this series, all of which are based on the same problem with varying conditions. Therefore, we’ll go through them in increasing order of difficulty and build solutions incrementally.
N.B. All files related to the problems for these challenges and their solutions are available here
Common Modulus 1
We made RSA Encryption Scheme/Tester. Can you break it? Common_Modulus_1.zip
Common Modulus 2
The previous one is very easy. so is this also easy? Common_Modulus_2.zip
Common Modulus 3
try harder! Common_Modulus_3.zip
The common setting is that we’re given two RSA-encrypted messages
are randomly generated primes in the first challenge, which are each multiplied by 3 and 17 for the second and third challenges respectively. which is the common modulus to both public keys, a large randomly generated semiprime of length 2048, 4096 and 8192 bits respectively for the first, second and third challenges.
In terms of operations that we can do, we can multiply both ciphertexts to get a third ciphertext
And if we were to raise
At this point, we can take advantage of Bézout’s identity, which simply states
For
and their greatest common divisor , there are such that
We can calculate
Common Modulus 1
This is the simplest variation, because
So we’ve successfully recovered the first message, and hence the the first flag: CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}
.
Common Modulus 2
For this variation, we don’t recover the message itself but instead we get
CBCTF{ ... 32 characters representing a hex-encoded MD5 hash ... }
Meaning that the bit length of the flag is
- 32 characters of the hash, at 8-bits per character, 256 bits +
- 5 characters of
CBCTF
, at 8-bits per character, 40 bits + - 2 charactes for
{
and}
, at 8-bits per character, 16 bits =
312 bits, and when multiplied by 3 (because this is the 3rd power), would be in the vicinity of 936 bits. This is a lot less than the bit length of CBCTF{d65718235c137a94264f16d3a51fefa1}
.
Common Modulus 3
In this variation, the hardest of the three, not only is the greatest common divisor of
- The modulus is quite large at 8192, meaning that the - unpadded - message must be at least 482 bits (8192 / 17 bits) so that the 17th power becomes sort of a problem. Therefore, knowing the length of the message is 312 bits because it follows the same format as the other challenges in this CTF, we can actually calculate the 17th root of
and successfully recover the flag IF there were no padding. - The padding is deterministic and linear. It is the equivalent of multiplying the flag with a very large power of 2, since the bitstring representation would be
where is the binary representation of the coveted flag.
Using these two facts stated above, we can unpad the message by first calculating the padding coefficient1 which is
So we’ve successfully calculated
But wait, we haven’t actually decided what CBCTF
. We can use a conservative starting value CBCTF{b5c96e00cb90d11ec6eccdc58ef0272d}
.
-
Probably not a real term. It simply seemed apt. ↩