[發明專利]一種元素的模逆計算方法及裝置

有效

• 申請號: 201310144914.0
• 申請日: 2013-04-24
• 公開（公告）號: CN104123431B
• 公開（公告）日: 2018-09-14
• 發明（設計）人: 劉娟;林燦偉;明瑞華;王昆;黃洋
• 申請（專利權）人: 國民技術股份有限公司
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 北京律和信知識產權代理事務所(普通合伙) 11446
• 代理人: 武玉琴;項榮

1.一種用于密鑰產生、密碼系統或數字簽名的元素模逆計算裝置，其特征在于，所述裝置被配置為包括初始化單元、奇數模逆計算單元以及模逆處理單元；其中，

所述初始化單元，用于獲取密鑰、密碼或數字簽名的臨時變量X1、X2和遞減變量u、v的初始值，其中，X1、X2的初始值分別為1、0；遞減變量u、v的初始值分別為a、P0；

所述奇數模逆計算單元，用于對密鑰、密碼或數字簽名的臨時變量X1、X2和遞減變量u、v進行迭代計算，其中迭代過程中滿足：a*X1＝u(modP0),a*X2＝v(modP0)；其中，a為元素，也即密鑰、密碼或數字簽名的參數；當a關于P的逆元存在時，X為其逆元，即滿足a*X＝1(modP)；P為模數，P＝P0*2^K；P0為奇數，K為2的指數；

所述模逆處理單元，用于在迭代計算中每完成一次迭代，判斷u、v中是否有一個為1，如u、v中沒有一個是1，繼續迭代計算；如u、v中有一個是1，結束迭代計算；在迭代計算結束后，如u為1，則將X1賦值給X，如v為1，則將X2賦值給X；當K＝0時，判斷X是否大于零，如X大于零，X即為密鑰、密碼或數字簽名的參數a關于P的模逆；如X小于零，X'＝X+P0；其中X'為密鑰、密碼或數字簽名的參數a關于P的模逆。

2.根據權利要求1所述的裝置，其特征在于，所述奇數模逆計算單元具體用于：

獲取u最低字節尾數0的個數ZeroNum，決定本次迭代u右移位數，該u右移位數為ZeroNum，如果ZeroNum大于設定值，令ZeroNum＝設定值，獲取系數n，湊齊X1+n*P0的尾數有ZeroNum個0，對大數u，X1進行迭代更新，u＝u>>ZeroNum,X1＝(X1+n*P0)>>ZeroNum；

或獲取v最低字節尾數0的個數ZeroNum，決定本次迭代v右移位數，該v右移位數為ZeroNum，如果ZeroNum大于設定值，令ZeroNum＝設定值，獲取系數n，湊齊X2+n*P0的尾數有ZeroNum個0，對大數v,X2進行迭代更新，v＝v>>ZeroNum,X2＝(X2+n*P0)>>ZeroNum；

或獲取u-v最低字節尾數0的個數ZeroNum，決定本次迭代u右移位數，該u右移位數為ZeroNum，如果ZeroNum大于設定值，令ZeroNum＝設定值，獲取系數n，湊齊X1+n*P0-X2的尾數有ZeroNum個0，對系數n做越界處理，保證|X1+n*P0-X2|<P0*2^ZeroNum，對大數u,X1進行迭代更新，u＝u>>ZeroNum,X1＝(X1+n*P0-X2)>>ZeroNum；

或獲取v-u最低字節尾數0的個數ZeroNum，決定本次迭代v右移位數，該v右移位數為ZeroNum，如果ZeroNum大于設定值，令ZeroNum＝設定值，獲取系數n，湊齊X2+n*P0-X1的尾數有ZeroNum個0；對系數n做越界處理，保證|X2+n*P0-X1|<P0*2^ZeroNum，對大數v,X2進行迭代更新，v＝v>>ZeroNum,X2＝(X2+n*P0-X1)>>ZeroNum；

所述設定值為大于1的整數。

3.根據權利要求2所述的裝置，其特征在于，所述裝置還包括：

偶數模逆計算單元，用于當K大于0時，獲取K比特的TailInvA，滿足a*TailInvA的最低K比特為00...01，選擇合適的n，將X”＝Y+nP0的最低K比特湊成與TailInvA一樣，則X”為密鑰、密碼或數字簽名的參數a關于P的模逆；其中Y為密鑰、密碼或數字簽名的參數a關于P0的模逆。

4.根據權利要求2或3所述的裝置，其特征在于，所述模逆處理單元包括：控制單元、多個存儲單元和算術運算單元；其中，所述控制單元，用于對模逆計算過程中整個流程的控制；

所述存儲單元，用于存儲大數中間變量；

所述算術運算單元，用于處理模逆運算中的32位比特級所有加法。