(EC)DSA で nonceが小さい時 - crypto-writeup-public

$s \equiv (h + rd)k^{-1} \mod n$ の $k$ が小さくて（ $k$ がsha1で決まるなど）、かつ複数のインスタンスを集められるときはHidden Number Problemになる

$k_i - s^{-1}rd - s^{-1}h_i \equiv 0 \mod n$ なので、Hidden Number Problemの式 $x_i - t_i y + a_i \equiv 0 \mod p$ と対応付けると次のようになる

$k_i \leftrightarrow x_i$

$s^{-1}r \leftrightarrow t_i$

$d \leftrightarrow y$

$a_i \leftrightarrow -s^{-1}h_i$

from hashlib import sha1

# secp256k1
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

n = int(E.order())

d = randint(2, n) # private key

P = d * G # public key

nonce_max = 2**128

def sign(msg):
    h = int(sha1(msg).hexdigest(), 16)
    while True:
        k = randint(2, nonce_max-1)
        if gcd(k, n) == 1:
            break

    r = int((h * G).xy()[0])
    s = (h + r*d) * inverse_mod(k, n) % n
    return (r, s)

msgs = [b"hello", b"world", b"heyheyhey"]
signs = [sign(m) for m in msgs]

N = len(msgs)
h = [int(sha1(m).hexdigest(), 16) for m in msgs]
r, s = zip(*signs)
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [h[i] * inverse_mod(-s[i], n) % n for i in range(N)]

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()
for row in list(L):
    k1 = abs(row[0])
    x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
    # x = abs(row[-2] / (nonce_max / n))
    if x*G == P:
        print(x) # find private key