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

有效

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

1.一種非模數(shù)乘法器，其特征在于，包括：

接口，其經(jīng)配置以接收n位的整數(shù)A和整數(shù)B；以及

電路，其經(jīng)配置以通過(guò)執(zhí)行計(jì)算序列來(lái)計(jì)算非模數(shù)乘積，所述非模數(shù)乘積表示為A*B，且經(jīng)配置以在執(zhí)行所述序列時(shí)使得所述非模數(shù)乘法器消耗的電力的模式隨機(jī)化，所述序列包括：

產(chǎn)生隨機(jī)數(shù)w；

確定取決于數(shù)值R及取決于所述隨機(jī)數(shù)w的模數(shù)M1和模數(shù)M2，其中R＝2^k，k等于所述模數(shù)M1和所述模數(shù)M2的位長(zhǎng)，并計(jì)算第一模數(shù)乘積C和第二模數(shù)乘積D，其中C＝A*B％M1，D＝A*B％M2；以及

基于所述第一模數(shù)乘積C和所述第二模數(shù)乘積D產(chǎn)生及輸出所述非模數(shù)乘積，

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

2.根據(jù)權(quán)利要求1所述的非模數(shù)乘法器，其中，所述電路經(jīng)配置以：通過(guò)計(jì)算w*A將所述整數(shù)A轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M1中的A'；通過(guò)計(jì)算(w-d)*B將所述整數(shù)B轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M2中的B'，其中d為小于w的整數(shù)；以及通過(guò)使用所述蒙哥馬利乘法器計(jì)算各別蒙哥馬利乘積A'⊙B和A⊙B'來(lái)計(jì)算所述第一模數(shù)乘積C和所述第二模數(shù)乘積D。

3.根據(jù)權(quán)利要求1所述的非模數(shù)乘法器，其中，A*B表示為低位部分AB_L和高位部分AB_H的組合而滿足A*B＝AB_H*R+AB_L，且其中所述電路經(jīng)配置以基于所述第一模數(shù)乘積C和所述第二模數(shù)乘積D計(jì)算所述高位部分AB_H和所述低位部分AB_L。

4.根據(jù)權(quán)利要求3所述的非模數(shù)乘法器，其中，所述電路經(jīng)配置以根據(jù)AB_H＝(C-D)/d計(jì)算所述高位部分AB_H，其中d為用于將所述整數(shù)B轉(zhuǎn)換為蒙哥馬利域的整數(shù)，且經(jīng)配置以根據(jù)AB_L＝C-w*AB_H計(jì)算所述低位部分AB_L。

5.根據(jù)權(quán)利要求1所述的非模數(shù)乘法器，其中，所述電路經(jīng)配置以根據(jù)M1＝R-w確定所述模數(shù)M1，且經(jīng)配置以根據(jù)M2＝R-(w-d)確定所述模數(shù)M2，其中d為小于所述隨機(jī)數(shù)w的整數(shù)。

6.一種用于非模數(shù)乘法的方法，其特征在于，包括：

接收n位的整數(shù)A和整數(shù)B；及

使用乘法器通過(guò)執(zhí)行計(jì)算序列來(lái)計(jì)算非模數(shù)乘積，所述非模數(shù)乘積表示為A*B，且在執(zhí)行所述序列時(shí)使得所述乘法器消耗的電力的模式隨機(jī)化，所述序列包括：

產(chǎn)生隨機(jī)數(shù)w；

確定取決于數(shù)值R及取決于所述隨機(jī)數(shù)w的模數(shù)M1和模數(shù)M2，其中，R＝2^k，k等于所述模數(shù)M1和所述模數(shù)M2的位長(zhǎng)，并計(jì)算第一模數(shù)乘積C和第二模數(shù)乘積D，其中C＝A*B％M1，D＝A*B％M2；以及

基于所述第一模數(shù)乘積C和所述第二模數(shù)乘積D產(chǎn)生及輸出所述非模數(shù)乘積，

其中，計(jì)算所述第一模數(shù)乘積C和所述第二模數(shù)乘積D包括使用蒙哥馬利乘法器計(jì)算所述第一模數(shù)乘積C和所述第二模數(shù)乘積D。

7.根據(jù)權(quán)利要求6所述的用于非模數(shù)乘法的方法，其中，計(jì)算所述第一模數(shù)乘積C和所述第二模數(shù)乘積D包括：通過(guò)計(jì)算w*A將所述整數(shù)A轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M1中的A'；通過(guò)計(jì)算(w-d)*B將所述整數(shù)B轉(zhuǎn)換為蒙哥馬利域的所述模數(shù)M2中的B'，其中d為小于w的整數(shù)；以及通過(guò)使用所述蒙哥馬利乘法器計(jì)算各別蒙哥馬利乘積A'⊙B和A⊙B'來(lái)計(jì)算所述第一模數(shù)乘積C和所述第二模數(shù)乘積D。

8.根據(jù)權(quán)利要求6所述的用于非模數(shù)乘法的方法，其中，A*B表示為低位部分AB_L和高位部分AB_H的組合而滿足A*B＝AB_H*R+AB_L，且包括基于所述第一模數(shù)乘積C和所述第二模數(shù)乘積D計(jì)算所述高位部分AB_H和所述低位部分AB_L。