[發明專利]一種實現SM2密碼體制的大整數求乘逆方法

有效

• 申請號: 201310281880.X
• 申請日: 2013-07-05
• 公開（公告）號: CN103389965A
• 公開（公告）日: 2013-11-13
• 發明（設計）人: 蔣聲障;張登峰;余杭軍
• 申請（專利權）人: 福建升騰資訊有限公司
• 主分類號: G06F17/11
• 分類號: G06F17/11
• 代理公司: 福州市鼓樓區京華專利事務所(普通合伙) 35212
• 代理人: 宋連梅

技術領域

本發明具體涉及一種實現SM2密碼體制的大整數求乘逆方法。

背景技術

在SM2密碼體制等金融安全相關領域，大數的求乘逆運算速度以及運算所需要的內存空間，直接影響了金融產品的使用性能及限制了部分應用范圍，可能還間接地影響金融產品的成本。目前業內公認擴展的歐幾里德算法為最快的求乘逆方法；為了滿足需求今后的加密需求，需要速度更快且內存消耗低的大整數求乘逆方法。

發明內容

本發明要解決的技術問題，在于提供一種實現SM2密碼體制的大整數求乘逆方法，速度快且耗內存小。

本發明是這樣實現的：一種實現SM2密碼體制的大整數求乘逆方法，包括：

整數寄存器：用于存儲大整數a的值，且在一次求乘逆運算過程中，a的值保持不變；

模值寄存器：用于存儲模值n，模值寄存器中的數據在SM2算法運算過程中保持不變；

方程系數寄存器一：用于存儲方程一未知數系數的數據C1；

方程系數寄存器二：用于存儲方程二未知數系數的數據C2；

方程常量寄存器一：用于存儲方程一常量的數據V1；

方程常量寄存器二：用于存儲方程二常量的數據V2；

移位數據寄存器：用于存儲待右移的數據D；

計算連續比特0個數模塊：用于計算移位數據寄存器的數據D以二進制表示時，從最低位開始連續比特0的位數k；

移位位數寄存器：用于存儲所述位數k；

有限域移位模塊：用于將二進制的所述數據D，依據所述位數k的值進行連續k次的右移1位運算；每次右移1位運算時，對二進制的所述數據D進行判斷，當二進制的所述數據D最低位為0時，則將二進制的所述數據D的該次右移1位運算后的結果記為數據D1；當二進制的所述數據D的最低位為1時，則將二進制的所述數據D與二進制的所述模值n二者相加的和進行右移1位運算后的結果記為數據D1；且將第1至第k－1次的右移1位運算后所產生出的所述數據D1記為下一次右移1位運算的所述數據D；

移位結果寄存器：用于存儲所述數據D1；

被加數寄存器：用于存儲一被加數值ADD1；

加數寄存器：用于存儲一加數值ADD2；

有限域加法模塊：用于將被加數值ADD1與加數值ADD2相加；當ADD1+ADD2>=n時，將ADD1+ADD2－n的結果記為數據ADD；當ADD1+ADD2<n時，將ADD1+ADD2的結果記為數據ADD；

加法結果寄存器：用于存儲所述數據ADD；

被減數寄存器：用于存儲被減數值SUB1；

減數寄存器：用于存儲減數值SUB2；

有限域減法模塊：用于將被減數值SUB1與減數值SUB2相減；當SUB1>=SUB2時，將SUB1-SUB2的結果記為數據SUB；當SUB1<SUB2時，將n+SUB1－SUB2的結果記為數據SUB；

減法結果寄存器：用于存儲所述數據SUB

方程系數比較模塊：用于比較C1和C2的大??；當C1>=C2時，輸出一表示TRUE的狀態值bCmp；當C1<C2時，輸出一表示FALSE的狀態值bCmp；

系數比較結果寄存器：用于存儲所述狀態值bCmp；所述狀態值bCmp僅表示TRUE或FALSE任一種；

分支判斷模塊：用于判斷所述數據C1和所述數據C2兩者于二進制表示中的低第2位的值；當所述數據C1的低第2位的值等于所述數據C2的低第2位的值時，輸出一表示FALSE的狀態值bAdd；當所述數據C1的低第2位的值不等于所述數據C2的低第2位的值時，輸出一表示TRUE的狀態值bAdd；

分支判斷結果寄存器：用于存儲所述狀態值bAdd，所述狀態值bAdd僅表示TRUE或FALSE任一種；

循環結束條件判斷模塊：用于判斷循環運算結果；當所述數據C1=1，將所述數據V1記為所述大整數a的乘逆運算值r，且輸出一表示TRUE的狀態值bRoop；當所述數據C2=1，將所述數據V2記為所述大整數a的乘逆運算值r，且輸出一表示TRUE的狀態值bRoop；當所述數據C1和數據C2均不等于1時，輸出一表示FALSE的狀態值bRoop；

輸出結果寄存器：用于存儲乘逆運算值r；

循環結束條件判斷結果寄存器：用于存儲所述狀態值bRoop，所述狀態值bRoop僅表示TRUE或FALSE任一種；