[發(fā)明專利]一種基于硬件設(shè)計的有限域求逆的方法及裝置

無效

• 申請?zhí)枺?/td>: 200810066915.7
• 申請日: 2008-04-28
• 公開（公告）號: CN101572602A
• 公開（公告）日: 2009-11-04
• 發(fā)明（設(shè)計）人: 陳婧;蔣俊潔;王石;鄧小鐵
• 申請（專利權(quán)）人: 陳婧;蔣俊潔;王石;鄧小鐵
• 主分類號: H04L9/30
• 分類號: H04L9/30;G06F7/72
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司
• 代理人: 劉 健;黃韌敏

1、一種基于硬件設(shè)計的有限域求逆的方法，應(yīng)用于橢圓曲線加密系統(tǒng)，其特征在于，所述方法包括步驟如下：

A、將有限域GF(p^m)內(nèi)一元素多項式a作為輸入元素a，并定義一不可約多項式f(x)，其中a＝a_m-1x^m-1+a_m-2x^m-2+...+a₁x+a₀，f(x)＝x^m+f_m-1x^m-1+...+f₁x+f₀，a_i和f_i分別為輸入元素a和不可約多項式f(x)的系數(shù)，m為正整數(shù)，而x屬于f(x)的自變量；

B、所述輸入元素a與不可約多項式f(x)反復(fù)乘以或除以x²并相加，在m次循環(huán)后，輸出該輸入元素a的乘法逆元a^-1。

2、根據(jù)權(quán)利要求1所述的方法，其特征在于，所述步驟B進一步包括：

將多項式變量S、R、U、V分別初始化為f、a、1和0，將變量δ初始化為0；根據(jù)所述變量S和R的最高兩組系數(shù)r_mr_m-1、s_ms_m-1的值，計算中間變量q與e；然后根據(jù)控制信號r_m、r_m-1、δ₀、δ₁、e以及i來計算所述四個變量S、R、U、V，其在一個時鐘周期內(nèi)完成計算，在下一個時鐘周期將四個變量S、R、U、V的值更新，在m次循環(huán)后，輸出該輸入元素a的乘法逆元a^-1。

3、根據(jù)權(quán)利要求2所述的方法，其特征在于，所述步驟B進一步包括：

B1、將變量S、R、U、V和δ分別初始化為f、a、1和0；中間變量q、e、temp1和temp2分別初始化為0；

B2、對i從0到m-1的范圍，執(zhí)行以下步驟：

B3、計算中間變量q＝s_m和e＝s_m-1-s_mr_m-1，其中s_m和s_m-1分別為變量S的最高位系數(shù)和次高位系數(shù)，r_m-1則為變量R的次高位系數(shù)；

B4、計算中間變量T＝S-s_mR；

B5、計算中間變量W＝V-s_mU；

B6、如果變量R的最高位系數(shù)r_m對應(yīng)為GF(p)元素1，執(zhí)行以下步驟：

B7、如果變量δ的最低兩位是都是0，并且變量e的值對應(yīng)GF(p)的元素0，則執(zhí)行以下子步驟B7a～B7h：

B7a)用R的值代替temp1的值；

B7b)計算x²T，將結(jié)果代替R的值；

B7c)用temp1的值代替S的值；

B7d)用U的值代替temp2的值；

B7e)計算xW?mod?f，將結(jié)果代替W的值；

B7f)重復(fù)子步驟B7e，用W的值代替U的值；

B7g)用temp2的值代替V的值；

B7h)用δ+2代替δ；

B8、如果變量δ的最低兩位是都是0，并且變量e的值對應(yīng)GF(p)的元素1，則執(zhí)行以下子步驟B8a～B8f：

B8a)計算xR-x²eT，將結(jié)果代替temp1的值；

B8b)計算xT，將結(jié)果代替R的值；

B8c)用temp1的值代替S的值；

B8d)計算U-e(xW?mod?f)，將結(jié)果代替temp2的值；

B8e)用W的值代替U的值；

B8f)用temp2的值代替V的值；

B9、如果變量δ的最低位和次低位分別為1和0，則執(zhí)行以下子步驟B9a～B9f：

B9a)用R的值代替temp1的值；

B9b)計算x²T-x(eR)，將結(jié)果代替R的值；

B9c)用temp1的值代替S的值；

B9d)計算U/x?mod?f，將結(jié)果代替temp2的值；

B9e)計算x(W-e·temp2)mod?f，將結(jié)果代替U的值；

B9f)用temp2的值代替V的值；

B10、如果變量δ的最低位和次低位分別為1和1，則執(zhí)行以下子步驟B10a～B10e：

B10a)計算x²T-x(e·R)，將結(jié)果代替S的值；

B10b)計算U/x?mod?f，將結(jié)果代替temp1的值；

B10c)計算W-e·temp1，將結(jié)果代替V的值；

B10d)重復(fù)子步驟B10b，將temp1的值代替U的值；

B10e)用δ-2代替δ；

B11、如果變量R的最高位系數(shù)r_m和次高位系數(shù)r_m-1皆對應(yīng)GF(p)的元素0，執(zhí)行以下子步驟B11a～B11d：

B11a)計算x²R，將結(jié)果代替R的值；

B11b)計算xU?mod?f，將結(jié)果代替U的值；

B11c)重復(fù)子步驟B11b；

B11d)用δ+2代替δ；

B12、如果變量R的最高位系數(shù)r_m和次高位系數(shù)r_m-1分別對應(yīng)GF(p)的元素0和1，執(zhí)行以下子步驟B12a～B12d：

B12a)計算xR，將結(jié)果代替R的值；

B12b)計算xT，將結(jié)果代替S的值；

B12c)計算xU?mod?f，將結(jié)果代替temp1的值；

B12d)計算V-q·temp1，將結(jié)果代替V的值；

B13、循環(huán)計數(shù)器的計數(shù)i增加一位，當i小于m-1時，返回步驟B2；

B14、計數(shù)m次，即i等于m-1時，有限域GF(p^m)的求逆運算結(jié)束，輸出值為輸入元素a的乘法逆元a^-1。