[發(fā)明專利]一種RSA算法數(shù)字簽名方法

有效

• 申請?zhí)枺?/td>: 201010622313.2
• 申請日: 2010-12-27
• 公開（公告）號: CN102571342A
• 公開（公告）日: 2012-07-11
• 發(fā)明（設(shè)計）人: 汪濤;范楠迪;馬寧
• 申請（專利權(quán)）人: 北京中電華大電子設(shè)計有限責(zé)任公司
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L9/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域：

本發(fā)明主要應(yīng)用于智能卡安全計算領(lǐng)域。

背景技術(shù)：

RSA私鑰運算主要涉及到兩個關(guān)鍵技術(shù)：

1.使用蒙哥馬利模乘算法：

記蒙哥馬利模乘為MonMul(a，b，m)，則：

MonMul(a，b，m)＝a*b*R^-1mod?m，其中a，b，m的位長為L，R＝2^L，R^-1滿足R^-1*R?modm＝1，mod為取模運算。

2.使用中國剩余定理進行加速：

記RSA私鑰運算的輸入數(shù)據(jù)為C，RSA的私鑰參數(shù)為p，q，d和n，其中p和q的位長為L/2，d和n的位長為L，則RSA私鑰運算Cd?mod?n，通過中國剩余定義可以轉(zhuǎn)化為關(guān)于p和q的模冪運算，提高運行速度。以下是使用中國剩余定理進行RSA私鑰運算的簡要說明，本發(fā)明主要是對其中的參數(shù)Cp和Cq計算方法的改進。

準(zhǔn)備：計算參數(shù)dp＝d?mod(p-1)，dq＝d?mod(q-1)和qInv，qInv滿足qInv*q?modp＝1。當(dāng)RSA體系中的密鑰固定時，這些參數(shù)可以作為常數(shù)預(yù)先計算出來，不必在每次進行RSA私鑰運算時進行計算，因此計算上述參數(shù)不占用RSA私鑰運算的時間，只是為了敘述方便，在這里簡單介紹上述參數(shù)的來由。

1.計算Cp和Cq，Cp＝C?mod?p，Cq＝C?mod?q，其中C為RSA私鑰運算的輸入數(shù)據(jù)。

2.計算Mp和Mq，其中Mp＝Cp^dp?mod?p，Mq＝Cp^dq?mod?q

3.計算Mpq，Mpq＝(Mp-Mq)*qInv?mod?p

4.計算Res＝Mpq*q+Mq。

在步驟1中的取模運算中，由于軟件取模函數(shù)計算效率低下，所以一般情況下使用硬件蒙哥馬利模乘計算器計算。但是在實際應(yīng)用中，上述中國剩余定理的計算過程中，步驟2和3中使用L/2位長的蒙哥馬利模乘器可以滿足需求，而在步驟1和4中，需使用L位長的硬件蒙哥馬利模乘器。

發(fā)明內(nèi)容：

本發(fā)明在步驟1和步驟4中使用L/2位長的蒙哥馬利模乘器進行計算，因此可以在只需RSA私鑰運算的芯片中采用小位長的模乘器，實現(xiàn)大于模乘器位長的公鑰運算，以這種方式運算，對硬件的要求就減少一半位數(shù)，不考慮其他資源，小位長硬件協(xié)處理器可支持大于模乘器位長的私鑰運算，同時，增添的軟件開銷也可以在應(yīng)用接受的范圍內(nèi)。從而降低芯片成本，或者使用現(xiàn)有的有限資源應(yīng)對市場變化，有助于產(chǎn)品快速上市。

步驟1中計算C?mod?P時使用以下方法：

1.將C分為等長度的兩個部分，記CH為高L/2部分，CL為低L/2部分，這樣，L長度的C被拆分為兩個L/2長度的數(shù)據(jù)，并且C＝CH＜＜L/2+CL，其中“＜＜”為向左平移操作。

2.進一步分析CH＜＜L/2，L/2長度的CH向左平移L/2后，還是L長度，超出了蒙哥馬利模乘器計算長度，因此此處還需要將轉(zhuǎn)換，其實，CH＜＜L/2＝CH*2^L/2。我們可以看到這里的2^L/2是L/2位長的蒙哥馬利模乘算法中的常數(shù)R。

3.那么C?mod?P可表示為(CH*R+CL)mod?P，將括號展開后，可得到CH*R?mod?P+CL?mod?P。其中CL和P的長度一樣，其取模操作可以用減法實現(xiàn)，記為CLP。

4.由于MonMul(a，b，m)＝a*b*R^-1mod?m，那么只需計算MonMul(CH，R²，p)，就可以得到CH*R?mod?P，也即CH＜＜L/2mod?P，記為CHP。

5.最后計算CHP+CLP即所需的C?mod?P，用同樣的方法，計算C?mod?Q。

步驟4中使用蒙哥馬利算法計算乘法，由于最終結(jié)果是L長度，因此需要將Mpq和q的高位補“0”填充至L長，然后使用L位長的蒙哥馬利模乘器計算乘法，此時，MonMul(a，b，m)中m＝2^L-1，長度為L。改進的方法如下：

1.將Mpq和Q作為a*b的輸入數(shù)據(jù)，將L/2位長的a和b拆分為等長度的兩部分，其中aH表示a的高L/4部分，aL表示a的低L/4部分，bH表示b的高L/4部分，bL表示b的低L/4部分。