SECCON 2015 Qual Writeup Crypto 200 Find the prime numbers
問題
つなぐと
2622440554406490912 + 0147433867683690946 = 4258610457570922687
などと表示される。数字は3秒おきに更新される。
解法
もらったソースを読む。
while 1: x = pow(random.randint(1000000000, 9999999999), n, (n * n)) o = (pow(n + 1, 1, n * n) * x) % (n * n) y = (((pow(o, l, n * n) - 1) // n) * d) % n if y == 1: break c = (pow(n + 1, int(v["num"]), n * n) * x) % (n * n) h = (c * o) % (n * n) q = "%019d + %019d = %019d" % (c, o, h) print q z = "QUERY_STRING" if z in os.environ and os.environ[z] != "": if w[e]["time"] < t and os.environ[z] == v["num"]: print "SECCON{" + v["flag"] + "}" w[e]["time"] = t + 60 w[e]["outp"] = q else: w[e]["time"] = t + 3 w[e]["outp"] = q
何をやっているのかはよくわからないが、v["num"]を当てれば良いらしい。
まず、nを当てたい。表示しているのはよく読むと
という等式のようだ。どう考えても、左辺+記号は*の間違いだろう。
つまり
となる、があたえられるわけだ。
ここから
つまり、を素因数分解すればの約数(素数p,q)が得られる。
たかだか36桁程度なのでmsieveを使って解ける(べつにためし割りでも大丈夫だろう)
$ msieve -v 386636553706711704268844486594760065 factoring 386636553706711704268844486594760065 (36 digits) p1 factor: 5 p1 factor: 7 p2 factor: 11 p5 factor: 42727 p5 factor: 42727 p5 factor: 58757 p5 factor: 58757 prp15 factor: 159337556575289
よって、が得られた。
次に、
のを復元したい。これも簡単で、と求められる。
最後に
からと求められる。
離散対数はPARI/GPを用いた。
? znlog(3792102298388437469,Mod(2510510340, 6302662162225894921)) %1 = 1510490612
が求まったのでサーバに送れば良い。
FLAG: SECCON{SECCoooo_oooOooo_ooooooooN}
たぶん、想定解ではないが、いずれにせよ桁が小さすぎるのでどうやっても解けるとおもう。