余數(shù)系統(tǒng)中算法單元及關(guān)鍵技術(shù)研究.pdf

1、和傳統(tǒng)的使用硬件規(guī)模帶來的并行性的方式不同，RNS是一種使用并行的數(shù)值表征系統(tǒng)達(dá)到天然并行的性的方法。近些年來以RSA、ECC為代表的公鑰算法廣泛使用了RNS架構(gòu)以提升加密的速度。隨著秘鑰長度的增加，對(duì)于RNS下算法單元尤其是模2n-2p-1下乘法單元的位寬和性能提出了更高的要求。另外后向轉(zhuǎn)換作為RNS架構(gòu)下的難點(diǎn)，一直是RNS架構(gòu)的性能瓶頸之一，{2n-1、2n+3、2n+1、2n-3}下快速后向轉(zhuǎn)換算法被提出后，由于模2n+3下乘法

2、單元的性能問題而少有應(yīng)用。本文結(jié)合余數(shù)系統(tǒng)在密碼學(xué)應(yīng)用和快速后向轉(zhuǎn)換等方向的最新進(jìn)展，針對(duì)相應(yīng)的特殊余數(shù)基下的算法單元進(jìn)行了深入的研究。通過對(duì)大量模2n±1乘法器相關(guān)參考文獻(xiàn)進(jìn)行分類研究，對(duì)適合本文設(shè)計(jì)要求的架構(gòu)進(jìn)行了篩選。本文根據(jù)模修正在二進(jìn)制乘法器介入的部位不同將模乘法器分為四種類型，并按照數(shù)據(jù)流的執(zhí)行順序進(jìn)行了命名，分別為修正1型、修正2型、修正3型以及修正4型。按照本文的分類方式，選擇形式為2n-2p-1、2n+3余數(shù)基下的算法

3、單元做了如下工作：
　　1.針對(duì)2n-2p-1類型動(dòng)態(tài)范圍利用率較低的問題，使用現(xiàn)有文獻(xiàn)中的擴(kuò)展方法，對(duì)模2n-2p-1加法運(yùn)算的相關(guān)公式進(jìn)行推導(dǎo)，降低了其約束條件并且將修正所需的判定項(xiàng)由A+B+T化簡為A+B。從而提出了一種適合2n-2p-1余數(shù)基下算法單元應(yīng)用的無損動(dòng)態(tài)擴(kuò)展方法。使用無損動(dòng)態(tài)范圍擴(kuò)展后的模2n-2p-1加法器和乘法器較同種結(jié)構(gòu)的算法單元在“面積×?xí)r延”效率上分別提高了41.1％和12.3%。
　　2.提出

4、了一種修正1型模2n-2p-1乘法器，利用模2n-2p-1的性質(zhì)，將包含布斯編碼選擇項(xiàng)的部分積中可能出現(xiàn)的負(fù)數(shù)問題進(jìn)行修正。經(jīng)過公式推導(dǎo)，將未修正部分積和修正項(xiàng)進(jìn)行合理的分離，使未修正部分積可以最大程度利用二進(jìn)制布斯編碼部分積生成的相關(guān)電路，最終得到了規(guī)整的部分積。這種結(jié)構(gòu)較傳統(tǒng)的通用型模乘法在平均時(shí)延和平均面積上分別減少了49.1%和6.5%。
　　3.針對(duì)修正3型提出了兩種不同結(jié)構(gòu)的模2n-2p-1乘法器，在布斯結(jié)構(gòu)中通過預(yù)先

5、計(jì)算解決了將2n位有符號(hào)補(bǔ)碼表示的部分積較難修正至n位的問題。進(jìn)而獲得了一個(gè)與(n,p)取值組合無關(guān)的統(tǒng)一結(jié)構(gòu)。在 TDM結(jié)構(gòu)中首次將 TDM算法引入到模乘法器的設(shè)計(jì)當(dāng)中，推導(dǎo)得到了一種較使用布斯編碼更為精簡的快速型結(jié)構(gòu)。這兩種模2n-2p-1乘法器在平均時(shí)延上較當(dāng)前的模2n-2p-1乘法器最高可以降低9.7%。
　　4.針對(duì)修正4型對(duì)2n-2p-1、2n+3兩種余數(shù)基分別提出了兩種乘法器結(jié)構(gòu)。在模2n-2p-1乘法器中，其關(guān)鍵路

6、徑上使用一級(jí)CSA代替了原來的一個(gè)p位二進(jìn)制進(jìn)位傳播加法器，縮短了關(guān)鍵路徑的時(shí)延。在模2n+3乘法器，利用模2n+3性質(zhì)在部分積進(jìn)行壓縮時(shí)產(chǎn)生“+9”和“-9”進(jìn)行抵消，節(jié)約了額外處理“-9”所需要的硬件資源。降低了關(guān)鍵路徑的時(shí)延。兩種結(jié)構(gòu)較當(dāng)前的同類型模乘法器在“面積×?xí)r延”效率上分別提高了12.4%和9.0%。
　　在本文的最后，為方便對(duì)本文提出的幾種算法單元進(jìn)行設(shè)計(jì)實(shí)現(xiàn)、測(cè)試及數(shù)據(jù)處理。本文構(gòu)建了一套自動(dòng)化的處理平臺(tái)，并給出