李 杨 王劲林 曾学文 叶晓舟

1(中国科学院声学研究所国家网络新媒体工程技术研究中心 北京 100190)2(中国科学院大学 北京 100190)

OCTEON处理器上实现国密SM2算法整体优化方案研究

李 杨1,2王劲林1曾学文1叶晓舟1

1(中国科学院声学研究所国家网络新媒体工程技术研究中心 北京 100190)2(中国科学院大学 北京 100190)

SM2椭圆曲线公钥密码算法的核心运算是椭圆曲线上点乘算法，因此高效实现SM2算法的关键在于优化点乘算法。对椭圆曲线的点乘算法提出从底层到高层逐层优化的整体方案。上层算法使用带预计算的modified-wNAF算法计算点乘，中间层使用a=-3的Jacobian投影坐标系计算点加和倍点，底层基于OCTEON平台的大数乘加指令使用汇编程序实现模乘算法。最终在OCTEON CN6645处理器上实现该算法，实验结果表明：SM2数字签名速度提高了约540%，验证提高了约72%，加密提高了169%，解密提高了61%。

SM2 椭圆曲线密码算法 点乘 OCTEON处理器

0 引 言

椭圆曲线密码体系ECC是1985年由Koblitz[1]和Miller[2]提出的，由于其使用密钥长度短，安全性高等特点已经被广泛应用。SM2椭圆曲线公钥密码算法[3]，是由国家密码管理局于2010年发布的一种基于ECC的公钥密码算法。SM2算法的软件实现中，加解密和签名验证等操作都是基于椭圆曲线上的点乘算法实现的。因此如何高效地实现点乘运算成为提高SM2算法实现性能的关键。OCTEON 处理器[4]是Cavium公司推出的一款基于cnMIPS II架构的多核64位通用型处理器。本文结合OCTEON处理器的特点，对点乘算法按运算层次从低至高逐层优化，提高点乘的运算效率，从而达到对基于OCTEON处理器上实现国密SM2算法整体优化的目的。

1 基础知识介绍

1.1 SM2算法

SM2椭圆曲线公钥密码算法，是由国家密码管理局于2010年12月发布的第21号公告中公布的密码行业标准。标准中规定了SM2数字签名算法，SM2密钥交换协议和SM2公钥加密算法；并在最后给出了一组推荐曲线，如图1所示。

图1 SM2椭圆曲线公钥密码算法曲线参数

1.2 ECC数学定义和定理介绍[5]

定义1在有限域Fp(p>3)上，Weierstrass方程：

y2=x3+ax+ba,b∈Fp(4a3+27b2)modp≠0

(1)

所确定的曲线称为有限域Fp上的椭圆曲线，满足式(1)的所有点(x,y)及无穷远点O共同构成了椭圆曲线上的点。即：E(Fp)={(x,y) |x,y∈Fp，且满足方程式(1)}∪{O}。椭圆曲线E(Fp)上点的数目用#E(Fp)表示，称为椭圆曲线的阶。如果椭圆曲线上存在一个点G使得(#E(Fp))G=O，则称点G为椭圆曲线的基点。n是#E(Fp)的素因子，称为基点G的阶，余因子h=#E(Fp)/n。

由定义1可知，椭圆曲线E(Fp)可由参数(p,a,b,n,G,h)确定。下面我们给出椭圆曲线上的群运算法则：

定义2E(Fp)上的所有点按照下面的加法运算规则，构成一个Abel群：

a)O单位元；对于∀P∈E(Fp)，满足P+O=O+P=P;

b) 负元素；对于∀P∈E(Fp)，P的负元素-P=(x,-y)，P+(-P)=O，此外-O=O;

c) 点加；P1= (x1,y1) ∈E(Fp){O}，P2= (x2,y2) ∈E(Fp){O}，P3= (x3,y3) =P1+P2≠O，则：

(2)

d) 倍点；P1= (x1,y1) ∈E(Fp){O}，P1≠-P1，P3= (x3,y3) = 2P1，则：

(3)

定义3设P是椭圆曲线E(Fp)上点，k为正整数，则k与P的点乘(标量乘)记为：

(4)

椭圆曲线上计算点乘有多种方法，目前高效计算标量乘的算法主要有：二进制法、加减法，窗口法、带符号的二进法、双基数法、优化定义域法、m进制法等。当前标准的椭圆曲线标量乘法是 IEEE P1363标准中给出的投影坐标下非临界标准型NAF(Non-Adjacent-Form)的二进制法。其基本思想是将点乘运算转化为一系列的点加和倍点运算。

1.3 OCTEON系列处理器介绍

OCTEON系列芯片是Cavium公司推出的一款基于Cavium Networks MIPS II (简称cnMIPS II)架构的多核64位通用型处理器，广泛集成了L3-L7的数据、内容。安全服务的硬件加速选项。本系统设计使用OCTEON CN66XX处理器[4]，8级流水线，双指令体系结构，核心频率1 200 MHz。除此之外，OCTEON CN66XX还具有大数乘法指令，包括128位和256位的大数乘加指令，具体大数指令的功能和应用例子如表1所示。

表1 OCTEON CN68XX指令列表及功能介绍

2 SM2算法整体优化方案

SM2椭圆曲线密码算法的实现主要可以分为三个层次，如图2所示，分别为：SM2密码协议层，椭圆曲线群操作层和有限域操作层。有限域操作层主要是实现有限域最基本的模运算；椭圆曲线群操作层是基于模运算实现的点加和倍点运算，在此基础上再实现点乘运算；SM2密码协议层基于有限域和椭圆曲线群操作的基础，实现上层的数字签名验证，密钥交换和公钥加解密等协议。层次由下而上，上层调用下层，下层是上层的基础。

图2 SM2椭圆曲线公钥密码算法实现层次结构图

基于这一实现层次，我们可以将SM2算法整体设计和优化分为三个层次：上层点乘算法设计优化、中间层点加和倍点运算方法设计优化和下层有限域大数计算方法设计优化。

2.1 有限域大数计算方法设计优化

在有限域的底层操作中，最基本且最耗时的操作是大数模乘/模平方操作。因此本节主要使用OCTEON平台上特有的大数乘加指令来优化模乘或平方操作。

1985年，Montgomery[6]提出的Montgomery模乘算法是现在应用最广泛的一种模乘算法。其基本思想是用简单省时的加法和移位操作代替普通模乘方法中费时的求逆和除法操作。其计算结构如图3所示，其中Montgomery模乘：MM(A,B)=A×B×R-1modN；普通模乘：M(A,B)=A×BmodN。

图3 Montgomery模乘计算结构示意图

1996年Koc等[7]对各种Montgomery模乘算法的实现方法进行了分析总结，并归纳了5种主要的改进Montgomery算法：SOS、CIOS、FIOS、FIPS和CIHS。目前效率较高且应用最为广泛的算法为CIOS算法。本节针对CIOS算法使用OCTEON平台上特有的64×64 bit大数乘加指令，对SM2算法中需要用到的256 bit大数模乘运算进行优化。

使用CIOS方法计算Montgomery模乘如算法1所示。可以看出，其需要计算的关键步骤为：(C,S)=t[j]+A[j]B[i]+C,t[j]=S(i固定，j∈[0,s-1])。其实质就是计算一个乘数固定的带进位的乘加运算，其中运算使用2.3节介绍的VMULU乘加指令直接实现。使用汇编算法直接实现256位CIOS算法见图4所示，由于为64位处理器，256位操作数A,B,N可以表示为4个字。

算法1CIOS Montgomery算法

输入：A,B,N,N′[0]，其中N′[0]=-N0-1mod 2w,s为N字数

输出：A*B*R-1modN

1: for i=0; i

2: C=0

3: for j=0; j

4: (C,S)=t[j]+A[j]*B[i]+C

5: t[j]=S

6: end for

7: (C,S)=t[s] +C

8: t[s]=S

9: t[s+1]=C

10: C=0

11: M=t[0]*N′[0] mod 2w

12: for j=0; j

13: (C,S)=t[j]+M*N[j] +C

14: t[j]=S

15: end for

16: (C,S)=t[s] +C

17: t[s]=S

18: t[s+1]= t[s+1]+C

19: end for

19: if(t>N)

20: t=t-N

21: end if

22: return t

由图4可以看出，算法使用6个寄存器R0-R5存储中间结果，B[i]A[0]+B[i]A[1]+B[i]A[2] +B[i]A[3]操作使用VMULU指令直接实现，这样使用汇编语言直接实现的256位CIOS Montgomery模乘可以利用硬件大数乘加指令的优点，提高算法的性能。图5是使用汇编程序实现256位CIOS算法的代码，其中t2、t5寄存器用来加载乘数和被乘数，s0-s5用来存储计算中间结果，最终得到的s0-s4是计算的最终结果被存储到最终结果product中。

图4 汇编实现256位CIOS算法结构

图5 汇编程序实现256位CIOS算法的代码

2.2 点加和倍点运算方法设计优化

对于点加和倍点运算，本文使用Jacobian投影坐标系[5]来进行计算，即投影点(X:Y:Z)与仿射点(X/Z2,Y/Z3)相对应，则椭圆曲线的方程转化为：

Y2Z=X3+aXZ4+bZ6

则点加的计算公式可以转化为：

(6)

倍点计算公式转化为：

(7)

由于国密SM2推荐曲线参数中:

a= FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF

FFFFFFFF 00000000 FFFFFFFF FFFFFFFC

p= FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF

FFFFFFFF 00000000 FFFFFFFF FFFFFFFF

即a=a-p=-3，则倍点公式可进一步优化为：

(8)

下面我们分析使用仿射坐标系和Jacobian投影坐标系计算点加和倍点的复杂度，用M表示乘法运算，S表示平方运算，I表示求逆运算，加减法运算相对于乘法平方和求逆运算占用时间小，分析时忽略。根据Bernstein[8]实验结果和分析知，如果选用域乘法效率不是特别低的情况下，I/M>8。这里假设S/M=0.8，I/M=8，分析点加和倍点运算复杂度如表2所示。

表2 不同坐标系下点加和倍点运算复杂度对比

测试OCTEON平台上openssl软件包中的BN_mod_mul(M), BN_mod_sqr(S), BN_mod_inverse(I)函数可知，OCTEON平台上M、S、I三种操作使用时间对比为：S=0.9M,I=35M。 因此仿射坐标系下点加算法复杂度为：I+2M+S=37.9M，倍点为：I+2M+2S=38.8M；Jacobian投影坐标系下点加算法复杂度为：12M+4S=15.6M，倍点为：4M+4S=7.6M。由此可见使用Jacobian投影坐标后，点加和倍点的运算效率可得到显著的提高。

2.3 点乘算法设计优化

SM2中用到的上层的点乘算法，主要分为两种，一种是计算固定点的点乘：例如计算kG(G为椭圆曲线的基点)；另一种是计算非固定点的点乘：例如计算lPA。对于点乘算法的优化，我们主要是参考Moller[9]提出的修改的wNAFs方法，对原始wNAF存在的问题进行分析，提出一种更易于实现的modified-wNAF方法。

下面先介绍原始的wNAF方法，使用窗口长度为w+1的NAF算法，将原来有{0,1}集合组成的二进制表示方式，转化为由集合B={±1, ±3,…, ±(2w-1)}中的数组成的带符号的wNAF方式。我们首先定义一个映射关系digit:{0,1,2,…,2w+1-1}->B∪{0}如下：

(9)

下文中使用LSBm(c)表示取c最低m位，即LSBm(c)=cmod 2m。原始的窗口长度为w+1的NAF算法具体实现方法如图6上半部分所示。这种算法采用从右至左的运算方式，取最低w+1位即b=LSBw+1(e)，通过digit映射关系，将w+1位二进制数映射到集合B∪{0}中，则b=digit(b)即为最终结果b0；计算e=(e-b)/2，取最低w+1位并重复上述步骤计算出b1；按照此方式可以依次计算出b0至bl即为最终的wNAF表示。由于b-digit(b)=0或2w+1，故图中求e=e-b=e-digit(b)的最低w位为0，e=(e-b)/2的最低w-1位为零。因此接下来求的(w-1)个bi为零，这就保证了wNAF表示中任何连续w个数字中最多1位为非零。

图6 wNAF和modified-wNAF算法计算步骤对比

modified-wNAF方法实现方式如算法2所示，则计算点乘的窗口NAF方法见算法3。从算法3中可以看出需要计算iP,i∈{1, 3,…, (2w-1)}，对于P点已知的情况iP可以通过预计算的方式，在程序开始之前计算完后存储在预计算表中。当程序运行时直接查表读取即可，这样可以有效地节省程序的运行时间。因此SM2中在程序开始之前预计算基点G相关的点：G,3G,…,(2w-1)G并存在预计算表中供下面程序查询使用，这样可以大大提高接下来计算kG的效率。

算法2modified-wNAF算法

输入：正整数e=(el-1,…,e1,e0)，窗口长度w+1

输出：b=modified-NAFw(e) =(bl,…,b1,b0)

1: c←e

2: i←0

3: while c>0 do

4: b←LSBw+1(c)

5: if (i+w+1)≥l && b≥2w

6: b←LSBw(b)

7: else

8: b←digit(b)

9: end if

10: c←c-b

11: bi←b

12: i←i+1

13: c←c/2

14: end while

15: return (bi-1,…,b1,b0)

算法3计算点乘的modified-wNAF算法

输入：正整数k，窗口长度w+1，P∈E(Fq)

输出：kP

1: modified-wNAF(k)= (kl-1,…, k1, k0)

2: for i∈{1, 3,…, 2w-1} do

3: Pi=iP

4: end for

5: Q←Ο

6: for i=l-1 to 0 do

7: Q←2Q

8: if ki>0

9: Q←Q+Pki

10: else if ki<0

11: Q←Q-Pki

12: end if

13: end for

14: return Q

2.4 优化方案安全性分析

在上述的优化方案中，最上层的点乘算法采用modified-wNAF算法。从算法3中可以看出：当ki≠0时，需要计算一次倍点和一次点加运算；而当ki=0时，仅需要计算一次倍点运算即可。攻击者可以通过对能量曲线的分析，得到标量的哪些位为零。虽然不能直接破译标量的值，但是对算法自身的安全性带来严重的威胁。因此后续工作会展开对安全性的分析和优化。

3 仿真实验与结果分析

本文在cavium公司的OCTEON CN6645平台上[10]基于开源软件库openssl，实现了SM2数字签名验证及公钥加解密算法。分别测试了在单核上运行优化前后数字签名、验证、公钥加密、公钥解密程序的执行速度(每秒能完成次数)，测试结果如表3及图7所示。优化1表示使用带预计算的modified-wNAF方法，优化2表示使用大数乘加指令优化256位模乘算法。

表3 SM2各种算法优化前后速度对比(每秒执行次数)

图7 SM2各种算法优化前后速度对比(每秒执行次数)

从实验结果可以看出，优化2对于各种算法速度提高的百分比基本相同，大约在66%左右；而优化1对于各种算法速度提升的作用不尽相同。对于数字签名这种主要操作是计算固定点点乘，优化1对于速度的提升是巨大的，能够提升300%以上；对于公钥解密这种计算非固定点点乘，优化1对于速度提升无影响；对于验证和公钥加密这种即需要计算非固定点又需要计算固定点点乘的算法，优化1能够带来一部分的速度提升。

总体来讲，在OCTEON CN6645处理器上对国密SM2算法的整体优化，使得数字签名速度提高了约为540%，验证提高了约为72%，加密提高了169%，解密提高了61%。

4 结 语

本文提出了在OCTEON 处理器上实现SM2椭圆曲线密码算法的整体优化方案，其重点就是对椭圆曲线上点乘算法进行优化。基于OCTEON处理器大数乘加指令和通用算法的优化，对点乘的实现算法从底层模运算，中间层点加倍点运算到最上层点乘运算逐层进行了优化。实验结果表明：此种优化方案显著提高了SM2算法的运算效率，SM2数字签名效果最明显，速度提高了约540%，每秒签名次数由原来的299次提高到了1 920次。在提高算法效率的基础上，算法的安全性也是需要重点考虑的问题。接下来的工作将会对算法的安全性进行优化，重点考虑抗SPA攻击，使算法在保证效率的基础上兼顾了安全特性。

[1] Koblitz N.Elliptic curve cryptosystems[J].Mathematics of computation,1987,48:203-209.

[2] Miller V S.Use of Elliptic Curves in Cryptography[J].Lecture Notes in Computer Science,1986,218(1):417-426.

[3] 国家密码管理局.SM2椭圆曲线公钥密码算法[S/OL].[2010-12-17].http://www.oscca.gov.cn/News_1197.htm.

[4] Cavium.OCTEON II CN66XX Multi-Core MIPS64 Processors[J/OL].[2011-07].http://www.cavium.com/OCTEON-II_CN66XX.html.

[5] Hankerson D,Menezes A J,Vanstone S.Guide to elliptic curve cryptography[M].Springer,2004.

[6] Montgomery P L.Modular multiplication without trial division[J].Mathematics of Computation,1985,44(170):519-521.

[7] Koc C,Acar T,Kaliski B S.Analyzing and Comparing Montgomery Multiplication Algorithms[J].Micro IEEE,1996,16(3):26-33.

[8] Bernstein D,Lange T.Analysis and optimization of elliptic-curve single-scalar multiplication[J].Contemporary Mathematics,2008.

[9] Möller B.Improved Techniques for Fast Exponentiation[C]//Information Security and Cryptology-Icisc 2002,International Conference Seoul,Korea,November 28-29,2002,Revised Papers,2002:298-312.

[10] 李军,陈君,倪宏,等.基于多核协作的流媒体内容缓存算法[J].网络新媒体技术,2014,3(4):12-18.

RESEARCHONWHOLEOPTIMIZATIONOFSM2PUBLICKEYCRYPTOGRAPHICIMPLEMENTATIONALGORITHMONOCTEONPROCESSOR

Li Yang1,2Wang Jinlin1Zeng Xuewen1Ye Xiaozhou11

(NationalNetworkNewMediaEngineeringResearchCenter,InstituteofAcoustics,ChineseAcademyofSciences,Beijing100190,China)2(UniversityofChineseAcademyofSciences,Beijing100190,China)

The core operation of SM2 elliptic curve public key cryptographic systems is point multiplication on elliptic curve. So, the key of efficient implementation of SM2 algorithm is to optimize the point multiplication. In this paper, we propose a whole optimization scheme to optimize the point multiplication from bottom to top. The top algorithm uses modified-wNAF with precomputation algorithm to compute point multiplication. The middle algorithm computes point adding and doubling with the Jacobian projected coordinate system. And the bottom algorithm optimizes the modular multiplication based on large multiply instructions on OCTEON platform. At last we implement the algorithms on OCTEON CN6645 and the experimental results show that SM2 signature, SM2 verify, SM2 encrypt and SM2 decrypt algorithms obtain increases by about 540%, 72%, 169% and 61% respectively.

SM2 Elliptic curve cryptographic algorithm Point multiplication OCTEON processor

TP309.7

A

10.3969/j.issn.1000-386x.2017.09.060

2016-10-11。中国科学院战略性先导科技专项课题(XDA06010302)；中国科学院声学研究所知识创新工程项目(Y154191601)。李杨，博士生，主研领域：网络安全。王劲林，研究员。曾学文，研究员。叶晓舟，研究员。