椭圆曲线国密算法实现

实验三

椭圆曲线国密算法实现

姓名：徐慧聪

学号：2023103793

---

1. 实验要求

实现SM2，SM3，SM4算法

2. 代码实现

2.1 SM3

SM3 消息摘要。可以用MD5作为对比理解。该算法已公开。校验结果为256位。

因为SM2需要调用SM3，所以我们先实现SM3算法。

• 一些辅助函数

def left_rotate(x, n):
    # 将 x 的二进制表示左移 n 位，并将最左侧的位移动到最右侧
    n = n % 32  # 取模确保位移量在 0 到 31 之间
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF  # 确保结果在 32 位范围内
def P0(X):
    shift_9_left = left_rotate(X, 9)
    shift_17_left = left_rotate(X, 17)
    result = X ^ shift_9_left ^ shift_17_left
    return result

def P1(X):
    shift_15_left = left_rotate(X, 15)
    shift_23_left = left_rotate(X, 23)
    
    # 将 X 和两次位移的结果进行异或操作
    result = X ^ shift_15_left ^ shift_23_left
    
    return result

def FF_j(X, Y, Z, j):
    if j <= 15:
        return X ^ Y ^ Z
    else:
        return (X & Y) | (X & Z) | (Y & Z)

def GG_j(X, Y, Z, j):
    if j <= 15:
        return X ^ Y ^ Z
    else:
        return (X & Y) | ((~X) & Z)

# 将结果以16进制拼接
def hex_join(result):
    return ''.join('{:08x}'.format(x) for x in result)

# 定义常量 Tj
T = {
    j: 0x79cc4519 if j <= 15 else 0x7a879d8a
    for j in range(64)
}

• 填充至512的倍数
• 迭代压缩
  • 消息扩展，生成132个字W
  • 迭代压缩

# 实现椭圆曲线密码SM3
def SM3(plaintext, iv):
    # 消息填充
    # 假设消息m 的长度为l 比特。首先将比特“1”添加到消息的末尾，
    # 再添加k 个“0”，k是满足l + 1 + k ≡ 448mod512 的最小的非负整数。然后再添加一个64位比特串，
    # 该比特串是长度l的二进制表示。填充后的消息m′ 的比特长度为512的倍数。
    # 将消息填充到满足要求的长度
    padding = b'\x80' + b'\x00' * ((56 - len(plaintext) - 1) % 64)
    length_bits = (8 * len(plaintext)).to_bytes(8, byteorder='big')
    padded_message = plaintext + padding + length_bits
    # print(len(padded_message))
    # print("Padded message:", padded_message)
    # 消息分组，每组 64 字节
    messages = [padded_message[i:i+64] for i in range(0, len(padded_message), 64)]
    # 迭代压缩
    V = iv
    for i in range(len(messages)):
        V = SM3_compress(V, messages[i])
    return hex_join(V)
    
def SM3_compress(V,B):
    # 初始化
    # 扩展消息分组 B 生成 132 个字 W0, W1, ..., W67, W'0, W'1, ..., W'63
    W = [0] * 68
    W_prime = [0] * 64
    
    # 将消息分组 B 划分为 16 个字 W0, W1, ..., W15
    W[:16] = [int.from_bytes(B[i:i+4], 'big') for i in range(0, len(B), 4)]
    
    # 根据公式扩展生成字 W16 到 W67
    for j in range(16, 68):
        W[j] = P1(W[j-16] ^ W[j-9] ^ ((W[j-3] << 15) % 2**32)) ^ ((W[j-13] << 7) % 2**32) ^ W[j-6]
    
    # 生成字 W'0 到 W'63
    for j in range(64):
        W_prime[j] = W[j] ^ W[j+4]
    
    # 初始化字寄存器
    A, B, C, D, E, F, G, H = V
    
    # 迭代压缩
    for j in range(64):
        SS1 = left_rotate((left_rotate(A, 12) + E + (left_rotate(T[j], j))) , 7)
        SS2 = SS1 ^ (left_rotate(A , 12))
        TT1 = (FF_j(A, B, C, j) + D + SS2 + W_prime[j]) & 0xFFFFFFFF
        TT2 = (GG_j(E, F, G, j) + H + SS1 + W_prime[j]) & 0xFFFFFFFF
        
        D, C, B, A = C, (left_rotate(B, 9)), A, TT1
        H, G, F, E = G, (left_rotate(F, 19)), E, P0(TT2)
    
    # 更新压缩结果
    V_new = (A, B, C, D, E, F, G, H)
    return V_new

2.2 SM2

SM2为非对称加密，基于ECC。该算法已公开。由于该算法基于ECC，故其签名速度与秘钥生成速度都快于RSA。ECC 256位（SM2采用的就是ECC 256位的一种）安全强度比RSA 2048位高，运算速度快于RSA。

• 辅助函数
• 定义了椭圆曲线的一些函数

class ECCPoint:
    def __init__(self, x, y, a, b, p):
        self.x = x
        self.y = y
        self.a = a
        self.b = b
        self.p = p

    def __str__(self):
        return f"({self.x}, {self.y})"

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def point_add(self, other):
        if self == other:
            lam_numerator = (3 * self.x ** 2 + self.a) % self.p
            lam_denominator = (2 * self.y) % self.p
        else:
            lam_numerator = (other.y - self.y) % self.p
            lam_denominator = (other.x - self.x) % self.p
        # 计算 lam 的模逆
        lam_inverse = pow(lam_denominator, -1, self.p)
        # 计算 lam
        lam = (lam_numerator * lam_inverse) % self.p
        # 计算新的点坐标
        x3 = (lam ** 2 - self.x - other.x) % self.p
        y3 = (lam * (self.x - x3) - self.y) % self.p

        return ECCPoint(x3, y3, self.a, self.b, self.p)

    def point_multiply(self, n):
        result = ECCPoint(self.x, self.y, self.a, self.b, self.p)
        for _ in range(n - 1):
            result = result.point_add(self)
        return result

# 字符串转换，采用未压缩形式
# q = p
# 域元素转化成长度为l的字符串
def int_to_bytes(x, k):
    # 初始化一个长度为 k 的字节数组
    M = [0] * k
    # 逐字节填充 M
    for i in range(k - 1, -1, -1):  # 从最高位开始填充
        M[i] = x & 0xFF  # 将 x 的最低字节赋值给 M[i]
        x >>= 8          # 右移 8 位，去除 x 的最低字节

    # 返回字节数组 M
    return bytes(M)

def bytes_to_int(M):
    # 初始化整数 x
    x = 0
    # 逐字节构建 x
    for byte in M:
        x = (x << 8) + byte  # 左移 8 位，并加上当前字节的值

    # 返回整数 x
    return x

def Region_to_str(P, p):
    q = p
    # t = log2p取上整
    # 计算取模数 q 的比特长度
    t = math.ceil(math.log2(q))
    # 计算字节串 S 的长度，取 t/8 的上整数
    l = math.ceil(t / 8)
    S = int_to_bytes(P, l)
    return S

def Point_to_str(P, p):
    X1 = Region_to_str(P.x, p)
    Y1 = Region_to_str(P.y, p)
    PC = b'\x04'
    S = PC + X1 + Y1
    return S

def Get_C1_point(P_str, p, a, b):
    # 获取前缀
    PC = P_str[0]
    # 获取 X 和 Y
    X = int.from_bytes(P_str[1:33], byteorder='big')
    # 采用未压缩形式
    Y = int.from_bytes(P_str[33:65], byteorder='big')
    # 创建点
    P = ECCPoint(X, Y, a, b, p)
    
    # 验证椭圆曲线方程
    y2P_square = (P.y ** 2) % p  # y^2 的平方
    x3P_plus_axP_plus_b = (P.x ** 3 + a * P.x + b) % p  # x^3 + ax + b
    if y2P_square != x3P_plus_axP_plus_b:
        print(x3P_plus_axP_plus_b)
        print(y2P_square)
        raise ValueError("Invalid point: Does not satisfy the elliptic curve equation")
    return P

def xor_strings(s1, s2):
    # 使用zip函数将两个字符串逐字符进行按位异或操作，并使用chr函数将结果转换为字符
    return ''.join(chr(ord(c1) ^ ord(c2)) for c1, c2 in zip(s1, s2))

加密算法：

• 设需要发送的消息为比特串M，klen为M的比特长度。
• 为了对明文M进行加密，作为加密者的用户A应实现以下运算步骤：
• A1：用随机数发生器产生随机数k∈[1,n-1]；
• A2：计算椭圆曲线点C1=[k]G=(x1,y1)，按本文本第1部分4.2.8和4.2.4给出的细节，将C1的数据类型转换为比特串；
• A3：计算椭圆曲线点S=[h]PB，若S是无穷远点，则报错并退出；
• A4：计算椭圆曲线点[k]PB=(x2,y2)，按本文本第1部分4.2.5和4.2.4给出的细节，将坐标x2、y2 的数据类型转换为比特串；
• A5：计算t=KDF(x2 ∥ y2, klen)，若t为全0比特串，则返回A1；
• A6：计算C2 = M ⊕ t；
• A7：计算C3 = Hash(x2 ∥ M ∥ y2)；
• A8：输出密文C = C1 ∥ C2 ∥ C3。

解密算法：

• 设klen为密文中C2的比特长度。
• 为了对密文C=C1 ∥ C2 ∥ C3 进行解密，作为解密者的用户B应实现以下运算步骤：
• B1：从C中取出比特串C1，按本文本第1部分4.2.3和4.2.9给出的细节，将C1的数据类型转换为椭圆曲线上的点，验证C1是否满足椭圆曲线方程，若不满足则报错并退出；
• B2：计算椭圆曲线点S=[h]C1，若S是无穷远点，则报错并退出；
• B3：计算[dB]C1=(x2,y2)，按本文本第1部分4.2.5和4.2.4给出的细节，将坐标x2、y2的数据类型转换为比特串；
• B4：计算t=KDF(x2 ∥ y2, klen)，若t为全0比特串，则报错并退出；
• B5：从C中取出比特串C2，计算M′ = C2 ⊕ t；
• B6：计算u = Hash(x2 ∥ M′ ∥ y2)，从C中取出比特串C3，若u = C3，则报错并退出；
• B7：输出明文M′。

# 获取密钥对
def get_key(p, a, b, n, Gx, Gy):
    G = ECCPoint(Gx, Gy, a, b, p)
    # 用随机数发生器产生整数d ∈ [1,n−2]
    d = random.randint(1, 5)
    # 计算公钥点PB = dP
    P = G.point_multiply(d)
    return d, P

def KDF(Z, klen, v=256):
    print(len(Z))
    # 初始化计数器
    ct = 0x00000001
    # 计算需要迭代的次数
    num_iterations = (klen + v - 1) // v
    # 初始化密钥数据比特串
    K = ''
    
    for i in range(1, num_iterations + 1):
        # 计算Hai=Hv(Z ∥ ct)
        input_data = Z + ct.to_bytes(4, byteorder='big')
        Hai = SM3(input_data,V_init)
        
        # 更新K
        if i == num_iterations and klen % v != 0:
            # 若klen/v不是整数，处理最后一个Ha
            last_Ha = Hai[:klen % v // 8]  # 取最左边的 (klen - (v × ⌊klen/v⌋)) 比特
            K += last_Ha
        else:
            K += Hai
        
        # 更新计数器
        ct += 1
    
    return K.encode()  # 返回长度为klen的密钥数据比特串K

# 实现椭圆密码SM2
def SM2_encrypt(Pbulic_key, M, klen, p, a, b, n, Gx, Gy):
    G = ECCPoint(Gx, Gy, a, b, p)
    PB = Pbulic_key
    # 步骤 A1：生成随机数 k
    k = random.randint(1, 5)
    # 步骤 A2：计算椭圆曲线点 C1 = k(Gx,Gy)
    C1 = G.point_multiply(k)
    C1_str = Point_to_str(C1, p)
    # 步骤 A4：计算椭圆曲线点 [k]PB
    kPB = PB.point_multiply(k)
    X2_str = Region_to_str(kPB.x, p)
    Y2_str = Region_to_str(kPB.y, p)
    # 步骤 A5：计算 t
    t = KDF(X2_str + Y2_str, klen)
    # 步骤 A6：计算密文 C2
    C2 = bytes([M[i] ^ t[i] for i in range(len(M))])
    
    # 步骤 A7：计算哈希值 C3
    C3_str = SM3(X2_str + M + Y2_str,V_init)
    C3 = C3_str.encode()
    
    # 输出密文
    return C1_str + C2 + C3

def SM2_decrypt(private_key, cipher, klen, p, a, b):
    C1 = Get_C1_point(cipher, p, a, b)
    tmp = C1.point_multiply(private_key)
    x2 = Region_to_str(tmp.x, p)
    y2 = Region_to_str(tmp.y, p)
    t = KDF(x2 + y2, klen)
    C2 = cipher[65:65 + len(t)]
    M = bytes([C2[i] ^ t[i] for i in range(len(C2))])
    u = SM3(x2 + M + y2,V_init).encode()
    if u != cipher[65+ len(t):]:
        print("解密失败")
    return M

2.3 SM4

SM4 无线局域网标准的分组数据算法。对称加密，密钥长度和分组长度均为128位。

• 辅助函数

密钥扩展算法：

# SM4
S_BOX = [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 wd_to_byte(wd, bys):
    bys.extend([(wd >> i) & 0xff for i in range(24, -1, -8)])

def bys_to_wd(bys):
    ret = 0
    for i in range(4):
        bits = 24 - i * 8
        ret |= (bys[i] << bits)
    return ret

def s_box(wd):
    """
    进行非线性变换,查S盒
    :param wd: 输入一个32bits字
    :return: 返回一个32bits字   ->int
    """
    ret = []
    for i in range(0, 4):
        byte = (wd >> (24 - i * 8)) & 0xff
        row = byte >> 4
        col = byte & 0x0f
        index = (row * 16 + col)
        ret.append(S_BOX[index])
    return bys_to_wd(ret)

def rotate_left(wd, bit):
    """
    :param wd: 待移位的字
    :param bit: 循环左移位数
    :return:
    """
    return (wd << bit & 0xffffffff) | (wd >> (32 - bit))

def Linear_transformation(wd):
    """
    进行线性变换L
    :param wd: 32bits输入
    """
    return wd ^ rotate_left(wd, 2) ^ rotate_left(wd, 10) ^ rotate_left(wd, 18) ^ rotate_left(wd, 24)

def Tx(k1, k2, k3, ck):
    """
    密钥扩展算法的合成变换
    """
    xor = k1 ^ k2 ^ k3 ^ ck
    t = s_box(k1 ^ k2 ^ k3 ^ ck)
    return t ^ rotate_left(t, 13) ^ rotate_left(t, 23)

def T(x1, x2, x3, rk):
    """
    加密算法轮函数的合成变换
    """
    t = x1 ^ x2 ^ x3 ^ rk
    t = s_box(t)
    return t ^ rotate_left(t, 2) ^ rotate_left(t, 10) ^ rotate_left(t, 18) ^ rotate_left(t, 24)

def key_extend(main_key):
    MK = [(main_key >> (128 - (i + 1) * 32)) & 0xffffffff for i in range(4)]
    # 将128bits分为4个字
    keys = [FK[i] ^ MK[i] for i in range(4)]
    # 生成K0~K3
    RK = []
    for i in range(32):
        t = Tx(keys[i + 1], keys[i + 2], keys[i + 3], CK[i])
        k = keys[i] ^ t
        keys.append(k)
        RK.append(k)
    return RK

def R(x0, x1, x2, x3):
    # 使用位运算符将数值限制在32位范围内
    x0 &= 0xffffffff
    x1 &= 0xffffffff
    x2 &= 0xffffffff
    x3 &= 0xffffffff
    s = f"{x3:08x}{x2:08x}{x1:08x}{x0:08x}"
    return s

加密算法：

解密算法：

def SM4_encrypt(plaintext, rk):
    X = [plaintext >> (128 - (i + 1) * 32) & 0xffffffff for i in range(4)]
    for i in range(32):
        t = T(X[1], X[2], X[3], rk[i])
        c = (t ^ X[0])
        X = X[1:] + [c]
    ciphertext = R(X[0], X[1], X[2], X[3])
    # 进行反序处理
    return ciphertext

def SM4_decrypt(ciphertext, rk):
    ciphertext = int(ciphertext, 16)
    X = [ciphertext >> (128 - (i + 1) * 32) & 0xffffffff for i in range(4)]
    for i in range(32):
        t = T(X[1], X[2], X[3], rk[31 - i])
        c = (t ^ X[0])
        X = X[1:] + [c]
    m = R(X[0], X[1], X[2], X[3])
    return m

def output(s, name):
    out = ""
    for i in range(0, len(s), 2):
        out += s[i:i + 2] + " "
    print(f"{name}:", end="")
    print(out.strip())

def pad_plaintext(plaintext):
    # 计算明文的长度
    byte_length = len(plaintext)
    
    # 计算需要填充的字节数
    padding_length = 16 - (byte_length % 16)
    
    # 如果长度刚好是16字节，不需要填充
    if padding_length == 16:
        padding_length = 0
    
    # 构造填充后的明文
    padded_plaintext = plaintext + bytes([padding_length] * padding_length)
    
    return padded_plaintext

3. 实验

3.1 SM3

参数如下：

# 将 IV 分成 32 位字
IV_parts = [
    int('7380166f', 16),
    int('4914b2b9', 16),
    int('172442d7', 16),
    int('da8a0600', 16),
    int('a96f30bc', 16),
    int('163138aa', 16),
    int('e38dee4d', 16),
    int('b0fb0e4e', 16)
]

# 设置初始状态 V
V_init = tuple(IV_parts)

# 调用 SM3 函数进行加密
cipher = SM3(b"hello world",V_init)
# cipher = hex_join(cipher)
print(len(cipher),cipher)

实验结果

3.2 SM2

参数如下：

# SM2的椭圆曲线参数
p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
a = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
Gx = 0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy = 0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0

# 获取密钥对
private_key, public_key = get_key(p, a, b, n, Gx, Gy)
public_key_x = public_key.x
public_key_y = public_key.y

public_key = ECCPoint(public_key_x, public_key_y, a, b, p)

Message = b"encryption standard"
klen = len(Message) * 8
cipher =  SM2_encrypt(public_key,Message,klen,p,a,b,n,Gx,Gy)
print(len(cipher), cipher)
integer = int.from_bytes(cipher, byteorder='big')
print(hex(integer))

M  = SM2_decrypt(private_key, cipher, klen, p, a, b)
print(M)

实验结果：

3.3 SM4

参数如下：

if __name__ == '__main__':
    plaintext = b"hello world"
    pad_plaintext = pad_plaintext(plaintext)
    plain = int.from_bytes(pad_plaintext, byteorder='big')
    print("Plaintext:",hex(plain))
    main_key = 0x0123456789abcdeffedcba9876543210
    rk = key_extend(main_key)
    print("加密:")
    ciphertext = SM4_encrypt(plain, rk)
    output(ciphertext, "ciphertext")
    print("解密:")
    m = SM4_decrypt(ciphertext, rk)
    output(m, "plaintext")

实验结果：

4. 总结

• 按照国密标准实现了SM2、SM3、SM4算法
• 算法实现比较复杂，代码量也比较大
• 提供了一些测试用例并进行了测试