Same RSA modulus and correlated public exponents

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} (\mod N)

And hidden underneath this calculus something interesting should happen:

(m^{e_{1}})^{u} * (m^{e_{2}})^{u} (\mod N)

= m^{u \cdot e_{1} + v \cdot e_{2}} (\mod N)

= m (\mod 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 :)

Same RSA modulus and correlated public exponents

recent posts

elsewhere