[發明專利]基于蒙哥馬利模乘運算的數據加解密處理方法及裝置

有效

• 申請號: 201110116480.4
• 申請日: 2011-05-06
• 公開（公告）號: CN102207847A
• 公開（公告）日: 2011-10-05
• 發明（設計）人: 梁鵬飛;張永強
• 申請（專利權）人: 廣州杰賽科技股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 廣州三環專利代理有限公司 44202
• 代理人: 郝傳鑫

技術領域

本發明涉及計算機技術領域，尤其涉及一種基于蒙哥馬利模乘運算的數據加解密處理方法及裝置。

背景技術

隨著無線網絡通信技術的迅速發展，人們對信息安全的要求不斷提高，相關的網絡安全協議不斷產生，如國家無線局域網委員會提出的WAPI(Wireless?LAN?Authentication?and?Privacy?Infrastructure，無線局域網鑒別和保密基礎結構)網絡安全協議；網絡安全方面的產品也不斷推出；因此，開發一種高效而安全的加密算法是勢在必行的。

目前所流行的加密算法有對稱加密算法和非對稱加密算法，而在非對稱加密算法當中，RSA和ECC加密算法的應用普及率最高。在WAPI無線局域網技術文件里面就有提到，WAPI的安全協議采用的就是ECC(橢圓曲線密碼算法)加密算法。ECC加密算法中的底層運算基本上是依靠模乘來完成的，而模乘的運算速度和效率也決定了整個ECC加密算法的效率和速度。

在目前的大整數模乘算法的硬件實現中，蒙哥馬利(Montgomery)模乘算法被認為是最高效的，也是最適合用硬件實現的一種算法。Montgomery算法設計了一個剩余類系統，將普通模乘的計算過程轉換到Montgomery剩余類(余數域)里面進行，在這個剩余類里面，所有的數的計算過程中產生的大數都會被規約到剩余類里，它的計算會顯得更加簡潔，特別是在硬件實現上面，能夠提供更加迅速的計算速度和更簡單的硬件結構。Montgomery算法理論的基礎是下面的定理1。

定理1：假設N和R是互素的兩個整數，N′＝-N^-1?modR，則對于所有的整數T，當M＝T×N′modR時，是一個整數，而且滿足：其中N′是N的逆，T是乘數A和被乘數B的乘積。

為了讓Montgomery模乘算法在實際應用中(軟件、硬件)能更方便地使用，可以根據計算機或者芯片精度的要求，把每個大數分解成為2ⁿ為基底的數，按照字節的處理方式來實現Montgomery算法。

設q是2為基底的數，利用q來表示多精度的大數A如下：

A＝a_n-1q^n-1+a_n-2q^n-2++a₁q+a₀

根據上述定理1所推導的Montgomery模乘算法轉換成代碼在FPGA(Field-Programmable?Gate?Array，現場可編程門陣列)上實現時，不具備并行運算的可能性，幾個乘法的實現形式是串行進行的，它們的運算結果都需要依賴前面計算所得的值，因此在FPGA上實現起來的運算速度慢，導致整個ECC加密算法的效率低，速度低。

發明內容

本發明所要解決的技術問題是，提供一種高效的蒙哥馬利模乘算法，以達到降低系統運行的周期、提高整體模乘效率的效果，使其應用于數據加密算法中時，能夠提高數據加解密的效率和速度。

為解決以上技術問題，本發明實施例提供一種基于蒙哥馬利模乘運算的數據加解密處理方法，包括：

獲取由待處理的數據構成的模冪運算；

將所述模冪運算轉換為模乘運算，根據所述模乘運算的結果獲取所述模冪運算的結果；

根據所述模冪運算的結果獲得處理后的數據；

所述待處理的數據為待加密的明文，所述處理后的數據為密文；或者所述待處理的數據為待解密的密文，所述處理后的數據為明文；

所述模乘運算的實現方法如下：

輸入被乘數A、乘數B、模數P和模數P的逆q，按照蒙哥馬利模乘算法進行運算，輸出模乘結果C；其中，C＝AB2^-nmodP；

以基底2^k來表示整數，按照從數據的低位開始、每k位為一段的拆分方式，分別將A、B、P和q轉換為m維數組，則其中，k是處理器的運算字長；

設置外循環變量i、內循環變量j、中間變量z、t_i和s，所述蒙哥馬利模乘運算的步驟如下：

S01、令C為0；

S02、令外循環變量i為0，開始外循環；

S03、令z為0；

S04、將c₀加上a_i與b₀的乘積，再與q相乘后，求其對模2^k的余數，將結果賦給t_i；

S05、令內循環變量j為0，開始內循環；