回顾常见国密算法

常见国密算法

这次 商密杯,做点赛前的康复训练吧.
国密算法是我国商用密码体系的算法,常见的公开算法有

算法	类型	用途
SM2	非对称算法	数字签名,公钥加密,密钥交换
SM3	摘要算法	数字摘要,完整性校验
SM4	对称分组密码	数据加密
ZUC	序列密码	移动数据通信加密
SM9	标识密码

SM4分组密码算法

加密过程

输入128bit明文M=(X0,X1,X2,X3) Key=(MK0,MK1,MK2,MK3)
输出密文(X0,X1,X2,X3)
![[Pasted image 20260717193000.png]]
加密流程$X_{i}$待定$X_{i+1},X_{i+2},X_{i+3}$
然后 获得 $SBOX_INPUT=X_{i+1}\oplus X_{i+2} \oplus X_{i+3} \oplus rk_{i}$
之后拆分成4*8bit进入Sbox替换,获得32bit的Sbox_output 结果
之后将这个32bit 进行上述循环左移动xxx位.得到$y_{2} ,y_{10},y,y_{18},y_{24}$
$X_{i+4}=y_{2}\oplus y_{10} \oplus y \oplus y_{18} \oplus y_{24} \oplus x_{i}$
最后获得输出密文$(X_{35},X_{34},X_{33},X_{32})$
密钥扩展
大同小异,见参考图

解密过程

$x_{4}=x_{0}\oplus T(x_{1}\oplus x_{2} \oplus x_{3 \oplus rk_{0}})$
这是加密过程的函数
那么 $x_{0}=x_{4}\oplus T(x_{1}\oplus x_{2} \oplus x_{3 \oplus rk_{0}})$
那么$x_{31}=x_{35}\oplus T(x_{32}\oplus x_{33} \oplus x_{34} \oplus rk_{31})$
那么依次类推就能得到前面的

算法实现

"""
纯 Python SM4 实现。

包含：
- 128 位密钥扩展
- 16 字节分组加密、解密
- ECB 模式
- CBC 模式
- PKCS#7 填充

说明：
- SM4 的分组长度和密钥长度均为 128 bit，即 16 字节。
- 本实现主要用于学习、算法验证和 CTF。
- 生产环境应优先使用经过审计的密码学库。
"""

from __future__ import annotations

from typing import Iterable


BLOCK_SIZE = 16
_MASK32 = 0xFFFFFFFF


SBOX = (
    0xD6, 0x90, 0xE9, 0xFE, 0xCC, 0xE1, 0x3D, 0xB7,
    0x16, 0xB6, 0x14, 0xC2, 0x28, 0xFB, 0x2C, 0x05,
    0x2B, 0x67, 0x9A, 0x76, 0x2A, 0xBE, 0x04, 0xC3,
    0xAA, 0x44, 0x13, 0x26, 0x49, 0x86, 0x06, 0x99,
    0x9C, 0x42, 0x50, 0xF4, 0x91, 0xEF, 0x98, 0x7A,
    0x33, 0x54, 0x0B, 0x43, 0xED, 0xCF, 0xAC, 0x62,
    0xE4, 0xB3, 0x1C, 0xA9, 0xC9, 0x08, 0xE8, 0x95,
    0x80, 0xDF, 0x94, 0xFA, 0x75, 0x8F, 0x3F, 0xA6,
    0x47, 0x07, 0xA7, 0xFC, 0xF3, 0x73, 0x17, 0xBA,
    0x83, 0x59, 0x3C, 0x19, 0xE6, 0x85, 0x4F, 0xA8,
    0x68, 0x6B, 0x81, 0xB2, 0x71, 0x64, 0xDA, 0x8B,
    0xF8, 0xEB, 0x0F, 0x4B, 0x70, 0x56, 0x9D, 0x35,
    0x1E, 0x24, 0x0E, 0x5E, 0x63, 0x58, 0xD1, 0xA2,
    0x25, 0x22, 0x7C, 0x3B, 0x01, 0x21, 0x78, 0x87,
    0xD4, 0x00, 0x46, 0x57, 0x9F, 0xD3, 0x27, 0x52,
    0x4C, 0x36, 0x02, 0xE7, 0xA0, 0xC4, 0xC8, 0x9E,
    0xEA, 0xBF, 0x8A, 0xD2, 0x40, 0xC7, 0x38, 0xB5,
    0xA3, 0xF7, 0xF2, 0xCE, 0xF9, 0x61, 0x15, 0xA1,
    0xE0, 0xAE, 0x5D, 0xA4, 0x9B, 0x34, 0x1A, 0x55,
    0xAD, 0x93, 0x32, 0x30, 0xF5, 0x8C, 0xB1, 0xE3,
    0x1D, 0xF6, 0xE2, 0x2E, 0x82, 0x66, 0xCA, 0x60,
    0xC0, 0x29, 0x23, 0xAB, 0x0D, 0x53, 0x4E, 0x6F,
    0xD5, 0xDB, 0x37, 0x45, 0xDE, 0xFD, 0x8E, 0x2F,
    0x03, 0xFF, 0x6A, 0x72, 0x6D, 0x6C, 0x5B, 0x51,
    0x8D, 0x1B, 0xAF, 0x92, 0xBB, 0xDD, 0xBC, 0x7F,
    0x11, 0xD9, 0x5C, 0x41, 0x1F, 0x10, 0x5A, 0xD8,
    0x0A, 0xC1, 0x31, 0x88, 0xA5, 0xCD, 0x7B, 0xBD,
    0x2D, 0x74, 0xD0, 0x12, 0xB8, 0xE5, 0xB4, 0xB0,
    0x89, 0x69, 0x97, 0x4A, 0x0C, 0x96, 0x77, 0x7E,
    0x65, 0xB9, 0xF1, 0x09, 0xC5, 0x6E, 0xC6, 0x84,
    0x18, 0xF0, 0x7D, 0xEC, 0x3A, 0xDC, 0x4D, 0x20,
    0x79, 0xEE, 0x5F, 0x3E, 0xD7, 0xCB, 0x39, 0x48,
)

FK = (
    0xA3B1BAC6,
    0x56AA3350,
    0x677D9197,
    0xB27022DC,
)

CK = (
    0x00070E15, 0x1C232A31, 0x383F464D, 0x545B6269,
    0x70777E85, 0x8C939AA1, 0xA8AFB6BD, 0xC4CBD2D9,
    0xE0E7EEF5, 0xFC030A11, 0x181F262D, 0x343B4249,
    0x50575E65, 0x6C737A81, 0x888F969D, 0xA4ABB2B9,
    0xC0C7CED5, 0xDCE3EAF1, 0xF8FF060D, 0x141B2229,
    0x30373E45, 0x4C535A61, 0x686F767D, 0x848B9299,
    0xA0A7AEB5, 0xBCC3CAD1, 0xD8DFE6ED, 0xF4FB0209,
    0x10171E25, 0x2C333A41, 0x484F565D, 0x646B7279,
)


def _rotl32(value: int, shift: int) -> int:
    """32 位循环左移。"""
    value &= _MASK32
    return ((value << shift) | (value >> (32 - shift))) & _MASK32


def _tau(value: int) -> int:
    """对 32 位字的四个字节分别进行 S 盒代换。"""
    return (
        (SBOX[(value >> 24) & 0xFF] << 24)
        | (SBOX[(value >> 16) & 0xFF] << 16)
        | (SBOX[(value >> 8) & 0xFF] << 8)
        | SBOX[value & 0xFF]
    )


def _linear_transform(value: int) -> int:
    """
    加解密轮函数中的线性变换 L：

    L(B) = B xor (B <<< 2) xor (B <<< 10)
             xor (B <<< 18) xor (B <<< 24)
    """
    return (
        value
        ^ _rotl32(value, 2)
        ^ _rotl32(value, 10)
        ^ _rotl32(value, 18)
        ^ _rotl32(value, 24)
    ) & _MASK32


def _key_linear_transform(value: int) -> int:
    """
    密钥扩展中的线性变换 L'：

    L'(B) = B xor (B <<< 13) xor (B <<< 23)
    """
    return (
        value
        ^ _rotl32(value, 13)
        ^ _rotl32(value, 23)
    ) & _MASK32


def _bytes_to_words(data: bytes) -> list[int]:
    """按大端序将 16 字节转换为四个 32 位整数。"""
    return [
        int.from_bytes(data[offset:offset + 4], "big")
        for offset in range(0, 16, 4)
    ]


def _words_to_bytes(words: Iterable[int]) -> bytes:
    """按大端序将若干 32 位整数转换为字节。"""
    return b"".join(
        (word & _MASK32).to_bytes(4, "big")
        for word in words
    )


def _xor_bytes(left: bytes, right: bytes) -> bytes:
    if len(left) != len(right):
        raise ValueError("异或运算的两个字节串长度必须相同")
    return bytes(a ^ b for a, b in zip(left, right))


def pkcs7_pad(data: bytes, block_size: int = BLOCK_SIZE) -> bytes:
    """PKCS#7 填充。"""
    if not 1 <= block_size <= 255:
        raise ValueError("block_size 必须位于 1 到 255 之间")

    padding_length = block_size - len(data) % block_size
    return data + bytes([padding_length]) * padding_length


def pkcs7_unpad(data: bytes, block_size: int = BLOCK_SIZE) -> bytes:
    """检查并移除 PKCS#7 填充。"""
    if not data or len(data) % block_size != 0:
        raise ValueError("待去填充数据的长度不合法")

    padding_length = data[-1]

    if padding_length == 0 or padding_length > block_size:
        raise ValueError("PKCS#7 填充值不合法")

    expected_padding = bytes([padding_length]) * padding_length
    if data[-padding_length:] != expected_padding:
        raise ValueError("PKCS#7 填充校验失败")

    return data[:-padding_length]


class SM4:
    """SM4 分组密码实现。"""

    block_size = BLOCK_SIZE
    key_size = 16

    def __init__(self, key: bytes) -> None:
        if not isinstance(key, bytes):
            raise TypeError("key 必须是 bytes")
        if len(key) != self.key_size:
            raise ValueError("SM4 密钥必须恰好为 16 字节")

        self._encrypt_round_keys = self._expand_key(key)
        self._decrypt_round_keys = tuple(
            reversed(self._encrypt_round_keys)
        )

    @staticmethod
    def _expand_key(key: bytes) -> tuple[int, ...]:
        """
        从 128 位主密钥生成 32 个轮密钥 rk[0] ... rk[31]。
        """
        master_key = _bytes_to_words(key)

        key_words = [
            master_key[index] ^ FK[index]
            for index in range(4)
        ]

        round_keys: list[int] = []

        for index in range(32):
            temp = (
                key_words[index + 1]
                ^ key_words[index + 2]
                ^ key_words[index + 3]
                ^ CK[index]
            )

            next_key = (
                key_words[index]
                ^ _key_linear_transform(_tau(temp))
            ) & _MASK32

            key_words.append(next_key)
            round_keys.append(next_key)

        return tuple(round_keys)

    @staticmethod
    def _crypt_block(
        block: bytes,
        round_keys: tuple[int, ...],
    ) -> bytes:
        if not isinstance(block, bytes):
            raise TypeError("block 必须是 bytes")
        if len(block) != BLOCK_SIZE:
            raise ValueError("SM4 单个分组必须恰好为 16 字节")

        words = _bytes_to_words(block)

        for index in range(32):
            temp = (
                words[index + 1]
                ^ words[index + 2]
                ^ words[index + 3]
                ^ round_keys[index]
            )

            next_word = (
                words[index]
                ^ _linear_transform(_tau(temp))
            ) & _MASK32

            words.append(next_word)

        # 最终反序输出：X35 || X34 || X33 || X32
        return _words_to_bytes(
            (words[35], words[34], words[33], words[32])
        )

    def encrypt_block(self, plaintext: bytes) -> bytes:
        """加密一个 16 字节分组。"""
        return self._crypt_block(
            plaintext,
            self._encrypt_round_keys,
        )

    def decrypt_block(self, ciphertext: bytes) -> bytes:
        """
        解密一个 16 字节分组。

        SM4 解密算法与加密算法结构相同，
        只需要逆序使用 32 个轮密钥。
        """
        return self._crypt_block(
            ciphertext,
            self._decrypt_round_keys,
        )

    def encrypt_ecb(
        self,
        plaintext: bytes,
        *,
        padding: bool = True,
    ) -> bytes:
        """
        ECB 模式加密。

        注意：ECB 会暴露相同明文分组的结构，
        一般不适合实际业务数据。
        """
        if not isinstance(plaintext, bytes):
            raise TypeError("plaintext 必须是 bytes")

        data = pkcs7_pad(plaintext) if padding else plaintext

        if len(data) % BLOCK_SIZE != 0:
            raise ValueError(
                "关闭填充时，明文长度必须是 16 字节的整数倍"
            )

        return b"".join(
            self.encrypt_block(data[offset:offset + BLOCK_SIZE])
            for offset in range(0, len(data), BLOCK_SIZE)
        )

    def decrypt_ecb(
        self,
        ciphertext: bytes,
        *,
        padding: bool = True,
    ) -> bytes:
        """ECB 模式解密。"""
        if not isinstance(ciphertext, bytes):
            raise TypeError("ciphertext 必须是 bytes")
        if not ciphertext or len(ciphertext) % BLOCK_SIZE != 0:
            raise ValueError(
                "密文长度必须是非零的 16 字节整数倍"
            )

        plaintext = b"".join(
            self.decrypt_block(ciphertext[offset:offset + BLOCK_SIZE])
            for offset in range(0, len(ciphertext), BLOCK_SIZE)
        )

        return pkcs7_unpad(plaintext) if padding else plaintext

    def encrypt_cbc(
        self,
        plaintext: bytes,
        iv: bytes,
        *,
        padding: bool = True,
    ) -> bytes:
        """CBC 模式加密。"""
        if not isinstance(plaintext, bytes):
            raise TypeError("plaintext 必须是 bytes")
        if not isinstance(iv, bytes):
            raise TypeError("iv 必须是 bytes")
        if len(iv) != BLOCK_SIZE:
            raise ValueError("CBC 的 IV 必须恰好为 16 字节")

        data = pkcs7_pad(plaintext) if padding else plaintext

        if len(data) % BLOCK_SIZE != 0:
            raise ValueError(
                "关闭填充时，明文长度必须是 16 字节的整数倍"
            )

        previous = iv
        output = bytearray()

        for offset in range(0, len(data), BLOCK_SIZE):
            block = data[offset:offset + BLOCK_SIZE]
            encrypted = self.encrypt_block(
                _xor_bytes(block, previous)
            )
            output.extend(encrypted)
            previous = encrypted

        return bytes(output)

    def decrypt_cbc(
        self,
        ciphertext: bytes,
        iv: bytes,
        *,
        padding: bool = True,
    ) -> bytes:
        """CBC 模式解密。"""
        if not isinstance(ciphertext, bytes):
            raise TypeError("ciphertext 必须是 bytes")
        if not isinstance(iv, bytes):
            raise TypeError("iv 必须是 bytes")
        if len(iv) != BLOCK_SIZE:
            raise ValueError("CBC 的 IV 必须恰好为 16 字节")
        if not ciphertext or len(ciphertext) % BLOCK_SIZE != 0:
            raise ValueError(
                "密文长度必须是非零的 16 字节整数倍"
            )

        previous = iv
        output = bytearray()

        for offset in range(0, len(ciphertext), BLOCK_SIZE):
            block = ciphertext[offset:offset + BLOCK_SIZE]
            decrypted = self.decrypt_block(block)
            output.extend(_xor_bytes(decrypted, previous))
            previous = block

        plaintext = bytes(output)
        return pkcs7_unpad(plaintext) if padding else plaintext


def _self_test() -> None:
    """
    使用 SM4 标准单分组测试向量进行验证。

    key:
        0123456789abcdeffedcba9876543210

    plaintext:
        0123456789abcdeffedcba9876543210

    ciphertext:
        681edf34d206965e86b3e94f536e4246
    """
    key = bytes.fromhex(
        "0123456789abcdeffedcba9876543210"
    )
    plaintext = bytes.fromhex(
        "0123456789abcdeffedcba9876543210"
    )
    expected_ciphertext = bytes.fromhex(
        "681edf34d206965e86b3e94f536e4246"
    )

    sm4 = SM4(key)
    ciphertext = sm4.encrypt_block(plaintext)
    decrypted = sm4.decrypt_block(ciphertext)

    assert ciphertext == expected_ciphertext
    assert decrypted == plaintext

    print("[+] SM4 标准测试向量验证通过")
    print("密钥：", key.hex())
    print("明文：", plaintext.hex())
    print("密文：", ciphertext.hex())
    print("解密：", decrypted.hex())


def _usage_example() -> None:
    key = bytes.fromhex(
        "0123456789abcdeffedcba9876543210"
    )
    iv = bytes.fromhex(
        "000102030405060708090a0b0c0d0e0f"
    )
    message = "SM4 算法测试：Hello, world!".encode("utf-8")

    sm4 = SM4(key)

    ciphertext = sm4.encrypt_cbc(message, iv)
    plaintext = sm4.decrypt_cbc(ciphertext, iv)

    print("\n[+] CBC 模式示例")
    print("原始数据：", message)
    print("密文 HEX：", ciphertext.hex())
    print("恢复数据：", plaintext)
    print("恢复文本：", plaintext.decode("utf-8"))


if __name__ == "__main__":
    _self_test()
    _usage_example()

SM2算法

SM2用于签名

之前还学过这玩意,这次再看看
椭圆曲线有限域:$F_{p}={0,1,2,..p-1}$
椭圆曲线 : $y^2=x^3+ax+b$
已有参数

• p:有限域模数
• a,b:曲线方程参数
• $G=G(G_{x},G_{y}):基点$
• n:基点G的阶
  私钥:$d_{A} \ni (n-2)$
  公钥:$P_{A}=d_{A}G=(x_{A},y_{A})$
• $ID_{A}$:用户身份标识
• $ENTL_{A}:ID_{A}的比特长度$
• 消息明文M

签名过程

生成摘要:$Z_{A}=SM_{3}(ENTL_{A}\parallel ID_{A} \parallel a \parallel b \parallel x_{G} \parallel y_{G} \parallel x_{A} \parallel y_{A})$
之后再计算$e=SM_{3}(Z_{A} \parallel M)$
随机生成$k\ni [1,n-1]$ k是一次性的,每次签名都不一样
计算:$(x_{1},y_{1})=[k]G$
然后计算:$r=(e+x_{1})Mod n$
$s=(1+d_{A})^{-1}(k-rd_{A})Modn$
得到的(r,s)就是前面

验证签名

验证的过程中验证者拥有:

• 消息M
• 前面(r,s)
• A的公钥:$P_{A}$
• A的身份:$ID_{A}$
• G
  首先检查:
  $1\le r \le n-1$
  $1\le s \le n-1$
  然后重新计算$Z_{A}$和e
  然后$t=(r+s)Modn$
  如果t=0,验证失败
  然后计算
  $(x’{1},y’{1})=sG+tP_{A}$
  最后计算$R=e+x’_{1}Modn$
  验证R=r即可
  原理:

  $k=s(1+d_{A})+r d_{A}=s+sd_{A}+rd_{A}$
  因此:$sG+tP_{A}=sG+(r+s)d_{A}G=(s+r d_{A}+s d_{A})G$
  显然成立了

SM2用于公钥加密

Alice->bob发送消息M

• 私钥为$d_{B}$
• 公钥为:
  $P_{B}=d_{B}G$

加密过程

Alice随机生成$k\ni [1,n-1]$
计算$C_{1}=kG$
之后计算$kP_{B}=kd_{B}G=(x_{2},y_{2})$
之后再使用KDF派生出密钥流
$t=KDF(x_{2}||y_{2},klen)$,klen 是明文M的比特长度,目的是为了保证m和t的长度一样
如果t全部为0,则重新生成k
生成$C_{2}=t\oplus M$
之后计算$C_{3}=SM_{3}(x_{2}\parallel M\parallel y_{2})$
最终输出的密文C=(C1,C2,C3)

解密流程

解密的bob是知道$d_{B}$的
所以直接可以得到$(x_{2},y_{2})=d_{B}C_{1}$
之后同样的利用$x_{2},y_{2}$得到t,就能计算出$M=C_{2}\oplus t$
之后再验证C3确保没有被篡改

SM2用于密钥交换

获取各自私钥

双方长期密钥:
Alice:
$P_{A}=d_{A}G$
Bob:
$P_{B}=d_{B}G$
双方生成临时密钥:
Alice生成临时随机数$r_{A}$
计算:$R_{A}=r_{A}G=(x_{1},y_{1})$
Bob生成临时随机数$r_{B}$
计算$R_{B}=r_{B}G=(x_{2},y_{2})$
然后对临时点横坐标进行压缩处理

首先定义：

$$
w=\left\lceil\frac{\log_2 n}{2}\right\rceil-1
$$

然后分别计算 Alice 和 Bob 临时公钥横坐标的转换值：

$$
\bar{x}_1=2^w+\left(x_1\bmod 2^w\right)
$$

$$
\bar{x}_2=2^w+\left(x_2\bmod 2^w\right)
$$

其中：

• $x_1$ 是 Alice 临时公钥 $R_A$ 的横坐标；

• $x_2$ 是 Bob 临时公钥 $R_B$ 的横坐标；

• $n$ 是椭圆曲线基点 $G$ 的阶；

• $\bar{x}_1$ 和 $\bar{x}_2$ 是经过转换后得到的整数。

这里的处理并不是通常所说的“椭圆曲线点压缩”。它只是从临时公钥的横坐标中提取部分低位，并强制设置一个高位，从而得到后续密钥交换计算所需的整数。

计算共享

Alice 计算共享点

Alice 首先计算：

$$
t_A=\left(d_A+\bar{x}_1r_A\right)\bmod n
$$

然后 Alice 计算共享点：

$$
U=[h t_A]\left(P_B+[\bar{x}_2]R_B\right)
$$

设：

$$
U=(x_U,y_U)
$$

• $h$ 是椭圆曲线的余因子；表示整条椭圆曲线点的总数与基点G所生成子群的大小的倍数关系

Bob 计算共享点

Bob 首先计算：

$$
t_B=\left(d_B+\bar{x}_2r_B\right)\bmod n
$$

然后 Bob 计算共享点：

$$
V=[h t_B]\left(P_A+[\bar{x}_1]R_A\right)
$$

设：

$$
V=(x_V,y_V)
$$

当双方提供的数据正确，并且密钥交换过程没有出现异常时，应当满足：

$$
U=V
$$

也就是：

$$
x_U=x_V
$$

$$
y_U=y_V
$$

为什么双方计算出的共享点相同

Alice 的长期公钥和临时公钥分别为：

$$
P_A=[d_A]G
$$

$$
R_A=[r_A]G
$$

Bob 的长期公钥和临时公钥分别为：

$$
P_B=[d_B]G
$$

$$
R_B=[r_B]G
$$

Alice 计算：

$$
U=[h t_A]\left(P_B+[\bar{x}_2]R_B\right)
$$

$$
U=[h t_A]\left([d_B]G+[\bar{x}_2r_B]G\right)
$$

$$
U=[h t_A(d_B+\bar{x}_2r_B)]G
$$

由于：

$$
t_B=(d_B+\bar{x}_2r_B)\bmod n
$$

因此可以写为：

$$
U=[h t_At_B]G
$$

同理，Bob 计算：

$$
V=[h t_B]\left(P_A+[\bar{x}_1]R_A\right)
$$

代入：

$$
P_A=[d_A]G
$$

以及：

$$
R_A=[r_A]G
$$

得到：

$$
V=[h t_B]\left([d_A]G+[\bar{x}_1r_A]G\right)
$$

继续合并：

$$
V=[h t_B(d_A+\bar{x}_1r_A)]G
$$

由于：

$$
t_A=(d_A+\bar{x}_1r_A)\bmod n
$$

所以：

$$
V=[h t_Bt_A]G
$$

标量乘法中的整数乘法满足交换律，因此：

$$
t_At_B=t_Bt_A
$$

最终得到：

$$
U=[h t_At_B]G
$$

$$
V=[h t_Bt_A]G
$$

所以：

$$
\boxed{U=V}
$$

派生会话密钥

Alice 根据共享点 $U=(x_U,y_U)$ 计算会话密钥：

$$
K_A=
\operatorname{KDF}
\left(
x_U\parallel y_U\parallel Z_A\parallel Z_B,
klen
\right)
$$

Bob 根据共享点 $V=(x_V,y_V)$ 计算会话密钥：

$$
K_B=
\operatorname{KDF}
\left(
x_V\parallel y_V\parallel Z_A\parallel Z_B,
klen
\right)
$$

其中：

• $Z_A$ 是 Alice 的用户杂凑值；

• $Z_B$ 是 Bob 的用户杂凑值；

• $klen$ 是需要派生的会话密钥长度；

• $\parallel$ 表示字节串拼接；

• $\operatorname{KDF}$ 表示密钥派生函数。

由于双方计算出的共享点相同：

$$
U=V
$$

因此：

$$
x_U=x_V
$$

$$
y_U=y_V
$$

双方输入 KDF 的数据完全相同，所以最终得到：

$$
\boxed{K_A=K_B}
$$

这个密钥不会直接在网络中传输，而是由 Alice 和 Bob 分别在本地计算出来。

ZUC算法

梦回一年前的西湖论剑,哎空悲切
输入是初始K 和iv 输出 Key=ZUC(K,iv),之后$C=M\oplus Key$
ZUC由这几个部分构成

密钥和初始向量装载

128bit 的密钥分别为16字节:$K=k_{0}\parallel k_{1}\parallel \dots \parallel k_{15}$
128bit的 初始向量 分成16字节 $IV=iv_{1}\parallel \dots \parallel iv_{15}$
ZUC还自带16个固定的15bit常量 $D={d_{0},d_{1},\dots,d_{15}}$.具体见后续代码
之后我们能得到$s_{i}=k_{i}\parallel d_{i}\parallel iv_{i}$
然后非线性函数F的输入R0和R1都清零,R0=0,R1=0

LFSR线性反馈

LFSR线性反馈有两种模式
$$ v= \left( 2^{15}S_{15} +2^{17}S_{13} +2^{21}S_{10} +2^{20}S_{4} +\left(1+2^{8}\right)S_{0} \right) \bmod \left(2^{31}-1\right) $$ 计算新的寄存器单元： $$ S_{16}=(v+u)\bmod \left(2^{31}-1\right) $$ 若： $$ S_{16}=0 $$ 则令： $$ S_{16}=2^{31}-1 $$ 随后更新线性反馈移位寄存器： $$ (S_0,S_1,\ldots,S_{15}) \leftarrow (S_1,S_2,\ldots,S_{16}) $$ 等价地，可以展开为： $$ \begin{aligned} S_0 &\leftarrow S_1,\ S_1 &\leftarrow S_2,\ S_2 &\leftarrow S_3,\ &\ \vdots\ S_{14} &\leftarrow S_{15},\ S_{15} &\leftarrow S_{16}. \end{aligned} $$ 如果寄存器从左到右排列为： $$ S_0,S_1,S_2,\ldots,S_{15} $$ 则其数据移动方向可以表示为： $$ S_0 \leftarrow S_1 \leftarrow S_2 \leftarrow \cdots \leftarrow S_{15} \leftarrow S_{16} $$ 其中，原来的 $S_0$ 被移出，新计算得到的 $S_{16}$ 从寄存器最右侧进入。

初始化模式

LFSR接收一个31bit字u的输入,对寄存器单元变量进行更新
$$ v= \left( 2^{15}S_{15} +2^{17}S_{13} +2^{21}S_{10} +2^{20}S_{4} +\left(1+2^{8}\right)S_{0} \right) \bmod \left(2^{31}-1\right) $$
之后$S_{16}=(v+u)$,这个u来自前面的非线性函数F输出取高位次31bit
之后就
$$ S_0 \leftarrow S_1 \leftarrow S_2 \leftarrow \cdots \leftarrow S_{15} \leftarrow S_{16} $$
其实就是变成$(s_{1},s_{2},..,s_{16})$

工作模式

没有u那部分
$$ s_{16}= \left( 2^{15}S_{15} +2^{17}S_{13} +2^{21}S_{10} +2^{20}S_{4} +\left(1+2^{8}\right)S_{0} \right) \bmod \left(2^{31}-1\right) $$
$(s_{0},..,s_{15})<–(s_{1},\dots,s_{16})$

比特重组

输入 LFSR的16bit,输出 $X_{0},X_{1},X_{2},X_{3}$
$X_{0}=S_{15}[30:15]\parallel S_{14}[15:0]$
$X_{1}=S_{11}[15:0]\parallel S_{9}[30:15]$
$X_{2}=S_{7}[15:0]\parallel S_{5}[30:15]$
$X_{3}=S_{2}[15:0]\parallel S_{0}[30:15]$

• $X_{0},X_{1},X_{2}进入非线性函数F作为输入$
• $X_{3}最后与F的输出异或,生成密钥流$

非线性函数F

据上述输入为$X_{0},X_{1},X_{2}$
内部寄存器为$R_{0},R_{2}$
计算流程如下
$W=X_{0}(X_{0}\oplus R_{1})\boxplus R_{2}$之后会给LFSR的初始状态
这个像田一样的表示$(a+b) Mod~2^{32}$
同时$W_{1}=R_{1}\boxplus X_{1}$ $W_{2}=R_{2}\oplus X_{2}$
然后W1和W2都分成两个$W_{1h},W_{1l},W_{2h},W_{2l}$ 就是高16bit和低16bit
之后开始拼接
$P=W_{1l}\parallel W_{2h}$
$Q=W_{2l}\parallel W_{1h}$
然后定义两个线性变化$L_{1}和L_{2}$,ROTL表示循环左移
$L_{1}(X)=X\oplus ROTL_{32}(X,2)\oplus ROTL_{32}(X,10)\oplus ROTL_{32}(X,18)\oplus ROTL_{32}(X,24)$
$L_{2}(X)=X\oplus ROTL_{32}(X,8)\oplus ROTL_{32}(X,14)\oplus ROTL_{32}(X,22)\oplus ROTL_{32}(X,30)$

之后Sbox变换我就不说了,反正整体流程如下
$W=X_{0}(X_{0}\oplus R_{1})\boxplus R_{2}$
$W_{1}=R_{1}\boxplus X_{1}$
$W_{2}=R_{2}\oplus X_{2}$
$P=W_{1l}\parallel W_{2h}$
$Q=W_{2l}\parallel W_{1h}$
$U_{F}=L_{1}(P),V_{F}=L_{2}(Q)$
$R_{1}=S(U_{F}),R_{2}=S(V_{F})$
函数会返回一个W

流密钥生成的整体流程

初始化阶段

完成密钥和iv装载后
$R_{1}=R_{2}=0$
之后进行32轮初始化

比特重组

$(X_{0},X_{1},X_{2},X_{3})=BR(s_{0},\dots,s_{15})$

调用非线性函数F

$W=F(X_{0},X_{1},X_{2})$
之后更新R1和R2
截取$u=W\gg{1}$

初始化模式LFSR

输入u,和s0…,s15
这样执行32轮次

初始化后丢弃部分

额外执行$BR()$
$F(X_{0},X_{1},X_{2})$
之后再执行一次LFSR工作模式,就更新$R_{1},R_{2}$

生成密钥流

比特重组

$(X_{0},X_{1},X_{2},X_{3})=BR(S_{0},\dots,S_{15})$

调用非线性函数

$W=F(X_{0},X_{1},X_{2})$

生成密钥流字

$Z_{i}=W\oplus X_{3}$

更新lFSR

使用LFSR的工作模式更新
后面得到n个Z合并起来作为流密钥

模板

gmssl实现

from gmssl import Zuc, ZUC_KEY_SIZE, ZUC_IV_SIZE


def zuc_crypt(key: bytes, iv: bytes, data: bytes) -> bytes:
    if len(key) != ZUC_KEY_SIZE:
        raise ValueError("key 必须为 16 字节")

    if len(iv) != ZUC_IV_SIZE:
        raise ValueError("iv 必须为 16 字节")

    ctx = Zuc(key, iv)

    result = ctx.update(data)
    result += ctx.finish()

    return result


def zuc_encrypt(
    key: bytes,
    iv: bytes,
    plaintext: bytes
) -> bytes:
    return zuc_crypt(key, iv, plaintext)


def zuc_decrypt(
    key: bytes,
    iv: bytes,
    ciphertext: bytes
) -> bytes:
    return zuc_crypt(key, iv, ciphertext)


key = bytes.fromhex(
    "00112233445566778899aabbccddeeff"
)

iv = bytes.fromhex(
    "ffeeddccbbaa99887766554433221100"
)

plaintext = "你好，ZUC！".encode("utf-8")

ciphertext = zuc_encrypt(key, iv, plaintext)

print("密文:", ciphertext.hex())

decrypted = zuc_decrypt(key, iv, ciphertext)

print("解密:", decrypted.decode("utf-8"))

源码实现

from __future__ import annotations

MASK31 = 0x7FFFFFFF
MASK32 = 0xFFFFFFFF

D = (
    0x44D7, 0x26BC, 0x626B, 0x135E,
    0x5789, 0x35E2, 0x7135, 0x09AF,
    0x4D78, 0x2F13, 0x6BC4, 0x1AF1,
    0x5E26, 0x3C4D, 0x789A, 0x47AC,
)

S0 = (
    0x3e,0x72,0x5b,0x47,0xca,0xe0,0x00,0x33,0x04,0xd1,0x54,0x98,0x09,0xb9,0x6d,0xcb,
    0x7b,0x1b,0xf9,0x32,0xaf,0x9d,0x6a,0xa5,0xb8,0x2d,0xfc,0x1d,0x08,0x53,0x03,0x90,
    0x4d,0x4e,0x84,0x99,0xe4,0xce,0xd9,0x91,0xdd,0xb6,0x85,0x48,0x8b,0x29,0x6e,0xac,
    0xcd,0xc1,0xf8,0x1e,0x73,0x43,0x69,0xc6,0xb5,0xbd,0xfd,0x39,0x63,0x20,0xd4,0x38,
    0x76,0x7d,0xb2,0xa7,0xcf,0xed,0x57,0xc5,0xf3,0x2c,0xbb,0x14,0x21,0x06,0x55,0x9b,
    0xe3,0xef,0x5e,0x31,0x4f,0x7f,0x5a,0xa4,0x0d,0x82,0x51,0x49,0x5f,0xba,0x58,0x1c,
    0x4a,0x16,0xd5,0x17,0xa8,0x92,0x24,0x1f,0x8c,0xff,0xd8,0xae,0x2e,0x01,0xd3,0xad,
    0x3b,0x4b,0xda,0x46,0xeb,0xc9,0xde,0x9a,0x8f,0x87,0xd7,0x3a,0x80,0x6f,0x2f,0xc8,
    0xb1,0xb4,0x37,0xf7,0x0a,0x22,0x13,0x28,0x7c,0xcc,0x3c,0x89,0xc7,0xc3,0x96,0x56,
    0x07,0xbf,0x7e,0xf0,0x0b,0x2b,0x97,0x52,0x35,0x41,0x79,0x61,0xa6,0x4c,0x10,0xfe,
    0xbc,0x26,0x95,0x88,0x8a,0xb0,0xa3,0xfb,0xc0,0x18,0x94,0xf2,0xe1,0xe5,0xe9,0x5d,
    0xd0,0xdc,0x11,0x66,0x64,0x5c,0xec,0x59,0x42,0x75,0x12,0xf5,0x74,0x9c,0xaa,0x23,
    0x0e,0x86,0xab,0xbe,0x2a,0x02,0xe7,0x67,0xe6,0x44,0xa2,0x6c,0xc2,0x93,0x9f,0xf1,
    0xf6,0xfa,0x36,0xd2,0x50,0x68,0x9e,0x62,0x71,0x15,0x3d,0xd6,0x40,0xc4,0xe2,0x0f,
    0x8e,0x83,0x77,0x6b,0x25,0x05,0x3f,0x0c,0x30,0xea,0x70,0xb7,0xa1,0xe8,0xa9,0x65,
    0x8d,0x27,0x1a,0xdb,0x81,0xb3,0xa0,0xf4,0x45,0x7a,0x19,0xdf,0xee,0x78,0x34,0x60,
)

S1 = (
    0x55,0xc2,0x63,0x71,0x3b,0xc8,0x47,0x86,0x9f,0x3c,0xda,0x5b,0x29,0xaa,0xfd,0x77,
    0x8c,0xc5,0x94,0x0c,0xa6,0x1a,0x13,0x00,0xe3,0xa8,0x16,0x72,0x40,0xf9,0xf8,0x42,
    0x44,0x26,0x68,0x96,0x81,0xd9,0x45,0x3e,0x10,0x76,0xc6,0xa7,0x8b,0x39,0x43,0xe1,
    0x3a,0xb5,0x56,0x2a,0xc0,0x6d,0xb3,0x05,0x22,0x66,0xbf,0xdc,0x0b,0xfa,0x62,0x48,
    0xdd,0x20,0x11,0x06,0x36,0xc9,0xc1,0xcf,0xf6,0x27,0x52,0xbb,0x69,0xf5,0xd4,0x87,
    0x7f,0x84,0x4c,0xd2,0x9c,0x57,0xa4,0xbc,0x4f,0x9a,0xdf,0xfe,0xd6,0x8d,0x7a,0xeb,
    0x2b,0x53,0xd8,0x5c,0xa1,0x14,0x17,0xfb,0x23,0xd5,0x7d,0x30,0x67,0x73,0x08,0x09,
    0xee,0xb7,0x70,0x3f,0x61,0xb2,0x19,0x8e,0x4e,0xe5,0x4b,0x93,0x8f,0x5d,0xdb,0xa9,
    0xad,0xf1,0xae,0x2e,0xcb,0x0d,0xfc,0xf4,0x2d,0x46,0x6e,0x1d,0x97,0xe8,0xd1,0xe9,
    0x4d,0x37,0xa5,0x75,0x5e,0x83,0x9e,0xab,0x82,0x9d,0xb9,0x1c,0xe0,0xcd,0x49,0x89,
    0x01,0xb6,0xbd,0x58,0x24,0xa2,0x5f,0x38,0x78,0x99,0x15,0x90,0x50,0xb8,0x95,0xe4,
    0xd0,0x91,0xc7,0xce,0xed,0x0f,0xb4,0x6f,0xa0,0xcc,0xf0,0x02,0x4a,0x79,0xc3,0xde,
    0xa3,0xef,0xea,0x51,0xe6,0x6b,0x18,0xec,0x1b,0x2c,0x80,0xf7,0x74,0xe7,0xff,0x21,
    0x5a,0x6a,0x54,0x1e,0x41,0x31,0x92,0x35,0xc4,0x33,0x07,0x0a,0xba,0x7e,0x0e,0x34,
    0x88,0xb1,0x98,0x7c,0xf3,0x3d,0x60,0x6c,0x7b,0xca,0xd3,0x1f,0x32,0x65,0x04,0x28,
    0x64,0xbe,0x85,0x9b,0x2f,0x59,0x8a,0xd7,0xb0,0x25,0xac,0xaf,0x12,0x03,0xe2,0xf2,
)


def _rot31(x: int, n: int) -> int:
    return ((x << n) | (x >> (31 - n))) & MASK31


def _rot32(x: int, n: int) -> int:
    x &= MASK32
    return ((x << n) | (x >> (32 - n))) & MASK32


def _add31(*values: int) -> int:
    total = sum(values)
    while total >> 31:
        total = (total & MASK31) + (total >> 31)
    return total if total != 0 else MASK31


def _l1(x: int) -> int:
    return (x ^ _rot32(x, 2) ^ _rot32(x, 10) ^ _rot32(x, 18) ^ _rot32(x, 24)) & MASK32


def _l2(x: int) -> int:
    return (x ^ _rot32(x, 8) ^ _rot32(x, 14) ^ _rot32(x, 22) ^ _rot32(x, 30)) & MASK32


def _s_transform(x: int) -> int:
    return (
        (S0[(x >> 24) & 0xFF] << 24)
        | (S1[(x >> 16) & 0xFF] << 16)
        | (S0[(x >> 8) & 0xFF] << 8)
        | S1[x & 0xFF]
    )


class ZUC:
    """ZUC-128 stream cipher core.

    A fresh object must be used for each independent message. Reusing the same
    key and IV repeats the keystream and is insecure.
    """

    KEY_SIZE = 16
    IV_SIZE = 16

    def __init__(self, key: bytes, iv: bytes):
        if not isinstance(key, (bytes, bytearray)) or len(key) != self.KEY_SIZE:
            raise ValueError("key must be exactly 16 bytes")
        if not isinstance(iv, (bytes, bytearray)) or len(iv) != self.IV_SIZE:
            raise ValueError("iv must be exactly 16 bytes")

        self.s = [((key[i] << 23) | (D[i] << 8) | iv[i]) & MASK31 for i in range(16)]
        self.r1 = 0
        self.r2 = 0

        for _ in range(32):
            x0, x1, x2, _ = self._bit_reorganization()
            w = self._f(x0, x1, x2)
            self._lfsr_init_mode(w >> 1)

        # Discard one F output, then clock the LFSR once in work mode.
        x0, x1, x2, _ = self._bit_reorganization()
        self._f(x0, x1, x2)
        self._lfsr_work_mode()

        self._byte_buffer = bytearray()

    def _bit_reorganization(self) -> tuple[int, int, int, int]:
        s = self.s
        x0 = ((s[15] & 0x7FFF8000) << 1) | (s[14] & 0xFFFF)
        x1 = ((s[11] & 0xFFFF) << 16) | (s[9] >> 15)
        x2 = ((s[7] & 0xFFFF) << 16) | (s[5] >> 15)
        x3 = ((s[2] & 0xFFFF) << 16) | (s[0] >> 15)
        return x0 & MASK32, x1 & MASK32, x2 & MASK32, x3 & MASK32

    def _f(self, x0: int, x1: int, x2: int) -> int:
        w = ((x0 ^ self.r1) + self.r2) & MASK32
        w1 = (self.r1 + x1) & MASK32
        w2 = (self.r2 ^ x2) & MASK32

        u = _l1(((w1 & 0xFFFF) << 16) | (w2 >> 16))
        v = _l2(((w2 & 0xFFFF) << 16) | (w1 >> 16))

        self.r1 = _s_transform(u)
        self.r2 = _s_transform(v)
        return w

    def _feedback(self) -> int:
        s = self.s
        return _add31(
            s[0],
            _rot31(s[0], 8),
            _rot31(s[4], 20),
            _rot31(s[10], 21),
            _rot31(s[13], 17),
            _rot31(s[15], 15),
        )

    def _shift(self, new_value: int) -> None:
        self.s = self.s[1:] + [new_value if new_value != 0 else MASK31]

    def _lfsr_init_mode(self, u: int) -> None:
        self._shift(_add31(self._feedback(), u))

    def _lfsr_work_mode(self) -> None:
        self._shift(self._feedback())

    def generate_word(self) -> int:
        x0, x1, x2, x3 = self._bit_reorganization()
        z = (self._f(x0, x1, x2) ^ x3) & MASK32
        self._lfsr_work_mode()
        return z

    def keystream(self, length: int) -> bytes:
        if length < 0:
            raise ValueError("length must be non-negative")
        while len(self._byte_buffer) < length:
            self._byte_buffer.extend(self.generate_word().to_bytes(4, "big"))
        result = bytes(self._byte_buffer[:length])
        del self._byte_buffer[:length]
        return result

    def crypt(self, data: bytes) -> bytes:
        if not isinstance(data, (bytes, bytearray)):
            raise TypeError("data must be bytes-like")
        ks = self.keystream(len(data))
        return bytes(a ^ b for a, b in zip(data, ks))


def zuc_encrypt(key: bytes, iv: bytes, plaintext: bytes) -> bytes:
    return ZUC(key, iv).crypt(plaintext)


def zuc_decrypt(key: bytes, iv: bytes, ciphertext: bytes) -> bytes:
    return ZUC(key, iv).crypt(ciphertext)


def _self_test() -> None:
    vectors = [
        (bytes(16), bytes(16), "27bede74018082da"),
        (bytes([0xFF]) * 16, bytes([0xFF]) * 16, "0657cfa07096398b"),
        (
            bytes.fromhex("3d4c4be96a82fdaeb58f641db17b455b"),
            bytes.fromhex("84319aa8de6915ca1f6bda6bfbd8c766"),
            "14f1c2723279c419",
        ),
    ]
    for key, iv, expected in vectors:
        got = ZUC(key, iv).keystream(8).hex()
        assert got == expected, f"expected {expected}, got {got}"


if __name__ == "__main__":
    _self_test()

    key = bytes.fromhex("00112233445566778899aabbccddeeff")
    iv = bytes.fromhex("ffeeddccbbaa99887766554433221100")
    plaintext = "你好，ZUC！".encode("utf-8")

    ciphertext = zuc_encrypt(key, iv, plaintext)
    decrypted = zuc_decrypt(key, iv, ciphertext)

    print("plaintext :", plaintext)
    print("ciphertext:", ciphertext.hex())
    print("decrypted :", decrypted.decode("utf-8"))