【密码学】一文读懂SM9算法

本篇文章，来填一个之前挖的坑吧，SM9，一直拖了很久，拖到现在才写，一个最主要的原因是因为，SM9这个体系吧，涉及到的知识相比于之前的SM2, SM3以及SM4来说，要多不少，本篇文章，我们不过多的讲解其中涉及到的数学知识，包括配对如何寻找，以及相关的算法，这里通俗的理解，这个算法。

前言

如果读者学过代数几何或者说椭圆曲线的相关知识呢，可以直接跳过前面的部分，直接看后面的内容，这里，建议，先简单看两道高考模拟题目，来回顾一下高中学过的知识[7, 8]。

首先，找一下，SM9的官方文档[1]，这个依赖于搜索引擎，不难找到对应的资料。这个文档，一共分了5部分，分别是

• 第一部分: 总则
• 第二部分: 数字签名算法
• 第三部分: 密钥交换协议
• 第四部分: 密钥封装机制和公钥加密算法
• 第五部分: 参数定义

通过标题，我们可以知道，这是一个标识密码算法，也就是基于身份的体系，然后对于第一部分，它详细描述了实现标识密码算法所需的数学基础知识和相关密码技术，为后续各部分的密码机制提供理论支持。

然后，大概的翻一下，然后，这个是基于双线性配对来设计的密码体系，然后和SM2一样，这也是一套算法体系，不过这里相比于SM2多了一个KEM, 有关于KEM的知识，可以参考下大佬的解释[11]，这里不过多赘述。然后，这里，简单写一下用到的相关知识。

前置知识

首先，我们来看一下，椭圆曲线的坐标表示，因为后面我们写代码为了方便，直接打印的坐标和大家熟知的坐标有些区别。

射影坐标和Jacobi坐标

针对于椭圆曲线上的点，我们可以有多种表示的方式，之前我们经常使用的方式，也就是在平面解析几何当中的坐标表示方式，被称作是仿射平面，因此，在仿射平面上的点的坐标表示，也被称作是仿射坐标，也就是(x, y), 在椭圆曲线当中，有一个非常重要的点，无穷远点，也就是在群中的单位元，我们用O来表示。

在一般情况下，我们不会直接采用仿射坐标来进行运算，后面，我们在看相关代码的时候，可以发现，默认的打印方式，这里，我们就会有射影坐标，以及Jacobi坐标的表示。

简单的射影坐标，我们可以理解为把仿射坐标进行通分，然后将分母的分量作为一个新的坐标，因此，对于点(x, y), 我们可以通分得到的形式，然后改写一下，可以得到新的表示

的形式，对于这种形式，当然，任意的倍，都表示的是一个点，然后，这里，我们要求，这里就可以和仿射坐标对应起来了，而在的时候，那么这个点，就是无穷远点了。有关于，这个换成射影坐标之后，我们如何运算，不在本文的讨论范围之内，大家有兴趣的，可以自行查阅一下相关的资料。

理解了上面的射影坐标呢，现在，来看Jacobi坐标，就会比较容易了，这个，我们同样也用三个坐标来表示，具体的关系如下

对于域的特征大于3时，方程的形式为

在Jacobi坐标下，无穷远点的坐标是[0, 1, 0], 仿射坐标(x, y)到Jacobi坐标的转换为X=x, Y=y, Z=1，这里，后面，我们再用sage来实现的时候，打印出来，默认就是Jacobi坐标。

Sage基础

然后，因为我不想自己写有限域扩域的相关运算，并且，我也不想自己写椭圆曲线的相关运算，因此，这里，这里为了演示使用，我们直接用在密码学当中使用非常广泛的一个库，也就是sage, 相信读者应该并不陌生，这里简单的提及一下。

这里，仅提供mac的安装方式作为参考，其他的安装，请参考官方文档[3]。对于Mac，我们只需要用homebrew进行安装就可以了[4]。

brew install --cask sage

安装完成之后，测试一下安装的情况。

可以发现，这里是安装成功的，接下来，为了方便写代码，我们把这个配置到Pycharm当中[5]。

这里，配置下Sage的Python的解释器，然后，就配置好了。

配置完成之后，可以实验一下，配置的情况。

可以发现，配置是成功的，但是，这里，有个问题我没有解决，就是，这个对于sage语法的支持不是很好，部分语法不能正常显示，不打紧，这里看个人习惯了。

这里，我们来试验一下，这里椭圆曲线是如何使用的，对于sagemath当中的API, 建议查阅官方文档，这里不做过多描述。

这里，默认打印坐标形式为Jocobi坐标，后续，我们也直接用这种坐标就好了。

双线性配对

因为，在SM9当中，用到了双线性配对(Bilinear Paring)的知识，这里，先来简单的介绍一下。

令和是两个循环群，生成元分别为，双线性配对是一个满足如下性质，一个映射

对于，，我们有

简单理解，就是，我们不能把所有元素，都映射为单位元，也就是存在使得

其中是的单位元。

对于给定的，计算是容易的，也就是可以在多项式时间内计算得到结果。

存在一个有效的，公开的同构映射使得。

实际上，我们一般情况下，令，也就是我们采用对称配对，对于上面的同构映射，那么我们选取恒等映射就可以了，接下来，我们来看一下，对于对称配对，我们可以得到那些性质

对于任意的，我们有

• ，注意这里对于是做了a次的在中的运算，是对于做了次运算
• ，这里是中的单位元

因为，我们是基于椭圆曲线的双线性配对的，因此，这里，我们简单再来补充一下相关的知识。

挠群(Torsion Group)和除子(Divisor)

在代数中，挠群（torsion group）是一个概念，通常用于描述一个群中所有“挠子”元素构成的子群。

在一个群G(+)中，如果存在一个元素以及一个正整数n，使得

其中e是群中的单位元，表示g做n-1次+运算，我们称g是挠子元素。

一个群 G 被称为挠群，如果它的每一个元素都是挠子元素，也就是，这个群中所有的元素，都存在一个正整数n使得。

我们知道，在有限域上的椭圆曲线构成一个群，对于群当中的单位元O是椭圆曲线当中的无穷远点，如果存在一个正整数，我们有，也就是点P的阶为m，我们把满足阶是m的点放到一个集合当中，也就是

其中E是某个有限域下的椭圆曲线。

我们来看一个例子，比如在，对应椭圆曲线方程为

可以得到，这个椭圆曲线的阶为28，这个椭圆曲线，我们实际上，在上面已经看到过了，然后，我们令m=14，这里，我们可以得到，其中的一个挠群。

{(12 : 4 : 1), (0 : 1 : 0), (7 : 11 : 1), (4 : 0 : 1), (7 : 12 : 1), (5 : 4 : 1), (17 : 3 : 1), (17 : 20 : 1), (5 : 19 : 1), (12 : 19 : 1), (6 : 19 : 1), (6 : 4 : 1), (13 : 7 : 1), (13 : 16 : 1)}

我们可以验证一下。

对于挠群，有一个比较好的性质，对于椭圆曲线，如果，那么存在正整数k，使得

成立，也就是，存在一个扩域上的椭圆曲线的挠群同构与两个阶为m的循环群的直积，至于什么是扩域，我们稍后再来聊。

有理函数

有理函数是指一个函数可以表示为两个多项式的比值。更具体地说，如果和是多项式，并且，那么有理函数可以表示为

这里，们更关心的是有理函数的零点和极点，也就是找到潜在的使得或者，找到潜在的使得的点，考虑代数闭域，我们可以将有理函数转换为如下的形式

除子(Divisor)

除子是椭圆曲线上的形式和，是用来记录函数的零点和极点的一种方法(极点和射影坐标有关)[6]，在这里，从上面的式子来看，我们确定极点或者零点的因素有两个，第一个是具体零点或者极点的值，也就是和第二个是极点或者零点的重数，也就是对应的指数，我们这里，可以通过一个和的形式，把上面提到的东西串联起来，这就是除子，注意，这里，我们不关心具体的解的情况，而是注重于这个形式的和。

这里，我们将零点的符号记为正数，极点的符号记为负数，这里注意，[x]，里面的元素，是形式记号，而不是具体的数值。

来看一个例子，帮助理解一下，我们考虑有理函数

然后，对应的这个没有极点，有两个零点和，那么对应的除子，可以表示为

椭圆曲线上的有理函数

这里，我们结合一下上面讲过的椭圆曲线以及有理函数，这里我们还是考虑维尔斯特形的曲线，对于椭圆曲线来说，他是

上面点的集合，我们可以转换成为坐标方程的表示

这里，我们考虑在椭圆曲线上的有理函数，这里是一个二元的有理函数

这里是定义在椭圆曲线上的多项式，满足并且，同样的，这里我们也有对应的零点和极点的概念。然后，我们扩展一下我们上面介绍的除子的概念，来记录零点和极点，这里之前的和由之前的数值，变成了点，因此，我们可以定义椭圆曲线的上有理函数的除子

其中是点P的零点或者极点的重数，因为椭圆曲线仅有有限个零点和极点，因此其余的点对应的重数为0，这个和是有限的。

Weil配对

我们，来看一个具体的配对的例子，这里，我们只看一个相对简单的配对，也就是Weil配对，对于其他的比如Tate配对，Ate配对，R-ate配对，有兴趣的读者可以自行了解。这里，对于Weil配对，有两种定义方式，具体可以看资料[10], 这里我们只给出第一种。

根据前文，我们描述的，m-挠群的性质，也就是E[m]同构域，Weil配对是将E[m]上的两点P, Q映射到上，也就是

其中是m次单位根群，也就是满足方程的所有的z构成的集合。

然后，我们考虑在椭圆曲线上的有理函数f, 我们有主除子

令，我们有

进一步，找到使得，然后存在一个有理函数g使得

然后，这个函数f与函数g有相同的除子，因此，我们可以假设。

最后，令并且，我们有

因此，我们可以找到一个映射

也就是

这里，就不证明，他满足双线性配对了，感兴趣的读者，可以看下资料[10]里面，有证明。

这里，我们知识证明了存在性，对于实际应用来说，存在性，作用是不大的，我们需要找到这个具体的函数，这里有Miller算法，具体可以参考资料[10]，这里也不展开了，后面有机会，这个我们单独来聊，咋感觉，又给自己挖坑了。

有限域的扩张

这里，我们还是简单来理解，这里，我们以二次扩张为例，后面的都类似，可以参考后文的代码部分。

首先，我们有一个基域，也就是素数域，我们之前讲解的阶为素数方幂的域，是基于多项式的，这里，我们看一个新的表示方法，因为可以证明，相同阶的域都是同构的，有兴趣可以看下资料[12]。

对于SM9当中的扩张，具体公式如下

这里，扩张的多项式为，其中，这里，大家可以简单理解到复数上，形式是一样的，我们考虑实数的扩张，对于全体实数可以构成一个域，这个就不证明了，读者自行验证一下。然后我们考虑多项式

这个多项式的零点，我们在实数域当中，是没有解的，这里，我们引入了一个记号，也就是虚数单位i， 这里有，然后全体复数，我们可以表示为

其中，，同样的，对于上面的有限域，我们也有类似的东西，我们令，然后，我们可以得到当中的元素，也就是

然后，对应的乘法和加法，类似于复数当中的运算，这里就不展开了，好嘞，到这里，基础知识，就补充的差不多了。

数字签名算法

有了前面的知识铺垫，我们就可以来看基于双线性对实现的基于标识的数字签名算法，这里，我们来看核心的结构，对于具体的细节，可以参考资料[1]。

密钥生成算法

对于这个密钥生成，其实分为两个部分，第一个是签名的「主私钥」，也就是从1到N-1随机选择一个随机数，然后，要生成签名的主公钥，这里计算，这里元素在当中。

然后，密钥生成算法，需要选择并公开一个字节表示的签名私钥生成函数标识符hid，后面文档给的参数里面，这个取了0x01。

后面，还要生成对应用户A的签名私钥。这里，用户A的标识为，首先，在有限域计算，如果，需要重新选择ks，并重新计算，然后计算，这里最终签名私钥为。

签名算法

假设，待签名的消息为M, 最终生成的消息的签名为(h, S)，具体的方案如下。

1. 计算群中的元素
2. 生成一个随机数
3. 计算，这个值是在当中
4. 计算
5. 计算，如果l=0，重新选择r, 进入步骤2
6. 计算签名
7. 最终，返回签名

验签算法

这里，我们拿到接受到的消息以及收到的签名信息，具体的验签步骤如下。

1. 首先，判断是否成立，不成立验签失败，因为根据签名算法的第4步范围
2. 判断是否成立，因为根据签名步骤6，这个点依然是当中的元素
3. 计算
4. 计算
5. 计算
6. 计算
7. 计算
8. 计算
9. 计算，判断是否成立，如果成立，验签通过，如果不成立，验签失败。

正确性证明

密钥交换协议

接下来，我们来看一下，密钥交换协议。这里，假设A是发起方，B是响应方，这里和文档当中一致，首先，还是需要做密钥生成。

密钥生成

首先，KGC生成随机数作为加密的主私钥，然后计算当中的元素作为加密的主公钥。

这里，针对于用户A和用户B的标识分别为和，这里，针对于用户A，需要生成加密私钥首先计算

如果需要重新生成主私钥和主公钥 ，否则计算，最终

对于用户B需要生成加密私钥，这里采用同样的方案

同样的，我们要求，否则需要重新计算，之后需要计算，最终

接下来，就是密钥交换的过程了，一共分为4（3）次交互(有部分验证是可选的)，我们分别来看，首先用户A需要计算传输给用户B信息。

用户A

1. 计算
2. 生成随机数
3. 计算，并发送给B

用户B

这里，用户B收到了用户A发来的消息

1. 计算
2. 生成随机数
3. 计算
4. 验证是否成立，不成立，协商失败，否则计算、、
5. 计算
6. 【可选】计算，并将以及发送给A

用户A

到这里，用户B实际上，已经拿到了所需交换的密钥了，这里，A需要计算同样的密钥

1. 验证是否成立，如果不成立，则协商失败，否则计算，，
2. 【可选】计算，验证是否成立，不成立，认证失败
3. 计算
4. 【可选】计算并发送给B

用户B

这一步，是可选的，如果收到，这里用户B计算

验证是否成立，如果不成立，协商失败。

正确性证明

这里，我们只需要验证以及即可，这里，简单证明下吧。

这里，需要两边互相推一下，我们来看

接下来，我们只需要证明，这个证明过程和上面类似，这就留给读者自证一下吧，证明过程类似，这里就不证明了。

公钥加密算法

这里，对于公钥加密算法，我们也分为三个部分，分别是密钥生成，加密算法和解密算法。

密钥生成

这里，密钥生成，也是分成了两步，首先KGC产生随机数作为加密的主私钥。然后计算当中的元素作为加密的主公钥。

KGC选择并公开一个字节表示的加密私钥生成函数标识符hid。

假设用户B的标识为，对于加密的私钥，按照如下的方式来计算

这里，如果是0，那么需要重新生成主私钥和主公钥，否则计算，然后，计算

加密算法

假设，需要发送的消息为M, 其中M的长度为mlen。具体加密过程如下。

1. 计算
2. 产生随机数
3. 计算
4. 计算
5. 计算
6. 这里，加密有两种方式，一种是分组密码，一种是序列密码，对于分组密码，需要产生分组密码的密钥，而对于序列密码来说，产生的是对应长度的密钥序列，这里不展开写了，可以参考下原始的文档，这里，最终得到的密文为, 并且输出用于下一步计算MAC的密钥
7. 计算
8. 最终输出

这里的输出，和SM2当中的输出类似。

解密算法

这里，接受到密文C。

1. 首先，从C中提取出并验证这个是否满足
2. 计算
3. 同样，这里解密也分为两种，分组密码和序列密码，上面要对应起来，对应的，然后最终得到明文，以及用于验证的MAC的
4. 计算，判断和u是否相等，不相等则解密失败
5. 输出明文

正确性证明

我们，只需要证明，首先注意到

然后，注意到，

因此，成立。

代码实现

这里，我不打算实现完整的代码，这里，我们借助代码，来看一下其中用到的相关的运算，相关的实现，可以自己从github找一下，里面还是比较多的实现的。

这里，我们用文档[1]中的附录，来简单的看一下，首先，这里椭圆曲线采用的方程是

然后，我们有对应的参数

# Fqq = 0XB640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D# 群的阶N = 0XB640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25

然后，我们来看一下和，根据附录A, 我们知道的生成元

# P_1x_p1 = 0X93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDDy_p1 = 0X21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616

这里，我们简单来验证一下。

可以发现，这个确实是成立的，然后对于，这里是一个扩域，生成扩域的代码如下

defext_field(Fq, alpha):# 构建Fq上的多项式环    x = polygen(Fq)# 定义扩域Fq2    Fq2.<mu> = Fq.extension(x^2 - alpha)return Fq2, mu

这里，我们同样，可以来验证一下

可以发现，也是好用的，然后，根据文档当中的数据，验证一下。

可以发现，和文档也是一样的。

然后，我们再来算一个当中的元素，这里，我们同样需要进行扩域，这里不再过多赘述了。

x_p1 = 0X93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDDy_p1 = 0X21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616x_p2 = (0X85AEF3D078640C98597B6027B441A01FF1DD2C190F5E93C454806C11D8806141,0X3722755292130B08D2AAB97FD34EC120EE265948D19C17ABF9B7213BAF82D65B)y_p2 = (0X17509B092E845C1266BA0D262CBEE6ED0736A96FA347C8BD856DC76B84EBEB96,0XA7CF28D519BE3DA65F3170153D278FF247EFBA98A71A08116215BBA5C999A7C7)q = 0XB640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457DN = 0XB640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25g = (0x4E378FB5561CD0668F906B731AC58FEE25738EDF09CADC7A29C0ABC0177AEA6D,0x28B3404A61908F5D6198815C99AF1990C8AF38655930058C28C21BB539CE0000,0x38BFFE40A22D529A0C66124B2C308DAC9229912656F62B4FACFCED408E02380F,0xA01F2C8BEE81769609462C69C96AA923FD863E209D3CE26DD889B55E2E3873DB,0x67E0E0C2EED7A6993DCE28FE9AA2EF56834307860839677F96685F2B44D0911F,0x5A1AE172102EFD95DF7338DBC577C66D8D6C15E0A0158C7507228EFB078F42A6,0x1604A3FCFA9783E667CE9FCB1062C2A5C6685C316DDA62DE0548BAA6BA30038B,0x93634F44FA13AF76169F3CC8FBEA880ADAFF8475D5FD28A75DEB83C44362B439,0xB3129A75D31D17194675A1BC56947920898FBF390A5BF5D931CE6CBB3340F66D,0x4C744E69C4A2E1C8ED72F796D151A17CE2325B943260FC460B9F73CB57C9014B,0x84B87422330D7936EABA1109FA5A7A7181EE16F2438B0AEB2F38FD5F7554E57A,0xAAB9F06A4EEBA4323A7833DB202E4E35639D93FA3305AF73F0F071D7D284FCFB)defext_field_q2(q, alpha):    Fq = GF(q)    x = polygen(Fq)    Fq2.<mu> = Fq.extension(x^2 - alpha)return Fq2, mudefext_field_q4(Fq2, mu):    x = polygen(Fq2)    Fq4.<v> = Fq2.extension(x^2 - mu)return Fq4, vdefext_field_q12(Fq4, v):    x = polygen(Fq4)    Fq12.<w> = Fq4.extension(x^3 - v)return Fq12, walpha = -2Fq2, mu = ext_field_q2(q, alpha)print(f"二次扩域Fq2: {Fq2}")Fq4, v = ext_field_q4(Fq2, mu)print(f"四次扩域Fq4: {Fq4}")Fq12, w = ext_field_q12(Fq4, v)print(f"12次扩域Fq12: {Fq12}")g_Fq12 = Fq12(    (v * (mu * g[0] + g[1]) + (mu *  g[2] + g[3])) * w^2 +    (v * (mu * g[4] + g[5]) + (mu * g[6] + g[7])) * w +    (v * (mu * g[8] + g[9]) + (mu * g[10] + g[11])))r = 0x033C8616B06704813203DFD00965022ED15975C662337AED648835DC4B1CBEprint(g_Fq12 ^ r)

可以发现，结果是正确的，不过，这个代码第一次运行时间，可能会比较长，需要耐心的等待一下。

后续，就是双线性配对的寻找和实现了，文档当中用的是R-ate对，这里就先不聊了，后面有机会，单独聊一下配对的知识。

总结

本篇文章，我们主要简单的介绍了一下SM9的相关知识，SM9其中包含了3个算法，分别是签名算法、密钥协商算法、公钥加密算法，其中核心是双线性配对问题，这里，我省略了，绝大多数的细节，但是，整篇文章，写的还是比较长的，感谢，能看到这里的读者，好了，这个坑终于算是填完了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://www.math.pku.edu.cn/teachers/qiuzy/qfiles/SM9.pdf
2. https://lsa.umich.edu/content/dam/math-assets/math-document/reu-documents/Li_Siyan%202014%20REU.pdf
3. https://doc.sagemath.org/html/en/installation/index.html
4. https://formulae.brew.sh/cask/sage
5. https://ask.sagemath.org/question/39742/make-pycharm-recognise-the-sage-python-interpreter/
6. https://crypto.stackexchange.com/questions/55342/i-cannot-understand-the-concept-of-a-divisor-for-an-elliptic-curve
7. https://mp.weixin.qq.com/s/ffrxFzt3Bu_R7U_MXtWjtQ
8. https://mp.weixin.qq.com/s/ZZYCavw2CL3AqXLwq73QTQ
9. https://www.jmilne.org/math/Books/EC2.pdf
10. https://tjerandsilde.no/files/Bachelor_Thesis.pdf
11. https://www.zhihu.com/question/443779639/answer/1739265602
12. https://math.stackexchange.com/questions/456703/are-all-finite-fields-isomorphic-to-mathbbf-p