読者です 読者をやめる 読者になる 読者になる

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

 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