摘 要： 采用大数的高基表示方法和Karatsuba递归思想改进了Montgomery模乘中的IFIOS实现算法，该算法可以应用于RSA公钥体制下的模乘法器的设计。模乘运算的速度决定了公钥加密系统和众多通信系统的系统性能，通过与IFIOS算法的比较分析发现，改进后的算法具有使用的乘法次数少、并行性能高等优点，是一种适合设计硬件的高效算法。此算法也适用于其他公钥体制的加解密处理器。
关键词： Montgomery模乘；Karatsuba递归思想；IFIOS
基于大整数分解的RSA体制是公钥密码体制中的一类，是目前应用最广泛的公钥密码体制之一。对于RSA来说，人们关心的一个重要问题是大整数模幂运算。为此，许多学者一直在对此进行研究[1-2]。加快模幂运算主要考虑减少模幂的次数和提高大整数模乘的运算速度。1985年，MONTGOMERY P.L.提出的大整数模乘算法是一种非常有效的方法。之后KOC C.C.对几种Montgomery算法的实现方法进行分析比较，发现FIOS算法是一种空间复杂度低的实现方法[3]。其他学者也对Montgomery算法进行了各式各样的改进，取得了一些进步[4-5]。基于Karatsuba递归思想的Karatsuba快速乘法算法已经被证实在计算机系统中比传统算法更具优势[6]。本文运用Karatsuba递归思想对Montgomery模乘算法进行了改进，给出了一种改进算法描述，对其复杂度和并行度做了分析比较。
1 Montgomery算法
1.1 Montgomery算法简介
Montgomery构造了一个特殊的剩余系,借此把普通的模乘转换成该剩余系中的模乘，把对n的模简化变为对一个任意r(r>n)的模简化，当选取为2的幂时，对r模简化只需简单的移位操作即可，这样在计算a·b(mod n)时避免了除法运算，从而实现了在计算机中快速计算模乘的目的。
由于Karatsuba算法是递归的，在计算中需要存储中间状态、临时变量等比较多。所以本文局部运用这种递归思想，并采用高基来改进算法，避免了这些问题的出现。
1.3 IFIOS算法
FIOS算法是Montgomery实现算法中的一种，需要的加法次数和读写次数稍多，但空间复杂度最低，因此适用于设计高速专用RSA密码芯片件。参考文献[5]给出了FIOS的改进算法——IFIOS算法，算法的性能进一步得到优化。
2 利用Karatsuba思想改进Montgomery模乘算法
2.1 Karatsuba- IFIOS模乘算法
为了进一步提高实现的效率，利用了Karatsuba思想对IFOS算法进行了改进，提出了Karatsuba- IFIOS模乘算法。首先设算法中的大整数采用基22w表示，存储空间以2w比特的存储单元进行存储。设n为k比特的整数，
2.2 性能分析及对比
对于加法的次数，由于减法运算可以通过补码转换为加法运算，所以可把减法看做加法来计算。Karatsuba-IFIOS算法中均为2w位的加法，这样改算法共需要s(3s+9)+2次2w位加法和s(s+3)次w位加法。
最后计算临时存储单元的数目。只考虑如下一些临时存储单元：一部分是2w位的存储单元t[s/2+1],t[s/2],…,t[0]，一个2w位的m和3个2w位的存储变量(Karatsuba(x,y,type)算法中需要的)，这样总数目为(s/2+6)×2=s+12个w位的存储单元。与IFIOS算法相比，增加了9个w位的存储单元。需要说明的是，由于初始输入a,b,n的存储单元数目不变，只是单元存储由w位变为2w位，n′[0]是在预计算中得到的，还有C,S,B均为计算中运算器的寄存器，不占用存储单元，所以这些均不考虑在本算法内。
由于k比特乘法运算的时间复杂度是O(k2)加法运算的复杂度是O(k)。一般可认为1次k比特的乘法运算需要k次k比特的加法运算来实现。因此，提高算法的运算速度关键是看其乘法次数的多少。
2.3 并行性分析与比较
算法并行性的优劣，在密码芯片设计中至关重要，它决定了硬件芯片设计的可扩展性：一个具有较好并行性的算法，可以通过增加一定的硬件资源，利用并行和流水线技术，设计出高速的密码芯片。
下面对改进后的IFIOS算法进行并行性分析：
(1) IFIOS算法的并行性
首先观察循环内的运算，算法内层循环中的(R0,S):=t[j]+a[j]×b[i]+R0和(R1,S):=S+m×n[j]+R1运算可分别并行处理：t[j]+R0和a[j]×b[i]以及S+R1和m×n[j]在同一个时钟周期内并行处理，然后在下一个时钟内完成两个计算结果的累加。这样可在两个时钟周期内完成这两步的运算，提高了运算效率。
由于s内循环之间的数据是无关的，因此可以在并行的基础上建立两级流水线，当前一个循环(j=k)进行(R0,S):=t[j]+a[j]×b[i]+R0的最后结果累加时，后一循环(j=k+1)计算t[j]+R0和a[j]×b[i]的值。
(2) Karatsuba-IFIOS算法的并行性
Karatsuba-IFIOS算法的并行处理主要有Karatsuba(x,y,type)t[j]+Kartsuba(a[j],b[i],0)+R0的计算。由于数据无关，在Karatsuba(x,y,type)乘法算法中temp1=x[1]·y[1]和temp2=x[0]·y[0]，还有x[1]-x[0]与y[0]-y[1]可以在一个时钟周期内并行处理；同样temp1+temp2的计算和x[1]-x[0]与y[0]-y[1]乘积也可以在一个时钟周期内并行处理。因此，函数Karatsuba(x,y,type)在硬件芯片设计中采用双乘法器和双加法器,只要3个时钟周期即可。而t[j]+Karatsuba(a[j],b[i],0)+R0的并行计算类似于IFIOS的处理方法，在同一个时钟周期里计算t[j]+R0和Karatsuba(a[j],b[i],0)，所以只要2个时钟周期。
在改进算法的主循环里有t[j]+Karatsuba(a[j],b[i],0)+R0和S+Karatsuba(m,n[j],0)+R1这样两个类似的计算，在硬件设计中共需要10次加法的顺序,如果采用双加法器就能够获得更好的并行处理性能。另外需要注意，w的取值应根据不同的应用需求和不同的设计结构选取。由于w值决定了乘法器和加法器的位数，所以w值不能太大，否则会导致芯片的实现面积和时延较大，也会使硬件实现的复杂度增加。
利用Karatsuba递归思想成功地将IFIOS算法进行了改进，并给出算法的具体描述。通过分析和比较，改进后的Karatsuba-IFIOS算法比IFIOS算法的乘法次数明显减少，并行处理性能更高，是一种适合硬件设计的好算法。Karatsuba递归思想也可以改进其他的算法，并能不同程度地减少乘法次数。
参考文献
[1] IPUT H K, ASEP B N, RANDY S P, et al. Very fast pipelined RSA architecture based on montgomery’s algorithm[C]. 2009 International Conference on Elec- trical Engineering and Informatics. Bangi, Malaysia IEEE Computer Socitey Press, 2009:491-495.
[2] FANG X Y, ZHANG J H. The researcher and implement of high-speed modular multiplication algorithm basing on parallel Pipelining[C]. 2009 AsiaPacific Conference on Information Processing. Shenzhen, China, IEEE Computer Socitey Press, 2009:398-403.
[3] KOC C C, ACAR T, KALISKI B S. Analyzing and comparing montgomery multiplication algorithms[J]. IEEE Micro. 1996,16(3):26-33.
[4] WU C L. An efficient common-multiplicand-multiplication method to the montgomery algorithm for speeding up exponentiation[J]. Information Scien- ces. 2009,179(4):410-421.
[5] 王红霞,王金荣,赵宪生. Montgomery模乘算法的改进及其应用[J]. 计算机工程与应用, 2007,43(20):52-55.
[6] 蔡风景, 李涛.一种快速乘法算法—Karatsuba 乘法算法[J]. 湘潭师范学院学报, 2004,26(1):55-56.
