problem

LCG の出力をnonceとして行われた DSA による署名が与えられる。 DSAの秘密鍵を復元せよ。

solution

重要なのは$Q = M$と法が重複していること。 $s \equiv k^{-1}(H(m) + xr)$であり、隣接する$(r_1, s_1), (r_2, s_2)$をとり$k_2 \equiv a k_1 + b$ とおくと $s_2 k_2 \equiv H(m_2) + x r_2 \equiv s_2 (a k_1 + b)$である。 $s_1 k_1 \equiv H(m_1) + x r_1$と併せて$x$を消去すれば$k_1$が求まる。 ひとつ$k$が求まれば$s \equiv k^{-1}(H(m) + xr)$から$x$も求まる。

note

  • tasks.py の出力と signatures の内容がずれてたりして微妙にguessingっぽい
  • 解けたはずなんだけど答えが合わないので見てほしいと @h_noson に投げたらバグを見つけてくれた

implementation

#!/usr/bin/env python3
import hashlib
import gmpy2

# Digital Signature Algorithm
g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
q = 1118817215266473099401489299835945027713635248219

# Linear Congruential Generators
a = 3437776292996777467976657547577967657547
b = 828669865469592426262363475477574643634
m = 1118817215266473099401489299835945027713635248219

assert q == m  # the same

signatures = [
    ('VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}', 1030409245884476193717141088285092765299686864672, 830067187231135666416948244755306407163838542785),
    ('VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}', 403903893160663712713225718481237860747338118174, 803753330562964683180744246754284061126230157465),
    ('VolgaCTF{8NXrNihQFZHXN/aLQeYKtg==}', 573204611556272128788136170196175308321188191436, 91103585122319085944642441222968347176761155259),
    ('VolgaCTF{uDh3jKDKW2utTkblP43NQw==}', 988208923601321592314278832250352152086708201148, 535902494423594375360085340272213659149931817732),
    ('VolgaCTF{gtE4LCuhT5drcDunvKz/oQ==}', 398664332680411743333343859695363011153860369916, 392831307484494740050270232580899453387203218646),
    ('VolgaCTF{rS9IEsyvXHOCUo0/TL2c1A==}', 1069308776596602518230279648695605679674084062212, 1092197517441497735860968374670599451237193808469),
    ('VolgaCTF{4gEh/j9EGwZ20NEoBieDbQ==}', 299126738734367538949359921058714964192219834697, 1033663138335940105270395993670462206279669465530),
    ('VolgaCTF{RwpewhJhMGH0MORFtXQfAw==}', 45947153576235029841784762518202071246619636555, 160232137675713914067049553022084774145041067326),
    ('VolgaCTF{i7QjVusEQboUz2tPx/Uxkw==}', 158481243947457932495342738131507924205209157088, 260728631055453998945003114392349125641429319965),
    ('VolgaCTF{nQwf/+78QMObu3S3Oh1Olg==}', 117030185689896730023482874167356847173848413476, 645757721193000290408806214518814010431656731046),
]

# reconstruct k_i
ks = [ None ] * len(signatures)
for i in range(len(signatures) - 1):
    m1, r1, s1 = signatures[i]
    m2, r2, s2 = signatures[i + 1]
    h1 = int(hashlib.md5(m1.encode()).hexdigest(), 16)
    h2 = int(hashlib.md5(m2.encode()).hexdigest(), 16)
    k1 = gmpy2.invert(s1 * r2 - s2 * a * r1, q) * (h1 * r2 + (s2 * b - h2) * r1) % q
    k2 = (a * k1 + b) % q
    assert pow(g, k1, p) % q == r1
    assert pow(g, k2, p) % q == r2
    ks[i    ] = k1
    ks[i + 1] = k2

# reconstruct x
for i in range(len(signatures)):
    m, r, s = signatures[i]
    k = ks[i]
    h = int(hashlib.md5(m.encode()).hexdigest(), 16)
    assert pow(g, k, p) % q == r
    print(hex((s * k - h) * gmpy2.invert(r, q) % q))