一种改进的Montgomery模乘快速算法.pdfVIP

31 8 2005 4 Vol.31 8 Computer Engineering April 2005 · · 2005 A TP309 Montgomery 250100 Karatsuba-Ofman Montgomery CIOS CIOS 25% RSA RSA Montgomery CIOS Karatsuba-Ofman An Improved Fast Montgomery Multiplication Algorithm KONG Fanyu, YU Jia, LI Daxing (Institute of Network Security , Shandong University, Jinan 250100) Abstract Montgomery algorithm is one of the most efficient algorithms implementing long integer modular multiplication in RSA cryptosystem. The CIOS method of Montgomery algorithm is improved via the idea of Karatsuba-Ofman algorithm,: the decrease rate amounts to nearly 25%. Furthermore, the improved CIOS algorithm can be implemented with parallel processing of two independent multiplications and is well suited to designing high-speed RSA crypto-chips. Key words RSA cryptosystem; Montgomery modular multiplication; CIOS method; Karatsuba-Ofman algorithm RSA function MonPro (a, b, r, n) RSA Step 1 t := a∙b e Step 2 u := (t + (t∙n’mod r) n) / r RSA m mod n Step 3 if u ≥ n then RSA return u-n else return u k r = 2 mod r/r RSA a∙b mod n [1] Montgomery Montgomery [2] a∙b ∙r–1 mod n mod n Koc r–1 Montgomery Montgomery 5 CIOS