kurenaif2000 Writeup

kurenaifさんのYouTubeチャンネルの登録者数が2000人を超えたのを記念して出題してくれた問題が結構面白かったので久々にWriteupとかいうやつを書きます。

https://t.co/bRDAnR9SLW
私からのささやかなお礼ですが、問題を1問作ってみました。サクッと作った問題なので、気軽に説いてくれると嬉しいです！
ちょっとだけエスパー要素はありますが、同じ環境で安定して解けることは確認したのでぜひ解いてみてください！#kurenaif2000 https://t.co/QmryPCvSxC
— kurenaif@VTuber (@fwarashi) October 1, 2021

ツイート中にもありますが、問題が置かれているリポジトリはこちら: kurenaif_2000_subscribers_challenge

配布ファイル

配布ファイルは problem.py と output.txt の2つでCTFにありがちな実行ファイルと出力結果が配られるパターンの問題です。

problem.py:

from Crypto.Util.number import *

flag = bytes_to_long(b"kurenaifCTF{DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMY}")
print("# bit_length = ", flag.bit_length())
e = 20000

ns = []
cs = []

for i in range(2*200):
    p = getPrime(20)
    q = getPrime(20)
    n = p * q
    ns.append(n)
    cs.append(pow(flag, e, n))

print("e=", e)
print("ns=", ns)
print("cs=", cs)

output.txt:

# bit_length =  383
e= 20000
ns= [416139590521, 427116314293, 629446878757, ...]
cs= [69902148630, 222211746557, 205569643709, ...]

初動

まず最初に気づくのは $e=20000$ であるという点です。 $e$ は一般に $ed \equiv 1 \pmod{\phi(N)}$ を満たす必要があり、$\phi(N)$は必ず偶数なので$d$を求めることができません¹。というわけで復号の段階で工夫をする必要があります。

次に、暗号化に使っている素数のビット数が20ビットしかないことに気づきます。ここから「素因数分解は簡単だけど前述の条件を満たさないと復号できないよ」というメッセージを受け取ります。ついでにフラグのビット長が383と、40ビット程度の$N$では全然足りないので中国剰余定理を使って法を大きくする必要があることも頭に入れておきます。

$e$と$\phi(N)$が互いに素でないときの復号

これは過去にも出題されているトピックで、phiN % e == 0のときどうするかという内容での記事があります。

だこつさん: p - 1 ≡ 0 (mod e) のときの RSA 復号方法
うしがぃさん: p-8RSA作問者Writeup

これらとやることはほとんど同じです。

まずは$\phi(N)$から$e$と共通する素因数$s$を消した$\phi'=\phi(N)/s$を計算し、$\phi'$を使って通常通りにRSAを解きます。このとき、$ed = 1 + k\phi'$から値を計算していくと、$$m^{ed}=m \cdot m^{k\phi'}$$になっているはずです。本来であれば$m^{ed}=m$になっているはずなので邪魔な$m^{k\phi'}$を消す必要があります。ここで$\phi'=\phi(N)/s$なので、この$m^{k\phi'}$は位数$s$であることが予想されます。

次に、この$m^{k\phi'}$をどうにかキャンセルする方法を考えます。適当な数$i$に対して$i^{\phi}$を計算して掛け合わせると、次のようになって位数$s$のまま底の方に値を掛け合わせることができます。 $$ m^{k\phi'} \cdot i^{\phi'} = \left(m^k i \right)^{\phi'}$$ したがって、$\left(m^k i \right)^{\phi'}$の取る値は$s$通りしかなく$i$をランダムに取れば$1/s$の確率で復号できることになります。

中国剰余定理を掛けすぎない

この問題では$N, c$の組が400個提供されていますが、これを全て中国剰余定理に入れてしまうと先ほどの$s$が非常に大きくなってしまい、$1/s$の確率を引くのが非常に難しくなります。一方で法が小さすぎては復号自体ができないので、$s$が小さくなるように10個$N$を選んで使います。 $N$は40ビットなので10個掛けると約400ビットとちょうどいい大きさになります。

$\phi(N)$自体が$(p-1)(q-1)$より4の倍数が確定しているので、$e$の素因数である2と5がそれ以上増えないように10個選びました。このとき$s$の値は$4^{10}=1048576$です。

スクリプト

以上の考察からSageのコードを書きます。ちなみにこのスクリプトは運が悪いので i=976335 になるまで正解しません。悲しいね

from output import *

ns2 = []
cs2 = []
pdic = {}
for i in range(len(ns)):
    x = factor(ns[i])
    p = x[0][0]
    q = x[1][0]
    if (p - 1) * (q - 1) % 5 == 0:
        continue
    if (p - 1) * (q - 1) % 8 == 0:
        continue

    ns2.append(p * q)
    cs2.append(cs[i])

    if p not in pdic:
        pdic[p] = 0
    pdic[p] += 1

    if q not in pdic:
        pdic[q] = 0
    pdic[q] += 1

    if len(ns2) == 10:
        break

c2 = crt(cs2, ns2)
n = prod(ns2)

phi = 1
for p in pdic:
    phi *= (p - 1) * p^(pdic[p] - 1)

print('phi:', phi)

phi2 = phi
while phi2 % 2 == 0:
    phi2 /= 2

k = phi / phi2

print('phi2:', phi2)
print('k:', k)
d = pow(e, -1, phi2)
plain_base = pow(c2, d, n)

for i in range(2, k):
    x = plain_base * pow(i, int(phi2), n) % n
    s = int(x).to_bytes(int(x).bit_length() // 8 + 1, 'big')
    if b'kurenaif' in s:
        print(f'Found {i} {s.decode()}')
        break

Flag: kurenaifCTF{https://forms.gle/dmnQPuNRXXXXXXXXX}
（URLなので一応伏せています）

$ed + k\phi(N) = 1$から$d,k$を求めるためには$e,\phi(N)$が互いに素である必要がある ↩︎