面向物联网安全的素域SM2点乘硬件优化

Hardware Optimization of Prime Field SM2 Point Multiplication for IoT Security

摘要: 为解决现有SM2软硬件实现在物联网应用中由于成本与功耗限制所存在的计算速度较慢问题，采用自下而上的思想对SM2点乘算法分层硬件优化。首先基于DSP乘法器提出单周期并行256位乘法算法KO-5，藉此设计了可流水线操作的2个时钟周期的256位模乘法器；然后基于并行化和流水线技术等设计点运算模块，大大减少了计算时间；最后，通过使用固定窗口点乘算法提升效率。实验结果分析表明，经过优化的点乘模块计算时间为136.68 us，逻辑资源使用仅19.59 kLUTs和144 DSPs，相对同类工作在性能和资源消耗方面均有优势，适用于高性能物联网安全场景。

Abstract: To solve the problems of slow computation speed in the existing SM2 hardware and software implementations under the cost and power constraints of IoT applications, a bottom-up approach was adopted to optimise the SM2 algorithm hardware hierarchically. Firstly, a single-cycle parallel 256-bit multiplie algorithm KO-5 was proposed based on DSP multiplier, and utilized to design a two-clock-cycle pipeline version of the 256-bit modular multiplication; then the point operation module was designed by through parallelization techniques and pipeline techniques, which greatly reduced the calculation time. Finally, a fixed-window point multiplica-tion algorithm was used to improve the efficiency. The experimental results show that the computation time of the optimized point multiplication module is reduced to 136.68 us only by using 19.59 kLUTs and 144 DSPs logical resources, which has advantages of performance and lower resource utilization compared to similar works, and is suitable for high-performance IoT security scenarios.

1. 引言

随着人工智能和大数据等技术的发展，人们对于物联网的需求也逐步从“万物互联”向“万物智联”转变 [1] 。与此同时，物联网和边缘计算设备面临着众多安全挑战 [2] 。保护物联网安全是一项复杂而持续的任务，需要采取综合性的措施来防御各种威胁。其中，以椭圆曲线密码(Elliptic Curve Cryptography, ECC)为典型的公钥密码，具有经典陷门函数特性，在保障数据安全和隐私、防止数据篡改和伪造、确保身份认证方面发挥着重要的作用，已经成为物联网安全领域的重要基石。为保护我国信息安全，国家密码管理局推出了基于椭圆曲线密码改进的SM2算法 [3] 。

SM2的核心运算是椭圆曲线标量乘法(Elliptic Curve Scalar Multiplication)，也被称为椭圆曲线点乘法(Elliptic Curve Point Multiplication，简称点乘)。点乘是椭圆曲线密码系统中使用最频繁、耗时最长的运算，点乘运算速度是改进椭圆曲线密码的关键之一；同时，在物联网应用中，FPGA硬件面临着成本和功耗问题。因此，本文考虑在资源受限情况下 [4] ，提出分层硬件优化方法：首先从SM2底层有限域运算层出发，针对调用最多的模乘部分提出了基于DSP乘法器的256 bit乘法算法KO-5，仅需一个时钟周期得到乘法结果的同时大大降低了乘法器模块的逻辑资源使用率，并结合快速模约减算法实现了两个时钟周期的模乘法器，随后在此基础上采用流水线技术、预计算技术和固定窗口算法等优化方法逐层优化。最终设计实现了一个高性能和低资源消耗的SM2点乘模块，可应用于具有较高性能需求的物联网数据加解密、设备身份认证和数据源认证等场景。

2. SM2参数与架构

2.1. SM2参数

伪梅森素数域GF(p)上的椭圆曲线表示为：

$y^2=x^3+ax+b$ (1)

国家密码管理局推荐的SM2系统参数为：

p = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 00000000 FFFFFFFF FFFFFFFF

a = FFFFFFFE FFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFF 00000000 FFFFFFFF FFFFFFFC

b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93

2.2. SM2架构分析

公钥密码系统一般是由模加、模减、模乘法和模逆等有限域运算单元构建，SM2算法分层次架构如图1所示。

Figure 1. Hierarchy of SM2 algorithm

图1. SM2算法分层架构

第一层是有限域运算层，包括模加、模减、模乘法等基本模运算，本层主要是在模乘法器部分对于速度和逻辑资源使用率的优化。

第二层为椭圆曲线上的点运算层，通过对已知的坐标，进行有限域运算得到另一个未知点坐标。

第三层是群运算层，点乘是椭圆曲线密码的核心运算，对椭圆曲线上的一个P点求解在曲线上的k倍点kP坐标。

顶层为协议层，一般有椭圆曲线数字签名算法、验签和公钥加解密算法等。

3. 硬件优化设计

3.1. 模乘优化

模乘由于具有计算密集性和高频次调用 [5] ，其运算性能和功耗显著影响着SM2系统性能。一般将模乘分为大数乘法和模约减两个部分。

3.1.1. 大数乘法优化

两个N位整数相加时间复杂度为 $O\left(n\right)$ ，而两个N位数乘法时间复杂度为 $O\left(n^2\right)$ ，乘法运算的复杂度对于整数来说太高 [6] 。一般可以采用Karatsuba-Ofman乘法算法，通过用成本低的加减法运算代替部分乘法运算来降低复杂度。

算法1 Karatsuba-Ofman乘法

输入 $0\le x,y\le 2N$ //2N为位宽

输出 $P=x*y$

1) 划分 $x=x_1{2}^N+x_0$ , $y=y_1{2}^N+y_0$ ；

2) $p_0=x_0\ast y_0$ , $p_1=x_1\ast y_1$ ；

3) $p_{01}=\left(x_1+x_0\right)\ast \left(y_1+y_0\right)$ ；

4) $P=x_1{y}_1{2}^{2N}+\left(x_1{y}_0+x_0{y}_1\right)2^N+x_0{y}_0$

$=p_1{2}^{2N}+\left(p_{01}-p_0-p_1\right)2^N+p_0$ 。

在算法1第四步中，KO算法通过用资源消耗低的减法和加法运算代替部分乘法运算来执行乘法运算。通过转化，原本需要四个N位乘法减少到两个N位乘法加一个N + 1位乘法，代价仅是增加了额外的加法器。

Xilinx提供的硬件DSP乘法器最高只到64 bit，而SM2需要256 bit乘法计算。主流算法采用多级KO算法实现，第一级由64 bit乘法器与多个加法器构成128 bit乘法器，第二级在此基础上构成256 bit乘法器，乘积需要多个计算时钟周期。因此，本文基于并行思想提出和设计了将乘数划分成5部分的KO-5算法，具体算法设计如算法2所示。

算法2 KO-5乘法

输入 $x,y$ //256 bit

输出 $P=x*y$ //512 bit

1) $x=x_4{2}^{4N}+x_3{2}^{3N}+x_2{2}^{2N}+x_1{2}^N+x_0$ ；

$y=y_4{2}^{4N}+y_3{2}^{3N}+y_2{2}^{2N}+y_1{2}^N+y_0$ ；

2) $p_0=x_0\ast y_0$ ， $p_1=x_1\ast y_1$ ，

$p_2=x_2\ast y_2$ ， $p_3=x_3\ast y_3$ ， $p_4=x_4\ast y_4$ ；

3) //部分积计算

$p_{01}=\left(x_1+x_0\right)\ast \left(y_1+y_0\right);p_{02}=\left(x_2+x_0\right)\ast \left(y_2+y_0\right)$ ，

$p_{03}=\left(x_3+x_0\right)\ast \left(y_3+y_0\right);p_{04}=\left(x_4+x_0\right)\ast \left(y_4+y_0\right)$ ，

$p_{12}=\left(x_2+x_1\right)\ast \left(y_2+y_1\right);p_{13}=\left(x_3+x_1\right)\ast \left(y_3+y_1\right)$ ，

$p_{14}=\left(x_4+x_1\right)\ast \left(y_4+y_1\right);p_{23}=\left(x_3+x_2\right)\ast \left(y_3+y_2\right)$ ，

$p_{24}=\left(x_4+x_2\right)\ast \left(y_4+y_2\right);p_{34}=\left(x_4+x_3\right)\ast \left(y_4+y_3\right)$ ；

4) $P=x_4\ast y_4{2}^{8N}$

$+\left(x_4\ast y_3+x_3\ast y_4\right)2^{7N}$

$+\left(x_4\ast y_2+x_3\ast y_3+x_2\ast y_4\right)2^{6N}$

$+\left(x_4\ast y_1+x_3\ast y_2+x_2\ast y_3+x_1\ast y_4\right)2^{5N}$

$+\left(x_4\ast y_0+x_3\ast y_1+x_2\ast y_2+x_1\ast y_3+x_0\ast y_4\right)2^{4N}$

$+\left(x_3\ast y_0+x_2\ast y_1+x_1\ast y_2+x_0\ast y_3\right)2^{3N}$

$+\left(x_2\ast y_0+x_1\ast y_1+x_0\ast y_2\right)2^{2N}$

$+\left(x_1\ast y_0+x_0\ast y_1\right)2^N$

$+x_0\ast y_0$

$=p_4{2}^{8N}$

$+\left(p_{34}-p_3-p_4\right)2^{7N}$

$+\left(p_{24}+p_3-p_2-p_4\right)2^{6N}$

$+\left(p_{23}+p_{14}-p_1-p_2-p_3-p_4\right)2^{5N}$

$+\left(p_{13}+p_{04}+p_2-p_0-p_1-p_3-p_4\right)2^{4N}$

$+\left(p_{12}+p_{03}-p_0-p_1-p_2-p_3\right)2^{3N}$

$+\left(p_{02}+p_1-p_0-p_2\right)2^{2N}$

$+\left(p_{01}-p_0-p_1\right)2^N$

$+p_0$ 。

3.1.2. 快速模约减

乘法运算得到512 bit的乘积后，需要约减为0~P₂₅₆。为了保证SM2运算性能，本文采用针对SM2模P₂₅₆的快速模约减方法，如算法3所示。

算法3 快速模约减

输入 $a,P_{256}$ //a 512 bit，P₂₅₆ 256 bit

输出 $r=a\text{mod}{P}_{256}$ //r 256 bit

1) ai均为32 bit

2) $S_1=\left(\text{a07||a06||a05||a04||a03||a02||a01||a00}\right)$

3) $S_2=\left(\text{a15||a14||a13||a12||a11||0||a09||a08}\right)$

4) $S_3=\left(\text{a14||0||a15||a14||a13||0||a14||a13}\right)$

5) $S_4=\left(\text{a13||0||0||0||0||0||a15||a14}\right)$

6) $S_5=\left(\text{a12||0||0||0||0||0||0||a15}\right)$

7) $S_6=\left(\text{a11||a11||a10||a15||a14||0||a13||a12}\right)$

8) $S_7=\left(\text{a10||a15||a14||a13||a12||0||a11||a10}\right)$

9) $S_8=\left(\text{a09||0||0||a09||a08||0||a10||a09}\right)$

10) $S_9=\left(\text{a08||0||0||0||a15||0||a12||a11}\right)$

11) $S_{10}=\left(\text{a15||0||0||0||0||0||0||0}\right)$

12) $S_{11}=\left(\text{0||0||0||0||0||a14||0||0}\right)$

13) $S_{12}=\left(\text{0||0||0||0||0||a13||0||0}\right)$

14) $S_{13}=\left(\text{0||0||0||0||0||a09||0||0}\right)$

15) $S_{14}=\left(\text{0||0||0||0||0||a08||0||0}\right)$

16) $r=\left(S_1+S_2+S_3+S_4+S_5+S_6\right)$

$+2\left(S_7+S_8+S_{\text{9}}+S_{\text{10}}\right)$

$-\left(S_{11}+S_{12}+S_{13}+S_{14}\right)$

对特定的伪梅森素数简化，只需要一个时钟周期的组合逻辑运算即可完成512 bit数据的快速模约减运算。

为了提高模乘计算性能，在第1个时钟周期计算乘法后将512位乘积寄存，第2个时钟周期直接进行模约减，所以模乘可以采用流水线技术提高计算效率。

3.2. 点运算优化

对于点运算，本文采用并行化和流水线等技术进行优化提高性能，并行表现为1M + 1AS架构，即一路M (模乘法器)和一路AS (模加、减法器)，其中模乘法器需要两个时钟周期，采取流水线方式计算，预计算 $T_0=4b$ ，则倍点、点加计算流程 [7] 如表1、表2所示。

Table 1. The process of point doubling

表1. 倍点运算流程

Table 2. The process of point addition

表2. 点加运算流程

(a)(b)

Figure 2. Point Doubling and Point Addition timing sequence. (a) Point doublingtiming sequence; (b) point addition timing sequence

图2. 点加和倍点计算时序。(a) 倍点计算时序；(b) 点加计算时序

由于采用并行化和流水线技术，倍点和点加均只需要11个步骤完成点计算，即12个时钟周期得到计算结果。由于倍点计算次数相比较多，因此考虑在倍点和点加计算的第12个时钟周期进行预计算①、②，在连续倍点计算时可减少到11个时钟周期，具体计算时序如图2所示。

3.3. 群运算(点乘)优化

对于一个二进制序列，汉明重量(Hamming Weight)是指非零位的个数。在椭圆曲线点乘运算中，倍点运算次数难以减少，对点乘运算的速度优化主要是降低二进制随机数k的汉明重量，即减少点加的运算次数。对于256位二进制随机数k，传统的Double-and-Add算法(倍点–点加算法)汉明密度为128，即需要128次点加运算。

为了提升点乘计算效率，本文采用窗口 $w=4$ 的固定窗口算法。固定窗口算法利用窗口表预先计算出窗口内的点乘结果，在计算过程中能够将汉明密度降低至64，点加运算次数降低了50%，提高了计算速度。固定窗口点乘算法如下所示：

算法4 固定窗口点乘

输入 $k,n,G\left(x,y\right)$ //k, n256bit, n为曲线的阶

输出 $Q=kG$

1) $l=\lceil 256/4\rceil$ ；

2) $k$ 按窗口分组 $k_4\left[l\right],k_4\left[l-1\right],\cdots ,k_4\left[0\right]$ ；

3) 预计算 $2G,3G,4G,\cdots ,15G$ ；

4) $Q=\left(k_4\left[l\right]\right)G$ ；

5) for i from l-1 to 0: // $k_4\left[i\right]\in \left(0~15\right)$

5.1 $Q=2^{4}Q$ ; //四次倍点计算

5.2 if ( $k_4\left[i\right]\ne 0$ ):

$Q=Q+\left(k_4\left[i\right]\right)G$ ;//点加计算

5.3 if ( $Q=\infty$ ): //出现无穷远点

5.3.1 $Q=\left(k_4\left[i-1\right]\right)G$ ;

5.3.2 $i=i-1$ ；

6) 返回 $Q=kG$ 。

算法4中，为了避免无穷远点出现，步骤5.3在计算结束进行点的验证。

4. 实现结果与对比

为了验证前文所述的SM2点乘结构，本文采用Xilinx Vivado 18.3开发平台进行设计和仿真，并在高性价比的ZYNQ7020平台对256位素域SM2点乘进行了功能和性能测试验证。

4.1. 大数乘法器优化对比

表3显示了本文所提出设计的乘法器优化前后性能对比结果。256 bit大数乘法器优化前单周期内计算相对较少，乘法器最大时钟频率较高。但由于需要进行两次KO乘法，且需要分别用64位和128位乘法器分别修正得到65位和129位乘法器结果，因此计算时间较长，LUT资源消耗较高。

优化后LUT资源消耗有所减少，DSP资源不变，计算时间减少，且由于只需要1个时钟周期，更方便上层点运算采用流水线调度。

Table 3. The multiplier performance comparison before and after optimization

表3. 乘法器优化前后性能对比

4.2. 点乘设计对比

表4显示了本文提出的点乘设计与其他现有素域P-256的点乘设计结果对比。

Table 4. The result comparison of different point multiplication designs

表4. 不同点乘设计结果对比

文献 [7] 采用Xcku060平台，在单周期内基于64位DSP乘法器完成两级KO分治乘法，采用Montgomery点乘算法并行实现点加和倍点运算，但最大频率较低，且DSP资源消耗过高，不适用于物联网应用中的低成本FPGA平台。

文献 [8] 采用Xc7vx330t平台，基于64位DSP乘法器，应用两级KO分治算法实现大数乘法器，并通过三路MAD (复用的模乘、加减法器)并行加速。

以上工作中均使用了高性能高成本的FPGA平台，本文由于应用于物联网安全场景，在有限域、点和群运算层均对性能和逻辑资源使用率上的权衡和优化，DSP资源使用率占ZYNQ7020的65.5%，点乘计算需要4020个时钟周期，计算时间为136.68 us，比仅文献 [7] 增加24.3%的计算时间，但降低了50%的DSP资源消耗，相比则减少了34.4%的LUT资源，计算时间也减少了38.2%。综合对比各研究，本文在性能和资源消耗均有较大优势，但优化时序仍有提升空间，以获得更高的系统时钟频率。

5. 结语

本文提出了一种对素域SM2点乘算法自下而上分层硬件优化方法，首先针对SM2中调用最多的高性能大数乘法器需求提出了基于DSP乘法器的256 bit乘法算法KO-5，大幅减少乘法计算和乘法器模块的逻辑资源使用率，随后在此基础上采用流水线技术、预计算技术和快速模约减算法，固定窗口算法等优化方法逐层优化。设计实现了一个高性能和低资源消耗的素域SM2点乘模块。经过测试比较，本文相对于同类工作具有更高的性能和较低的资源消耗，可应用于具有较高性能需求的物联网数据加解密、设备身份认证和数据源认证等场景。

NOTES

^*通讯作者。