SM2国密算法之数学原理

ECC背后的数学

Posted by 泽群 on November 25, 2020

1. SM2算法简介

SM2算法全称是SM2椭圆曲线公钥密码算法(SM是商用密码的拼音缩写),是一种基于“椭圆曲线”的密码。2016年,SM2成为中国国家密码标准。 在商用密码体系中,SM2主要用于替换RSA加密算法。

既然SM2是用于替换RSA加密算法,那就有必要介绍一下RSA算法,RSA是非常著名的非对称加密算法,它的安全性建立在整数因数分解难题(IFP)之上。即使没有听说过RSA算法,想必大家也听说过这个整数因数分解难题,并且直觉上也认为,嗯,这个问题的确很难。

那么问题来了,既然有RSA这么成熟的算法了,为什么还需要SM2,这其中有很多原因,但是不可忽视的一点是,SM2是一种基于椭圆曲线的密码(Elliptic Curve Cryptography,简称ECC),ECC有其天然优势,那就是可以以较小的密钥长度获取和RSA同等的安全强度。以下是来自NIST美国国家标准技术研究所的推荐密钥长度,表中同行代表了具有同等的安全强度,也就是破解所需的计算时间是等同的。

RSA key size (bits) ECC key size (bits)
1024 160
2048 224
3072 256
7680 384
15360 521

可以看出同等安全强度下,ECC密钥的长度比RSA密钥的长度要小得多,并且,随着RSA密钥的翻倍,ECC密钥并不需要翻倍就能获取同等的安全强度。这一点对于移动设备、嵌入式以及其它功耗受限、计算能力受限的场景来说就很有用了。

RSA名气很大,并且整数因数分解难题大家感觉自己也能“理解”,但是个人感觉RSA的数学原理比ECC要更加困难,因为RSA的数学原理涉及到许多“数论”的概念,数论不仅抽象,而且不容易理解;而ECC的数学原理刚好是另外一个取向,ECC的数学原理涉及到的数学概念不仅是9年义务教育+高中不会涉及到的,甚至绝大部分专业的大学阶段都也不会接触到,这就使得对于ECC的理解被赋予了很高的门槛,但实际上这些数学概念并没有那么难,并且ECC也只使用了这些数学概念中比较基础的部分,并没有涉及非常深的领域,个人感觉这些概念比数论要容易理解。再加上椭圆曲线是有图像的,图像可以大大帮助我们的理解,所以理解ECC真的没有那么难,你要对自己有信心。

2. ElGamal公钥密码体系

上文提到,SM2是一种公钥密码算法,公钥密码算法都要建立在某种单向函数之上的,之所以说这种函数是单向的,是因为其逆函数是计算不可行的,也就是说,有这么一种函数,它正向计算很容易,反向计算很难(试想一下,如果真的是这么一种众生平等的函数,别人反向计算困难,那意味着解密方——喜闻乐见的Bob,解密也很难,这当然不是我们想要的),除非你知道某些别人不知道的信息,有了这些信息,你就可以方便地反向计算,也就意味着解密只对拥有这些信息的人可行,这些“信息”就是我们常说的私钥。我们把这种函数称为单向陷门函数,RSA的单向陷门函数的构造就是基于上文说的的IFP。

SM2作为一种公钥密码算法,自然也需要构造出这么一种单向陷门函数,好消息是,我们并不需要从头开始去“摸索”出这么一种函数,有一种现成且成熟的公钥密码体系——ElGamal公钥密码体系,这种体系基于某些数学概念构造出了一种通用的单向陷门函数,而SM2所基于的椭圆曲线密码正是ElGamal公钥密码体系在椭圆曲线上的应用。

ElGamal体系是构建在有限域的循环子群之上的,SM2的数学基础也是这些,以下内容将介绍这些数学概念。这些数学概念有些抽象,并且比较难于理解,但是这是理解SM2及ECC的必由之路。当你感到困惑时,你要记住,并不是我们要生搬硬套一些抽象的概念,而是有现成的公钥体系建立在这些抽象概念之上的,我们只是想把椭圆曲线应用到这些概念上。

3. 什么是椭圆曲线

椭圆大家都知道,方程表示是这个样子:

$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$

是不是唤起了你高中某些不愉快的回忆,没关系,这才刚刚开始,以下的内容会让你更加不愉快。
那什么是椭圆曲线呢?用方程表示的话是:$y^2 = x^3 + ax + b(4a^3 + 27b^2 \ne 0)$其中a,b都是实数。a,b取不同的值时,图像大概是这样的:

椭圆曲线

从图像上,从方程式中我们都可以看出,椭圆曲线是关于x轴对称的。你可能会想,这椭圆曲线也看不出跟椭圆有毛的关系啊,恭喜你,答对了,椭圆和椭圆曲线的关系,就好像Java和JavaScript的关系一样,之所以叫椭圆曲线,是因为计算椭圆周长的积分中的一部分跟椭圆曲线方程很像,所以叫把这种方程表示的曲线叫着椭圆曲线,还真的是有理有据,一点都不牵强。

4. 群论的一点点知识

说完椭圆曲线,我们要介绍一个重要的概念,群。一个群是由一个集合以及定义在该集合上的一个二元运算(记作$\cdot$)所组成,且符合“群公理”:

  1. 封闭性:若$a$和$b$是集合$\mathbb{G}$的成员,则$a\cdot b$属于$\mathbb{G}$
  2. 结合律:$(a\cdot b)\cdot c=a\cdot (b\cdot c) $
  3. 单位元:存在单位元$e$,使得$a\cdot e=a\cdot e=a $
  4. 逆元:集合$\mathbb{G}$中的任意成员a,存在b,使得$a\cdot b=e $,a,b互为逆元,记$a=b^{-1}$,同样$b=a^{-1}$。

通俗地说,群就是一个集合然后上面定义一种运算,集合上的元素参与这种运算不会脱离这个集合,并且集合上有个有点特殊的元素叫单位元,单位元跟集合中别的元素做运算得到的还是那个元素,并且集合中每个元素都有相反的一个元素,它们两个做运算会得到刚才定义的单位元。

显然,全体整数和普通加法构成一个群,单位元就是0。而全体整数和普通乘法构不成一个群,前三条都满足,并且单位元就是1,但是除了1,别的元素的逆元都不存在,比如2的逆元应该是1/2,但是1/2不在整数范围内。虽然“群公理”看上去理所应当,但是这些条件也不是那么容易满足的。还有就是,单位元很“特殊”,我们一会儿说单位元是0,一会儿说单位元是1,这都是对于特定的运算而言,你可以把单位元理解成普通加法中的0和普通乘法中的1,那么逆元就是普通加法中的相反数,普通乘法中的倒数。

我们小学的时候就学过,加法满足结合律和交换律,然而群公理中并没有包括交换律这一条,那是因为不需要,仅仅是这四条公理就足以让我们推导出来很多有用的定理了,没有必要再加一条使得“群”的适用性变窄。但是,如果这种二元运算满足交换律,那自然是更好的,我们就能推导出更多的定理,这种满足交换律的“加强群”我们称为交换群阿贝尔群

再举个例子,在线性代数中,我们都学过,一个n阶的方阵是不一定存在逆矩阵的,只有在满足一定条件下才有逆矩阵,n阶的“可逆”方阵在矩阵乘法下构成群,其单位元就是单位矩阵,逆元肯定存在,因为我们定义的就是n阶的“可逆”方阵,但是这个群不是一个交换群,线性代数一个基本的常识就是矩阵乘法不满足交换律$A\cdot B\ne B\cdot A$。所以说,交换律也不是那么理所应当的,全看这种二元运算是如何定义的。

5. 椭圆曲线群

我们了解了什么是椭圆曲线,什么是群,其实我们想做的是如何在椭圆曲线上构造一个群。为什么会有这么奇怪的想法?你是不是又忘了,椭圆曲线密码ECC是椭圆曲线在ElGamal体系下的应用,ElGamal体系就是定义在群上的。好了,那么该如何定义在椭圆曲线上的二元运算呢?像我等木鱼肯定是想不出来的,好在数学家已经帮你想好了。

在介绍椭圆曲线上的二元运算(以下就称为椭圆曲线上的加法)之前,我们要做一点小小的补充。群是定义在集合之上的,椭圆曲线集合自然就是椭圆曲线上所有的点,但是,这里面有一点“麻烦”,定义群是需要一个集合上的“特殊”元素的,也就是单位元,你再看看椭圆曲线上的哪个点长得很“特殊”呢?其实没有,椭圆曲线上的每个点地位都是一样的,所以为了能在椭圆曲线上构造一个群,需要首先对椭圆曲线集合做一个扩充,引入一个“特殊”的点,这个点叫“无穷远点”,记作0:

\[\begin{array}{rcl} \left\{(x, y) \in \mathbb{R}^2 \right. & \left. | \right. & \left. y^2 = x^3 + ax + b, \right. \\ & & \left. 4a^3 + 27b^2 \ne 0\right\}\ \cup\ \left\{0\right\} \end{array}\]

这个无穷远点就是我们的单位元,为什么这么说呢,这需要结合以下的椭圆曲线加法来看。那么,无穷远点究竟在哪呢?废话,当然在无穷远处,就好像我问你平行线的交点在哪里呢?你肯定会说平行线哪有交点。其实,也可以说平行线的交点在无穷远处,对,就是那个点,是不是有点感觉了。

有了对椭圆曲线集合的扩充,我们就可以定义椭圆曲线的加法了:

  1. 单位元:无穷远点0
  2. 三点P,Q,R共线则它们的和为单位元:P+Q+R=0
  3. 关于x轴对称的两个点互为逆元。

三点共线则和为0

这就是数学家想出来的,满足群公理的椭圆曲线上的加法定义。我们可以验证一下:

  1. 封闭性,显然满足,点加来加去肯定还在椭圆曲线上,要么就是无穷远点。
  2. 结合律,满足,三点共线并没有规定顺序,所以(P+Q)+R=0=P+(Q+R)
  3. 单位元,就是无穷远点0,每个点加无穷远点还等于这个点
  4. 逆元,每个点的逆元肯定存在,因为椭圆曲线关于x轴对称,但是为啥逆元相加等于无穷远点0呢?这个不是很显然,我们可以换个角度看。

要定义椭圆曲线加法,但是上面的定义却是在说三个点相加,我们来看一种更加直接的定义,P+Q=-R,椭圆曲线上两个点相加等于过这两个点做直线与椭圆曲线交点关于x轴的对称点。除了一些特殊情况,过椭圆曲线上的两点做直线一定会与椭圆曲线有且仅有一个交点,也就是说,这么定义加法,结果是一定存在的。

P+Q=-R

所谓特殊情况就是:

  1. 两个对称点相加,也就是竖直线与椭圆曲线的只有两个或者一个交点(切线),那么这两个点相加就等于无穷远点0,正如之前所说,没有第三个交点,其实也可以说交点在无穷远处。所以说,逆元相加等于无穷远点0,颇有道理。
  2. 相同的点相加,也就是P+P,其实就是取极限,过P点椭圆曲线的切点,见图。
  3. P为切点,P+Q=-P,一样取极限,见图。

其实,根据以上定义,椭圆曲线上的加法也是满足交换律的,显然P+Q=Q+P,所以这不仅是个群,而且是个交换群。

你肯定会有疑问,为什么要这么定义?有什么道理?其实,就是没有什么道理,这么定义的出发点就是要定义一种二元运算满足群公理,我们已经看到了,这么定义是满足群公理的。你觉得普通实数的加法“有道理”是因为你在现实生活中能找到对应,像这种抽象的运算,根本不需要有你所认为的“道理”,只需要运算满足“条件”(即群公理),并且“自洽”,也就是运算规则本身能“自圆其说”。如果要在密码学中应用的话,还需要做到便于计算。这就是这么定义的道理。

5.1 标量乘法

我们定义了椭圆曲线的加法,其实就可以进而定义其标量乘法,所谓标量乘法就是同一个点加n次:

$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$

根据之前的定义,我们可以一步一步去计算,计算n次就可以得到nP,但实际上并不需要这么做,还有更快的算法,以n=151为例,151用二进制表示就是10010111,也就是说

$151 = 2^7 + 2^4 + 2^2 + 2^1 + 2^0$

那么我们可以这么做,先计算2P,然后计算4P、8P、16P、32P、64P、128P,然后

$151P = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P=128P+16P+4P+2P+P$

简单来说就是每次都翻倍加,这样就可以快速计算出nP。以上示例是想说明,椭圆曲线上的标量乘法是可以快速计算出来的。

这里有个网站,可以直观地看到椭圆曲线上加法的运算椭圆曲线上的加法

以上关于椭圆曲线加法的介绍都是基于几何图像的,几何图像对于人而言比较直观,便于我们理解,具体计算还得是代数形式的,显然可以联立椭圆曲线和直线的方程,求出交点,交点的对称点就是结果,具体计算公式不再给出,你只需要记住这种计算方式可行且这种公式存在就可以了。

6. 有限域

我们先把椭圆曲线和群都放一边,来看看另外一个数学概念——有限域。

域是加强的群,具体定义不再给出。我们只来看一种最常用的、最容易理解的有限域$F_p$,模p的整数域,其中p是一个素数,这个域包含的元素是0到p-1这p个整数。域上的运算也很简单,就是普通的运算然后对p取模,这对程序员来说应该很熟悉,以$F_{23}$为例:

\[(18+9) \pmod{23} = 4 \\ (7-14) \pmod{23} = 16 \\ 4\times 7 \pmod{23} = 5 \\\]

这都很简单,关键是“除法”:

$\frac{1}{9}\pmod{23} = 9^{-1} \pmod{23}$

其实“除法”的意义就是乘以某个元素的乘法逆元,那么9在$F_{23}$上的乘法逆元是多少呢?其实就是问:

$9\times ? \pmod{23}=1(1是乘法的单位元)$

试一试可以知道$9\times 18 \pmod{23}=1$,所以9在$F_{23}$上的乘法逆元是18,所以

$\frac{1}{9}\pmod{23} = 9^{-1} \pmod{23}=18$

之所以要求p一定要是一个素数,就是因为只有p是一个素数的时候,才能保证1到p-1每个元素都有乘法逆元(显然0没有乘法逆元),实际上,p就是prime的缩写。并且,有方法可以快速求出每个元素的乘法逆元,这就是著名的扩展欧几里得算法

7. 有限域上的椭圆曲线

我们引入有限域的概念就是为了把椭圆曲线定义在有限域上,先别问为什么要这么做,这个问题之后会解释,我们就接受这种设定,来看看有限域上的椭圆曲线长什么样子。

\[\begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array}\]

方程跟之前的一样,只是对于其中所有参数x,y包括a,b施加了有限域的限制,也就是说x,y,a,b都只能取0到p-1中的整数。那个长得三条线的等号是代表同余的意思,意思就是说等式的左边计算的结果对p取模等于等式右边的结果对p取模。那么施加了这个限制之后椭圆曲线会变成什么样子呢?看图。

以上是$y^2 \equiv x^3 - 7x + 10 \pmod{p}$在p取19,97,127,487值时的图像。我们来看几个例子,以左上角的图像为例,p=19,对于点(2,2),$2^2 \equiv 2^3 - 7\times 2+ 10 \equiv 4 \pmod{19}$成立,对于点(16,17),$17^2 \equiv 16^3 - 7\times 16+ 10 \equiv 4 \pmod{19}$成立。其实就是图中的每个点带入方程计算对p取模的结果相等。注意到图像是关于y=p/2对称的。

下面的问题就是,有限域上的椭圆曲线的加法应该是什么呢?其实跟我们刚才看到的实数域上的椭圆曲线上的加法是一样的,但是因为有限域上的椭圆曲线变成了离散的点,再去说什么两点连线求交点就变得不再形象了,但是之前强调过,图像只是给人看的,我们通过联立方程的方式得到的计算点加法的公式,在有限域上的椭圆曲线仍然是成立的,只不过公式中的运算也要受到有限域的限制,也就是计算结果需要对p取模,计算过程中的“除法”需要转换为乘以乘法逆元。

虽然我们对椭圆曲线施加了有限域的限制,但是,有限域上的椭圆曲线及其点加法仍然构成交换群。

7.1 群的阶

群的阶也就是群中元素的个数,在实数域上的椭圆曲线不会有这个问题,因为显然实数域上群的阶是无穷大的,但是在有限域上就可以去问这个问题了,有限域上群的阶是多少呢?显然可以让x从0步进到p-1,然后把所有的点求出来,但是,现实中p会是一个很大的素数,这么做不可行。万幸,数学家已经解决了这个问题,Schoof算法可以快速求出有限域上椭圆曲线群的阶。

7.2 循环子群

有限域上的椭圆曲线还有一个很有用的结论,其上任意一个点P,经过若干次标量乘之后都会回到无穷远点0,也就是说总存在n,使得nP=0。我们来看一个具体的例子,对于$y^2 \equiv x^3 + 2x + 3 \pmod{97}$上的点$P(3,6)$而言

$5P=0$,并且你可以继续验证$6P=P,7P=2P \dots kP = (k \bmod{5})P$。这五个点组成了一个封闭集合,你在这个集合中做点加运算,结果仍在在这个集合中,我们称这个集合是群的一个循环子群。对于上例而言,该循环子群的阶就是5,这个循环子群中的其它点都是通过点P得到的,我们称P是这个循环子群的基点或者生成元

循环子群很重要,循环子群是椭圆曲线密码学以及其它许多加密系统的基础。

这里再引入群论当中的一个结论,子群的阶一定是父群阶的一个因子。假设父群的阶是N,子群的阶是n,那么h=N/n一定是一个整数,h被称为子群的余因子。对于上面的例子而言,通过Schoof算法可以算出,父群的阶是100,以P为基点的循环子群的阶是5,所以余因子h=20。

讲到这里,你可能会好奇,我们如何在有限域上的椭圆曲线中确定一个基点和它对应的循环子群的阶呢?这个问题很重要,但其实你不用关心,因为Alice和Bob要想使用ECC通讯就必须在同一条曲线上计算,而这个曲线通常会选用标准曲线,标准曲线之所以标准,就是这条曲线上的参数都是确定的,基点和循环子群的阶自然也是确定的,并且是告诉你的,你只要知道有办法去确定基点和循环子群的阶就可以了,具体方法你可以忽略。

8. 椭圆曲线离散对数难题

讲了这么多,铺垫了这么多,终于要到高潮了。引入了这么多数学概念,就是为了构造这么一个数学难题:已知有限域上的椭圆曲线的循环子群上的两个点P和Q,求k为多少时,Q=kP。当这个循环子群的阶比较小时,这么问题很简单,我们可以一个一个k值去试,但当子群的阶很大时,这个问题就很难了,目前在经典计算机上还没有多项式时间复杂度的算法可以求解。并且这个难题比整数因子分解难题更加困难,所以ECC可以用较小的密钥获得和RSA一样的安全强度。

主观地讲,有限域上的椭圆曲线的点加法,即使在你了解其加法规则的时候,也难以发现其规律,结果就像是从这个点跳到另外一个点,基于规则我们可以快速求出从一个点“跳”n步之后到了哪个点,但是如果告诉你这里有两个点,问它们之间的联系,是“跳跃”了多少步才到达“终点”的,这个问题很难回答。

ECC的安全性建立在椭圆曲线离散对数难题(elliptic curve discrete logarithm problem,ECDLP)之上的,这个问题之所以困难,并不是说我在这嘚啵了半天,引入了这么多数学概念它才困难,而是它真的困难(拜托,相信我)——这个理由还真的是一点都不牵强啊!关键还在于,我们找不出有效的算法来求解这个问题,总之,你知道这是个难题就可以了。

9. 椭圆曲线密码学ECC

有了上面的数学难题,我们就可以在其基础上构造出公钥加密体系,一般包括三个方面:

  1. ECDH(Elliptic Curve Diffie-Hellman):密钥交换
  2. ECDSA(Elliptic Curve Digital Signature Algorithm):数字签名
  3. 非对称加密

我们一个一个来看,看如何把ECDLP来应用到上面这些方面。

9.1 密钥交换

简单来说,密钥交换就是Alice和Bob通过公开交互一些信息就可以协商出来一个只有他们两个人知道的密钥,别的人通过公开的信息,求解出这个密钥是计算不可行的;这个交换得到的密钥特别适合于用作对称加密的密钥。ECDH的基本原理如下:

  • 有限域上的椭圆曲线基点为$G$
  • Alice的私钥是$d_A$,公钥是$H_A=d_AG$
  • Bob的私钥是$d_B$,公钥是$H_B=d_BG$
  • Alice和Bob相互交换公钥,他们可以求出相同的密钥S

$S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A$

Alice和Bob都可以很容易的求出S,但是“中间人”很难求出S

一般认为已知椭圆曲线的参数从$H_A$和$H_B$求解出$S$的难度等同于ECDLP,显然这个问题并不会比ECDLP更困难,因为求解出ECDLP必然能求出$S$。

9.2 数字签名

简单来说,数字签名就是Alice通过其私钥“签名”了某个信息,其他人包括Bob都可通过Alice的公钥来验证这个信息确实是他签的,因为这个信息只能通过Alice的私钥签出来,别的人签不出来。ECDSA的基本原理如下:

  • 用密码级安全的哈希函数把待签名的信息m转换为哈希值z
  • 在${1, \dots, n - 1}$范围内生成随机数k,n为循环子群的阶
  • 计算$P = kG$
  • $r = x_P \bmod{n}\ (x_P是P的横坐标)$
  • $s = k^{-1} (z + rd_A) \bmod{n}$
  • (r,s)就是签名信息

任何人通过Alice的公钥都可以验证,信息m的数字签名(r,s)是否来自Alice,具体验证步骤不再给出。通俗地说,r隐藏了随机数k的信息,s混合了Alice的私钥和待签名的信息,有了这些信息,我们可以从另外一个方向来验证,这些信息是来自Alice的。这里有张图形象地说明了这一点:

ECDSA签名、验签过程示例,为了方便展示,以实数域上的椭圆曲线为例

s之所以设计成那个样子就是为了使得,rP+zG=sR。

注意,计算s需要使用k模n的乘法逆元,前面说过,只有n为素数的时候,k的乘法逆元才能保证存在,而n是椭圆曲线循环子群的阶,这也就是为什么几乎所有的标准曲线的n都是素数。

9.3 非对称加密

非对称加密就不需要多解释了,公钥加密,只有私钥才能解密。在ECC中,非对称加密的基本原理是:

  • Alice的私钥是$d_A$,公钥是$H_A=d_AG$
  • Bob将要发送的消息m编码为椭圆曲线上的点M,并生成一个随机数r
  • Bob把$C_1=M+rH_A \ \ C_2=rG$ 发给Alice
  • Alice解密$C_1-d_AC_2=M+rH_A-d_ArG=M+rd_AG-d_ArG=M$

通俗地说,Bob要传递的信息就在$C_1$中,但是只有Alice才能把$C_1$中多余的部分减去。

9.4 一点说明

本节讲解了,基于椭圆曲线离散对数难题如何实现密钥交换、数字签名、非对称加密。但是,这只是一些原理说明,并不代表具体的算法实现,真正的算法设计可能比这些原理要更复杂,已获得更好的安全性,或者更巧妙的设计以使得运算速度更快。

10. 标准曲线

secp256k1标准曲线的领域参数如下:

1
2
3
4
5
6
7
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
xG = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
yG = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
h = 1

有限域大致是2的256次方,余因子h=1,说明群的阶和循环子群的阶是一样的,都是n,并且可以验证,n是一个素数,也大致接近2的256次方。通常来说,余因子h都是1,2,4这些数,这样循环子群就有更多的点,破解起来难度就更大。这条曲线很有名,因为它被用作比特币的数字签名。

除了这条标准曲线外,还有很多其它的标准曲线,这些曲线的名字也不是随意取的,名字中涵盖着椭圆曲线的一些信息,更具体的可以参看一场椭圆曲线的寻根问祖之旅

SM2标准椭圆曲线叫做sm2p256v1,具体领域参数如下:

1
2
3
4
5
6
7
p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
a = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
xG = 0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
yG = 0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
h = 1

和secp256k1类似,有限域和群的阶都接近2的256次方。

11. SM2在设计什么

其实,椭圆曲线密码学的理论已经很成熟了,国际上通用的椭圆曲线密码算法也有很多,那么SM2在设计些什么呢?其实主要有两点:

  1. 选择合适的领域参数,避免“弱曲线”,对抗已知的攻击手段。
  2. 设计出具体的密钥交换、数字签名、非对称加密的标准算法,即要保证安全,又要保证计算效率。

12. 问题

  1. 悖论:标准椭圆曲线是否暗藏后门,椭圆曲线离散对数问题并不是在任何条件下都是困难的,在某些特定的椭圆曲线上就比较简单,那么如果保证标准的椭圆曲线不是经过“精心设计”的,然后设计者知道某些不公开的破解手段呢?这是个悖论,无论标准椭圆曲线的参数取什么值都会有这样的疑虑。相反RSA就不存在这样的问题,因为也不需要什么标准的素数这种东西。但是,我觉得这也不是个问题,想通过“公开”的方式去“隐藏”这本身就不太可行。
  2. 信息如何编码到点,如何从点反推出信息,这部分内容没有涉及,因为我也不知道。
  3. 椭圆曲线有很多种,文中所说的都是一种叫Weierstrass的椭圆曲线,这种椭圆曲线最常用,当然还有别的形式的椭圆曲线。
  4. 常见的有限域除了$F_p$还有$F_2^m$,$F_p$上的运算比较好理解,$F_2^m$上的运算就不是那么容易理解了,当然,也有定义在$F_2^m$有限域上的标准曲线。

13. 总结

不严谨地讲,在椭圆曲线上构建出群,是使得椭圆曲线可以用于密码系统的基础,而有限域的引入使得椭圆曲线离散对数问题变得困难。

14. 参考

关于ECC最好最通俗地介绍应该是这篇国外的文章:Elliptic Curve Cryptography: a gentle introduction 这是一个系列文章,包括四篇。本文许多图表、示例都来自这篇文章。有中文翻译版:椭圆曲线密码学简介

How Schnorr signatures may improve Bitcoin,这篇文章介绍了比特币签名的细节,本文ECDSA的图片即来自这篇文章。

椭圆曲线密码学是系统且专业的领域,更多专业内容可以查看这本书《椭圆曲线密码学导论》。

转载注明原始出处 SM2国密算法之数学原理 © 芯盾技术团队