Montgomery算法在RSA中的应用及其优化  

Optimization and Application of Montgomery Algorithm in RSA

作　　者：王琴琴[1] 陈相宁[1] 

机构地区：[1]南京大学电子科学与工程系,江苏南京210093

出　　处：《计算机技术与发展》2007年第6期145-146,150,共3页Computer Technology and Development

摘　　要：Montgomery算法作为一种快速模乘算法,常被应用于RSA、ElGamal等公钥密码算法的基本运算。对RSA和Montgomery算法进行简要的介绍和分析,并阐述了普通的Montgomery算法在RSA中的应用的思路和步骤。最常用的传统算法选取参数r为2的幂,基数为2,通过对普通算法的思路和步骤的分析,讨论改变其中参数r和基数的选择来减少乘方的模乘法数,并同时应用Dussé快速算法,从而达到大大提高运算速度的目的。Montgomery algorithm is a fast modular multiplication algorithm and is widely used in the base operation of public- key cryptography algorithms such as RSA and ElGamal. Firstly, the algorithm of RSA and Montgomery are simply introduced and analyzed. Method and calcutive steps of normal application of Montgomery algorithm in RSA are expatiated also. Algorithm in most conmmon use chooses parameter r to power of 2 and the base to 2. Via analyzing the method and calcutive steps of normal algorithm, discusses changing the numerical value of parameter r and the base and use the fast algorithm of Dussé in the meantime, to advance the calcutive velocity a lot.

关 键 词：RSA MONTGOMERY算法 模乘 Dussé快速算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]