SECCON 2015 Qual Writeup Crypto 200 Find the prime numbers

問題

つなぐと

2622440554406490912 + 0147433867683690946 = 4258610457570922687

などと表示される。数字は３秒おきに更新される。

解法

もらったソースを読む。

	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を当てたい。表示しているのはよく読むと

$x (n + 1)^k + (n + 1) x = (n + 1)^{m+1} x^2 \mod n^2$
という等式のようだ。どう考えても、左辺+記号は*の間違いだろう。
つまり
$a * b = c \mod n^2$
となる、 $a, b, c$ があたえられるわけだ。
ここから
$a * b = c + l n^2$
$l n^2 = a * b - c$
つまり、 $a* b - c$ を素因数分解すれば $n^2$ の約数（素数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

よって、 $n = 42727 \times 58757 = 2510510339$ が得られた。
次に、
$x (n + 1)^k + (n + 1) x = (n + 1)^{m+1} x^2 \mod n^2$
の $x$ を復元したい。これも簡単で、 $x = b(n + 1)^{-1} \mod n^2$ と求められる。
最後に
$x (n + 1)^k = a$ から $k = \log_{n+1}(a x^{-1})$ と求められる。
離散対数はPARI/GPを用いた。

? znlog(3792102298388437469,Mod(2510510340, 6302662162225894921))
%1 = 1510490612

$k = 1510490612$ が求まったのでサーバに送れば良い。
FLAG: SECCON{SECCoooo_oooOooo_ooooooooN}

たぶん、想定解ではないが、いずれにせよ桁が小さすぎるのでどうやっても解けるとおもう。

使ったPython スクリプト

 giste65da419e982225b22de