kurenaif 2000 subscribers challenge writeup

強いCTFerかつVTuberのkurenaif先生が2000subscriber記念に問題を提供されていたので取り組みました。面白かったです。

kurenaif先生のチャンネルはこちら

www.youtube.com

問題はこちら

383bitの平文 $m$ を40bit程度の $n$ を用いたRSAで400回暗号化しています。40bitの素因数分解は簡単なので、暗号文を復号すればいいと思いきや、 $m > n_i$ なので復号に成功したとしても $m$ 全体がわかるわけではありません。このような場合の対応として、各暗号文を復号して400個の $m \mod n_i$ を得て中国剰余定理に従って $N = \prod n_i$ 上の $m$ を求めるテクがあります。

しかしここで問題を難しくしているのが、公開鍵 $e = 20000$ です。 $20000 = 2^5 * 5^4$ です。 $\phi_i = (p_i - 1)(q_i - 1)$ は $p_i, q_i$ が素数であることから偶数×偶数＝偶数であり、 $gcd(e, \phi_i) = 1$ はまず間違いなく満たされません。

このとき、暗号文 $c_i \mod n_i$ のe乗根は一意に定まらず、複数個存在します。 $phi_i$ が5を素因数に含んでいないケースだけを考えても、各暗号文ごとに少なくとも $2^5 = 32$ 個程度のe乗根が存在して、そのうち $m \mod n_i$ を満たすものは一つだけです。各暗号文についてe乗根全体を探索するのは明らかに不可能です。

そこでe乗根の数を減らすことを考えます。まず、 $c_i \mod n_i$ ではなく、 $c_i \mod p_i, c_i \mod q_i$ について考えます。これで組み合わせの個数が減ることはありませんが、問題を解くのに不便な素因数を除外して考えることができるようになります。

問題を解くのに不便な素因数とは何でしょう。例えば $p_i - 1$ が5を素因数に含むケースは今回はスキップしてしまうことで $e' = 2^5$ を公開鍵とした暗号文についてだけ考えればよくなります。

また、 $p \equiv 3 \mod 4$ のとき、この剰余の法のもとでの $2^x$ 乗根の数は2個に限定されます（どうやって証明するのかわからなかった）。この性質を使うことで、 $m^e \mod p_i$ という暗号文についての答えの候補を2個に絞ることができます。

$p_i$ はおよそ20bitですから、20個ほどの組を集めれば $2^{20}$ 通りの全探索で $m$ の候補が列挙でき、そのなかにフラグがあることを期待できます。

実際には22個の組をつかってやりました。

import ast
with open("output.txt") as f:
    f.readline()
    e = ast.literal_eval(f.readline().strip().split("= ")[1])
    ns = ast.literal_eval(f.readline().strip().split("= ")[1])
    cs = ast.literal_eval(f.readline().strip().split("= ")[1])

e1 = 5^4
e2 = 2^5

xs = []
mods = []
cnt = 0
for i in range(len(ns)):
    for p, _ in factor(ns[i]):
        if p % 4 == 3 and (p-1) % 5 != 0:
            dp = int(pow(e1, -1, p-1))
            xs.append(pow(cs[i], dp, p))
            mods.append(p)

roots = []
for i in range(len(xs)):
    r1, r2 = GF(mods[i])(xs[i]).nth_root(32, all=True)
    roots.append((int(r1), int(r2)))

T = 22
from tqdm import tqdm
from itertools import product
print(2^T)
for pat in tqdm(product([0, 1], repeat=T)):
    rs = []
    for i in range(T):
        rs.append(roots[i][pat[i]])
    x = CRT_list(rs, mods[:T])
    x = int(x)
    if x.bit_length() == 383:
        print(x.to_bytes((383 + 7) // 8, "big"))

kurenaif先生、登録者数2000人突破おめでとうございます。これからもますますのご活躍を期待しています。

ふるつき

v('=')v かに

kurenaif 2000 subscribers challenge writeup