Writeup: EBCTF 2013 - Challenge CRY200 “One to many”

タイトルは"1対多"でいかにもRSAの同一平文だし、実際に中国人の剰余定理からも計算できたそうですが、別の解法を。

$\gcd(n_k,\, (\prod n_i)/n_k)$ を計算するとn_763, n_3821が互いに素ではないことがわかる。よって共通の素数pをgcd(n_763, n_3821)から求めることができてnの素因数分解ができた。

eの値がまだ不明だが、id:k_operafanさんにとりあえず65537を試してみよと言われて、試したら当たってしまった。怖い。あとは普通にRSAの鍵を作って計算するだけである。

import Crypto.PublicKey.RSA as RSA
from Crypto.Util.number import *

e = long(65537)

def read_message(filename):
    with open(filename) as f:
        n = int(f.readline()[2:-1])
        c = int(f.readline()[14:-1])
    return n, c

n, c = read_message("files/message%d.txt" % 763)
n2, c2 = read_message("files/message%d.txt" % 3821)
p = GCD(n, n2)
q = n/p
d = inverse(e, (p-1)*(q-1))
m = RSA.construct((n, e, d)).decrypt(c)
print long_to_bytes(m)

This is a secret message, for your eyes only: ebCTF{b517aba29f132c52c9426a177952a2d8}

複数の解法を用意してるのだろうか。