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

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

2、單元的性能問題而少有應用。本文結合余數(shù)系統(tǒng)在密碼學應用和快速后向轉換等方向的最新進展，針對相應的特殊余數(shù)基下的算法單元進行了深入的研究。通過對大量模2n±1乘法器相關參考文獻進行分類研究，對適合本文設計要求的架構進行了篩選。本文根據(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加法運算的相關公式進行推導，降低了其約束條件并且將修正所需的判定項由A+B+T化簡為A+B。從而提出了一種適合2n-2p-1余數(shù)基下算法單元應用的無損動態(tài)擴展方法。使用無損動態(tài)范圍擴展后的模2n-2p-1加法器和乘法器較同種結構的算法單元在“面積×時延”效率上分別提高了41.1％和12.3%。
　　2.提出

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

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

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