HITCON CTF 2019 Crypto Writeup(+1) Crypto道場七[10/100]

どうも。duckです。
HITCONCTFやってきました。辛うじて１題解けたのでWriteup書きます。

１．Lost Modulus Again
今回もファイル共有から。

output
Dropbox - output - Simplify your life
prob.py
Dropbox - prob.py - Simplify your life

短いのでprob.pyは貼る。

from Crypto.Util.number import *
 
 
class Key:
    def __init__(self, bits):
        assert bits >= 512
        self.p = getPrime(bits)
        self.q = getPrime(bits)
        self.n = self.p * self.q
        self.e = 0x100007
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
        self.dmp1 = self.d%(self.p-1)
        self.dmq1 = self.d%(self.q-1)
        self.iqmp = inverse(self.q, self.p)
        self.ipmq = inverse(self.p, self.q)
 
    def encrypt(self, data):
        num = bytes_to_long(data)
        result = pow(num, self.e, self.n)
        return long_to_bytes(result)
 
    def decrypt(self, data):
        num = bytes_to_long(data)
        v1 = pow(num, self.dmp1, self.p)
        v2 = pow(num, self.dmq1, self.q)
        result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
        return long_to_bytes(result)
 
    def __str__(self):
        return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)
 
def main():
    key = Key(1024)
    flag = open('flag').read()
    encrypt_flag = key.encrypt(flag)
    assert key.decrypt(encrypt_flag) == flag
    print key
    print encrypt_flag.encode('hex')
 
 
if __name__ == '__main__':
    main()

いつものごとく長い文字を置き換える。
$I_p={\rm ipmq},I_q={\rm iqmp}$ 。dmp1,dmp2はRSA-CRTでの処理高速化に使う項なので無視。
ふつーのRSA-CRTなら $I_p$ か $I_q$ の片方でいいのでなんか変だな？と思っておく。

次に

return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)

を見ると、やべえ秘密鍵dが流出してるうける。
が、 $N$ がないので復号無理。
というわけで $N$ を求めに行く。
given: $e,d,I_p,I_q$

$p I_p = 1\pmod q, q I_q = 1 \pmod p$ の周りから情報を抜き出す。
$p,q$ から $I_p,I_q$ を求めていることを考えると、拡張ユークリッドの互除法より
$xp+qy=1$ の $x,y$ から
$I_p=x \bmod q,I_q=y \bmod p$ としているはず。
$x=I_p$ とすると $y$ は負の数であり、bit数を考えると $I_q - p$ しかない。

よって $I_p p + q(I_q - p) = 1$ 。
変形して
$p(I_p-1)+q(I_q-1)=(p-1)(q-1) \cdots ①$ 。
$I_p-1,I_q-1$ に対する拡張ユークリッの互除法から $x_0,y_0$ が求まり
$x_0(I_p-1)+y_0(I_q-1)=\gcd{(I_p-1,I_q-1)} = 18 \cdots ②$ と書ける。
$L=\frac{ed-1}{18},X_0=L*x_0,Y_0=L*y_0$ とおくと、②の両辺に $L$ をかけて
$X_0(I_p-1)+Y_0(I_q-1)=ed-1=k(p-1)(q-1)$ 、 $k$ :整数　を得る。
特殊解 $X_0,Y_0$ を用いて
$X(I_p-1)+Y(I_q-1)=k(p-1)(q-1)$ の一般解 $X,Y$ が $X=X_0 - \frac{I_q-1}{18}l,Y=Y_0 + \frac{I_p - 1}{18}l$ と表せる。
①からこの解のなかに $X=kp,Y=kq$ となるものがあるはずなので、 $l$ に対してブルートフォースする。
得られた $X=kx_p,Y=ky_q$ としたときの $x_p,y_q$ が正しい $p,q$ の判定には、 $k(x_p-1)(y_q-1)=ed-1$ を満たすかを用いた。
探索範囲をbit数から絞りこんでなお１２分かかった。

p=166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929
q=135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477

$N$ がわかったので解けた。 $C$ を暗号文とする。