david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and 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 a comment or read something else.

Comments

Manal

What if a similar setting, but instead of encrypting the same message we have two different messages. would we be able to break the scheme?

leave a comment...