[發明專利]一種RSA電路結構及RSA加密方法

有效

• 申請號: 201710358249.3
• 申請日: 2017-05-19
• 公開（公告）號: CN107169380B
• 公開（公告）日: 2020-01-07
• 發明（設計）人: 張奇惠;曹健;于敦山;曹喜信;張興
• 申請（專利權）人: 北京大學
• 主分類號: G06F21/72
• 分類號: G06F21/72
• 代理公司: 11360 北京萬象新悅知識產權代理有限公司
• 代理人: 賈曉玲

1.一種RSA加密電路結構，其特征在于，包括移位器、選擇器和模乘器，選擇器與移位器和模乘器分別相連，其中：

移位器，用于完成對輸入冪指數的右移移位操作，并使用原始冪指數輸入或者其移位后輸出的最低位作為選擇器的選擇信號；

選擇器，用于在原始冪指數輸入或者其右移后輸出的最低位的控制下，選擇第一次模乘/模冪及其之后每次模乘/模冪的輸入；

模乘器，用于對原始輸入模和選擇器的輸出進行RSA算法的模乘/模冪操作，除了最后一次的模乘/模冪輸出作為最終的加密密文外，其他各次模乘/模冪的輸出反饋給選擇器作為下一次模乘/模冪的輸入；

其中，所述選擇器采用4個同步2輸入選擇器，其中：第一選擇器和第三選擇器，以原始冪指數輸入的最低位作為選擇信號；第二選擇器和第四選擇器，以原始冪指數輸入右移后輸出的最低位作為選擇信號；當選擇信號分別為1或0時，第一選擇器選擇原始明文或1作為第一次模乘/模冪的輸入；第三選擇器選擇1或原始明文作為第一次模乘/模冪的輸入；當進行第一次模乘/模冪時，如果選擇信號為1，則第一選擇器選擇原始明文作為第二選擇器的輸入，而第三選擇器選擇1作為第四選擇器的輸入；如果選擇信號為0，則第一選擇器選擇1作為第二選擇器的輸入，而第三選擇器選擇原始明文作為第四選擇器的輸入；當進行第一次之后的各次模乘/模冪時，如果選擇信號為1，則第二選擇器選擇本次模乘/模冪的輸出作為下一次模乘/模冪的輸入，而第四選擇器選擇1作為下一次模乘/模冪的輸入；如果選擇信號為0，則第二選擇器選擇1作為下一次模乘/模冪的輸入，而第四選擇器選擇本次模乘/模冪的輸出作為下一次模乘/模冪的輸入。

2.如權利要求1所述的RSA加密電路結構，其特征在于，所述模乘器包括3個移位器、3個選擇器、3個減法器和1個加法器，其中：

加法器與第二移位器、第一減法器、第七選擇器和第八選擇器分別相連，用于將第七選擇器的輸出和第二移位器的輸出相加；

第一減法器與第二移位器、第六選擇器和加法器分別相連，用于完成對第二移位器的輸出與原始模輸入相減的操作；

第二減法器與第三移位器、第七選擇器和第八選擇器分別相連，用于將第八選擇器的輸出和第三移位器左移一位的輸出相減；

第三減法器與第七選擇器和第八選擇器分別相連，用于將第八選擇器的輸出和原始模輸入相減；

第二移位器與第六選擇器、第一減法器和加法器分別相連，用于將第六選擇器的輸出左移一位得到新的被乘數；

第三移位器與第二減法器相連，用于完成對原始模輸入左移一位的操作；

第四移位器與第八選擇器相連，用于將乘數右移一位得到新的乘數；

第六選擇器與第二移位器和第一減法器分別相連，當第一減法器輸出的次高位分別為1和0時，第六選擇器分別選擇第二移位器的輸出和第一減法器的輸出；

第七選擇器與第二減法器、第三減法器、加法器和第八選擇器分別相連，根據第三減法器輸出的最高位和第二減法器輸出的最高位，選擇第八選擇器的輸出或者第三減法器的輸出或者第二減法器的輸出作為其輸出；當第三減法器輸出的最高位為1且第二減法器輸出的最高位也為1時，第七選擇器選擇第八選擇器的輸出；當第三減法器輸出的最高位為0且第二減法器輸出的最高位為1時，第七選擇器選擇第三減法器的輸出；否則第七選擇器選擇第二減法器的輸出；

第八選擇器與加法器、第四移位器和第七選擇器分別相連，當第四移位器輸出的最低位分別為1和0時，第八選擇器分別選擇加法器的輸出和第七選擇器的輸出作為第一乘積。

3.一種RSA加密的方法，包括以下步驟：

1)權利要求1所述的RSA加密電路結構上電后，首先鎖存明文，冪指數和模；

2)根據冪指數的最低位使用選擇器，選擇用于模乘運算的被乘數為明文或為1，并進行模乘運算；

3)將被乘數和乘數都選擇為明文，進行模冪運算；

4)使用移位器將冪指數右移一位；

5)根據冪指數右移后的最低位使用選擇器，選擇用于模乘運算的乘數為模冪輸出或為1，并進行模乘運算；

6)將被乘數和乘數都選擇為模冪輸出，進行模冪運算；

7)重復步驟4)-步驟6)，直到移位后的冪指數為0；

其中，所述RSA加密電路結構采用如權利要求2所述的模乘器進行模乘/模冪運算的具體步驟包括：

a)模乘/模冪運算開始后，首先使用第三移位器將模左移一位；

b)使用加法器將乘積和被乘數相加，根據乘數的最低位使用第八選擇器選擇第一乘積為加法器的輸出或為乘積；

c)第二乘積由第一乘積和模通過第三減法器得到；

d)第三乘積由第一乘積和模左移一位通過第二減法器相減得到；

e)根據第二乘積的最高位和第三乘積的最高位，通過第七選擇器選擇得到乘積；

f)第一被乘數由被乘數和模通過第一減法器相減得到；

g)根據相減后的結果，第一被乘數的次高位選擇第一被乘數是鎖存相減后的結果，還是鎖存被乘數；

h)將被第一乘數左移一位得到新的被乘數，將乘數右移一位得到新的乘數；

i)重復步驟b)-步驟h)，直到移位后的乘數為0。