熵密杯复现(一)

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

前置：SM2 加密与签名

1. SM2 加密算法

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

1.1 加密（持公钥 $P = dG$）

明文 $M$ 先转为字节串（长度 klen 字节）：

1. 产生随机数 $k \in [1, n-1]$；
2. 计算 $C_1 = kG$ —— 曲线上的点，相当于"临时公钥"；
3. 计算共享点 $(x_2, y_2) = kP = kdG$；
4. KDF 派生密钥流（基于 SM3）：

   $$t = \operatorname{KDF}(x_2 \,\|\, y_2,\ \text{klen})$$

klen：明文长度

5. 异或加密：$C_2 = M \oplus t$；
6. 完整性校验值：$C_3 = \operatorname{SM3}(x_2 \,\|\, M \,\|\, y_2)$；
7. 输出密文 $C = C_1 \,\|\, C_3 \,\|\, C_2$。

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

1.2 解密（持私钥 $d$）

1. 从密文取出点 $C_1$，并验证 $C_1$ 是曲线上的合法点；
2. 计算共享点：

   $$dC_1 = d(kG) = k(dG) = kP = (x_2, y_2)$$

3. 同样派生 $t = \operatorname{KDF}(x_2 \,\|\, y_2,\ \text{klen})$；
4. 异或还原：$M' = C_2 \oplus t$；
5. 校验 $\operatorname{SM3}(x_2 \,\|\, M' \,\|\, y_2) \stackrel{?}{=} C_3$，相等才输出。

[!tip] 神奇之处
解密方不需要知道随机数 $k$——靠私钥 $d$ 就能把加密时的共享点 $(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 签名（持私钥 $d_A$）

1. 计算杂凑值（绑定了用户身份，这是与 ECDSA 的区别之一）：

   $$e = H(Z_A \,\|\, M)$$

   其中 $Z_A = \operatorname{SM3}(\text{ENTL} \,\|\, \text{IDA} \,\|\, a \,\|\, b \,\|\, x_G \,\|\, y_G \,\|\, x_A \,\|\, y_A)$；
2. 随机选 $k \in [1, n-1]$，计算 $(x_1, y_1) = kG$；
3. 计算 $r = (e + x_1) \bmod n$；若 $r = 0$ 或 $r + k = n$，重新选 $k$；
4. 计算：

   $$s = (1 + d_A)^{-1} \cdot (k - r\, d_A) \bmod n$$

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

2.2 验签（持公钥 $P_A$）

1. 重算 $e' = H(Z_A \,\|\, M')$；
2. 计算 $t = (r' + s') \bmod n$（$t=0$ 则验签失败）；
3. 计算点：

   $$(x_1', y_1') = s'G + tP_A$$

4. 计算 $R = (e' + x_1') \bmod n$，检查 $R \stackrel{?}{=} r'$。

2.3 数学推导

展开第 3 步的点运算：

$$sG + tP_A = sG + (r+s)\,d_A G = \big(s + (r+s)d_A\big)\,G$$

由签名式 $s(1+d_A) = k - r\,d_A$，移项：

$$s + s\,d_A + r\,d_A = k \quad\Longrightarrow\quad s + (r+s)d_A = k$$

代回：

$$sG + tP_A = kG = (x_1, y_1)$$

所以 $x_1'$ 就是签名时的 $x_1$，于是 $R = (e + x_1) \bmod n = r$。✅

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

---

3. 加密 vs 签名对比

维度	SM2 加密	SM2 签名
用途	保密传输消息	身份认证 + 完整性
私钥角色	解密方持有	签名方持有
随机数 $k$ 的作用	生成共享点 $kP$	生成 $x_1$ 混入 $r$
核心等式	$dC_1 = kP$	$sG + tP_A = kG$
校验手段	$C_3$（SM3）	比较 $R = r$
$k$ 复用后果	泄露 $M \oplus M'$	私钥直接泄露 ❗

[!tip] 结构上的共同点

• 都有随机数 $k$，都算 $kG$；
• 安全性都靠"从 $kG$ 推不出 $k$"；
• 核心技巧都是让对方用自己的秘密（私钥）配平出同一个点。

---

4. 攻击面

常见出题点：

1. $k$ 复用？（加密 & 签名都先查这个）
2. $k$ 是弱随机数 / 可预测？（LCG、时间种子、低位泄露 → HNP 上格）
3. 私钥太小或部分泄露？（穷举 / 格攻击）
4. 曲线参数被换成弱曲线？（阶 $n$ 有小因子 → 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了，拉了一下原代码结果结果还真是是由这个库魔改的代码，这一下就好办了，我们对比分析代码差异就行了

标准实现：

本题实现：

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

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

取一组特值试试：$t = n, s = 1, r = n-1$

$$(x',y') = sG' + tP_A$$

带入得

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

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

谜题二

分析

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

谜题三