久しぶりにCTFに出た。暗号だけやってたけどこの問題だけ解けず。

def bytes_to_long(data):
    return int(data.encode("hex"),16)

def rsa(msg,e,n):
    return pow(bytes_to_long(msg),e,n)

flag = open('flag.txt','r').read()
tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N =  p*q
print('msg1 = '+str(rsa("You can't factor the modulus",e,N)))
print('msg2 = '+str(rsa("If you don't know the modulus!",e,N)))
print('flag = '+str(rsa(flag,e,N)))

RSA。ソースを読むと、平文\(m_1, m_2\)、公開鍵\(e\)、暗号文\(c_1,c_2,c_{\mathrm{flag}}\)が与えられてる。

公開鍵\(n\)がわからなくて、\(p,q\)のだいたいの比がわかる。

もし、\(n\) を計算できれば、\(p,q\)の比から\(p,q\)のbitの上位半分がわかるので、 Coppersmith法が使えて、\(p,q\)が求まる。

さらに、秘密鍵\(d\)が求まるので、flagを復号できる(Coppersmith’s Attack)。という流れ。

まず\(n\)の求める。

$$ c_1 = m_1^e \bmod n $$

$$ c_2 = m_2^e \bmod n $$

だから

$$ m_1^e – c_1 = k_1 n$$

$$ m_2^e – c_2 = k_2 n $$

ここで、\(k_1n,k_2n\)の最大公約数を取る。

$$ \gcd(k_1,k_2)n=\gcd(m_1^e-c_1,m_2^e-c_2) $$

\(\gcd(k_1,k_2)\)は十分小さいと予想できて、適当に全探索すれば\(n\)が求まる。あとでわかるけど\(1\)だったのでその必要はなかった。

CTF中は、多倍長整数と最大公約数の計算に C++ の Boost を使っていて、1時間経っても終わらなくて、もっと良い方法があるのかと思ってやめてしまった。GMP使ったら10秒かからなかった。GMP凄い。

Coopersmith法は、SageMathで実装されている。SageMathの実装だと、パラメータが、
$$ X=\mathrm{ceil}(1/2N^{\beta^2/\delta-\epsilon}) \\ \beta=1.0 \\ \epsilon = \beta/8 $$
で、\( b\ge N^\beta \)となるような\( N\)の任意の約数\( b\)について、\( |x|<X\)かつ\( f(x)=0 \bmod b\)となるような\( x\)を全て求めるアルゴリズム。ただし\( |x|\ge X\)となるような\( x\)を求めることもある。

$$ a_1 = \mathrm{0xDEAD} \\ a_2 = \mathrm{0xBEEF} $$

とすると、

$$ \frac{p}{q}\sim \frac{a_1}{a_2} $$

であり、\(p\)の下界\(\bar{p}\)が求まる。

$$ p>\sqrt{\frac{na_1 \cdot 2^{1023}}{a_2 \cdot 2^{1023} – 2^{500}}} = \bar{p} $$

これを用いて、

$$ f(x)=x+\bar{p} \\
|x|<2^{500} \\
\beta=0.5 $$

として、Coppersmith法を用いると、$$ f(x) = 0 \bmod p $$ となるような \(x\) が求まる。よって、$$ p = x+\bar{p} $$

\(p\)が求まったので、\(q\)が求まり、さらに\(d\)が求まるので flag を復号できる。

p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}


ソース

参考