Rating: 5.0

# C2: Flipping bits

- Category: Cryptology
- URL: <https://squarectf.com/2018/flipping_bits.html>

## Description

Disabling C2 requires cracking a RSA message. You have two ciphertexts. The public key is (e1, n).

Fortunately (this time), space rabiation caused some bit flibs and the second ciphertext was encrypted with a faulty public key (e2, n). Can you recover the plaintexts?

## Common Modulus Attack

From the given instructions, we are given two separate ciphertexts, two different exponents (albeit with a single bit difference) and a single modulus. It is given that the two public keys used for ct1 and ct2 are (e1, n) and (e2, n) respectively.

On the basis of this alone, we can exploit the weakness using a **Common Modulus Attack**. This [StackExchange post](https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack) explains it pretty well.

Essentially, since both e1 and e2 are coprime (their GCD is 1), we make use of [Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), which states that:

> Let _a_ and _b_ be integers with greatest common divisor _d_. Then, there exist integers _x_ and _y_ such that _ax + by = d_. More generally, the integers of the form _ax + by_ are exactly the multiples of _d_.

We can thus write the following:


GCD(e1, e2) = 1
=> e1s1 * e2s2 = 1, for some s1, s2 (by Bézout's identity)

c1^s1 * c2^s2 mod N
= (m^e1)^s1 * (m^e2)^s2 mod N
= m^(e1s1+e2s2) mod N
= m mod N


As such, by finding some s1 and s2 that fulfils the given properties, we can recover the plaintext.

## Exploit

For the exploit, we can write it in Python using [libnum](https://github.com/hellman/libnum), a useful package for crypto CTF challenges.

We first find s1 and s2 using the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm), inverting any negative results as necessary (by modulus). The plaintext m can be found by taking c1^s1 * c2^s2 mod N, and finally converting the decimal number into a string.

See [exploit.py](./exploit.py) for the complete Python script.

## Flag

sh
\$ python exploit.py
flag-54d3db5c1efcd7afa579c37bcb560ae0


Original writeup (https://github.com/irvinlim/square-ctf-2018/tree/master/c2).