摘要： 大数模乘是许多公钥密码体制的核心运算，也是运算效率提高的瓶颈。基于Montgomery模乘算法，该文提出了一种改进的快速模乘及其模幂算法，由于采用了新的booth编码，算法的循环次数减少近一半，因此性能提高近一倍。模幂器采用新型的保留进位加法器(CSA)树，此结构无须对每次模乘的结果求和。实验表明，在97MHz时钟频率下，1 024-bit模幂器的波特率为184Kb/s，适合于设计高速的公钥密码协处理器。

关键词: Montgomery模乘算法, 保留进位加法器, RSA

Abstract: Modular multiplication of large integers is the kernel operation in many public-key crypto-systems. It is also the bottleneck of the computing efficiency. Based on Montgomery multiplication algorithm, this paper presents an improved multiplication algorithm and its exponentiation algorithm, which is twice faster than the conventional version, with about 50% reduction in iterations by using modified booth encoding. A novel architecture using carry save adders (CSA) tree is applied to the modular exponentiator, without computing full addition of the output of each modular multiplication. The result shows that the modular exponentiator is about 184Kb/s for 1 024-bit operands at a clock of 97MHz and well suitable for designing the high-speed public-key coprocessor.

Key words: Montgomery modular multiplication algorithm, carry save adder, RSA

中图分类号: 

• TN47