2013年8月4日 星期日

ebCTF@OHM2013 Crypto200

Crypto200

Here we have 4096 RSA messages including the modulus (n) and the ciphertext (c), but no public exponent (e). As the title suggested, "One to many", I expect all plaintexts (m) are the same.

One possible attack is using the Chinese Remainder Theorem. Suppose e = 3, then we can recover m^3 from three messages by CRT:
 
Well. I don't know the e. So brute force it. Starting from 3, and then 5, 7, 11, 13, ... it doesn't work.
As e goes larger, the calculation time for CRT is longer and longer, and the program crashes.
Well, if I try e = 4093 (the largest possible e for this attack), the program crashes as expected.

So don't do this.

I remember someone told me that RSA is not safe because the modulus are not randomly generated, or p and q are not even prime. Well, because these messages use different n, we can try to find the gcd for each pair of n, just need 4096 * 4095 / 2 times. Worth to try.
#nn = [the list of modulus]
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b % a, a)

f = open('output.txt', 'a')
for i in range(0,4095):
    for j in range(i+1,4096):
        g = gcd(nn[i],nn[j])
        if g <> 1:
            print str(i)+","+str(j)+"\t"+str(g)+"\r\n"
            f.write(str(i)+","+str(j)+"\t"+str(g)+"\r\n")
f.close()

And the good thing is we have:
763,3821
10425079766382366420625494866767568875370400467976574956525983652357684133387986157895827317253539750222139144079507972326197750248804720295152321770469893

So the n in message763 and message3821 are not coprime. Now we get a prime factorizer :)
But wait, what is e? Just use the common one 65537 and try:
#nn = [list of modulus]
#cc = [list of ciphertext]

cop = 10425079766382366420625494866767568875370400467976574956525983652357684133387986157895827317253539750222139144079507972326197750248804720295152321770469893

def powMod(base, power, modulus):
    base = gmpy.mpz(base)
    power = gmpy.mpz(power)
    modulus = gmpy.mpz(modulus)
    result = pow(base, power, modulus)
    return long(result)

p1 = nn[763] / cop
p2 = nn[3821] / cop

tot1 = (p1-1) * (cop - 1)
tot2 = (p2-1) * (cop - 1)

d1 = gmpy.invert(65537, tot1)
d2 = gmpy.invert(65537, tot2)

m1 = powMod(cc[763], d1, nn[763])
m2 = powMod(cc[3821], d2, nn[3821])

print ("%x" % m1).decode("hex")
print ("%x" % m2).decode("hex")

And then you will see:
This is a secret message, for your eyes only: ebCTF{b517aba29f132c52c9426a177952a2d8}
This is a secret message, for your eyes only: ebCTF{b517aba29f132c52c9426a177952a2d8}


沒有留言:

張貼留言