摘 要： 提出了利用Montgomery階梯算法實(shí)現(xiàn)快速模冪運(yùn)的兩種方案,。第一種是將每個時鐘周期內(nèi)乘法和平方并行執(zhí)行,，且使用2×2正交變換器選擇輸出，使Montgomery階梯算法簡單,、高效,；第二種是使用循環(huán)展開技術(shù)將循環(huán)數(shù)減少一半，且只需要一半的時鐘,，運(yùn)算效率得到更大的提高,。
關(guān)鍵詞： 模冪運(yùn)算；標(biāo)量乘,；Montgomery階梯算法
大數(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)算是很耗時的運(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時才執(zhí)行乘法運(yùn)算[6],。這種在不同步中運(yùn)算數(shù)量的差異導(dǎo)致系統(tǒng)易受邊道攻擊[7],。在Diffie-Hellman和RSA系統(tǒng)中的模冪運(yùn)算中，冪為其密鑰,。一個成功的SCA攻擊可以計(jì)算模冪運(yùn)算的冪,，從而導(dǎo)致整個系統(tǒng)密鑰的丟失。本文利用循環(huán)展開技術(shù),，將兩個循環(huán)同時進(jìn)行并行處理,，提高了運(yùn)算速度和效率。同時,，根據(jù)Montgomery階梯算法原理,，設(shè)計(jì)了該算法的硬件實(shí)現(xiàn)。
1 Montgomery階梯算法
1.1 經(jīng)典Montgomery階梯算法
算法1描述的過程即為經(jīng)典Montgomery階梯算法流程,。
算法1：
Input：M,，k=（kn-1…k1 k0）2
Output：C=Mk
（1）Set R0←1,，R1←M,；
（2）For i=n-1 to 0 Step-1
?、買f（ki=0）
Then{Set R1←R0×R1，R0←R02}
?、贗f（ki=1）
Then{Set R0←R0×R1,，R1←R12}
（３）Return（C=R0）
由該算法可知,，將一次平方運(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)算，用一個雙核處理器,，在同一時鐘內(nèi)將乘法運(yùn)算和平方運(yùn)算同時進(jìn)行,，運(yùn)算速度將提高一倍?；谝陨峡紤],，本文將設(shè)計(jì)實(shí)現(xiàn)一種經(jīng)典Montgomery階梯算法。
1.2 MPL算法的快速實(shí)現(xiàn)
算法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)還包括一個模乘法器、模平方單元,、一個混合器和一個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)系,，這時乘法器和平方單元的輸出分別輸入R0和R1中,；如果kn-1-j=1，即控制端的輸入為E=0,， 變換表現(xiàn)為平行關(guān)系,，這時乘法器和平方單元的輸出分別為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ì)包含了一個模乘法運(yùn)算,，一個模平方運(yùn)算,，3個混合運(yùn)算和2個存儲器過程。算法時間復(fù)雜度為：
T=max{Tmultiplier,，Tsquarer+Tmux}+T2×2
=max{Tmultiplier+Tmux,，Tsquarer+2Tmux}
從圖2中可以看出，2×2正交變換等價于一個混合器,。由于是對大數(shù)的運(yùn)算,，可以認(rèn)為Tmultiplier>>Tsquarer，則一次循環(huán)耗時T=Tmultiplier+Tmux,。整個模冪運(yùn)算耗時nT=n（Tmultiplier+Tmux）,。
2 一種改進(jìn)的MPL算法及實(shí)現(xiàn)
2.1 一種改進(jìn)的MPL算法
經(jīng)典MPL算法是從k2的最高位循環(huán)到最低位，而且是單位循環(huán),。為了提高運(yùn)算速度,，需對經(jīng)典MPL算法進(jìn)行改進(jìn)。將循環(huán)展開技術(shù)應(yīng)用于MPL算法,，并將兩個循環(huán)合并,，得到如下改進(jìn)算法：
算法2：
Input：M，k= （kn-1…k1 k0）2
Output：C=Mk
(１)Set m←（n-2）/2 if n is even
otherwise set m←（n-1）/2 and kn←0
(２)Set R0←1,， R1←M;
(３)For i=m to 0 step-1
?、買f（k2i+1k2i=00）
Then{Set R1←R0×R1，R0←R02,，
R1←R0×R1，R0←R02 }
?、贗f（k2i+1k2i=01）
Then{Set R1←R0×R1,，R0←R02，
R0←R0×R1,，R1←R12 }
?、跧f（k2i+1k2i=10）
Then{Set R0←R0×R1，R1←R12,，
R1←R0×R1,，R0←R02 }
④If（k2i+1k2i=11）
Then{Set R0←R0×R1,，R1←R12,，
R0←R0×R1,，R1←R12 }
(4)Return(C=R0)
以上算法與M-ary算法中為m=4的情況類似。
2.2 改進(jìn)MPL算法的實(shí)現(xiàn)
實(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ù)時,，寄存器K有n比特,，k2m+1=kn-1，即m=n/2-1,；n為奇數(shù)時,，寄存器K有n+1比特，k2m=kn-1,，即m=（n-1）/2,。寄存器K每循環(huán)一次，有兩個比特輸出,。一個比特用來控制圖3上方的混合器和2×2的正交變換,；另一個比特用來控制圖3下方的混合器和2×2正交變換。除寄存器外,，改進(jìn)MPL設(shè)計(jì)還包括兩個乘法器,，兩個平方單元，兩個混合器和兩個2×2正交變換,。
這種設(shè)計(jì)可以分成上下兩部分,。兩部分結(jié)構(gòu)都與圖1結(jié)構(gòu)類似。不同之處在于,，上方部分2×2正交變換的輸出分別為下方部分乘法器和平方單元的輸入,。
分析該算法的實(shí)現(xiàn)，算法時間復(fù)雜度為：
T=max{2TMultiplier+2T2×2,，Tmultiplier+Tsquarer+2T2×2+Tmux,，2Tsquarer+2T2×2+2Tmux}
大數(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)用,。
參考文獻(xiàn)
[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.
（收稿日期：2013-03-09）