摘 要： 提出了利用Montgomery階梯算法實現快速模冪運的兩種方案。第一種是將每個時鐘周期內乘法和平方并行執行，且使用2×2正交變換器選擇輸出，使Montgomery階梯算法簡單、高效；第二種是使用循環展開技術將循環數減少一半，且只需要一半的時鐘，運算效率得到更大的提高。
關鍵詞： 模冪運算；標量乘；Montgomery階梯算法
大數模冪運算在Diffie-Hellman和RSA系統中得到了廣泛應用[1]。所謂模冪運算，就是已知大數a、x、m，求解ax（mod m）。這里的a、x、m一般為幾百比特甚至上千比特的大整數，m一般為素數，因此在此過程中需要做大量的乘法運算和模運算（即除法運算）。在計算機運行處理過程中，乘法運算是很耗時的運算，而除法運算更是乘法的幾倍之多。因此，在計算ax（mod m）的過程中，如何減少乘法，尤其是模運算的次數便成為提高模冪運算速度的關鍵。參考文獻[2]對常用算法進行了分析和總結。
經典Montgomery[3]階梯算法是將模運算轉化為乘法運算和移位運算，從而避免計算模運算，在RSA[4]和ECC[5]中得到廣泛應用。在該算法中執行運算的次數等于冪的二元進制長度，且平方運算是每步都要執行，僅當冪為1時才執行乘法運算[6]。這種在不同步中運算數量的差異導致系統易受邊道攻擊[7]。在Diffie-Hellman和RSA系統中的模冪運算中，冪為其密鑰。一個成功的SCA攻擊可以計算模冪運算的冪，從而導致整個系統密鑰的丟失。本文利用循環展開技術，將兩個循環同時進行并行處理，提高了運算速度和效率。同時，根據Montgomery階梯算法原理，設計了該算法的硬件實現。
1 Montgomery階梯算法
1.1 經典Montgomery階梯算法
算法1描述的過程即為經典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
①If（ki=0）
Then{Set R1←R0×R1，R0←R02}
②If（ki=1）
Then{Set R0←R0×R1，R1←R12}
（３）Return（C=R0）
由該算法可知，將一次平方運算認為是一次乘法運算，可以完成一次求冪運算，經典MPL算法至少將運用2logk次乘法運算，而平方乘的平均運算量達到3/2logk。參考文獻[8]指出MPL算法支持并行運算，用一個雙核處理器，在同一時鐘內將乘法運算和平方運算同時進行，運算速度將提高一倍。基于以上考慮，本文將設計實現一種經典Montgomery階梯算法。
1.2 MPL算法的快速實現
算法1的快速實現如圖1所示，變量R0和R1分別初始化為1和M，分別存儲在存儲器R0和R1中。設R0和R1可存儲大數Mk。指數k存儲在二進制移位寄存器中，該寄存器每次循環左移一位。算法硬件實現還包括一個模乘法器、模平方單元、一個混合器和一個2×2正交變換器。
設計工作原理如下：首先，將R0和R1分別初始化為1和M。在第j（j=0，1，2，…，n-1）輪循環，指數中比特kn-1-j是移位寄存器最左邊的比特，由它控制混合器運算和2×2正交變換。如果kn-1-j=0，則由R0輸出R0，并作乘法運算和平方運算，其中，平方運算生成R0；如果kn-1-j=1，則由R1輸出R1，并作乘法運算和平方運算，其中，平方運算生成R1。
2×2正交變換器工作原理：在第j（j=0，1，2，…n-1）輪循環，如果kn-1-j=0，即控制端輸入E=1，變換表現為交叉關系，這時乘法器和平方單元的輸出分別輸入R0和R1中；如果kn-1-j=1，即控制端的輸入為E=0， 變換表現為平行關系，這時乘法器和平方單元的輸出分別為R0和R1中。
在第j（j=0，1，2…，n-1）輪循環中，運行算法1中i=j的步驟。進行n輪循環后，存儲器R0中的值即為C=Mk。
設計包含了一個模乘法運算，一個模平方運算，3個混合運算和2個存儲器過程。算法時間復雜度為：
T=max{Tmultiplier，Tsquarer+Tmux}+T2×2
=max{Tmultiplier+Tmux，Tsquarer+2Tmux}
從圖2中可以看出，2×2正交變換等價于一個混合器。由于是對大數的運算，可以認為Tmultiplier>>Tsquarer，則一次循環耗時T=Tmultiplier+Tmux。整個模冪運算耗時nT=n（Tmultiplier+Tmux）。
2 一種改進的MPL算法及實現
2.1 一種改進的MPL算法
經典MPL算法是從k2的最高位循環到最低位，而且是單位循環。為了提高運算速度，需對經典MPL算法進行改進。將循環展開技術應用于MPL算法，并將兩個循環合并，得到如下改進算法：
算法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
①If（k2i+1k2i=00）
Then{Set R1←R0×R1，R0←R02，
R1←R0×R1，R0←R02 }
②If（k2i+1k2i=01）
Then{Set R1←R0×R1，R0←R02，
R0←R0×R1，R1←R12 }
③If（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 改進MPL算法的實現
實現算法2的設計如圖3所示。變量R0和R1分別初始化為1和M，存儲在存儲器R0和R1中。設R0和R1可存儲大數N-1（N為模數）。
如圖4所示，二進制指數k存儲在移位寄存器中。n為偶數時，寄存器K有n比特，k2m+1=kn-1，即m=n/2-1；n為奇數時，寄存器K有n+1比特，k2m=kn-1，即m=（n-1）/2。寄存器K每循環一次，有兩個比特輸出。一個比特用來控制圖3上方的混合器和2×2的正交變換；另一個比特用來控制圖3下方的混合器和2×2正交變換。除寄存器外，改進MPL設計還包括兩個乘法器，兩個平方單元，兩個混合器和兩個2×2正交變換。
這種設計可以分成上下兩部分。兩部分結構都與圖1結構類似。不同之處在于，上方部分2×2正交變換的輸出分別為下方部分乘法器和平方單元的輸入。
分析該算法的實現，算法時間復雜度為：
T=max{2TMultiplier+2T2×2，Tmultiplier+Tsquarer+2T2×2+Tmux，2Tsquarer+2T2×2+2Tmux}
大數模冪運算是公約密碼體質研究的熱點內容之一。本文結合經典Montgomery階梯算法能并行處理的特點，首先設計實現出經典Montgomery階梯算法；然后結合循環展開技術，提出了一種改進Montgomery階梯算法，設計并實現了該算法。分析表明，該方法能將經典Montgomery階梯算法的循環次數降低一半，使得該算法能在ECC和其他領域得到廣泛應用。
參考文獻
[1] DIFFIE W， HELLMAN M. New directions in cryptography[J]. IEEE tans. Inform. Theory， 1976（22）：644-654.
[2] 朱兆國，任忠保，桂祚勤.大數模冪運算的快速算法[J].高性能計算技術，2006（2）：45-48.
[3] MONTGOMERY P L. Modular multiplication without trial division[J]. Mathmatics of Computation，1985，44（170）：519-521.
[4] 王平水.公鑰密碼體制及其安全性分析研究[D].合肥：合肥工業大學，2006.
[5] 左平，龐世春，華宏圖，等.安全的并行橢圓曲線Montgomery階梯算法[J].吉林大學學報（物理版），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.密碼編碼學-加密方法的C與C++實現[M].趙振江，等譯.北京：電子工業出版社，2003.
（收稿日期：2013-03-09）