摘要：

国密SM9算法是基于双线性对的标识密码算法，其运行过程需进行多次十二次扩域的高次幂运算，其计算性能对SM9算法体制的应用至关重要。SM9签名运算中的高次幂可以预存点，在运算过程中通过查表减少运算时间。由于验签运算中高次幂的底数不确定，无法通过查表进行运算，因此分别使用Comb固定基和NAF算法在算法模型上降低高次幂中十二次扩域乘法运算量。为提高十二次扩域乘法的计算效率，根据R-ate对的特殊性质提出基于分圆子群的快速平方算法，降低扩域乘法所需的基域运算开销，并将其应用于高次幂的运算中。硬件架构创新性地采用基于自定义RISC指令集的ASIP微码控制方式实现，该架构的灵活性有利于在有限的硬件资源下实现复杂的SM9算法逻辑，其中可修改的指令集可以更好地与底层硬件适配。在Xilinx Artix-7系列的FPGA平台上的实验结果表明，在167 MHz的时钟频率条件下，不增加额外的硬件资源开销，该方法完成一次SM9签名的时间仅为0.244 ms。

关键词: SM9算法, 高次幂, R-ate对, 分圆子群, Comb固定基, NAF算法

Abstract:

The SM9 algorithm is an identification cipher algorithm based on bilinear pairs. The operation process requires multiple higher power operations of twelve domain expansions, and its computing performance is crucial to the application of the SM9 algorithm system. In SM9, the higher power of the signature operation can be stored in the point. The operation time is reduced by looking up the table in the operation process. The base number of the higher power in signature verification operation is uncertain and cannot be stored by looking up the table. The Comb fixed basis and NAF algorithm are used respectively to reduce the amount of multiplication of twelve times the higher power in the algorithm model. To further improve the calculation efficiency of the multiplication of the twelve degree extension field, this study proposes a fast square algorithm based on cyclotomic subgroups according to the special properties of R-ate pairs, which reduces the overhead base field operation required by the extension field multiplication and is applied to the operation of higher powers. The hardware architecture innovatively adopts the ASIP microcode control mode based on the customized RISC instruction set. The flexibility provided by the architecture is conducive to the implementation of the complex SM9 algorithm logic under limited hardware resources. The modifiable instruction set can also be adapted to the underlying hardware. The experimental results on the FPGA platform of the Xilinx Artix-7 series show that under the condition of the 167 MHz clock frequency, without additional hardware resource overhead, the time to complete an SM9 signature is only 0.244 ms.

Key words: SM9 algorithm, higher power, R-ate pairing, cyclotomic subgroup, Comb fixed-base, NAF algorithm