SECCON13 final [crypto] DLP+

問題文が短いし簡単そ～と思ったら、意外と大変だった

問題

まず好きな素数 $p$ をジャッジに送ります。するとジャッジが $2^{512}$ 未満の非負整数 $x$ を一様ランダムに生成し、 $g := \lfloor p/2 \rfloor, h := \lfloor p/3 \rfloor$ として $r := (g^x + h^x) \mod p$ を送り返してきます。$120$ 秒以内に $x$ を特定してください。

解法

• そもそも離散対数だけでも $p$ にいい条件がないと難しいのに、 $g^x + h^x$ なんてまともに扱えるわけがないので、どちらかの位数が小さくないと困りそう。ただどっちも小さいと $x$ を特定するのに十分な情報量がなくなるのでそもそも不可能(あとどっちも小さくするのは難しそう)。
• というわけで、$g = (p-1)/2$ の位数が小さい、つまり $2$ の位数が小さいような素数 $p$ であって、$h$ を底とする離散対数がそこそこ速く解けるような素数 $p$ を取るのを目標にした。
  • こうすると、$g^x \mod p$ を全探索できるので、$h^x = r-g^x$ から $x$ を求める離散対数を全部試せば良い
• $2$ の位数が小さい素数として思いつくのはメルセンヌ素数、フェルマー素数、あるいは $2^n-1$ や $2^n+1$ 自体が素数じゃなくてもその素因数、とか。
• 一方で、$h$ 側の離散対数を高速に解きたいため、(Pohlig–Hellman を使いたいので) $p-1$ の素因数がそこそこ小さい、具体的には $40$ bit 程度で収まっていてほしい、という要請もある。
• メルセンヌ素数 $p = 2^m-1$ なら、$p-1 = 2(2^{m-1}-1)$ がそこそこ素因数分解できると期待できるので色々試していたが、どれも結局かなり大きな素因数も残ってしまうので困っていたところ、kobaさんに「Pohlig-Hellman は要は最後に各($p-1$の)素因数 $q$ での離散対数を求めて中国剰余定理してるだけなので、$x$ が $512$ bit しかないなら大きい素因数は無視して小さい素因数だけで $512$ bit 分集まれば良い」と言われて、たしかに～～～となった
• sage の trial_division とかを使って色々試すと、$p = 2^{2281}-1$ の $33$bit 以下の素因数だけで $512$ bit 分集まることがわかったので、これを使うことにした
• とはいえ、$g$ の位数 ( $= -(1/2)$ の位数) は $2m = 4562$ なので、"$33$bit 程度の離散対数をいくつか" を $4562$ 回解くことになり、余裕で間に合わない
• 高速化の一つは、離散対数を baby-giant で解くときに、クエリが大量に来る場合は前計算を重めにしてクエリ時に探索する側を軽くするという競プロでありがちなやつで、これをやると $1$ 回解くのに $1$ 秒くらいになった
• もう一つより大事だったのは、$p-1 = 2(2^{m-1}-1)$ が素因数 $m=2281$ を持つことだった(フェルマーの小定理)。なぜこれが嬉しいかというと、$g^x$ 側の値を全探索する際に $e_g := x \mod 2m$ の値は分かっているので、$h$ 側の離散対数で求まった $x \mod m$ とこの値が矛盾するならその時点で不適なことがわかる。
• なので $g^x$ を fix したあとまずはじめに $h$ 側の $x \mod m$ の離散対数だけやって、これが矛盾してないときだけ残りの大きい素数たちでも離散対数を解いて $x$ を復元し、最後に実際に解になってるか判定 とすると、最後まで候補として残る $e_g$ が数通りくらいにまで減るので、十分高速になった