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

1、和傳統(tǒng)的使用硬件規(guī)模帶來的并行性的方式不同，RNS是一種使用并行的數(shù)值表征系統(tǒng)達到天然并行的性的方法。近些年來以RSA、ECC為代表的公鑰算法廣泛使用了RNS架構(gòu)以提升加密的速度。隨著秘鑰長度的增加，對于RNS下算法單元尤其是模2n-2p-1下乘法單元的位寬和性能提出了更高的要求。另外后向轉(zhuǎn)換作為RNS架構(gòu)下的難點，一直是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)換等方向的最新進展，針對相應(yīng)的特殊余數(shù)基下的算法單元進行了深入的研究。通過對大量模2n±1乘法器相關(guān)參考文獻進行分類研究，對適合本文設(shè)計要求的架構(gòu)進行了篩選。本文根據(jù)模修正在二進制乘法器介入的部位不同將模乘法器分為四種類型，并按照數(shù)據(jù)流的執(zhí)行順序進行了命名，分別為修正1型、修正2型、修正3型以及修正4型。按照本文的分類方式，選擇形式為2n-2p-1、2n+3余數(shù)基下的算法

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

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

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

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