VolgaCTF 2018 Quals Writeup

この大会は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