熵密杯复现(一)

据说是蛮好的比赛,争取下次去线下

前置:SM2 加密与签名

1. SM2 加密算法

本质:椭圆曲线版 ElGamal + KDF 密钥流异或 + SM3 完整性校验。

1.1 加密(持公钥 P=dGP = dG)

明文 MM 先转为字节串(长度 klen 字节):

  1. 产生随机数 k∈[1,n−1]k \in [1, n-1];
  2. 计算 C1=kGC_1 = kG —— 曲线上的点,相当于"临时公钥";
  3. 计算共享点 (x2,y2)=kP=kdG(x_2, y_2) = kP = kdG;
  4. KDF 派生密钥流(基于 SM3):

    t=KDF⁡(x2 ∥ y2, klen)t = \operatorname{KDF}(x_2 \,\|\, y_2,\ \text{klen})

klen:明文长度

  1. 异或加密:C2=M⊕tC_2 = M \oplus t;
  2. 完整性校验值:C3=SM3⁡(x2 ∥ M ∥ y2)C_3 = \operatorname{SM3}(x_2 \,\|\, M \,\|\, y_2);
  3. 输出密文 C=C1 ∥ C3 ∥ C2C = C_1 \,\|\, C_3 \,\|\, C_2。

[!warning] 坑
标准密文顺序是 C1C3C2,但很多库(如 gmssl 老版本)默认 C1C2C3。对接/解题时先确认顺序,否则解密直接失败。

1.2 解密(持私钥 dd)

  1. 从密文取出点 C1C_1,并验证 C1C_1 是曲线上的合法点;
  2. 计算共享点:

    dC1=d(kG)=k(dG)=kP=(x2,y2)dC_1 = d(kG) = k(dG) = kP = (x_2, y_2)

  3. 同样派生 t=KDF⁡(x2 ∥ y2, klen)t = \operatorname{KDF}(x_2 \,\|\, y_2,\ \text{klen});
  4. 异或还原:M′=C2⊕tM' = C_2 \oplus t;
  5. 校验 SM3⁡(x2 ∥ M′ ∥ y2)=?C3\operatorname{SM3}(x_2 \,\|\, M' \,\|\, y_2) \stackrel{?}{=} C_3,相等才输出。

[!tip] 神奇之处
解密方不需要知道随机数 kk——靠私钥 dd 就能把加密时的共享点 (x2,y2)(x_2, y_2) 还原出来。这就是椭圆曲线版 DH 密钥交换的思想。

1.3 一图流

加密(有公钥 P)                 解密(有私钥 d)
────────────── ──────────────
k ← 随机 从密文取 C1 = kG
C1 = kG d·C1 = (x2, y2) ← 私钥配平
kP = (x2, y2) t = KDF(x2‖y2)
t = KDF(x2‖y2) M = C2 ⊕ t
C2 = M ⊕ t 校验 C3
C3 = SM3(x2‖M‖y2)
输出 C1‖C3‖C2

2. SM2 签名算法

2.1 签名(持私钥 dAd_A)

  1. 计算杂凑值(绑定了用户身份,这是与 ECDSA 的区别之一):

    e=H(ZA ∥ M)e = H(Z_A \,\|\, M)

    其中 ZA=SM3⁡(ENTL ∥ IDA ∥ a ∥ b ∥ xG ∥ yG ∥ xA ∥ yA)Z_A = \operatorname{SM3}(\text{ENTL} \,\|\, \text{IDA} \,\|\, a \,\|\, b \,\|\, x_G \,\|\, y_G \,\|\, x_A \,\|\, y_A);
  2. 随机选 k∈[1,n−1]k \in [1, n-1],计算 (x1,y1)=kG(x_1, y_1) = kG;
  3. 计算 r=(e+x1) mod nr = (e + x_1) \bmod n;若 r=0r = 0 或 r+k=nr + k = n,重新选 kk;
  4. 计算:

    s=(1+dA)−1⋅(k−r dA) mod ns = (1 + d_A)^{-1} \cdot (k - r\, d_A) \bmod n

输出签名 (r,s)(r, s)。

2.2 验签(持公钥 PAP_A)

  1. 重算 e′=H(ZA ∥ M′)e' = H(Z_A \,\|\, M');
  2. 计算 t=(r′+s′) mod nt = (r' + s') \bmod n(t=0t=0 则验签失败);
  3. 计算点:

    (x1′,y1′)=s′G+tPA(x_1', y_1') = s'G + tP_A

  4. 计算 R=(e′+x1′) mod nR = (e' + x_1') \bmod n,检查 R=?r′R \stackrel{?}{=} r'。

2.3 数学推导

展开第 3 步的点运算:

sG+tPA=sG+(r+s) dAG=(s+(r+s)dA) GsG + tP_A = sG + (r+s)\,d_A G = \big(s + (r+s)d_A\big)\,G

由签名式 s(1+dA)=k−r dAs(1+d_A) = k - r\,d_A,移项:

s+s dA+r dA=k⟹s+(r+s)dA=ks + s\,d_A + r\,d_A = k \quad\Longrightarrow\quad s + (r+s)d_A = k

代回:

sG+tPA=kG=(x1,y1)sG + tP_A = kG = (x_1, y_1)

所以 x1′x_1' 就是签名时的 x1x_1,于是 R=(e+x1) mod n=rR = (e + x_1) \bmod n = r。✅

[!note]
(1+dA)−1(1+d_A)^{-1} 的作用
这个看起来别扭的因子,目的就是让私钥 dAd_A 在验签时恰好能被公钥 PA=dAGP_A = d_A G “配平”,同时防止从 ss 直接线性解出 dAd_A。


3. 加密 vs 签名对比

维度 SM2 加密 SM2 签名
用途 保密传输消息 身份认证 + 完整性
私钥角色 解密方持有 签名方持有
随机数 kk 的作用 生成共享点 kPkP 生成 x1x_1 混入 rr
核心等式 dC1=kPdC_1 = kP sG+tPA=kGsG + tP_A = kG
校验手段 C3C_3(SM3) 比较 R=rR = r
kk 复用后果 泄露 M⊕M′M \oplus M' 私钥直接泄露 ❗

[!tip] 结构上的共同点

  • 都有随机数 kk,都算 kGkG;
  • 安全性都靠"从 kGkG 推不出 kk";
  • 核心技巧都是让对方用自己的秘密(私钥)配平出同一个点。

4. 攻击面

常见出题点:

  1. kk 复用?(加密 & 签名都先查这个)
  2. kk 是弱随机数 / 可预测?(LCG、时间种子、低位泄露 → HNP 上格)
  3. 私钥太小或部分泄露?(穷举 / 格攻击)
  4. 曲线参数被换成弱曲线?(阶 nn 有小因子 → Pohlig-Hellman 求 DLP)
  5. 密文格式 C1C3C2 vs C1C2C3?

谜题一

题目

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

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了,拉了一下原代码结果结果还真是是由这个库魔改的代码,这一下就好办了,我们对比分析代码差异就行了

标准实现:
alt text
本题实现:
alt text

这里就是解题关键:
本题将对t的取余放在了验零后面

由此我们完全可以构造出不安全的值:t≡0mod  n)t \equiv 0 \mod n)

取一组特值试试:t=n,s=1,r=n−1t = n, s = 1, r = n-1

(x′,y′)=sG′+tPA(x',y') = sG' + tP_A

带入得

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

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

谜题二

分析

这个简单,最终的流密钥复用的问题,目标密文使用的xor密钥和其他索引相邻的密文块是一样的,很经典的nonce错误使用的问题,可以见我的另一篇分组加密的文章,也可见moectf里面那个题,思路一致

谜题三