摘 要： 提出了利用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）