蒙哥馬利模乘算法改進及硬件實現(xiàn)

任仕偉，王華陽，郝越，薛丞博

（北京理工大學(xué) 集成電路與電子學(xué)院 ，北京 100081）

數(shù)字通信技術(shù)的發(fā)展在提高信息傳輸?shù)谋憷院托实耐瑫r，也加劇了信息泄漏和竊聽的風(fēng)險.為了加強信息安全，許多加密算法被提出[1].目前，作為現(xiàn)代公鑰密碼學(xué)兩個主要標準的Rivest-Shamir-Adleman 算法（RSA）和橢圓曲線密碼（elliptic curve cryptography, ECC）是密碼系統(tǒng)研究的焦點之一[2-4].

以RSA 為例，該算法使用一個模數(shù)（modulus）M和兩個密鑰d和e，其中至少有一個密鑰是私鑰.要傳遞的信息A通過模冪運算被加密為C=AemodM，解密階段同樣通過模冪運算A=CdmodM解密.AemodM的計算過程主要由模乘和冪運算組成.

從前述可以看出，RSA 算法在加解密的過程中都會進行重復(fù)的模乘運算.類似地，ECC 算法中的點乘操作基于模乘操作實現(xiàn)[5].對于模乘運算，以RSA常用的1 024 位大數(shù)為例，設(shè)有乘數(shù)A， 被乘數(shù)B，模數(shù)N，需要先計算兩個1 024 位大數(shù)的積S=A×B，再將結(jié)果積對模數(shù)N取余數(shù)，在此計算過程中將會產(chǎn)生2 048 位的中間結(jié)果.對中間結(jié)果S的模約減步驟通常需要將S與模N進行比較，在最壞的情況下，意味著需要依次檢查兩個長數(shù)的每一位.因此模乘運算是RSA 和ECC 算法中主要的耗時操作，提高模乘操作的效率對提高公鑰密碼系統(tǒng)的性能起著關(guān)鍵作用.

在現(xiàn)有模乘算法中，蒙哥馬利算法[6]是最有效的方案.該算法提出基于加法及除以2n（n∈Z）的替代方法，以避免除法操作[7]，而除以2n（n∈Z）可通過簡單的移位操作在硬件上實現(xiàn)，從而達到節(jié)省硬件資源的效果.該算法在很多密碼學(xué)應(yīng)用中都得到了廣泛的應(yīng)用……