一種改進(jìn)的模逆算法與硬件實(shí)現(xiàn)

胡錦 李勇彬

摘要：在公鑰密碼體系中，無(wú)論是RSA密碼還是橢圓曲線密碼，模逆運(yùn)算都是非常關(guān)鍵的運(yùn)算.模逆運(yùn)算的前提是兩數(shù)的最大公約數(shù)為1，否則結(jié)果是沒(méi)有意義的.基于現(xiàn)有的二進(jìn)制模逆算法的基礎(chǔ)上提出了一種可以同時(shí)求最大公約數(shù)和進(jìn)行模逆運(yùn)算的算法，并且對(duì)算法進(jìn)行優(yōu)化，用VERILOGHDL語(yǔ)言進(jìn)行硬件實(shí)現(xiàn).通過(guò)功能仿真和FPGA驗(yàn)證，結(jié)果表明該設(shè)計(jì)可以正確進(jìn)行32～1024bit的大數(shù)模逆運(yùn)算.該設(shè)計(jì)應(yīng)用于一款汽車(chē)安全芯片的PKI模塊，采用UMC55nm工藝進(jìn)行流片，芯片面積為10mm2，工作電壓3.3V，鐘頻率為200MHz時(shí)，功耗約為30.2mW.

關(guān)鍵詞：RSA密碼;橢圓曲線密碼;公鑰密碼;模逆;最大公約數(shù)

中圖分類(lèi)號(hào)：TN492

文獻(xiàn)標(biāo)志碼：A

RSA密碼和橢圓曲線密碼是目前使用最廣泛的公鑰密碼算法.隨著物聯(lián)網(wǎng)的發(fā)展，用戶(hù)信息安全越來(lái)越重要，例如現(xiàn)今高速發(fā)展的智能汽車(chē)，安全性和實(shí)時(shí)性要求極高，軟件實(shí)現(xiàn)加密算法的方式已經(jīng)無(wú)法滿(mǎn)足需求，采用硬件方式實(shí)現(xiàn)算法是發(fā)展的趨勢(shì).模逆算法是公鑰密碼體系中的核心算法[1-2]，尤其在橢圓曲線密碼體系中[3]，也是最復(fù)雜[4]和最消耗時(shí)間的算法之一[5].在RSA密碼算法中，生成密鑰對(duì)時(shí)，需要計(jì)算d=e-1modφ，其中e表示公鑰，滿(mǎn)足1<e<φ且gcd（e，φ）=1，φ表示歐拉函數(shù)，d表示私鑰.為了安全，φ至少為1024位，用軟件實(shí)現(xiàn)模逆運(yùn)算，運(yùn)算量大，運(yùn)算時(shí)間長(zhǎng)，效率低[6].在橢圓曲線密碼算法中，進(jìn)行點(diǎn)加[7]、點(diǎn)乘和倍點(diǎn)運(yùn)算時(shí)，用雅可比坐標(biāo)進(jìn)行坐標(biāo)變換[8]也只能減少模逆運(yùn)算使用的次數(shù)而不能完全避免.本文在現(xiàn)有的二進(jìn)制模逆算法基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種在求逆過(guò)程中同時(shí)可以求取最大公約數(shù)的算法.此外，出于對(duì)實(shí)現(xiàn)算法的硬件資源考慮，對(duì)算法做了優(yōu)化，最后通過(guò)VERILOG語(yǔ)言進(jìn)行硬件實(shí)現(xiàn).

1算法介紹

1.1二進(jìn)制模逆算法

二進(jìn)制模逆算法原理是根據(jù)貝祖等式gcd（a，b）=gcd（b-a，a）=ax+by推導(dǎo)得出.目前常用的模逆算法還有擴(kuò)展歐幾里得算法[9-10]，但是由于算法中每步都要用到除法操作，開(kāi)銷(xiāo)很大[11]，尤其在進(jìn)行大素?cái)?shù)模逆運(yùn)算時(shí)缺點(diǎn)更突出.算法1只用到了移位操作和減法運(yùn)算，比擴(kuò)展歐幾里得算法更加高效.

算法1二進(jìn)制模逆算法輸入：素?cái)?shù)p和a∈[1，p]輸出：a-1modp1，u←a，v←p.2，x1←1，x2←0.

3，當(dāng)u=?1和v=?1時(shí)，重復(fù)執(zhí)行3.1當(dāng)u是偶數(shù)時(shí)，重復(fù)執(zhí)行u←u/2.

若x1是偶數(shù)，則x1←x1/2，否則，x1←（x1+p）/2.

3.2當(dāng)v是偶數(shù)時(shí)，重復(fù)執(zhí)行v←v/2.

若x2是偶數(shù)，則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改進(jìn)的模逆算法

算法1有一個(gè)缺陷是無(wú)法判定輸入的兩數(shù)是否互質(zhì)，如果gcd（a，p）不等于1時(shí)，再用算法1計(jì)算就會(huì)得到錯(cuò)誤的結(jié)果，或者說(shuō)算出的結(jié)果是沒(méi)有意義的.結(jié)合stein算法[11]，可以將上述算法改寫(xiě)為算法2，算法2在模逆運(yùn)算的同時(shí)可以求解最大公約數(shù)gcd（a，p），從而保證模逆運(yùn)算的結(jié)果是在gcd（a，p）=1的情況下得到的正確結(jié)果.在算法1中可以看出，循環(huán)計(jì)算時(shí)u和v的計(jì)算基本上是一致的，為了節(jié)省資源，可以進(jìn)行進(jìn)一步優(yōu)化.由于算法2中的步驟3和步驟5.2保證u和v每次循環(huán)最多只有一個(gè)為偶數(shù)，利用這個(gè)特點(diǎn)可以去掉u的循環(huán).

算法2改進(jìn)的模逆算法輸入：正整數(shù)a和p輸出：a-1modp和gcd（a，p）1，x←a，y←p.

2，g←1.

3，當(dāng)x和y都為偶數(shù)，重復(fù)執(zhí)行：x←x/2，y←y/2，g←2g.

4，當(dāng)x為偶數(shù)時(shí)，執(zhí)行：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，當(dāng)v=?0，重復(fù)執(zhí)行：

5.1當(dāng)v是偶數(shù)時(shí)，重復(fù)執(zhí)行v←v/2.

如果C和D都是偶數(shù)，執(zhí)行C←C/2，D←D/2.

否則：

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

5.2當(dāng)u≥v時(shí)，執(zhí)行

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，計(jì)算gcd（a，p）=u*g.

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

2算法硬件結(jié)構(gòu)框圖

模逆算法主要通過(guò)狀態(tài)機(jī)來(lái)控制算法流程，通過(guò)ram存儲(chǔ)大量的中間數(shù)據(jù)，圖1是模逆算法硬件結(jié)構(gòu)框圖，主要分為兩個(gè)模塊，INV_FSM模塊是狀態(tài)機(jī)模塊，INV_CAL是模逆算法的運(yùn)算模塊，受狀態(tài)機(jī)模塊的調(diào)度.ram為偽雙端口ram，主要用來(lái)存儲(chǔ)在運(yùn)算過(guò)程中產(chǎn)生的中間數(shù)據(jù)和運(yùn)算結(jié)果.

2.1算法狀態(tài)機(jī)圖2是模逆算法的狀態(tài)轉(zhuǎn)移圖，嚴(yán)格控制模逆算法的運(yùn)算流程.該狀態(tài)機(jī)共有9個(gè)狀態(tài)，IDLE是空閑狀態(tài)，開(kāi)始運(yùn)算時(shí)，進(jìn)入SHIFT狀態(tài)，SHIFT狀態(tài)完成x和y同時(shí)向右移位（即除以2），g向左移位，直到x和y不同時(shí)為偶數(shù).LOAD狀態(tài)主要完成u、v、A、B、C、D數(shù)據(jù)的裝載.INV_CAL狀態(tài)完成模逆算法的主體運(yùn)算直到v等于0時(shí)才跳出該狀態(tài).在GCD_CAL狀態(tài)中完成gcd（a，p）計(jì)算，在GCD_CAL狀態(tài)計(jì)算完成后判斷A的極性進(jìn)行狀態(tài)跳轉(zhuǎn).若A為負(fù)數(shù)，則跳轉(zhuǎn)到A_NEG狀態(tài)進(jìn)行A+y運(yùn)算，直到A為正數(shù)，則跳轉(zhuǎn)到DONE狀態(tài);若A為正數(shù)，則跳轉(zhuǎn)到A_POS1狀態(tài)進(jìn)一步判斷A是否大于y，若A小于y，則跳轉(zhuǎn)到DONE狀態(tài)，若A大于y則跳轉(zhuǎn)到A_POS2狀態(tài)進(jìn)行A-y運(yùn)算，直到A小于y，然后跳轉(zhuǎn)到DONE狀態(tài)，模逆運(yùn)算完成，最終回到IDLE狀態(tài).

2.2算法運(yùn)算模塊

算法運(yùn)算模塊主要功能是在狀態(tài)機(jī)的控制下進(jìn)行數(shù)據(jù)的運(yùn)算.從算法2中可以看出，求逆的過(guò)程需要用到大數(shù)加法和大數(shù)減法，還需要進(jìn)行兩數(shù)大小判斷和移位.大數(shù)加法和大數(shù)減法可以通過(guò)算法3和算法4實(shí)現(xiàn)，兩數(shù)的大小比較可以通過(guò)使用大數(shù)減法的借位信號(hào)來(lái)判斷.圖3是運(yùn)算模塊主要運(yùn)算電路，data_v和data_u通過(guò)mux來(lái)進(jìn)行選擇，mux的選擇信號(hào)通過(guò)比較data_u和data_v的大小得到，data_c和data_a、data_b和data_d類(lèi)似.從圖3中可以看出：改進(jìn)后的算法使用mux可以進(jìn)行u和v的選擇，從而實(shí)現(xiàn)資源的復(fù)用，減少了資源的消耗.運(yùn)算的中間結(jié)果和運(yùn)算結(jié)果保存在ram中.

該電路中輸入數(shù)據(jù)都是以32位為最小輸入單元，如果進(jìn)行1024位的模逆運(yùn)算，此電路需要計(jì)算32次，可以看出此電路其實(shí)還可以實(shí)現(xiàn)2048位甚至更大的模逆運(yùn)算.需要注意的是.計(jì)算的位寬越大，需要保存的中間數(shù)據(jù)也越多，ram的容量就需要越大.

算法3大數(shù)加法算法輸入：整數(shù)A=（ak-1，ak-2，...，a0）2

整數(shù)B=（bk-1，bk-2，...，b0）232

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

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

2，對(duì)于i從1到k-1，重復(fù)執(zhí)行2.1{c，s}i=ai+bi+c.3，返回（c，s）.

算法4大數(shù)減法算法輸入：整數(shù)A=（ak-1，ak-2，...，a0）2

整數(shù)B=（bk-1，bk-2，...，b0）232

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

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

2，對(duì)于i從1到k-1，重復(fù)執(zhí)行2.1{c，s}i=ai-bi-c.3，返回（c，s）.

3結(jié)果與分析

通過(guò)VCS對(duì)該電路進(jìn)行功能仿真，如圖4所示.模逆算法電路能正確計(jì)算出最大公約數(shù)和模逆運(yùn)算的結(jié)果，將計(jì)算的結(jié)果保存在ram中.仿真結(jié)果表明：該設(shè)計(jì)可以正確進(jìn)行32～1024bit的模逆運(yùn)算.

使用Xilinxvirtex-IIFPGA開(kāi)發(fā)板進(jìn)行了板級(jí)驗(yàn)證，驗(yàn)證了該設(shè)計(jì)的正確性.表1列出了該設(shè)計(jì)與同類(lèi)設(shè)計(jì)的資源消耗和性能比較.表格中的時(shí)間為計(jì)算256bit模逆運(yùn)算使用的時(shí)間.

該設(shè)計(jì)應(yīng)用于一款汽車(chē)安全芯片的PKI模塊，用于實(shí)現(xiàn)RSA和SM2算法.圖5為該安全芯片的版圖，采用UMC55nm工藝進(jìn)行流片，該芯片總面積為10mm2，在工作電壓3.3V，時(shí)鐘頻率為200MHz時(shí)，功耗僅為30.2mW，流片測(cè)試結(jié)果表明，芯片達(dá)到設(shè)計(jì)指標(biāo)要求.

本文提出了一種在現(xiàn)有二進(jìn)制模逆算法的基礎(chǔ)上進(jìn)行改進(jìn)的算法.該算法不僅可以進(jìn)行模逆運(yùn)算，還同時(shí)可以計(jì)算最大公約數(shù)，并且在算法上進(jìn)行了優(yōu)化，減少了算法實(shí)現(xiàn)的資源消耗，最后通過(guò)VERILOG語(yǔ)言實(shí)現(xiàn)了該算法.該設(shè)計(jì)電路結(jié)構(gòu)簡(jiǎn)單，可擴(kuò)展性強(qiáng).最后該設(shè)計(jì)采用UMC55nm工藝進(jìn)行流片，流片測(cè)試結(jié)果表明，芯片達(dá)到設(shè)計(jì)指標(biāo)要求.

參考文獻(xiàn)

[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]譚麗娟，陳運(yùn).模逆算法的分析、改進(jìn)及測(cè)試[J].電子科技大學(xué)學(xué)報(bào)，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(xiàn) r a n c e ：I E E E ，2 0 1 0 ：3 1 3 - 3 1 6 .