この大会は2018/3/24 0:00(JST)~2018/3/26 0:00(JST)に開催されました。
今回もチームで参戦。結果は860点で411チーム中59位でした。
自分で解けた問題をWriteupとして書いておきます。
Nonsense (crypto 200)
ECDSAの問題だが、ほぼ数学の問題。xの値を求めればよい。
state = seed state = (a * state + b) % m k = state (r, s) = signature.sign(message, k) state = (a * state + b) % m k = state (r, s) = signature.sign(message, k) : h1 = int(hashlib.md5(m1).hexdigest(), 16) h2 = int(hashlib.md5(m2).hexdigest(), 16) r1 = pow(g, k1, p) % q s1 = int((x * r1 + h1) * invert(k1, q) % q) r2 = pow(g, k2, p) % q s2 = int((x * r2 + h2) * invert(k2, q) % q) k2 = a * k1 + b (mod m)
m = qになっていることを使い、mod q を前提に式を変形していく。
s1 * k1 = x * r1 + h1 s2 * k2 = x * r2 + h2 ↓ s1 * k1 = x * r1 + h1 s2 * (a * k1 + b) = x * r2 + h2 ↓ s1 * s2 * k1 * a = x * r1 * s2 * a + h1 * s2 * a s1 * s2 * k1 * a + s1 * s2 * b = x * r2 * s1 + h2 * s1 ↓ s1 * s2 * b = x * (r2 * s1 - r1 * s2 * a) + (h2 * s1 - h1 * s2 * a) ↓ x = (s1 * s2 * b - (h2 * s1 - h1 * s2 * a)) * invert(r2 * s1 - r1 * s2 * a, q)
コードにすると、以下の通り。
import hashlib import gmpy2 q = 1118817215266473099401489299835945027713635248219 a = 3437776292996777467976657547577967657547 b = 828669865469592426262363475477574643634 r1 = 1030409245884476193717141088285092765299686864672 s1 = 830067187231135666416948244755306407163838542785 r2 = 403903893160663712713225718481237860747338118174 s2 = 803753330562964683180744246754284061126230157465 msg1 = 'VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}' msg2 = 'VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}' h1 = int(hashlib.md5(msg1).hexdigest(), 16) h2 = int(hashlib.md5(msg2).hexdigest(), 16) x = ((s1 * s2 * b - (h2 * s1 - h1 * s2 * a)) * gmpy2.invert(r2 * s1 - r1 * s2 * a, q)) % q flag = '%x' % x print flag
9d529e2da84117fe72a1770a79cec6ece4065212