Novel Architecture for Modular Exponentiator Based on Montgomery
Shaowu Zhang · Jisuanji gongcheng · 2007
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.