Hey! I'm David, a security engineer at the Blockchain team of Facebook, previously a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

# Same RSA modulus and correlated public exponents posted April 2015

Plaid, The biggest CTF Team, was organizing a Capture The Flag contest last week. There were two crypto challenges that I found interesting, here is the write-up of the second one:

You are given a file with a bunch of triplets:

{N : e : c}

and the hint was that they were all encrypting the same message using RSA. You could also easily see that N was the same modulus everytime.

The trick here is to find two public exponent $e$ which are coprime: $gcd(e_1, e_2) = 1$

This way, with Bézout's identity you can find $u$ and $v$ such that: $u \cdot e_1 + v \cdot e_2 = 1$

So, here's a little sage script to find the right public exponents in the triplets:

for index, triplet in enumerate(truc[:-1]):
for index2, triplet2 in enumerate(truc[index+1:]):
if gcd(triplet[1], triplet2[1]) == 1:
a = index
b = index2
c = xgcd(triplet[1], triplet2[1])
break

Now that have found our $e_1$ and $e_2$ we can do this:

$c_1^{u} * c_2^{v} \pmod{N}$

And hidden underneath this calculus something interesting should happen:

$(m^{e_1})^u * (m^{e_2})^u \pmod{N}$

$= m^{u \cdot e_1 + v \cdot e_2} \pmod{N}$

$= m \pmod{N}$

And since $m < N$ we have our solution :)

Here's the code in Sage:

m = Mod(power_mod(e_1, u, N) * power_mod(e_2, v, N), N)

And after the crypto part, we still have to deal with the presentation part:

hex_string = "%x" % m
import binascii
binascii.unhexlify(hex_string)

Tadaaa!! And thanks @spdevlin for pointing me in the right direction :)

Well done! You've reached the end of my post. Now you can leave me a comment :)