DiceCTF 2022 - pow-pow

TL;DR

ある関係式を満たすような3つ組の数を提出する問題
愚直にやる方法はあるが、非常に計算時間が掛かるため、別の方法でなんとかする必要がある
関係式を適当な根における指数で考えることで、(実質的に)一様ランダムに選んだ数がsmoothであるまで試行を繰り返すという問題になる
この確率はそこまで小さくないので頑張って回す

Prerequisite

(※特になし、使われている暗号スキームはゼロ知識証明っぽいが特に問題に必要ではない)

Writeup

次のようなスクリプトが与えられる。

#!/usr/local/bin/python

from hashlib import shake_128

# from Crypto.Util.number import getPrime
# p = getPrime(1024)
# q = getPrime(1024)
# n = p*q
n = 20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591
T = 2**64

def is_valid(x):
	return type(x) == int and 0 < x < n

def encode(x):
	return x.to_bytes(256, 'big')

def H(g, h):
	return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

def prove(g):
	h = g
	for _ in range(T):
		h = pow(h, 2, n)
	m = H(g, h)
	r = 1
	pi = 1
	for _ in range(T):
		b, r = divmod(2*r, m)
		pi = pow(pi, 2, n) * pow(g, b, n) % n
	return h, pi

def verify(g, h, pi):
	assert is_valid(g)
	assert is_valid(h)
	assert is_valid(pi)
	assert g != 1 and g != n - 1
	m = H(g, h)
	r = pow(2, T, m)
	assert h == pow(pi, m, n) * pow(g, r, n) % n

if __name__ == '__main__':
	g = int(input('g: '))
	h = int(input('h: '))
	pi = int(input('pi: '))
	verify(g, h, pi)
	with open('flag.txt') as f:
		print(f.read().strip())

2つの1024bit素数の積 $n$ と、 $T=2^{64}$ が定義され、それに対して次を満たすような $g,h,\pi$ を提出することが目標である。

$\begin{aligned} m &= H(g,h) \cr r &= 2^T \mod m \cr h &= \pi^m g^r \mod n \cr \end{aligned}$

計算してみると分かるが、様々な変数が他の変数に依存したりしているせいでこの関係を満たすようなものは簡単に見つからないように見える。

また、prove()という使われていない関数があるが、変数名を見る限り $g$ を決めたら、verify(g,h,pi)のassertionが成功する $h,\pi$ を計算するような関数だと思われる(確かめてないです)。ということはこれを走らせば良いんじゃないかと思うが、2箇所のfor _ in range(T): ...があり、 $T=2^{64}$ であることを考えるとこれは相当長い時間がかかる¹。最初はここの最適化を試みたがあえなく撃沈した。

というわけで、prove()を使わずに $g,h,\pi$ を求める方法を考える。目標の式の変形を試みようとしても、 $n$ が素因数分解出来ないせいで指数を上手く外すことが出来ない²。そこで適当な根 $g_0$ を用意し、左辺と右辺と $g_0$ の指数が同じになるような状態を考える。

$h, \pi, g$ に対して、 $h \equiv g_0^{e_h} \mod n, \pi \equiv g_0^{e_\pi} \mod n, g \equiv g_0^{e_g} \mod n$ とおく。これを利用すると目標とする形は次のようになる。

$g_0^{e_h} \equiv g_0^{e_\pi m} g_0^{e_g r} \mod n$

この両辺で $g_0$ の指数が一致するなら、当然この関係を満たすので次のような $e_h, e_\pi, e_g$ を探すことが目標になる。

$e_h = e_\pi m + e_g r$

ところで $e_g, e_h, g,h,m,r$ の依存関係は次のようになっている(a <- bで、aはbに依存している、つまり「bを決めたらaも決まる」とする)。

r <- m <- g <- e_g
     m <- h <- e_h

これを見ると $e_g, e_h$ を決定すると自動的に $m,r$ が決まり、その結果から $e_\pi$ も決まることが分かる。というわけで適切な $e_g, e_h$ を探す事を考える。

$e_\pi$ について解くと次のようになる。

$e_\pi = \frac {e_h - e_gr}{m}$

$e_\pi$ は当然整数なので $e_h - e_gr$ が $m$ の倍数になっているような $e_h, e_g$ を用意すれば良い。 $e_h - e_gr$ が多項式で面倒なので $e_h=0$ として $e_gr$ が $m$ の倍数となることを考える³。もっと言えば $r$ の部分を考えるのも面倒なので $e_g$ が $m$ の倍数となる事を考える⁴。

$m$ がハッシュ関数を使って求められるせいで、 $e_g$ が確定するまで予測出来ないことから、この関係を満たすのも難しいように思えるが、もし $m$ がsmoothかつ、 $e_g$ が大量の素因数の積からなる場合ならこの関係を満たすように思える。 $m$ はハッシュ関数によって生成されるので実質一様ランダムと考えると、一様ランダムな数を適当に取ってきた時にそれがある数未満の素因数の積で構成されるぐらいsmoothである確率を考える。

手元で軽い実験を行ってみると、ランダムに選んだ数が $10^6$ 未満の素因数に分解される確率は少なくとも $1/10^6$ よりは大きそうな結果が得られた(補遺を参照のこと)⁵。ということは $e_g$ を $10^6$ 未満の素数の積(加えてある程度小さい素数は複数回掛ける)とすれば、現実的な $e_g$ の選択回数( $\sim 10^6$ )で条件を満たす $e_g$ が得られる予感がする。

とは言っても $e_g$ は非常に大きな数になるため、 $e_g$ の選択の度に $g \equiv g_0 ^{e_g} \mod n$ を計算するのは現実的では無い。ある選択の $e_g$ に対して、2以上の適当な整数 $C$ を掛けた $Ce_g$ も $e_g$ として適切なので $e_g \leftarrow 2e_g$ と更新し、 $g_0^{2e_g} \equiv g^2 \mod n$ であるから、 $g \leftarrow g^2 \mod n$ とすることで計算量を抑える。

こうして $e_g$ を選択し、 $g,h$ から $m$ を求めて $e_g$ が $m$ の倍数であるかを判定し、そうであれば探索を終了して $e_\pi$ を求めてそこから $\pi$ を求めるという方法で目標を満たす $g,h,\pi$ が得られる。だいたい17万回ぐらいの選択で終わる。

Code

from hashlib import shake_128
from xcrypto.prime import create_sieve


def encode(x):
    return x.to_bytes(256, 'big')

def H(g, h):
    return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

def is_valid(x):
    return type(x) == int and 0 < x < n

def verify(g, h, pi):
    assert is_valid(g)
    assert is_valid(h)
    assert is_valid(pi)
    assert g != 1 and g != n - 1
    m = H(g, h)
    r = pow(2, T, m)
    assert h == pow(pi, m, n) * pow(g, r, n) % n

n = 20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591
T = 2**64

g0 = 2
sieve = create_sieve(10**6)

e_g = 1
for i, res in enumerate(sieve):
    if res:
        exponent = 1 if i > 100 else 10
        e_g *= i**exponent

e_h = 0
g = pow(g0, e_g, n)
h = pow(g0, e_h, n)  # obviously 1
C = 2

cnt = 0
print("[+] start searching...")
while True:
    cnt += 1
    if cnt % 1000 == 0:
        print(f"current: {cnt}")
    m = H(g, h)
    if e_g % m == 0:
        print("[+] Found!!")
        r = pow(2, T, m)
        e_pi = - e_g // m * r
        break

    e_g *= C
    g = pow(g, C, n)

pi = pow(g0, e_pi, n)
print(f"{g=}")
print(f"{h=}")
print(f"{pi=}")

verify(g, h, pi)

Flag

ローカルで解いただけだが、問題リポジトリにあった

dice{the_m1n1gun_4nd_f1shb0nes_the_r0ck3t_launch3r}

Resources

dicectf-2022-challenges/crypto/pow-pow at master · dicegang/dicectf-2022-challenges: 問題ファイル
priv.pub: 公式Writeup
CTFtime.org / DiceCTF 2022 / pow-pow / Writeup: 十分smoothな $m$ を得るまで回すという方針を示したWriteup

Appendix: smoothな数を得られる確率について

$10^6$ 未満の素因数の積で表される数が得られる確率の大まかなオーダーを検証するため、次のコードで軽い実験を行った。

a = 1
b = 2^128
lim = 10^6
cnt = 0

while True:
    found = True
    x = randint(a, b)
    f = factor(x, limit=lim)
    for p, e in f:
        if int(p) > lim:
            found = False
            break

    cnt += 1
    if cnt % 10000 == 0:
        print(f"current: {cnt}")
    if found:
        print(f"[+] Found at {cnt}")
        print(f)
        break

これを5回回してみたが、最高で65万回ぐらいのループが回ったぐらいで残り4回は30万回より小さかった(1回に関しては1万回にも満たなかったので外れ値扱いした)。

そういうわけで、一様ランダムに選んだ数が $10^6$ 未満の素数の積となるぐらいsmoothな確率は $1/10^6$ より大きく、 $e_g$ の選択回数の期待値は十分現実的であると判断した。

少なくともCTFの開催期間である48時間は余裕で超えるだろう

RSA暗号において、 $ed \equiv 1 \mod \phi(N)$ となる $d$ を $N$ の素因数分解無しで求めるのが難しいのと同じ理屈

現時点の自由度は $e_g, e_h$ の2つなので片方(ここでは $e_h$ を決定してもまだ $e_\pi$ は定まらない

⁴

$r = 2^T + ml$ となるので、右辺第二項は $m$ で割り切ることが出来、結局 $e_g2^T$ が $m$ の倍数であるかを考えれば良いのでそこまで面倒では無い

⁵

この結果は個人的にはかなり非自明で、当初はこの辺で解けないと思ってWriteupを見たら「 $m$ がsmoothになるまで $e_g$ を試す」と書いており、ビビって検証を始めた。 $e_g$ として大量の素因数の積を用いることを思いつかなったのが敗因