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

有效

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

本發明適用于計算機及通信技術領域，提供了一種元素的模逆計算方法及裝置，該方法包括：獲取臨時變量X1、X2和遞減變量u、v的初始值，其中，X1、X2的初始值分別為1、0；遞減變量u、v的初始值分別為a、P0；對臨時變量X1、X2和遞減變量u、v進行迭代計算，其中迭代過程中滿足：a*x1=u(mod P0),a*x2=v(mod P0)；在迭代計算中每完成一次迭代，判斷u、v中是否有一個為1，如u、v中沒有一個是1，繼續迭代計算；如u、v中有一個是1，結束迭代計算；在迭代計算結束后，如u為1，則將X1賦值給X，如v為1，則將X2賦值給X；當K=0時，判斷X是否大于零，如X大于零，X即為a關于P的模逆。本發明提供的技術方案具有計算速度快，計算資源需求少的優點。

技術領域

本發明屬于計算機及通信電子領域，尤其涉及一種元素的模逆計算方法及裝置。

背景技術

隨著計算機網絡技術和通信技術的發展，對元素求其模逆的問題應用越來越廣泛。譬如，RSA算法中的密鑰的產生，橢圓曲線公鑰密碼系統和數字簽名方案中，在選擇仿射坐標系的情況下,也需要頻繁地用到模逆運算。目前，通常元素的模逆計算方法一般有三種：費馬定理方法，蒙哥馬利模逆方法和二進制擴展歐幾里得算法。費馬定理不適合模逆不存在的情形，二進制擴展歐幾里得算法是目前已公布的速度最快的算法。但是二進制擴展歐幾里得算法的速度仍然很慢，且資源需求較大。

發明內容

本發明實施例的目的在于提供一種元素的模逆計算方法，旨在解決通過現有技術中計算速度慢，資源需求大的問題。

本發明實施例是這樣實現的，一種元素的模逆計算方法，所述方法包括：

獲取臨時變量X1、X2和遞減變量u、v的初始值，其中，X1、X2的初始值分別為1、0；遞減變量u、v的初始值分別為a、P0；

對臨時變量X1、X2和遞減變量u、v進行迭代計算，其中迭代過程中滿足：a*x1=u(mod P0),a*x2=v(mod P0)；其中，a為元素，當a關于P的逆元存在時，X為其逆元，即滿足a*x=1(mod P)，；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的模逆。

可選的，所述對臨時變量X1、X2和遞減變量u、v進行迭代計算具體包括：

獲取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。