[發(fā)明專利]非模數(shù)乘法器、用于非模數(shù)乘法的方法及計算裝置

有效

• 申請?zhí)枺?/td>: 201710137121.4
• 申請日: 2017-03-08
• 公開（公告）號: CN107273089B
• 公開（公告）日: 2020-09-29
• 發(fā)明（設(shè)計）人: 厄瑞·卡路茲尼
• 申請（專利權(quán)）人: 華邦電子股份有限公司
• 主分類號: G06F7/52
• 分類號: G06F7/52
• 代理公司: 中科專利商標代理有限責(zé)任公司 11021
• 代理人: 任巖

本發(fā)明提供了一種非模數(shù)乘法器、用于非模數(shù)乘法的方法及計算裝置，非模數(shù)乘法器包含接口和電路。所述接口經(jīng)配置以接收n位的整數(shù)A和整數(shù)B。所述電路經(jīng)配置以通過執(zhí)行計算序列來計算非模數(shù)乘積(A*B)，且經(jīng)配置以在執(zhí)行所述序列時使得所述乘法器消耗的電力的模式隨機化。所述序列包含：產(chǎn)生隨機數(shù)w；確定取決于數(shù)值R＝2^k(k等于M1和M2的位長)及取決于所述隨機數(shù)w的模數(shù)M1和M2，并計算第一模數(shù)乘積C＝A*B％M1和第二模數(shù)乘積D＝A*B％M2；以及基于所述第一模數(shù)乘積和所述第二模數(shù)乘積產(chǎn)生及輸出所述非模數(shù)乘積(A*B)。

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

本發(fā)明涉及數(shù)據(jù)安全，尤其涉及免受旁信道攻擊的高效非模數(shù)乘法。

背景技術(shù)

多個重要密碼系統(tǒng)(諸如RSA)使用具有大量模數(shù)值的模運算以及非模運算，包含求冪和相乘。計算非模數(shù)乘積的經(jīng)典方法涉及將操作數(shù)劃分為塊或“位(digits)”且將加權(quán)和應(yīng)用于所述位的交叉乘積。然而，此基本乘法方法在多個實際案例中計算上昂貴。

對于模數(shù)乘法(例如，在加密計算中)，慣例為使用被稱為蒙哥馬利模數(shù)乘法(或簡稱為蒙哥馬利乘法)的高效方法。為了執(zhí)行蒙哥馬利乘法，使用已知為蒙哥馬利約簡的算法將操作數(shù)轉(zhuǎn)換成專門的蒙哥馬利形式。蒙哥馬利形式的操作數(shù)的乘法避免了常規(guī)算術(shù)中模約簡的需要(然而如果得到的乘積大于模數(shù)則仍然需要較簡單的條件約簡)。蒙哥馬利約簡和乘法算法例如由Menezes等人描述于應(yīng)用密碼學(xué)手冊(Handbook of AppliedCryptography)(1996)的章節(jié)14.3.2、第600到603頁中，其公開內(nèi)容以引用的方式并入本說明書中。

密碼系統(tǒng)可遭受各種類型的旨在暴露內(nèi)部機密信息的攻擊。在被稱作旁信道攻擊(side channel attack；SCA)的攻擊中，可通過分析執(zhí)行下層加密函數(shù)期間的功率消耗行為推論出機密信息。舉例來說，Amiel等人在標題為“用于機密回收的功率分析和公鑰算法的逆向工程(Power Analysis for Secret Recovering and Reverse Engineering ofPublic Key Algorithms)”的文章中描述應(yīng)用于非模數(shù)乘法計算的差別功率分析(differential power analysis；DPA)攻擊(第14屆國際會議關(guān)于加密中的所選領(lǐng)域的會議記錄(SAC 2007，LNCS，第4876卷，第110至125頁，海德堡施普林格)，其公開內(nèi)容以引入的方式并入本說明書中。

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

根據(jù)本發(fā)明一方面，提供了包含接口和電路的乘法器。所述接口經(jīng)配置以接收n位的整數(shù)A和整數(shù)B。所述電路經(jīng)配置以通過執(zhí)行計算序列來計算非模數(shù)乘積，所述非模數(shù)乘積表示為(A*B)，且經(jīng)配置以在執(zhí)行序列時使得乘法器消耗的電力的模式隨機化，所述序列包括：產(chǎn)生隨機數(shù)w；確定取決于數(shù)值R及取決于所述隨機數(shù)w的模數(shù)M1和模數(shù)M2，其中R＝2^k，k等于所述模數(shù)M1和所述模數(shù)M2的位長，并計算第一模數(shù)乘積C和第二模數(shù)乘積D，其中C＝A*B％M1，D＝A*B％M2，以及基于所述第一模數(shù)乘積C和第二模數(shù)乘積D產(chǎn)生和輸出非模數(shù)乘積。

優(yōu)選地，電路包含蒙哥馬利乘法器，所述蒙哥馬利乘法器經(jīng)配置以計算所述第一模數(shù)乘積C和第二模數(shù)乘積D。

優(yōu)選地，電路經(jīng)配置以：通過計算w*A將所述整數(shù)A轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M1中的A′；通過計算(w-d)*B將所述整數(shù)B轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M2中的B′，d為小于w的整數(shù)；以及通過使用蒙哥馬利乘法器計算各別蒙哥馬利乘積A′⊙B和A⊙B′來計算所述第一模數(shù)乘積C和第二模數(shù)乘積D。

優(yōu)選地，表示為低位部分AB_L和高位部分AB_H的組合而滿足(A*B)＝AB_H*R+AB_L，且電路經(jīng)配置以基于所述第一模數(shù)乘積C和第二模數(shù)乘積D計算所述高位部分AB_H和所述低位部分AB_L。