SM2国密算法实现

文章发布时间:

最后更新时间:
写在前面

这次是最后一次密码学实验，实现SM2国密算法。基本上参考的都是官方文档上的说明，一切以官方文档为主。我贴一下实验报告

实验目的（包括实验环境、实现目标等等）

实现目标：SM2国密公钥算法实现

实验环境：Windows 10、Python 3.9.1、VScode

方案设计

背景及原理：

有限域乘法群上离散对数问题，目前最好的求解算法称为指标计算法，是亚指数时间算法。就现在的计算能力，1024比特规模阶数的有限域可以达到一定的安全性。人们试图寻找一个群，使得其上的离散对数问题没有亚指数算法。椭圆曲线加法群是非常好的候选对象。

1. 素域Fp的定义

img

2.Fp上的椭圆曲线

仿射坐标表示：

img

img

img

射影坐标表示：

img

加重射影坐标表示：

img

3. 二元扩域

img

4.二元扩域下的椭圆曲线

仿射坐标表示：

img

射影坐标表示：

img

img

加重射影坐标表示：

img

算法步骤：

1. 加密步骤：

img

2. 解密步骤：

img

img

方案实现

算法流程图：

加密流程

img

解密流程

img

参数说明：

首先说明我这里域的选择主要是大素数域而非二次扩域，其他参数均为SM2椭圆曲线公钥算法的推荐参数，因此其中有一步骤的余因子可以直接指定为1，在检验时省去了倍点运算的一步操作，相关参数如下所示：

img

中间设计数据类型和形式上的转换：

img

首先在这儿其中最重要的就是各种数据类型的转换，我结合了文档上针对每种类型转换的描述以及Python语言本身提供的一些特性函数，针对转换做出了实现：

对于整数到字节串的转换，我这里用了两种方式：

  1. bytes([<integer>])

  2. bytes.fromhex(<hex format string>)

对于字节串转换成整数，我只要先将字节串转换成十六进制的形式，然后利用int函数

int(binascii.hexlify(<byte string>), 16)

对于比特串到字节串我这里并没有特别进行实现，因为在所有函数当中需要使用比特串的时候，也对应有直接用字节串的实现方式，只有在特别需要比特串某一位时，我用bin函数来使用。

域元素与整数间的相互转换由于我选择的是大素数域，因此两者一致

对于点到字节串的转换，严格按照下图所示：

img

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def _byte_to_point(self, C, mode):
        l = math.ceil(gmpy2.log2(int(self.ecc_param['p'], 16))/8)
        l = int(l)

        PC = binascii.hexlify(bytes([C[0]]))

        # print(binascii.hexlify(C))
        xp = int(binascii.hexlify(C[1:l+1]), 16)

        # print(binascii.hexlify(xp))
        # print("PC: ", PC)
        if mode == 1:
            if PC != b"02" or PC != b"03":
                print("[+] Something Error during decrypting...")
                exit(-1)
            else:
                if PC == b"02":
                    yp = '0'
                else:
                    yp = '1'
            alpha = (pow(xp, 3) + int(self.ecc_param['a'], 16)*xp + int(
                self.ecc_param['b'], 16)) % int(self.ecc_param['p'], 16)
            beta, has_root = gmpy2.iroot(alpha, int(self.ecc_param['p'], 16))
            if has_root:
                if yp == bin(beta)[-1]:
                    yp = beta
                else:
                    yp = int(self.ecc_param['p'], 16) - beta
            else:
                print("[+] Something Error during decrypting...")
        elif mode == 2:
            if PC != b"04":
                print("[+] Something Error during decrypting...")
                exit
            else:
                yp = int(binascii.hexlify(C[l+1:2*l+1]), 16)
        else:
            if PC != b"06" or PC != b"07":
                print("[+] Something Error during decrypting...")
                exit(-1)
            else:
                yp = int(binascii.hexlify(C[l+1:2*l+1]), 16)
        # verify xp and yp
        if gmpy2.powmod(yp, 2, int(self.ecc_param['p'], 16)) == ((gmpy2.powmod(xp, 3, int(self.ecc_param['p'], 16)) + int(self.ecc_param['a'], 16)*xp + int(self.ecc_param['b'], 16)) % int(self.ecc_param['p'], 16)):
            return (xp, yp)
        else:
            print("[+] Something Error during decrypting...")
            exit(-1)

对于字节串到点的转换，也按如下步骤实现：

img

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def point_to_byte(self, P, mode):
        PC = None
        # 域元素xP转换成长度为l的字节串X1
        X1 = self._field_to_byte(P[0])
        # 1.压缩 2.未压缩 3.混合
        if mode == 1:
            print('[+] representation: compressed')
            # 计算比特y˜P
            yp = bin(P[1])[-1]
            if yp == '0':
                PC = '02'
            else:
                PC = '03'
            return PC + X1
        elif mode == 2:
            print('[+] representation: uncompressed')
            Y1 = self._field_to_byte(P[1])
            PC = '04'
            return PC + X1 + Y1
        else:
            print('[+] representation: mixed')
            Y1 = self._field_to_byte(P[1])
            yp = bin(P[1])[-1]
            if yp == '0':
                PC = '06'
            else:
                PC = '07'
            return PC + X1 + Y1

运算规则部分实现：

  1. 加法规则

img

里面针对 $\lambda$ 的除法，我转换成了乘以模拟的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def _add_point(self, P1, P2):
        p = int(self.ecc_param['p'], 16)

        P1_x, P1_y = P1[0], P1[1]
        P2_x, P2_y = P2[0], P2[1]
        if P1_x == 0 and P1_y == 0 and P2_x == 0 and P2_y == 0:
            return 0, 0
        if P1_x == P2_x and P1_y == P2_y:
            lbd = (3*pow(P1_x, 2) +
                   int(self.ecc_param['a'], 16))*gmpy2.invert((2*P1_y), p) % p
        else:
            if (P1 == (0, 0)) or (P2 == (0, 0)):
                return P1 if P1 != (0, 0) else P2
            lbd = (P2_y-P1_y)*gmpy2.invert(P2_x-P1_x, p) % p

        P3_x = (pow(lbd, 2) - P1_x - P2_x) % p
        P3_y = (lbd*(P1_x - P3_x) - P1_y) % p

        return P3_x, P3_y
  1. 倍点运算规则

倍点运算我这里利用二进制展开法进行的实现

img

img 

1
2
3
4
5
6
7
8
def _mutiply_p(self, multi, P):
        product = (0, 0)

        for i in bin(multi):
            product = self._add_point(product, product)
            if i == '1':
                product = self._add_point(product, P)
        return product

密钥派生部分

img

代码实现如下，其中需要注意的是klen长度是比特长度，而我们的类型中还包括整数的长度、字节长度，这里传参时要进行相应的转换：

1
2
3
4
5
6
7
8
9
10
11
12
def _KDF(self, bit_string, klen):
        klen = int(klen)
        ct = 0x00000001
        rcnt = math.ceil(klen/32)
        zin = [i for i in bytes.fromhex(bit_string.decode())]
        ha = ""
        for i in range(rcnt):
            msg = zin + \
                [i for i in binascii.a2b_hex(('%08x' % ct).encode())]
            ha = ha + sm3.sm3_hash(msg)
            ct += 1
        return ha[0: klen * 2]

最终汇总起来，按照加密流程实现加密函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def encrypt(self, M, mode):
        k = randint(1, int(self.ecc_param['n'], 16)-1)
        public_key = self.public_key
        print('[+] random number k:', k)
        # 实际上是随机值
        # k = int('4C62EEFD6ECFC2B95B92FD6C3D9575148AFA17425546D49018E5388D49DD7B4F', 16)

        l = len(self.ecc_param['n'])
        g = (int(self.ecc_param['g'][0: l], 16),
             int(self.ecc_param['g'][l:], 16))
        result = self._mutiply_p(k, g)

        # mode = 2    需要用户传参提供
        C1 = self.point_to_byte(result, mode)

        xy = self._mutiply_p(k, public_key)

        klen = len(M)*4  # 十六进制下
        # 比特长度
        result = self._KDF(
            (hex(xy[0])[2:]+hex(xy[1])[2:]).encode(), klen/8)
        if int(result, 16) == 0:
            return None
        else:
            # M = '656E6372797074696F6E207374616E64617264'
            C2 = hex(int(M, 16) ^ int(result, 16))[2:]

        C3 = sm3.sm3_hash([
            i for i in bytes.fromhex('%s%s%s' % (hex(xy[0])[2:], M, hex(xy[1])[2:]))
        ])

        return bytes.fromhex('%s%s%s' % (C1, C2, C3))

按照解密流程实现解密函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def decrypt(self, C, mode):
        """
        mode:
            1. 压缩 2. 未压缩 3. 混合
        """
        l = math.ceil(gmpy2.log2(int(self.ecc_param['p'], 16))/8)
        l = int(l)
        # 字节长度
        lengthOfS = 0
        if mode == 1:
            lengthOfS = l+1
        else:
            lengthOfS = 2*l+1

        # C2比特长度
        klen = (len(C) - lengthOfS - 32)
        C2 = int(binascii.hexlify(C[lengthOfS:lengthOfS+klen]), 16)
        C3 = C[lengthOfS+klen:]

        C1 = C[0:lengthOfS]
        C1 = self._byte_to_point(C1, mode)
        C1 = self._mutiply_p(self.private_key, C1)

        bytestring = bytes.fromhex('%s%s' % (hex(C1[0])[2:], hex(C1[1])[2:]))

        t = self._KDF(binascii.hexlify(bytestring), klen)
        iM = C2 ^ int(t, 16)

        u = sm3.sm3_hash([
            i for i in bytes.fromhex('%s%s%s' % (hex(C1[0])[2:], hex(iM)[2:], hex(C1[1])[2:]))
        ])

        if binascii.hexlify(C3).decode() == u:
            return binascii.a2b_hex(hex(iM)[2:]).decode()

        else:
            print("[+] Something Error during decrypting...")
            exit(-1)
数据分析

输入数据1:

One is always on a strange road, watching strange scenery and listening to strange music. Then one day, you will find that the things you try hard to forget are already gone.

运行结果如下:

首先可以看到一系列初始化操作以及输入的明文，由随机数生成器产生的随机数。

这里针对加密明文的表现形式选择了非压缩模式，密文结果由16进制表示。

当解密时会有验证Hash的操作，当Hash验证成功且解密的密文与输入明文数据相同时，会输出“[+] You have successfully decrypted”，由此可以看到加密解密成功

img

输入数据2：

Most of us compare ourselves with anyone we think is happier — a relative, someone we know a lot, or someone we hardly know. As a result, what we do remember is anything that makes others happy, anything that makes ourselves unhappy, totally forgetting that there is something happy in our own life.

运行结果：

img

输入数据3：

Happiness is not about being immortal nor having food or rights in one’s hand. It’s about having each tiny wish come true, or having something to eat when you are hungry or having someone’s love when you need love.

运行结果：

img

思考与总结
  1. 实验过程中遇到了什么问题，如何解决的？

其实刚开始就遇到了很多问题，像加法和倍点运算出现错误，刚开始我直接使用的除法运算，会碰到除0错误。倍点运算一开始直接采用循环相加的实现，导致运算时间过长，后来仔细看了一遍文档针对不同实现算法的说明后，重新构建思路，解决了此类运算问题。其次一个问题就是对于数据类型转换的问题，文档上提供的说明有的只是一系列公式比较抽象，结合对于Python相关函数的查询，我了解到了binascii库以及bin、hex、int、bytes等相关函数的使用场景，相结合之后实现了转换的问题。

  1. 通过该实验有何收获和感想？

这是最后一次密码学实验了，感觉收获相比于之前几次都很大。首先是课堂上老师讲的给出了一个整体的轮廓，但是具体的实现细节都需要自己去结合官方文档以及查阅资料来去了解明白。无论是从编程能力，还是对密码学分组密码的理解上都有了很大的提升。

≡