双线性密码引擎的实现*

2018-09-29王松，张洁

通信技术 2018年9期

王松，张洁

（1.中国电子科技集团公司第三十研究所，四川成都 610041；2.石家庄信息工程职业学院，河北石家庄 050035）

0 引言

为了简化公钥基础设施对用户公钥证书的管理，Shamir在1984年提出了基于身份密码体制的概念，核心思想是利用用户的身份信息作为用户的公钥[1]。在该体制下，用户利用对方的身份信息（如设备ID号、身份证号码、手机号码、邮件地址等）作为公钥来使用，用户无需事先申请证书，也不用查询和验证证书，相比传统的公钥基础设施具有突出的优势。

在2000年左右，密码学家们提出了使用椭圆曲线上的双线性对来设计基于身份加密方案的思路，并且给出了该密码方案的安全性证明，引起了密码学术界的极大反响[2]。此后，采用椭圆曲线上的双线性对来设计标识密码算法，成为密码学术界的研究热点。从2006年起，国家密码管理局组织了密码学领域的相关专家开始进行标识密码算法的研究，并在2016年3月颁布了我国的商用标识密码算法——SM9。标识密码算法发展的时间还不长，主要以软件实现为主。标识密码算法本身较为复杂，在现在大多数嵌入式处理器中的运行性能远远不能满足实际应用需求。在许多嵌入式设备中，可利用FPGA做一些辅助运算。如果能在FPGA中利用较少的资源实现复杂的双线性运算，将大大提高设备的标识算法运算性能。本文参考当前市场上的密码芯片设计原理[3]，设计了一款适合用于双线性标识密码算法的密码引擎，并完成了SM9算法的双线性运算在该引擎上的实现。最终的测试验证表明，相比嵌入式处理器，该密码引擎能有效实现双线性密码运算的加速。

1 SM9密码算法

1.1 SM9密码算法运算层次

在SM9标识密码算法的第5部分参数定义中规定，SM9标识密码发的曲线参数是基于BN曲线上R-ate对的，其椭圆曲线方程式为y2=x3+b。群G1和群G2分别在常曲线和参数为的扭曲线上。所有的运算都在素域上进行，数学运算层次可以分为基础运算层、曲线运算层、塔式扩张层、群运算层、双线性运算层和应用层。各个层次之间的关系如图1所示。

图1 标识密码算法运算层次

基础运算层在素域上进行，包括模加法运算、模减法运算、模逆运算、模乘运算、数据比较、数据比特移位等基础操作。曲线运算层包括常曲线和扭曲线的点加、倍点等运算。群运算层主要是指常曲线和扭曲线上的标量乘法。很多标识密码算法（如SM9等）的双线性运算在扩域中进行，塔式扩张层的作用是将扩域中的元素用基域中的元素进行表示和计算。双线性运算层通过调用底层的数学运算实现双线性对的运算。本文实现的双线性层运算是基于BN曲线上R-ate对。应用层一般是指密钥协商、签名验签和加解密等上层应用。

本文设计的双线性密码引擎设计定位是实现应用层以下的所有运算层。应用层以下的群运算层、双线性运算层等占用了标识密码算法的绝大部分运算时间。对该部分运算的加速能较好地提高标识密码的运算性能。

标识密码算法的应用层运算在整个算法中的运算开销不多。但是，不同的算法在这个层次的设计都有自己的特点，组织较为灵活。如果在密码引擎中实现应用层的运算，需要较多的硬件资源来实现这些处理模块，但对整个算法的性能并不能带来比较明显的提升。这种情况和ECC算法比较类似。国内绝大多数椭圆曲线密码芯片也仅实现了群运算层及以下的运算处理。

标识密码算法的应用层可在调用密码引擎的处理器中实现，达到标识密码算法性能加速的目的，如图2所示。

图2 标识密码算法实现方式

1.2 基础运算层

基础运算层是实现标识密码算法的基础。密码算法在运行过程中需要反复调用基础运算层的运算。基础运算层的运算性能对整个算法的性能影响较大，设计时需要尽量优化其性能。基础运算层的运算主要有素数域和二进制域两种。因为SM9算法规定的曲线参数定义在素域上，所以本文设计的双线性密码引擎的基础运算是基于素域的。

素域中的基础运算层运算是基于素数进行的。基础运算的结果需要对该素数求模。例如，数据d1、d2基于P的模乘法运算，是将两个数先做乘法，再将乘法结果对素数P进行求模。

在基础运算层中，模加法运算、模减法运算、模乘运算、数据比较、数据比特移位等基础操作采用硬件逻辑实现。其中，模乘运算较为复杂，如果直接实现该运算需要较多的硬件资源开销，且运算速度很慢。通常情况下，非对称密码算法中的模乘运算都转换到了蒙哥马利域中进行[4]，故双线性密码引擎中的模乘模块完成的是蒙哥马利模乘。模逆运算在整个标识密码算法中调用次数比其他基础运算模块要少得多，且其计算较为复杂，模逆运算的实现需要消耗大量的硬件资源，但对整个算法的性能提升影响不大。综上所述，模逆运算采用编程的方式调用其他基础运算模块实现。

1.3 曲线运算层

因为SM9算法的曲线有常曲线和扭曲线两种。曲线运算层的运算包括两种曲线的点加、倍点、无穷远点判断及处理等运算。扭曲线与常曲线的点加和倍点运算基于相同的运算步骤，区别在于二者所属的群不同。一般来讲，扭曲线的运算性能是常曲线的1/4左右。该层运算通过在密码引擎中编程的方式调用基础运算层的基础运算单元来实现。

1.4 塔式扩张层

塔式扩张运算是双线性运算的基础，SM9算法规定的曲线参数中嵌入次数等于12。Fq12可以按照1→2→4→12的方式进行扩张。下面以1→2为例，说明扩域中的运算规则。

Fq2[u]=Fq[u]/(u-a)，a=-2。定义两个Fq2中的元素A=(a0,a1)，B=(b0,b1)。Fq2上的模加法和模减法是对应维度上的数据进行模加运算和模减运算，即X+Y=(a0+b0,a1+b1)，X-Y=(a0-b0,a1-b1)。模乘法需要将多项式乘法的结果进行求模，X*Y在Fq2中的模乘结果为：X*Y=(a0*b1+a1*b0,a1*b1-2a0*b0)。

1.5 群运算层

群运算层实现常曲线和扭曲线的标量乘法运算，已经有比较成熟的方法。本设计中，为了节约硬件资源的开销，密码引擎模块仅支持二进制方法的标量乘法运算。群运算层的实现通过在密码引擎中编程的调用曲线层运算来实现。

1.6 双线性运算层

SM9算法双线性运算层的实现参考SM9标识密码算法第一部分中BN曲线上R-ate对计算给出的计算步骤来实现。在双线性对计算过程中，会使用Miller算法[5]。Miller算法是一种计算双线性对的有效算法，在SM9标识密码算法第一部分的附录B中有完整的表述。

2 双线性密码引擎设计

双线性密码引擎的的内部功能逻辑，如图3所示。

图3 双线性密码引擎内部功能逻辑

双线性密码引擎由密码引擎核、接口数据存储器、程序存储器、临时数据存储器、总线控制器以及基础运算层的硬件运算单元组成。

2.1 存储器

在双线性密码引擎内部包括三个存储器单元，分别是接口数据存储器、临时数据存储器和程序存储器。接口数据存储器主要用于配合接口总线完成与外部控制芯片的信息交换。临时数据存储器用于存放程序运行过程中的所有临时数据，以及一些程序的运行状态和堆栈信息等。程序存储器用于存储密码引擎运行的程序。为了保证程序存储器不会因为意外事件被破坏，程序存储器的外部设置了一个保护电路，用户需要更新程序存储器中的数据时，必须先配置对应的寄存器，才能完成程序存储器的写操作。

2.2 密码引擎核

密码引擎核是双线性密码引擎的核心单元。密码引擎核负责整个密码引擎的调度和控制。当外部控制芯片通过接口存储器和接口总线发起运算指令时，密码引擎立即将接收到的数据读入临时数据存储区，并根据程序存储器的程序对数据进行处理。为了更好地实现算法加速，双线性密码引擎在工作室采用取指、译码、执行的流水线操作。密码引擎核访问临时数据存储器和调用基础运算层的运算单元都是通过总线控制器进行的。当程序执行完成，密码引擎核将得到的运算结果从临时存储器读出，并写入接口数据存储器，然后将运算完成信息通过接口总线通知外部控制芯片。

2.3 基础运算模块

双线性密码引擎中，基础运算层的硬件模块负责完成一些底层的数学运算，如蒙哥马利模乘、模加减法和比特移位操作等。基础运算层的硬件模块通过总线控制器来完成临时数据存储器中的数据读写操作。

2.4 总线控制器

总线控制器是整个密码引擎的关键部分。该模块根据密码引擎核的指令进行整个密码引擎芯片的数据总线切换，完成数据流的控制。如果需要进行蒙哥马利模乘运算时，总线控制器必须及时将模乘模块和临时数据存储器模块的数据访问通道连接，同时断开其他模块与临时数据存储器的连接。在需要输出运算结果时，总线控制器又将根据密码引擎核送出的指令，将临时数据存储器中对应地址的数据写入接口数据存储器的对应地址中。