K的重要性

当我们使用ECDSA进行签名的时候，k的保密性非常重要。如果我们对所以的签名操作都用一样的k或者我们的随机数生成器存在可预测性，一个攻击者可能会猜出私钥。

索尼几年前曾犯过这个错误。PlayStation 3 只能运行被索尼的进行ECDSA签名的游戏。如果我想为PlayStation 3开发了一个新的游戏，除非我从索尼获得签名值，否则我及时发布了，也运行不了这个游戏。问题是，索尼签名时用了一个静态的k值而不是随机生成的。

这么获取私钥d和随机数k?

看看这个等式 s = k^-1 (z + r*da) mod n
显然，未知数只有2个，da和k。我们买2份索尼游戏，签名值分别是(r1 , s1)、(r2, s2), 由于k值一样，故r 值也一样

s1 = k^-1 (z1 + rda) mod n等式1
s2= k^-1 (z2 + rda) mod n等式2

等式1-等式2
s1 -s2 = k^-1 (z1 - z2) mod n
z1和z2 可以自己使用哈希算法对软件进行哈希能够获取到。s1和s2能够从前面值中获取到。所以k值就轻松的获取到了
K = (s1 -s2)^-1 * (z1 -z2) mod n
再把k值代入等式1或者等式2，就能计算da了。

例题：ecdsa：

源码：

import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor
import secret

p = getPrime(256)
gen = lambda: p + getPrime(16)
pad = lambda m: m + os.urandom(32 - len(m) % 32)

key = os.urandom(30)
sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)
sig1 = sk.sign(data=b'This is the first message.', k=gen()).hex()
sig2 = sk.sign(data=b'Here is another message.', k=gen()).hex()
enc = xor(hashlib.sha512(key).digest(), pad(secret.flag)).hex()

print(f"{sig1 = }\n{sig2 = }\n{enc = }")
'''
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
'''

wp：

from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Util.Padding import pad,unpad
import ecdsa
from hashlib import *
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor

sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
# print(long_to_bytes(int(enc,16)))
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
# E = EllipticCurve(GF(p),[a,b])
# G = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

r1 = int(sig1[:64], 16)
r2 = int(sig2[:64], 16)
s1 = int(sig1[64:], 16)
s2 = int(sig2[64:], 16)
enc = int(enc, 16)

z1 = sha1(b'This is the first message.').digest()
z2 = sha1(b'Here is another message.').digest()
s1_1 = inverse(s1,n)
s2_1 = inverse(s2,n)

for i in range(-2**16,2**16):
    x = (s2_1*bytes_to_long(z2) - s1_1*bytes_to_long(z1) + i)%n
    key = long_to_bytes(x * inverse(s1_1*r1 - s2_1*r2,n) % n)
    # print(sha512(key).digest())
    flag = long_to_bytes(bytes_to_long(sha512(key).digest()) ^ enc)
    if b'flag' in flag:
        print(flag)