袁仕繼,李博章,孫慧慧,張廣吉
(中國人民解放軍63888部隊(duì),河南 濟(jì)源454650)
大數(shù)模冪運(yùn)算在Diffie-Hellman和RSA系統(tǒng)中得到了廣泛應(yīng)用[1]。所謂模冪運(yùn)算,就是已知大數(shù)a、x、m,求解ax(mod m)。這里的a、x、m一般為幾百比特甚至上千比特的大整數(shù),m一般為素?cái)?shù),因此在此過程中需要做大量的乘法運(yùn)算和模運(yùn)算(即除法運(yùn)算)。在計(jì)算機(jī)運(yùn)行處理過程中,乘法運(yùn)算是很耗時(shí)的運(yùn)算,而除法運(yùn)算更是乘法的幾倍之多。因此,在計(jì)算ax(mod m)的過程中,如何減少乘法,尤其是模運(yùn)算的次數(shù)便成為提高模冪運(yùn)算速度的關(guān)鍵。參考文獻(xiàn)[2]對常用算法進(jìn)行了分析和總結(jié)。
經(jīng)典Montgomery[3]階梯算法是將模運(yùn)算轉(zhuǎn)化為乘法運(yùn)算和移位運(yùn)算,從而避免計(jì)算模運(yùn)算,在RSA[4]和ECC[5]中得到廣泛應(yīng)用。在該算法中執(zhí)行運(yùn)算的次數(shù)等于冪的二元進(jìn)制長度,且平方運(yùn)算是每步都要執(zhí)行,僅當(dāng)冪為1時(shí)才執(zhí)行乘法運(yùn)算[6]。這種在不同步中運(yùn)算數(shù)量的差異導(dǎo)致系統(tǒng)易受邊道攻擊[7]。在Diffie-Hellman和RSA系統(tǒng)中的模冪運(yùn)算中,冪為其密鑰。一個(gè)成功的SCA攻擊可以計(jì)算模冪運(yùn)算的冪,從而導(dǎo)致整個(gè)系統(tǒng)密鑰的丟失。本文利用循環(huán)展開技術(shù),將兩個(gè)循環(huán)同時(shí)進(jìn)行并行處理,提高了運(yùn)算速度和效率。同時(shí),根據(jù)Montgomery階梯算法原理,設(shè)計(jì)了該算法的硬件實(shí)現(xiàn)。
算法1描述的過程即為經(jīng)典Montgomery階梯算法流程。
由該算法可知,將一次平方運(yùn)算認(rèn)為是一次乘法運(yùn)算,可以完成一次求冪運(yùn)算,經(jīng)典MPL算法至少將運(yùn)用2logk次乘法運(yùn)算,而平方乘的平均運(yùn)算量達(dá)到3/2logk。參考文獻(xiàn)[8]指出MPL算法支持并行運(yùn)算,用一個(gè)雙核處理器,在同一時(shí)鐘內(nèi)將乘法運(yùn)算和平方運(yùn)算同時(shí)進(jìn)行,運(yùn)算速度將提高一倍?;谝陨峡紤],本文將設(shè)計(jì)實(shí)現(xiàn)一種經(jīng)典Montgomery階梯算法。
算法1的快速實(shí)現(xiàn)如圖1所示,變量R0和R1分別初始化為1和M,分別存儲在存儲器R0和R1中。設(shè)R0和R1可存儲大數(shù)Mk。指數(shù)k存儲在二進(jìn)制移位寄存器中,該寄存器每次循環(huán)左移一位。算法硬件實(shí)現(xiàn)還包括一個(gè)模乘法器、模平方單元、一個(gè)混合器和一個(gè)2×2正交變換器。
圖1 MPL快速實(shí)現(xiàn)(算法1)
假設(shè)模數(shù)M有m比特,存儲器R0和R1可存儲至少m比特。模乘法器和模平方單元輸入、輸出都為m比特。移位寄存器的輸出值ki決定混合器的輸出,輸出值為混合器輸入兩個(gè)m比特值中的一個(gè)。
圖2是圖1中2×2正交變換器的實(shí)現(xiàn)示意圖。它利用兩個(gè)混合器實(shí)現(xiàn)如下變換:
If E=0,then C=A,D=B
If E=1,then D=A,C=B
圖2 2×2正交變換器
設(shè)計(jì)工作原理如下:首先,將R0和R1分別初始化為1和M。在第j(j=0,1,2,…,n-1)輪循環(huán),指數(shù)中比特kn-1-j是移位寄存器最左邊的比特,由它控制混合器運(yùn)算和2×2正交變換。如果kn-1-j=0,則由R0輸出R0,并作乘法運(yùn)算和平方運(yùn)算,其中,平方運(yùn)算生成R0;如果kn-1-j=1,則由R1輸出R1,并作乘法運(yùn)算和平方運(yùn)算,其中,平方運(yùn)算生成R1。
2×2正交變換器工作原理:在第j(j=0,1,2,…n-1)輪循環(huán),如果kn-1-j=0,即控制端輸入E=1,變換表現(xiàn)為交叉關(guān)系,這時(shí)乘法器和平方單元的輸出分別輸入R0和R1中;如果kn-1-j=1,即控制端的輸入為E=0,變換表現(xiàn)為平行關(guān)系,這時(shí)乘法器和平方單元的輸出分別為R0和R1中。
在第j(j=0,1,2…,n-1)輪循環(huán)中,運(yùn)行算法1中i=j的步驟。進(jìn)行n輪循環(huán)后,存儲器R0中的值即為C=Mk。
設(shè)計(jì)包含了一個(gè)模乘法運(yùn)算,一個(gè)模平方運(yùn)算,3個(gè)混合運(yùn)算和2個(gè)存儲器過程。算法時(shí)間復(fù)雜度為:
從圖2中可以看出,2×2正交變換等價(jià)于一個(gè)混合器。由于是對大數(shù)的運(yùn)算,可以認(rèn)為Tmultiplier>>Tsquarer,則一次循環(huán)耗時(shí)T=Tmultiplier+Tmux。整個(gè)模冪運(yùn)算耗時(shí)nT=n(Tmultiplier+Tmux)。
經(jīng)典MPL算法是從k2的最高位循環(huán)到最低位,而且是單位循環(huán)。為了提高運(yùn)算速度,需對經(jīng)典MPL算法進(jìn)行改進(jìn)。將循環(huán)展開技術(shù)應(yīng)用于MPL算法,并將兩個(gè)循環(huán)合并,得到如下改進(jìn)算法:
以上算法與M-ary算法中為m=4的情況類似。
實(shí)現(xiàn)算法2的設(shè)計(jì)如圖3所示。變量R0和R1分別初始化為1和M,存儲在存儲器R0和R1中。設(shè)R0和R1可存儲大數(shù)N-1(N為模數(shù))。
如圖4所示,二進(jìn)制指數(shù)k存儲在移位寄存器中。n為偶數(shù)時(shí),寄存器K有n比特,k2m+1=kn-1,即m=n/2-1;n為 奇數(shù)時(shí),寄存器K有n+1比特,k2m=kn-1,即m=(n-1)/2。寄存器K每循環(huán)一次,有兩個(gè)比特輸出。一個(gè)比特用來控制圖3上方的混合器和2×2的正交變換;另一個(gè)比特用來控制圖3下方的混合器和2×2正交變換。除寄存器外,改進(jìn)MPL設(shè)計(jì)還包括兩個(gè)乘法器,兩個(gè)平方單元,兩個(gè)混合器和兩個(gè)2×2正交變換。
這種設(shè)計(jì)可以分成上下兩部分。兩部分結(jié)構(gòu)都與圖1結(jié)構(gòu)類似。不同之處在于,上方部分2×2正交變換的輸出分別為下方部分乘法器和平方單元的輸入。
分析該算法的實(shí)現(xiàn),算法時(shí)間復(fù)雜度為:
T=max{2TMultiplier+2T2×2,Tmultiplier+Tsquarer+2T2×2+Tmux,2Tsquarer+2T2×2+2Tmux}
完成模冪運(yùn)算需要m+1=(n+1)/2個(gè)循環(huán),則整個(gè)運(yùn)算耗時(shí)(M+1)T。
圖3 改進(jìn)MPL快速實(shí)現(xiàn)(算法2)
圖4 移位寄存器
大數(shù)模冪運(yùn)算是公約密碼體質(zhì)研究的熱點(diǎn)內(nèi)容之一。本文結(jié)合經(jīng)典Montgomery階梯算法能并行處理的特點(diǎn),首先設(shè)計(jì)實(shí)現(xiàn)出經(jīng)典Montgomery階梯算法;然后結(jié)合循環(huán)展開技術(shù),提出了一種改進(jìn)Montgomery階梯算法,設(shè)計(jì)并實(shí)現(xiàn)了該算法。分析表明,該方法能將經(jīng)典Montgomery階梯算法的循環(huán)次數(shù)降低一半,使得該算法能在ECC和其他領(lǐng)域得到廣泛應(yīng)用。
[1]DIFFIE W,HELLMAN M.New directions in cryptography[J].IEEE tans.Inform.Theory,1976(22):644-654.
[2]朱兆國,任忠保,桂祚勤.大數(shù)模冪運(yùn)算的快速算法[J].高性能計(jì)算技術(shù),2006(2):45-48.
[3]MONTGOMERY P L.Modular multiplication without trial division[J].Mathmatics of Computation,1985,44(170):519-521.
[4]王平水.公鑰密碼體制及其安全性分析研究[D].合肥:合肥工業(yè)大學(xué),2006.
[5]左平,龐世春,華宏圖,等.安全的并行橢圓曲線Montgomery階梯算法[J].吉林大學(xué)學(xué)報(bào)(物理版),2011,49(4):690-692.
[6]GORDON D M.A survey of fast exponentiation methods[J].Algorithms,1998,27(1):129-146.
[7]MESSERGES T S,DABBISH E A,SLOAN R H.Power analysis attacks of modular exponentiation in Smartcards[C].CHES′99,1999:144-157.
[8]WELSCHENBACH M.密碼編碼學(xué)-加密方法的C與C++實(shí)現(xiàn)[M].趙振江,等譯.北京:電子工業(yè)出版社,2003.
網(wǎng)絡(luò)安全與數(shù)據(jù)管理2013年11期