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

胡錦，李勇彬

（湖南大學(xué)物理與微電子科學(xué)學(xué)院，湖南長沙 410082）

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

1 算法介紹

1.1 二進制模逆算法

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

1.2 改進的模逆算法

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

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

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

圖1 模逆算法硬件結(jié)構(gòu)框圖Fig.1 Modular inversion algorithm hardware structure block diagram

2.1 算法狀態(tài)機

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

圖2 模逆算法狀態(tài)轉(zhuǎn)移圖Fig.2 State transition diagram of modular inversion algorithm

2.2 算法運算模塊

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

圖3 算法模塊電路圖Fig.3 Algorithm module circuit diagram

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

3 結(jié)果與分析

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

圖4 算法功能仿真圖Fig.4 Algorithm function simulation diagram

使用Xilinx virtex-II FPGA 開發(fā)板進行了板級驗證，驗證了該設(shè)計的正確性.表1 列出了該設(shè)計與同類設(shè)計的資源消耗和性能比較.表格中的時間為計算256 bit模逆運算使用的時間.

表1 FPGA結(jié)果對比Tab.1 FPGA result comparison

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

圖5 芯片版圖Fig.5 Chip layout

4 結(jié)語

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