[發(fā)明專利]一種實(shí)現(xiàn)SM2密碼體制的大整數(shù)求乘逆方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310281880.X
• 申請(qǐng)日: 2013-07-05
• 公開(kāi)（公告）號(hào): CN103389965A
• 公開(kāi)（公告）日: 2013-11-13
• 發(fā)明（設(shè)計(jì)）人: 蔣聲障;張登峰;余杭軍
• 申請(qǐng)（專利權(quán)）人: 福建升騰資訊有限公司
• 主分類號(hào): G06F17/11
• 分類號(hào): G06F17/11
• 代理公司: 福州市鼓樓區(qū)京華專利事務(wù)所(普通合伙) 35212
• 代理人: 宋連梅

1.一種實(shí)現(xiàn)SM2密碼體制的大整數(shù)求乘逆方法，其特征在于：包括：

整數(shù)寄存器：用于存儲(chǔ)大整數(shù)a的值，且在一次求乘逆運(yùn)算過(guò)程中，a的值保持不變；

模值寄存器：用于存儲(chǔ)模值n，模值寄存器中的數(shù)據(jù)在SM2算法運(yùn)算過(guò)程中保持不變；

方程系數(shù)寄存器一：用于存儲(chǔ)方程一未知數(shù)系數(shù)的數(shù)據(jù)C1；

方程系數(shù)寄存器二：用于存儲(chǔ)方程二未知數(shù)系數(shù)的數(shù)據(jù)C2；

方程常量寄存器一：用于存儲(chǔ)方程一常量的數(shù)據(jù)V1；

方程常量寄存器二：用于存儲(chǔ)方程二常量的數(shù)據(jù)V2；

移位數(shù)據(jù)寄存器：用于存儲(chǔ)待右移的數(shù)據(jù)D；

計(jì)算連續(xù)比特0個(gè)數(shù)模塊：用于計(jì)算移位數(shù)據(jù)寄存器的數(shù)據(jù)D以二進(jìn)制表示時(shí)，從最低位開(kāi)始連續(xù)比特0的位數(shù)k；

移位位數(shù)寄存器：用于存儲(chǔ)所述位數(shù)k；

有限域移位模塊：用于將二進(jìn)制的所述數(shù)據(jù)D，依據(jù)所述位數(shù)k的值進(jìn)行連續(xù)k次的右移1位運(yùn)算；每次右移1位運(yùn)算時(shí)，對(duì)二進(jìn)制的所述數(shù)據(jù)D進(jìn)行判斷，當(dāng)二進(jìn)制的所述數(shù)據(jù)D最低位為0時(shí)，則將二進(jìn)制的所述數(shù)據(jù)D的該次右移1位運(yùn)算后的結(jié)果記為數(shù)據(jù)D1；當(dāng)二進(jìn)制的所述數(shù)據(jù)D的最低位為1時(shí)，則將二進(jìn)制的所述數(shù)據(jù)D與二進(jìn)制的所述模值n二者相加的和進(jìn)行右移1位運(yùn)算后的結(jié)果記為數(shù)據(jù)D1；且將第1至第k－1次的右移1位運(yùn)算后所產(chǎn)生出的所述數(shù)據(jù)D1記為下一次右移1位運(yùn)算的所述數(shù)據(jù)D；

移位結(jié)果寄存器：用于存儲(chǔ)所述數(shù)據(jù)D1；

被加數(shù)寄存器：用于存儲(chǔ)一被加數(shù)值A(chǔ)DD1；

加數(shù)寄存器：用于存儲(chǔ)一加數(shù)值A(chǔ)DD2；

有限域加法模塊：用于將被加數(shù)值A(chǔ)DD1與加數(shù)值A(chǔ)DD2相加；當(dāng)ADD1+ADD2>=n時(shí)，將ADD1+ADD2－n的結(jié)果記為數(shù)據(jù)ADD；當(dāng)ADD1+ADD2<n時(shí)，將ADD1+ADD2的結(jié)果記為數(shù)據(jù)ADD；

加法結(jié)果寄存器：用于存儲(chǔ)所述數(shù)據(jù)ADD；

被減數(shù)寄存器：用于存儲(chǔ)被減數(shù)值SUB1；

減數(shù)寄存器：用于存儲(chǔ)減數(shù)值SUB2；

有限域減法模塊：用于將被減數(shù)值SUB1與減數(shù)值SUB2相減；當(dāng)SUB1>=SUB2時(shí)，將SUB1-SUB2的結(jié)果記為數(shù)據(jù)SUB；當(dāng)SUB1<SUB2時(shí)，將n+SUB1－SUB2的結(jié)果記為數(shù)據(jù)SUB；

減法結(jié)果寄存器：用于存儲(chǔ)所述數(shù)據(jù)SUB

方程系數(shù)比較模塊：用于比較C1和C2的大小；當(dāng)C1>=C2時(shí)，輸出一表示TRUE的狀態(tài)值bCmp；當(dāng)C1<C2時(shí)，輸出一表示FALSE的狀態(tài)值bCmp；

系數(shù)比較結(jié)果寄存器：用于存儲(chǔ)所述狀態(tài)值bCmp；所述狀態(tài)值bCmp僅表示TRUE或FALSE任一種；

分支判斷模塊：用于判斷所述數(shù)據(jù)C1和所述數(shù)據(jù)C2兩者于二進(jìn)制表示中的低第2位的值；當(dāng)所述數(shù)據(jù)C1的低第2位的值等于所述數(shù)據(jù)C2的低第2位的值時(shí)，輸出一表示FALSE的狀態(tài)值bAdd；當(dāng)所述數(shù)據(jù)C1的低第2位的值不等于所述數(shù)據(jù)C2的低第2位的值時(shí)，輸出一表示TRUE的狀態(tài)值bAdd；

分支判斷結(jié)果寄存器：用于存儲(chǔ)所述狀態(tài)值bAdd，所述狀態(tài)值bAdd僅表示TRUE或FALSE任一種；

循環(huán)結(jié)束條件判斷模塊：用于判斷循環(huán)運(yùn)算結(jié)果；當(dāng)所述數(shù)據(jù)C1=1，將所述數(shù)據(jù)V1記為所述大整數(shù)a的乘逆運(yùn)算值r，且輸出一表示TRUE的狀態(tài)值bRoop；當(dāng)所述數(shù)據(jù)C2=1，將所述數(shù)據(jù)V2記為所述大整數(shù)a的乘逆運(yùn)算值r，且輸出一表示TRUE的狀態(tài)值bRoop；當(dāng)所述數(shù)據(jù)C1和數(shù)據(jù)C2均不等于1時(shí)，輸出一表示FALSE的狀態(tài)值bRoop；

輸出結(jié)果寄存器：用于存儲(chǔ)乘逆運(yùn)算值r；

循環(huán)結(jié)束條件判斷結(jié)果寄存器：用于存儲(chǔ)所述狀態(tài)值bRoop，所述狀態(tài)值bRoop僅表示TRUE或FALSE任一種；

方程一化簡(jiǎn)模塊：用于化簡(jiǎn)所述數(shù)據(jù)C1，使所述數(shù)據(jù)C1轉(zhuǎn)化為奇數(shù)；將所述數(shù)據(jù)C1輸入至移位數(shù)據(jù)寄存器；先執(zhí)行所述計(jì)算連續(xù)比特0個(gè)數(shù)模塊，后執(zhí)行所述有限域移位模塊；將所述數(shù)據(jù)D1覆蓋輸入至方程系數(shù)寄存器一；將所述數(shù)據(jù)V1輸入至移位數(shù)據(jù)寄存器；執(zhí)行所述有限域移位模塊；將所述數(shù)據(jù)D1覆蓋輸入至方程常量寄存器一；

方程二化簡(jiǎn)模塊：用于化簡(jiǎn)所述數(shù)據(jù)C2，使所述數(shù)據(jù)C2轉(zhuǎn)化為奇數(shù)；將所述數(shù)據(jù)C2輸入至移位數(shù)據(jù)寄存器；先執(zhí)行所述計(jì)算連續(xù)比特0個(gè)數(shù)模塊，后執(zhí)行所述有限域移位模塊；將所述數(shù)據(jù)D1覆蓋輸入至方程系數(shù)寄存器一；將所述數(shù)據(jù)V1輸入至移位數(shù)據(jù)寄存器；執(zhí)行所述有限域移位模塊；將所述數(shù)據(jù)D1覆蓋輸入至方程常量寄存器一；

輸出模塊：用于將所述輸出結(jié)果寄存器中的乘逆運(yùn)算值r輸出；

該方法具體包括如下步驟：

步驟10、進(jìn)行初始化；將所述模值n存儲(chǔ)至所述模值寄存器；

步驟20、將大整數(shù)a存儲(chǔ)至整數(shù)寄存器；

步驟30、將所述大整數(shù)a存儲(chǔ)至所述方程系數(shù)寄存器一；將一數(shù)值1存儲(chǔ)至所述方程常量寄存器一；將所述模值n存儲(chǔ)至所述方程系數(shù)寄存器二；將一數(shù)值0存儲(chǔ)至所述方程常量寄存器二；

步驟40、執(zhí)行所述方程一化簡(jiǎn)模塊；

步驟50、執(zhí)行循環(huán)運(yùn)算；執(zhí)行所述循環(huán)結(jié)束條件判斷模塊；當(dāng)循環(huán)結(jié)束條件判斷結(jié)果寄存器中的狀態(tài)值bRoop表示TRUE時(shí)，則終止循環(huán)，進(jìn)入步驟60；當(dāng)環(huán)結(jié)束條件判斷結(jié)果寄存器中的狀態(tài)值bRoop表示FALSE時(shí)，進(jìn)入步驟51；

步驟51、執(zhí)行所述方程系數(shù)比較模塊；

步驟52、執(zhí)行所述分支判斷結(jié)果寄存器判斷；當(dāng)所述分支判斷結(jié)果寄存器中的狀態(tài)值bAdd表示TRUE時(shí)，進(jìn)入步驟53；當(dāng)所述分支判斷結(jié)果寄存器中的狀態(tài)值bAdd表示FALSE時(shí)，進(jìn)入步驟54；

步驟53、將所述數(shù)據(jù)C1、數(shù)據(jù)C2分別輸入至所述被加數(shù)寄存器、加數(shù)寄存器后，執(zhí)行所述有限域加法模塊；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示TRUE時(shí)，將所述加法結(jié)果寄存器中的數(shù)據(jù)ADD覆蓋輸入至所述數(shù)據(jù)C1；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示FALSE時(shí)，將所述加法結(jié)果寄存器中的數(shù)據(jù)ADD覆蓋輸入所述數(shù)據(jù)至C2；

將所述數(shù)據(jù)V1、數(shù)據(jù)V2分別輸入至所述被加數(shù)寄存器、加數(shù)寄存器后，執(zhí)行所述有限域加法模塊；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示TRUE時(shí)，將所述加法結(jié)果寄存器中的數(shù)據(jù)ADD覆蓋輸入至所述數(shù)據(jù)V1；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示FALSE時(shí)，將所述加法結(jié)果寄存器中的數(shù)據(jù)ADD覆蓋輸入至所述數(shù)據(jù)V2；進(jìn)入步驟55；

步驟54、當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示TRUE時(shí)，將所述數(shù)據(jù)C1、數(shù)據(jù)C2分別輸入至所述被減數(shù)寄存器、減數(shù)寄存器后，執(zhí)行所述有限域減法模塊；將所述減法結(jié)果寄存器中的數(shù)據(jù)SUB覆蓋輸入至所述數(shù)據(jù)C1；將所述數(shù)據(jù)V1、數(shù)據(jù)V2分別輸入至所述被減數(shù)寄存器、減數(shù)寄存器后，執(zhí)行所述有限域減法模塊；將所述減法結(jié)果寄存器中的數(shù)據(jù)SUB覆蓋輸入至所述數(shù)據(jù)V1；進(jìn)入步驟55；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示FALSE時(shí)，將所述數(shù)據(jù)C2、數(shù)據(jù)C1分別輸入至所述被減數(shù)寄存器、減數(shù)寄存器后，執(zhí)行所述有限域減法模塊；將所述減法結(jié)果寄存器中的數(shù)據(jù)SUB覆蓋輸入至所述數(shù)據(jù)C2；將所述數(shù)據(jù)V2、數(shù)據(jù)V1分別輸入至所述被減數(shù)寄存器、減數(shù)寄存器后，執(zhí)行有限域減法模塊；將所述減法結(jié)果寄存器中的數(shù)據(jù)SUB覆蓋輸入至所述數(shù)據(jù)V2；進(jìn)入步驟55；

步驟55、當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示TRUE時(shí)，執(zhí)行所述方程一化簡(jiǎn)模塊，返回步驟50；

當(dāng)所述系數(shù)比較結(jié)果寄存器中的狀態(tài)值bCmp表示FALSE時(shí)，執(zhí)行所述方程二化簡(jiǎn)模塊，返回步驟50；

步驟60、執(zhí)行所述輸出模塊。