Rating:

# Common Modulus 1 - Cryptography - 98 points - 162 teams solved

> We made RSA Encryption Scheme/Tester. Can you break it?
>
> [Common_Modulus_1.zip](./Common_Modulus_1.zip-37882dbd7dd05381bbf72a11fbbdb3f23def0e4981bc9ffcd399e4c138549fc8)

# Common Modulus 2 - Cryptography - 133 points - 104 teams solved

> The previous one is very easy. so is this also easy?
>
> [Common_Modulus_2.zip](./Common_Modulus_2.zip-24d74ea8d1b7bc154d30bb667f6f13ef24a9fe260a7741caab427421d1070c98)

# Common Modulus 3 - Cryptography - 210 points - 48 teams solved

> try harder!
>
> [Common_Modulus_3.zip](./Common_Modulus_3.zip-275005199fd0ecbec4183fd7e1b421f65c7bb982ffba65a12a4089e263899152)

These challenges are three variations of the same problem, where a plaintext is RSA encrypted twice, with public keys (e1, n) and (e2, n) where n is the same in both keys but e1 != e2. We are given a file with both public keys and the two ciphertexts ct1 and ct2.

At first I totally missed that e1 and e2 was explicitly given in the files, so I wrote a script to brute force find the private keys by generating ct1 ** x mod n and ct2 ** y mod n until I found a match. This works because (m ** e1) ** x = m ** (e1 * x) = m ** (e2 * y) mod n when e1 = y and e2 = x. Since each e1 and e2 are generated from a random number below 2 ** 20 this just takes a few minutes.

With the two public keys fully known, the solution is as described [in this Stackexchange post](https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem) - you take the extended GCD for e1 and e2 to find two values where e1 * s + e2 * t = 1 which then can be extended to [(ct1 ** s) * (ct2 ** t) = (m ** (e1 * s)) * (m ** (e2 * t)) = m ** (e1 * s + e2 * t) = m ** 1 = m] mod n. The only issue is that either s or t is negative, so you have to use modular multiplicative inverse to calculate a negative power. After this, we get m, convert it to bytes, and get the first flag CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}

In the second problem, e1 and e2 is generated with e = 3 * get_random_prime(20), so they have a common factor. We simply divide both of them by 3, and the above alorithm still works. The only problem is that we are left with the result m ** 3. Since the number of bits in m is assumed to be less than one third of the size of n, we can simply find the cube root of the result, and get the proper m. The second flag is CBCTF{d65718235c137a94264f16d3a51fefa1}.

In the third problem, the common factor is now 17, but more importantly, the flag is left aligned with zero bytes until the plaintext is 8192 bits in length. In practice, this means that mp = m ** (1 << (x*8)), and the value we get when repeating the algorithm from the previous problems give us mp ** 17. Our solution then becomes to generate modular multiplicative inverses for all 1 << (x*8) mod n, then try all of them. One of them will leave us with m ** 17 as the result, which we then can take the 17th root of to get the original m, and the flag which is CBCTF{b5c96e00cb90d11ec6eccdc58ef0272d}.

Original writeup (https://github.com/ymgve/ctf-writeups/tree/master/codeblue2017/crypto-common_modulus).