一种改进的模逆算法与硬件实现

胡锦 李勇彬

摘要：在公钥密码体系中，无论是RSA密码还是椭圆曲线密码，模逆运算都是非常关键的运算.模逆运算的前提是两数的最大公约数为1，否则结果是没有意义的.基于现有的二进制模逆算法的基础上提出了一种可以同时求最大公约数和进行模逆运算的算法，并且对算法进行优化，用VERILOGHDL语言进行硬件实现.通过功能仿真和FPGA验证，结果表明该设计可以正确进行32～1024bit的大数模逆运算.该设计应用于一款汽车安全芯片的PKI模块，采用UMC55nm工艺进行流片，芯片面积为10mm2，工作电压3.3V，钟频率为200MHz时，功耗约为30.2mW.

关键词：RSA密码;椭圆曲线密码;公钥密码;模逆;最大公约数

中图分类号：TN492

文献标志码：A

RSA密码和椭圆曲线密码是目前使用最广泛的公钥密码算法.随着物联网的发展，用户信息安全越来越重要，例如现今高速发展的智能汽车，安全性和实时性要求极高，软件实现加密算法的方式已经无法满足需求，采用硬件方式实现算法是发展的趋势.模逆算法是公钥密码体系中的核心算法[1-2]，尤其在椭圆曲线密码体系中[3]，也是最复杂[4]和最消耗时间的算法之一[5].在RSA密码算法中，生成密钥对时，需要计算d=e-1modφ，其中e表示公钥，满足1<e<φ且gcd（e，φ）=1，φ表示欧拉函数，d表示私钥.为了安全，φ至少为1024位，用软件实现模逆运算，运算量大，运算时间长，效率低[6].在椭圆曲线密码算法中，进行点加[7]、点乘和倍点运算时，用雅可比坐标进行坐标变换[8]也只能减少模逆运算使用的次数而不能完全避免.本文在现有的二进制模逆算法基础上进行了改进，提出了一种在求逆过程中同时可以求取最大公约数的算法.此外，出于对实现算法的硬件资源考虑，对算法做了优化，最后通过VERILOG语言进行硬件实现.

1算法介绍

1.1二进制模逆算法

二进制模逆算法原理是根据贝祖等式gcd（a，b）=gcd（b-a，a）=ax+by推导得出.目前常用的模逆算法还有扩展欧几里得算法[9-10]，但是由于算法中每步都要用到除法操作，开销很大[11]，尤其在进行大素数模逆运算时缺点更突出.算法1只用到了移位操作和减法运算，比扩展歐几里得算法更加高效.

算法1二进制模逆算法输入：素数p和a∈[1，p]输出：a-1modp1，u←a，v←p.2，x1←1，x2←0.

3，当u≠1和v≠1时，重复执行3.1当u是偶数时，重复执行u←u/2.

若x1是偶数，则x1←x1/2，否则，x1←（x1+p）/2.

3.2当v是偶数时，重复执行v←v/2.

若x2是偶数，则x2←x2/2，否则，x2←（x2+p）/2.

3.3若u≥v，则u←u-v，x2←x1-x2，否则v←v-u，x2←x2-x1.

4，若u=1，返回（x1modp），否则，返回（x2modp）.

1.2改进的模逆算法

算法1有一个缺陷是无法判定输入的两数是否互质，如果gcd（a，p）不等于1时，再用算法1计算就会得到错误的结果，或者说算出的结果是没有意义的.结合stein算法[11]，可以将上述算法改写为算法2，算法2在模逆运算的同时可以求解最大公约数gcd（a，p），从而保证模逆运算的结果是在gcd（a，p）=1的情况下得到的正确结果.在算法1中可以看出，循环计算时u和v的计算基本上是一致的，为了节省资源，可以进行进一步优化.由于算法2中的步骤3和步骤5.2保证u和v每次循环最多只有一个为偶数，利用这个特点可以去掉u的循环.

算法2改进的模逆算法输入：正整数a和p输出：a-1modp和gcd（a，p）1，x←a，y←p.

2，g←1.

3，当x和y都为偶数，重复执行：x←x/2，y←y/2，g←2g.

4，当x为偶数时，执行：u←y，v←x，A←0，C←1，B←1，D←0.否则：u←x，v←y，A←1，C←0，B←0，D←1.5，当v≠0，重复执行：

5.1当v是偶数时，重复执行v←v/2.

如果C和D都是偶数，执行C←C/2，D←D/2.

否则：

C←（C+y）/2，D←（D-x）/2.

5.2当u≥v时，执行

u←v，v←u-v;A←C，C←A-C，B←D，D←B-D.否则：

v←v-u，C←C-A，D←D-B.

6，计算gcd（a，p）=u*g.

7，返回（Amody）和gcd（a，p）.

2算法硬件结构框图

模逆算法主要通过状态机来控制算法流程，通过ram存储大量的中间数据，图1是模逆算法硬件结构框图，主要分为两个模块，INV_FSM模块是状态机模块，INV_CAL是模逆算法的运算模块，受状态机模块的调度.ram为伪双端口ram，主要用来存储在运算过程中产生的中间数据和运算结果.

2.1算法状态机图2是模逆算法的状态转移图，严格控制模逆算法的运算流程.该状态机共有9个状态，IDLE是空闲状态，开始运算时，进入SHIFT状态，SHIFT状态完成x和y同时向右移位（即除以2），g向左移位，直到x和y不同时为偶数.LOAD状态主要完成u、v、A、B、C、D数据的装载.INV_CAL状态完成模逆算法的主体运算直到v等于0时才跳出该状态.在GCD_CAL状态中完成gcd（a，p）计算，在GCD_CAL状态计算完成后判断A的极性进行状态跳转.若A为负数，则跳转到A_NEG状态进行A+y运算，直到A为正数，则跳转到DONE状态;若A为正数，则跳转到A_POS1状态进一步判断A是否大于y，若A小于y，则跳转到DONE状态，若A大于y则跳转到A_POS2状态进行A-y运算，直到A小于y，然后跳转到DONE状态，模逆运算完成，最终回到IDLE状态.

2.2算法运算模块

算法运算模块主要功能是在状态机的控制下进行数据的运算.从算法2中可以看出，求逆的過程需要用到大数加法和大数减法，还需要进行两数大小判断和移位.大数加法和大数减法可以通过算法3和算法4实现，两数的大小比较可以通过使用大数减法的借位信号来判断.图3是运算模块主要运算电路，data_v和data_u通过mux来进行选择，mux的选择信号通过比较data_u和data_v的大小得到，data_c和data_a、data_b和data_d类似.从图3中可以看出：改进后的算法使用mux可以进行u和v的选择，从而实现资源的复用，减少了资源的消耗.运算的中间结果和运算结果保存在ram中.

该电路中输入数据都是以32位为最小输入单元，如果进行1024位的模逆运算，此电路需要计算32次，可以看出此电路其实还可以实现2048位甚至更大的模逆运算.需要注意的是.计算的位宽越大，需要保存的中间数据也越多，ram的容量就需要越大.

算法3大数加法算法输入：整数A=（ak-1，ak-2，...，a0）2

整数B=（bk-1，bk-2，...，b0）232

输出：{c，s}=A+B.

1，{c，s0}=a0+b0.

2，对于i从1到k-1，重复执行2.1{c，s}i=ai+bi+c.3，返回（c，s）.

算法4大数减法算法输入：整数A=（ak-1，ak-2，...，a0）2

整数B=（bk-1，bk-2，...，b0）232

输出：{c，s}=A-B.

1，{c，s0}=a0-b0.

2，对于i从1到k-1，重复执行2.1{c，s}i=ai-bi-c.3，返回（c，s）.

3结果与分析

通过VCS对该电路进行功能仿真，如图4所示.模逆算法电路能正确计算出最大公约数和模逆运算的结果，将计算的结果保存在ram中.仿真结果表明：该设计可以正确进行32～1024bit的模逆运算.

使用Xilinxvirtex-IIFPGA开发板进行了板级验证，验证了该设计的正确性.表1列出了该设计与同类设计的资源消耗和性能比较.表格中的时间为计算256bit模逆运算使用的时间.

该设计应用于一款汽车安全芯片的PKI模块，用于实现RSA和SM2算法.图5为该安全芯片的版图，采用UMC55nm工艺进行流片，该芯片总面积为10mm2，在工作电压3.3V，时钟频率为200MHz时，功耗仅为30.2mW，流片测试结果表明，芯片达到设计指标要求.

本文提出了一种在现有二进制模逆算法的基础上进行改进的算法.该算法不仅可以进行模逆运算，还同时可以计算最大公约数，并且在算法上进行了优化，减少了算法实现的资源消耗，最后通过VERILOG语言实现了该算法.该设计电路结构简单，可扩展性强.最后该设计采用UMC55nm工艺进行流片，流片测试结果表明，芯片达到设计指标要求.

参考文献

[1] CHEN C P，QIN Z P.Fast algorithm and hardware architecture for modular inversion in GF（p）[C]//2009 Second International Conference on Intelligent Networks and Intelligent Systems.Tian⁃j i a n ，C h i n a ：I E E E ，2 0 0 9 ：4 3 - 4 5 .

[2] WANG J，JIANG A P.An area-efficient design for modular inver⁃sion in GF（2m）[C]//APCCAS 2006 - 2006 IEEE Asia Pacific Conference on Circuits and Systems. Singapore：IEEE，2006： 1496-1499.

[3] XU S，GU H H，WANG L Y，et al.Efficient and constant time modular inversions over prime fields[C]//2017 13th International Conference on Computational Intelligence and Security（CIS）. Hong Kong，China：IEEE，2017：524-528.

[4] LIN S Y，HE S，GUO X，et al.An efficient algorithm for comput⁃ing modular division over GF（2m）in elliptic curve cryptography [C]//2017 11th IEEE International Conference on Anti- counterfeiting，Security，and Identification （ASID）. Xiamen， C h i n a ：I E E E ，2 0 1 7 ：1 7 9 - 1 8 2 .

[5] TIAN C L，YU J，ZHANG H L，et al.Novel secure outsourcing of modular inversion for arbitrary and variable modulus[J].IEEE Transactions on Services Computing，2019：1-1.

[6] CHOI P，KONG J T，KIM D K.Analysis of hardware modular in⁃version modules for elliptic curve cryptography[C]//2015 Interna⁃tional SoC Design Conference （ISOCC） . Gyeongju，Korea （ S o u t h ）：I E E E ，2 0 1 5 ：3 1 3 - 3 1 4 .

[7] MRABET A，EL-MRABET N，BOUALLEGUE B，et al.An effi⁃cient and scalable modular inversion/division for public key crypto⁃systems[C]//2017 International Conference on Engineering & MIS （ I C E M I S ）. M o n a s t i r ，T u n i s i a ：I E E E ，2 0 1 7 ：1 - 6 .

[8] RAHMAN M S，HOSSAIN M S，RAHAT E H，et al. Efficient hardware implementation of 256-bit ECC processor over prime field[C]//2019 International Conference on Electrical，Computer and Communication Engineering （ECCE）. Cox′sBazar，Bangla?d e s h ：I E E E ，2 0 1 9 ：1 - 6 .

[9] FU B W.A rapid algorithm and its implementation for modular inversion[C]//2009 Fifth International Conference on Information Assurance and Security.Xi′an，China：IEEE，2009：697-700.

[10] PHIAMPHU D，SAHA P. Redesigned the architecture of extended-euclidean algorithm for modular multiplicative inverse and jacobi symbol[C]//2018 2nd International Conference on Trends in Electronics and Informatics（ICOEI）. Tirunelveli，In⁃d i a ：I E E E ，2 0 1 8 ：1 3 4 5 - 1 3 4 9 .

[11]谭丽娟，陈运.模逆算法的分析、改进及测试[J].电子科技大学学报，2004，33（4）：383-386.

[12] HOSSAIN M S，KONG Y N.High-performance FPGA implemen⁃tation of modular inversion over F256 for elliptic curve cryptography [C]//2015 IEEE International Conference on Data Science and Data Intensive Systems. Sydney，NSW，Australia：IEEE，2015： 169-174.

[13] VLIEGEN J，MENTENS N，GENOE J，et al.A compact FPGA- based architecture for elliptic curve cryptography over prime fields [C]//ASAP 2010 - 21st IEEE International Conference on Application-specific Systems， Architectures and Processors. R e n n e s ，F r a n c e ：I E E E ，2 0 1 0 ：3 1 3 - 3 1 6 .