常见国密算法

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

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

SM4分组密码算法

加密过程

输入128bit明文M=(X0,X1,X2,X3) Key=(MK0,MK1,MK2,MK3) 输出密文(X0,X1,X2,X3) 加密流程$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})~Mod~n$ 得到的(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)~Mod~n$ 如果t=0,验证失败然后计算 $(x'{1},y'{1})=sG+tP_{A}$ 最后计算$R=e+x'_{1}~Mod~n$ 验证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"))

本博客采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议(CC BY-NC-SA 4.0) 发布.

回顾常见国密算法

常见国密算法

SM4分组密码算法

加密过程

解密过程

SM2算法

SM2用于签名

签名过程

验证签名

SM2用于公钥加密

加密过程

解密流程

SM2用于密钥交换

获取各自私钥

计算共享

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

ZUC算法

密钥和初始向量装载

LFSR线性反馈

初始化模式

工作模式

比特重组

非线性函数F

流密钥生成的整体流程

初始化阶段

比特重组

调用非线性函数F

初始化模式LFSR

初始化后丢弃部分

生成密钥流

比特重组

调用非线性函数

生成密钥流字

更新lFSR

模板

gmssl实现

源码实现

相关文章