初投稿。
CTF初心者です。
Daily AlpacaHack 1/2のsuper-tomato解いたwriteupです。
ぴんくいろ の ぼうしょく は とまと を もとめて いる...
ubuntu に nc～～を入力すると
問題文のpythonファイルは
19行目にある通り、2048bitのランダムな素数のPと、1024bitのランダムな素数のa、を使って、Aのchoice乗をpで割った余りが1になるような整数choiceを求める問題。
桁数が小さい場合は全探索でごり押してもいいけど、今回の場合は、2つの数とも桁数が凄いことになってるのでそんなことしてたら処理が終わりそうにありません。
ここで、choiceを求める方法として、フェルマーの小定理というものがあります(調べるまで知らなかった。)
フェルマーの小定理とは、pが素数で、AがPの倍数でない正の整数のとき
A^(P−1)≡1(modP)
が成り立つことだそうです。凄いですね。
そして、choice=p-1 とすればflagが得られます。
というのも、そもそも、pは2048bitの素数でaは1024bitの素数で、互いに素(2つの整数の最大公約数が1。例えば、2と5とか。)の自然数なのでフェルマーの小定理を使えます。