Balsn CTF 2019 Crypto - CTFと共に生きる

どうも。duckです。
解けません。
どこまでflagににじり寄ったかまとめます。ついでに調べて得た知識もかるく。

1.collision
ハッシュは逆算不可能なんだよ！！
ってことで解けません。

ハッシュの問題って
・DB検索（レインボーテーブル含む）
・ハッシュ衝突させるやつ

ぐらいしか思いつかないんですがどうなんでしょう。解いてる人多いし悔しい。

2.unpredictable
これが一番解けそうでした。
疑似乱数生成器（メルセンヌツイスタ）の内部状態を復元して、RSAもどきを解く問題だと思います。

Mersenne Twisterの出力を推測してみる - ももいろテクノロジー
こことほぼ同じなんですが

randrange(3133731337)

から復元する部分が違います。これがまじむりつらい。

randrangeの実装をソース読んでみたんですけど（後メルセンヌツイスタのソースも）
randrange(N)はNのビット数以下の乱数をメルセンヌツイスタからもらってもしそれがNより大きいなら取り直すってことやってるんすよ。
今、 $2^{31} < 3133731337 < 2^{32}$
なので、 $3133731337 < メルセンヌ　< 2^{32}$ のときはその値が破棄されてしまうと。output.texに書かれてるのは $メルセンヌ　< 3133731337$ となった時だけです。

つまるところ、我々が入手したデータは穴抜けのデータであり、メルセンヌツイスタの内部情報を参考記事のように簡単には復元できないと。
悲しい。

ということで、メルセンヌツイスタの動作から、穴抜け部分の復元を図ります。
3つの内部状態から新たな内部状態１つを作るので、３つわかってれば復元できます。
このプログラムを考えてたら終わってました。
つうか確率で失敗するのでやる気出ませんでした。
だって $1/4$ くらいでとりなおしがはっせいするんだぜ？運ゲーじゃーん。
まあでもたぶんこの方針だよなあ。