[發明專利]提高大整數Montgomery模乘運算速度的方法

無效

• 申請號: 200710304567.8
• 申請日: 2007-12-28
• 公開（公告）號: CN101470598A
• 公開（公告）日: 2009-07-01
• 發明（設計）人: 程登峰;張慶勝;王磊;丁瑤
• 申請（專利權）人: 航天信息股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72;H04L9/14
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司
• 代理人: 孫皓晨;朱世定

技術領域

本發明涉及的是一種加密算法，特別涉及的是一種提高大整數Montgomery模乘運算速度的方法。

背景技術

隨著Internet的迅猛發展，網絡安全問題顯得越來越重要，相關網絡安全協議應運而生，而這些協議又是以高效安全的加密算法為前提的。

加密算法分為對稱加密算法和非對稱加密算法。在網絡上進行數據傳輸時，通常使用對稱加密算法加密所要傳輸的數據，而用非對稱加密算法加密密鑰。

就非對稱加密算法來說，目前RSA與ECC的應用比較普及。RSA與大素數域上的ECC的底層運算都離不開大整數模乘運算，大整數模乘運算的速度直接決定了RSA與ECC加密算法的速度。

在目前的所有有效的大整數模乘算法中，Montgomery算法在大多數環境下被認為是最為高效的。而在具體以字為單位實現Montgomery算法的方法中，CIOS(Coarsely?Integrated?Operand?Scanning)算法復雜度最低。現將此算法描述如下：

假設Montgomery算法的參數為(M，M′[0]，r，n，X，Y)，M為大整數，r＝2^w為最小字處理單元，n為大整數的字個數。M′[0]＝M^-1[0]mod?r。X，Y為要計算Montgomery模乘的乘數。CIOS算法如下：

for?i＝0?to?n-1{

?????C＝0；

?????for?j＝0?to?n?-1{

?????(C，S)＝T[j]+X_ha[j]*Y_lb[i]+C；

?????}

?????(C，S)＝T[n]+C；

?????T[n]＝S；

?????T[n+1]＝C；

?????C＝0；

?????m＝T[0]*M′[0]mod?r；

????(C，S)＝T[0]+m*M′[0]

????for?j＝1?to?n?-1{

????(C，S)＝T[j]+m*M[j]+C；

????T[j-1]＝S；

????}

???(C，S)＝T[n]+C；

???T[n-1]＝S；

???T[n]＝T[n+1]+C；

}

在大整數運算中，關鍵運算為乘法運算，加法運算時間都可忽略不計，上述CIOS中乘法的次數為2n²+n。如何減少乘法運算的次數，成為改進MontgomeryCIOS算法的關鍵。

一些學者注意到了這一點，文章《Dual-Residue?Montgomery?Multiplication》也闡述了一種提高速度的方案，該文章的主要創新點如下：

為了提高運算速度，他將乘數中的一個拆分為高低項之和，Y＝Y_Hr^a+Y_L，然后并行計算XY_Hr^-b?mod?M，XY_Lr^-n?mod?M的值。

因為b<n所以XY_Hr^-b?mod?M通過CIOS算法比原來的運算量小，而XY_Lr^-nmod?M中的Y_L的字數比原來少，而兩項的計算又是并行的，所以運算速度比原來得到提高。

但是該文章中僅對一個乘數進行了拆分，XY_Lr^-nmod?M的計算中乘法的運算量在取時約為6n²/4+n。

鑒于上述問題，本發明創作者經過長時間的研究和試驗，在此算法的基礎上獲得一種提高大整數運算速度的方法。

發明內容

本發明的目的在于，提供一種提高大整數Montgomery模乘運算速度的方法，用以克服上述缺陷。

為實現上述目的，本發明采用的技術方案在于，提供一種提高大整數Montgomery模乘運算速度的方法，其包括的步驟為：

步驟a：將兩個大整數乘數X、Y分別拆分為高數位和低數位

步驟b：并行計算，，X_laY_lbr^-n?modM；

步驟c：計算的值，得到最終結果；