ECDSA 与 SM2 签名

写了两个签名的题,总结复盘一下

主要还是顺便学习了一下国密族

动手能力还是不好,很多关于圆曲运算的sage代码不会写,debug效率低下

ECDSA

算法实现

签名

  • 随机选取私钥d和临时私钥k
  • 选取基点G
  • 计算Q=d⋅G,R=k⋅GQ = d \cdot G, R = k \cdot G
  • r≡  xR(modn)r \equiv \; x_R (mod n)
  • s=k−1⋅(H(m)+r⋅d) mod ns=k^{-1}\cdot\big(H(m)+r\cdot d\big)\bmod n
  • 输出签名(r,s)(r,s)

验签

  • 计算 z=H(m)z=H(m)
  • u=z⋅s−1(modn),v=r⋅s−1(modn)u = z\cdot s^{-1}\pmod n,\quad v = r\cdot s^{-1}\pmod n
  • P=uG+vQP = uG + vQ
  • 验证:r=?xP(modn)r \stackrel{?}{=} x_P \pmod n 若相等,则消息未经篡改

常见攻击面基本都是针对临时私钥k的攻击:弱随机数 k 重用 /部分已知 nonce k/Nonce k 和私钥线性相关等等

sages实现:

p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA08708A21168A3908A07239A118014A68344975B8824422C37B0850
gx = 0x6B17D1F2E12C4247F8BCE6E56A44F277037D812DEB33A0F4A13945D898C296
gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

E = EllipticCurve(GF(p), [a, b])
G = E(gx, gy) # 基点
order_G = n # 基点阶

# 2. 生成密钥对
def ecdsa_keygen():
d = randint(1, order_G - 1) # 私钥 d
Q = d * G # 公钥 Q = dG
return d, Q

# 3. ECDSA 签名函数
def ecdsa_sign(d, msg_hash_int):
while True:
k = randint(1, order_G - 1)
r = (k * G).x() % order_G
if r == 0:
continue
# s = k^{-1} * (hash + d*r) mod n
k_inv = pow(k, -1, order_G)
s = (k_inv * (msg_hash_int + d * r)) % order_G
if s != 0:
return (r, s)

def ecdsa_verify(Q, msg_hash_int, sig):
r, s = sig
if not (1 <= r < order_G and 1 <= s < order_G):
return False
s_inv = pow(s, -1, order_G)
u1 = (msg_hash_int * s_inv) % order_G
u2 = (r * s_inv) % order_G
P = u1 * G + u2 * Q
return P.x() % order_G == r

SM2

算法实现

签名

  1. r=(e+x1) mod n,(x1,y1)=kGr = (e + x_1) \bmod n,\quad (x_1,y_1)=kG
  2. s=(1+d)−1⋅(k−r⋅d) mod ns = (1+d)^{-1}\cdot(k - r\cdot d) \bmod n

验签

  1. t=(r+s) mod nt=(r+s)\bmod n
  2. (x1′,y1′)=sG+tPA(x_1',y_1') = sG + tP_A
  3. 校验 r=?(e+x1′) mod nr \overset{?}{=}(e + x_1') \bmod n
    常见攻击面大部分也是围绕k的泄露来的

sage实现

# ========= SM2 sm2p256v1 标准参数 国密推荐曲线 =========
p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
a = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
Gx =0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy =0xBC3736A2F4F6779C59BDCEE36B692153D0A29682A12839A62E000B5B32C48508

E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy)

# ---------------- 密钥生成 ----------------
def sm2_keygen():
d = randint(1, n-1) #私钥 d
P = d * G #公钥 P = dG
return d, P

# ---------------- SM2签名函数 ----------------
def sm2_sign(d, e_int):
while True:
k = randint(1, n-1)
x1 = (k * G).x()
r = (e_int + x1) % n
if r == 0 or r + k == n:
continue
# s = (1+d)^(-1) * (k - r*d) mod n
inv_1d = pow(1 + d, -1, n)
s = (inv_1d * (k - r*d)) % n
if s != 0:
return (r, s)

# ---------------- SM2验签函数 ----------------
def sm2_verify(P, e_int, sig):
r, s = sig
# 范围校验
if not (1 <= r < n and 1 <= s < n):
return False
t = (r + s) % n
if t == 0:
return False
# 计算点 (x1',y1') = s*G + t*P
point = s * G + t * P
x1p = point.x()
R = (e_int + x1p) % n
return R == r

# ---------------- SM3 哈希封装(python hashlib 支持sm3) ----------------
def sm3_hash(msg_bytes):
h = hashlib.new('sm3')
h.update(msg_bytes)
return h.digest()

例题1:0xgame2026-为美好的密码线上解密

题目

大意就是nonce为5位lfsr输出,在给出数组签名,要求对特定消息实现签名伪造

分析

5位lfsr输出周期是31,也就是说给出的签名0和签名31的临时私钥k是完全一样的
由此即可恢复d:

s1=(h1+dr)⋅k−1(modn)s2=(h2+dr)⋅k−1(modn)\begin{align*} s_1 &= (h_1 + d r) \cdot k^{-1} \pmod{n} \\ s_2 &= (h_2 + d r) \cdot k^{-1} \pmod{n} \end{align*}

两式变形消去 k−1k^{-1}:

s1k=h1+dr⇒k=(h1+dr)⋅s1−1(modn)s_1k = h_1 + dr \quad \Rightarrow \quad k = (h_1 + dr)\cdot s_1^{-1} \pmod{n}

s2k=h2+dr⇒k=(h2+dr)⋅s2−1(modn)s_2k = h_2 + dr \quad \Rightarrow \quad k = (h_2 + dr)\cdot s_2^{-1} \pmod{n}

h1+drs1=h2+drs2(modn)\frac{h_1 + dr}{s_1} = \frac{h_2 + dr}{s_2} \pmod{n}

h1s2+drs2=h2s1+drs1(modn)h_1s_2 + drs_2 = h_2s_1 + drs_1 \pmod{n}

dr(s2−s1)=h2s1−h1s2(modn)dr(s_2 - s_1) = h_2s_1 - h_1s_2 \pmod{n}

d=(h2s1−h1s2)⋅[r(s2−s1)]−1(modn)d = (h_2s_1 - h_1s_2)\cdot \big[r(s_2 - s_1)\big]^{-1} \pmod{n}

exp

from pwn import *

from hashlib import *

from gmpy2 import *

# nc1.ctfplus.cn 18897

io = remote("nc1.ctfplus.cn" ,23879)


p = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

a = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC

b = 0x0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00



E = EllipticCurve(GF(p),[a,b])

Q = E(3572009387695018320845707500498751193263666714239053483021122707826151015088729275791812940840630891267988493799579980699063300320438493369224320490122718653,6803177871117790518403020923333477541398690865925042846983740217231156666443004820781768430463608915702023256608899756948916619020711907072084865099255404104)

G = E(0x00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66,0x011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650)

n = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409

h = 1

# 数据采样

io.recv()

io.sendline(b'32')



ms,ss,rs = [],[],[]



for i in range(32):

io.recvuntil(b'msg = ')

ms.append(io.recvline().strip().decode())

io.recvuntil(b'r = ')

rs.append(int(io.recvline().strip().decode()))

io.recvuntil(b's = ')

ss.append(int(io.recvline().strip().decode()))

io.recv()

io.sendline(b'y')



io.recvuntil(b'message = ')

tar_m = io.recvline().strip()

io.recvuntil(b'r = ')

tar_r = int(io.recvline().strip().decode())


def _h(m):

"""SHA-512 摘要转整数。n 是 521 bit > 512 bit,所以无需截断。"""

if isinstance(m, str): m = m.encode()

return int.from_bytes(sha512(m).digest(), 'big')


z0 = _h(ms[0])

z31 = _h(ms[31])

tar_z = _h(tar_m)


d = (ss[0]*z31 - ss[31]*z0) * inverse_mod(rs[0]*ss[31] - rs[31]*ss[0],n)

tar_k = n-1

s = pow(tar_k,-1,n)*(tar_z + tar_r*d) % n



io.recv()

io.sendline(str(s).encode())

print(io.recv())

熵密杯2025谜题一

题目

题目要求 构造一组可以通过验签的摘要值以及对应的签名值,并提交答案。


import secrets
​
default_table = {
'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
'g': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7'
'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}
​
class Crypt():
​
def __init__(self, private_key, public_key, mode=0):
self.private_key = private_key
if public_key.startswith("04"):
self.public_key = public_key[2:]
else:
self.public_key = public_key
self.para_len = len(default_table['n'])
self.ecc_a3 = (
int(default_table['a'], base=16) + 3) % int(default_table['p'], base=16)
assert mode in (0, 1), 'mode must be one of (0, 1)'
self.mode = mode
​
def _kg(self, k, Point): # kP运算
if k == 0:
return None#无穷远点
Point = '%s%s' % (Point, '1')
mask_str = '8'
for i in range(self.para_len - 1):
mask_str += '0'
mask = int(mask_str, 16)
Temp = Point
flag = False
for n in range(self.para_len * 4):
if (flag):
Temp = self._double_point(Temp)
if (k & mask) != 0:
if (flag):
Temp = self._add_point(Temp, Point)
else:
flag = True
Temp = Point
k = k << 1
return self._convert_jacb_to_nor(Temp)
​
def _double_point(self, Point): # 倍点
if Point is None:
return None
l = len(Point)
len_2 = 2 * self.para_len
if l < self.para_len * 2:
return None
else:
x1 = int(Point[0:self.para_len], 16)
y1 = int(Point[self.para_len:len_2], 16)
if l == len_2:
z1 = 1
else:
z1 = int(Point[len_2:], 16)
​
T6 = (z1 * z1) % int(default_table['p'], base=16)
T2 = (y1 * y1) % int(default_table['p'], base=16)
T3 = (x1 + T6) % int(default_table['p'], base=16)
T4 = (x1 - T6) % int(default_table['p'], base=16)
T1 = (T3 * T4) % int(default_table['p'], base=16)
T3 = (y1 * z1) % int(default_table['p'], base=16)
T4 = (T2 * 8) % int(default_table['p'], base=16)
T5 = (x1 * T4) % int(default_table['p'], base=16)
T1 = (T1 * 3) % int(default_table['p'], base=16)
T6 = (T6 * T6) % int(default_table['p'], base=16)
T6 = (self.ecc_a3 * T6) % int(default_table['p'], base=16)
T1 = (T1 + T6) % int(default_table['p'], base=16)
z3 = (T3 + T3) % int(default_table['p'], base=16)
T3 = (T1 * T1) % int(default_table['p'], base=16)
T2 = (T2 * T4) % int(default_table['p'], base=16)
x3 = (T3 - T5) % int(default_table['p'], base=16)
​
if (T5 % 2) == 1:
T4 = (T5 + ((T5 + int(default_table['p'], base=16)) >> 1) - T3) % int(
default_table['p'], base=16)
else:
T4 = (T5 + (T5 >> 1) - T3) % int(default_table['p'], base=16)
​
T1 = (T1 * T4) % int(default_table['p'], base=16)
y3 = (T1 - T2) % int(default_table['p'], base=16)
​
form = '%%0%dx' % self.para_len
form = form * 3
return form % (x3, y3, z3)
​
def _add_point(self, P1, P2): # 点加函数,P2点为仿射坐标即z=1,P1为Jacobian加重射影坐标
if P1 is None:
return P2
if P2 is None:
return P1
len_2 = 2 * self.para_len
l1 = len(P1)
l2 = len(P2)
if (l1 < len_2) or (l2 < len_2):
return None
else:
X1 = int(P1[0:self.para_len], 16)
Y1 = int(P1[self.para_len:len_2], 16)
if (l1 == len_2):
Z1 = 1
else:
Z1 = int(P1[len_2:], 16)
x2 = int(P2[0:self.para_len], 16)
y2 = int(P2[self.para_len:len_2], 16)
​
T1 = (Z1 * Z1) % int(default_table['p'], base=16)
T2 = (y2 * Z1) % int(default_table['p'], base=16)
T3 = (x2 * T1) % int(default_table['p'], base=16)
T1 = (T1 * T2) % int(default_table['p'], base=16)
T2 = (T3 - X1) % int(default_table['p'], base=16)
T3 = (T3 + X1) % int(default_table['p'], base=16)
T4 = (T2 * T2) % int(default_table['p'], base=16)
T1 = (T1 - Y1) % int(default_table['p'], base=16)
Z3 = (Z1 * T2) % int(default_table['p'], base=16)
T2 = (T2 * T4) % int(default_table['p'], base=16)
T3 = (T3 * T4) % int(default_table['p'], base=16)
T5 = (T1 * T1) % int(default_table['p'], base=16)
T4 = (X1 * T4) % int(default_table['p'], base=16)
X3 = (T5 - T3) % int(default_table['p'], base=16)
T2 = (Y1 * T2) % int(default_table['p'], base=16)
T3 = (T4 - X3) % int(default_table['p'], base=16)
T1 = (T1 * T3) % int(default_table['p'], base=16)
Y3 = (T1 - T2) % int(default_table['p'], base=16)
​
form = '%%0%dx' % self.para_len
form = form * 3
return form % (X3, Y3, Z3)
​
def _convert_jacb_to_nor(self, Point): # Jacobian加重射影坐标转换成仿射坐标
if Point is None:
return None
len_2 = 2 * self.para_len
x = int(Point[0:self.para_len], 16)
y = int(Point[self.para_len:len_2], 16)
z = int(Point[len_2:], 16)
z_inv = pow(
z, int(default_table['p'], base=16) - 2, int(default_table['p'], base=16))
z_invSquar = (z_inv * z_inv) % int(default_table['p'], base=16)
z_invQube = (z_invSquar * z_inv) % int(default_table['p'], base=16)
x_new = (x * z_invSquar) % int(default_table['p'], base=16)
y_new = (y * z_invQube) % int(default_table['p'], base=16)
z_new = (z * z_inv) % int(default_table['p'], base=16)
if z_new == 1:
form = '%%0%dx' % self.para_len
form = form * 2
return form % (x_new, y_new)
else:
return None
​
def verify(self, Sign, data):
if Sign is None or Sign == '':
return None
r = int(Sign[0:self.para_len], 16)
s = int(Sign[self.para_len:2*self.para_len], 16)
e = int(data.hex(), 16)
# 参数合法性
if not (1 <= r < int(default_table['n'], base=16) and 1 <= s < int(default_table['n'], base=16)):
return False
t = r + s
if t == 0:
return False
else:
t = t % int(default_table['n'], base=16)
​
if self.public_key is None or self.public_key == '':
return None
​
P1 = self._kg(s, default_table['g'])
if P1 is None:
return False
P2 = self._kg(t, self.public_key)
if P1 == P2:
P1 = '%s%s' % (P1, 1)
P1 = self._double_point(P1)
else:
P1 = '%s%s' % (P1, 1)
P1 = self._add_point(P1, P2)
P1 = self._convert_jacb_to_nor(P1)
​
x = int(P1[0:self.para_len], 16)
return r == ((e + x) % int(default_table['n'], base=16))
​
def sign(self, data):
k = secrets.randbelow(int(default_table['n'], 16) - 1) + 1
if not (1 <= k <= int(default_table['n'], base=16)- 1):
return None
E = data.hex()
e = int(E, 16)
if self.private_key is None or self.private_key == '':
return None
​
d = int(self.private_key, 16)
P1 = self._kg(k, default_table['g'])
​
x = int(P1[0:self.para_len], 16)
A = ((e + x) % int(default_table['n'], base=16))
if A == 0 or A + k == int(default_table['n'], base=16):
return None
d_1 = pow(
d+1, int(default_table['n'], base=16) - 2, int(default_table['n'], base=16))
B = (d_1*(k + A) - A) % int(default_table['n'], base=16)
if B == 0:
return None
else:
return '%064x%064x' % (A, B)
​
if __name__ == '__main__':
crypt = Crypt(
# 公钥格式为64字节的16进制字符串
public_key='',
# 私钥格式为32字节的16进制字符串
private_key=''
)
data = '919535c3ef53d3fa359196b5229c4bbb386ce209f5905d33fc7bcdff46ae27c2'
sign = crypt.sign(bytes.fromhex(data))
print(sign)
verify = crypt.verify(sign,bytes.fromhex(data))
print(verify)

分析

伪造签名的问题,方向要清晰: 我们构造自己的消息e,e算出的R要和原始r相同即可过签

666上来给我这么大段代码真的给我唬住了

不知道断不断网 不断网要人肉分析这个代码还是有点搞人的

由此想到有没有可能是某个权威库的改编 查了一下最权威的国密库应该是gmssl了,拉了一下原代码结果结果还真是是由这个库魔改的代码,这一下就好办了,我们对比分析代码差异就行了

首先看看常见k,发现没问题,没有常见的k复用/泄露问题

一行行盯下来

标准实现(gmssl):先取模,再验零

t = (r + s) % n
if t == 0:
return False

本题实现:先验零,再取模

t = r + s
if t == 0:
return False
else:
t = t % n

这里就是解题关键: 本题将对t的取余放在了验零后面
由此我们完全可以构造出不安全的值:t≡0mod  nt \equiv 0 \mod n
取个特值:r+s=nr + s = n
x′=s′Gx' = s' G
想要过签则:
e+x′=n−se + x' = n - s
到此为止已经完全绕过私钥d未知的限制:
e已知,s和r可以任意伪造, 满足之和为n即可,e+x′=n−se + x' = n - s成立和d完全没有了联系

我们弄一组最简单方便的数据:
t=n,s=1,r=n−1t=n,s=1,r=n−1

(x′,y′)=sG′+tPA(x′,y′)=sG′+tPA​

(x′,y′)=G(x′,y′)=G(x′,y′)=G(x′,y′)=G

e是可控的,我们弄一个e = r - x’即可过签