from hashlib import sha256 def keygen(password): while True: p = 2 * random_prime(2 ^ 521) + 1 if p.is_prime(proof=False): break base, h = 3, password for i in range(256): h = sha256(h).digest() x = int.from_bytes(h * 2, "big") return base, p, pow(base, x, p), x def sign(message, priv): h = int(sha256(message).hexdigest(), 16) k = next_prime(int.from_bytes( sha256(message + priv.to_bytes(128, "big")).digest() + sha256(message).digest(), "big" )) r = int(pow(g, (k - 1) / 2, p)) s = int(Zmod((p - 1) / 2)(-r * priv + h) / k) return r, s g, p, pub, priv = keygen(b"[redacted]") r, s = sign(b"blockchain-ready deterministic signatures", priv) ''' ----------------------------------------------------------------------------------------X8 sage: p 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463 sage: pub 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198 sage: r 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521 sage: s 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967 sage: "midnight{" + str(priv) + "}" == flag True sage: time CPU times: user 4 µs, sys: 0 ns, total: 4 µs Wall time: 6.91 µs Hammer time: yes '''
https://furutsuki.hatenablog.com/entry/2021/04/11/092829#dbcsig_64434
DSA だがだし、
# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage ... from hashlib import sha256 g = 3 p = 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463 pub = 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198 r = 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521 s = 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967 message = b"blockchain-ready deterministic signatures" h = int(sha256(message).hexdigest(), 16) q = (p-1) // 2 # assert q.is_prime ???????? PR.<d_, kh, a> = PolynomialRing(Zmod(q)) f = 2^256 * s * kh + s * (h + a) + r * (d_ + 2^256 * d_) - h roots = small_roots(f, [2^256, 2^256, 1000], d=4, m=4) for root in roots: dval = Integer(root[0]) dval = dval * 2^256 + dval if pow(g, dval, p) == pub: print("[+] found: {}".format(dval)) break else: print("[-] wrong: {}".format(dval))
Inequality_Solving_with_CVP のテクを使って、次のようにも解ける
import os from hashlib import sha256 g = 3 # while True: # p = 2*random_prime(2^521) + 1 # if p.is_prime(proof=False): # break p = 2208999820857629084844898049184204625514077638848903812266763331630270258760615385915643248593594110916852840723890149166178203356254570529299804284681970479 q = (p-1) // 2 d = int.from_bytes(sha256(os.urandom(16)).digest() * 2, "big") pub = pow(g, d, p) message = b"takoyakitabetai" h = int(sha256(message).hexdigest(), 16) k = int.from_bytes(sha256(d.to_bytes(128, "big")).digest(), "big")*2^256 + h r = int(pow(g,(k-1)//2,p)) s = int((-r*d+h) * inverse_mod(k, q) % q) # (k_, d1, d2, t) M = matrix(ZZ, [ [2^256*s, 2^256*r, r,-q], [ 1, 0, 0, 0], [ 0, 1, 0, 0], [ 0, 0, 1, 0], [ 0, 1,-1, 0], #lb = 0, ub = 0 [ 0, 0, 0, 1], ]) c = -s*h + h lb = [c, 0, 0, 0, 0, 0] ub = [c, 2^256, 2^256, 2^256, 0, q] results, weights = solve(M.transpose(), lb, ub) print([results[i] // weights[i] for i in range(len(results))]) print([d % 2^256, k >> 256])
