可重組多功能大數運算器的小規模硬件實(shí)現

　　隨著(zhù)各種加解密算法密鑰長(cháng)度的逐步增加，在一些具有安全性需求的芯片設計中，大規格數據運算的硬件實(shí)現已成為硬件設計的主要考慮因素和設計難點(diǎn)．比如RSA等基于大數分解的公鑰密碼算法，雖然目前密鑰長(cháng)度已達1024位，但是仍然不能避免將被破解的厄運，致使密鑰還需進(jìn)一步增加．這種運算規格的增長(cháng)不僅使加解密運算速度降低，而且增加了硬件實(shí)現的難度．

　　目前國內外對大數值運算器的研究，主要集中在大數模冪乘運算的實(shí)現上，其數學(xué)表達式為S=ABmodN．大數模冪乘一般用模平方和模乘來(lái)實(shí)現；對于一個(gè)指數B，模平方的次數是固定的，而模乘的次數是可以?xún)?yōu)化的．因此可在以下兩方面考慮運算加速：(1)減少模乘次數；(2)提高大數模乘速度．針對第一種方案提出的加速算法有m進(jìn)制方法、加法鏈法、Yacobi法；針對第二種方案有估商型系列算法和Montgomery系列算法_．以上各種方案或者需要預計算，占用較大的存儲空間，或者需要設置專(zhuān)門(mén)的乘法單元，都是在犧牲規模的前提下提高運算速度．在對規模要求嚴格的安全芯片中，以上方法不再適用．而且，它們也并未涉及其他運算(如加、減、乘、除等四則運算)的大規格實(shí)現方法．

　　根據保密終端安全芯片CSTU(China secureterminal unit，國家密碼委員會(huì )審批項目，產(chǎn)品型號SSX11)對運算速度要求不高(主頻20 MHz)、對規模要求嚴格的設計需求，提出了一種小規模的大數值運算器設計方法.基于加法操作，在掃描鏈的配合下，全部用邏輯電路實(shí)現了包括加減乘除及模乘、模冪乘等多種運算功能，各功能支持的運算規格從8位一直擴展到2048位．經(jīng)綜合驗證，在20MHz的主頻下，設計規模只有13887門(mén)，完全適用于CSTU安全體系的面積優(yōu)先的設計要求．

　　1 CSTU 安全芯片體系結構簡(jiǎn)介

　　隨著(zhù)人們對安全需求的不斷增加，采用固定或單一加解密算法的產(chǎn)品已經(jīng)無(wú)法滿(mǎn)足人們的需求，目前的安全產(chǎn)品需要經(jīng)常更換加解密算法甚至改變整個(gè)安全策略．適應這種需求常用的方法是在基本運算器之上，使用軟件編程的方式靈活的實(shí)現算法的轉換．但是面對不斷升級的軟件破解技術(shù)的挑戰，以及軟件方式的低速率性，各種加解密算法也由軟件實(shí)現向硬件電路實(shí)現過(guò)渡．為解決這一矛盾．可支持多種加解密算法的硬件安全產(chǎn)品就應運而生，其中基于可重組方式設計的安全芯片無(wú)疑又具有領(lǐng)先優(yōu)勢．

　　CSTU保密終端安全芯片采用了可重組設計思想，綜合分析了當前大量使用的DES，AES，IDEA，RSA，MD5等十余種加解密算法的實(shí)現過(guò)程，支持對稱(chēng)、公鑰、摘要密碼算法及用戶(hù)隱秘算法，提供這些算法實(shí)現所需的IP平臺，不同的用戶(hù)可以根據自己的需要在平臺上進(jìn)行二次開(kāi)發(fā)，形成自己定義的安全算法及策略．

　　CSTU安全芯片可用于保密電話(huà)、安全卡證或移動(dòng)安全終端等產(chǎn)品中，這些產(chǎn)品的共同特點(diǎn)是對規模要求比較嚴格，對公鑰密碼算法的速度要求不高．為提供對公鑰密碼算法和數字簽名算法的支持，大數運算器成為CSTU安全體系中關(guān)鍵的核心IP．根據實(shí)際需求，本設計在滿(mǎn)足硬件規模盡可能小同時(shí)支持盡可能多的運算功能和多種規格的數據運算的條件下，最終保證整個(gè)系統的靈活性．

　　2 算法分析

　　2．1 模冪乘算法分析

　　模冪乘運算采用平方乘算法，將模冪乘運算轉化為模乘和模平方運算實(shí)現．

　　平方-乘算法：一般地，求S=ABmodN，其中AN，BN；將指數B表示為二進(jìn)制，即

　　觀(guān)察算法，由于指數B化為二進(jìn)制后的長(cháng)度不確定，多數情況下高位會(huì )存在很多個(gè)0．如果完全按照該算法實(shí)現，指數B從最高位起開(kāi)始運算，在第一個(gè)1出現以前，雖進(jìn)行了多次運算，但D的值一直為1；當B出現第一個(gè)1后才進(jìn)入有效的模乘運算．在具體實(shí)現時(shí)，設計專(zhuān)門(mén)的電路從高到低掃描指數B的每一位，當在找到第一個(gè)1之前，不做任何運算，找到第一個(gè)1時(shí)，使D=A，以后根據每次掃描的6[i]值，調用模乘實(shí)現運算．

　　經(jīng)過(guò)對多種公鑰加解密算法的分析——如RSA算法，通常公鑰的有效位較短，而私鑰有效位較長(cháng)．加密中的模冪乘運算，指數有效位很少，所以上面的改進(jìn)可大大減少模乘次數，加快加密過(guò)程．以目前常用的私鑰和模數1 024 bit，公鑰128bit情況為例，采用上述改進(jìn)可減少896次不必要的模乘．解密過(guò)程使用中國余數定理(CRT)，可有效降低解密指數的長(cháng)度，整個(gè)算法的執行效率得到進(jìn)一步提高．

　　2．2 模乘及模加的實(shí)現方法

　　模乘采用改進(jìn)的Blakley加法型算法，原理與平方-乘算法類(lèi)似，核心是將模乘轉化為模加實(shí)現．如通常S=(A×B)modN，AN，BN可以按如下方式考慮．

　　將B表示成二進(jìn)制：

　　由上式可知，可以像平方一乘算法一樣，將模乘轉化為模加實(shí)現．

　　一般模加運算表示為S=(A+B)modN，觀(guān)察以上模乘及模冪乘算法原理描述，可知在其調用的模加運算中，因為AN且BN，則(A+B)2N，所以，

　　因此考慮在運算中同時(shí)計算(A+B)和(A+B-N)兩個(gè)結果，運算完成后通過(guò)判斷加法器與減法器的進(jìn)位輸出(CO)與借位輸出(BO)．決定哪個(gè)為本次模加的正確結果．同上，A，B，N均為l位的二進(jìn)制數，若CO=1，則說(shuō)明(A+B)為l+1位二進(jìn)制數，必大于l位的N；若CO=0，則(A+B)和N同為l位，當BO=1時(shí)(A+B)N，當BO=0時(shí)N≤(A+B)．

　　從而可以在一次運算中完成加法和求模過(guò)程，使模加的運算速度提高1倍．

　　2．3 其他功能實(shí)現

　　經(jīng)過(guò)對多種公鑰加解密算法及簽名算法的分析，為提高芯片整體靈活性本設計還給出了對乘法、除法、求模、模加法逆、開(kāi)方幾種常用運算的支持．同樣選擇基于加減運算的算法實(shí)現，充分考慮算法對掃描鏈等已有邏輯資源的服用，設計出符合產(chǎn)品運算速度的面積最小化的系統．表1列出系統實(shí)現的其他功能模塊采用的算法名稱(chēng)、詳細算法及相關(guān)文獻．

　　3 設計實(shí)現

　　以一個(gè)可以完成32位規格加、減、模加、增減量、移位等基本功能的ALU為基本運算單元，在掃描鏈邏輯的控制下，可以完成乘、除、開(kāi)方、模乘、模冪乘等多種復雜運算．設計結構如圖1所示．大數值運算器的外接口信號分以下三類(lèi)．(1)控制：功能，規格以及源、目的指示；(2)數據：來(lái)自體RAM的源操作數，運算結果到RAM的反饋；(3)狀態(tài)：運算結束，對體系相應狀態(tài)寄存器的控制信號．

　　基本運算單元(ALU)：可在單周期內完成32位加減、增(減)量、模加、左右移一位功能，其核心結構如圖2所示，由輸入選通控制MUX-IN，32位加法器ADD，32位減法器SUB，移位邏輯SF和輸出選通控制MUX-OUT組成．

　　各功能在ALU中的具體實(shí)現方式見(jiàn)表2：

　　功能控制邏輯：完成各個(gè)功能的控制，可分為簡(jiǎn)單功能和復雜功能兩類(lèi)不同的控制．

　　1)簡(jiǎn)單功能：32位規格以上的加減、模加、增(減)量、移位功能．功能實(shí)現通過(guò)多周期迭代調用ALU相應功能實(shí)現，多次調用間保持進(jìn)/借位傳遞．

　　2)復雜功能：模乘、模冪乘、乘除、開(kāi)方功能.根據算法原理設計狀態(tài)機，根據掃描鏈邏輯的配合信號，通過(guò)調用簡(jiǎn)單功能實(shí)現運算．

　　掃描鏈邏輯：當功能控制邏輯在完成復雜功能時(shí)，驅動(dòng)掃描鏈邏輯動(dòng)作．核心電路為32位的移位寄存器，掃描鏈邏輯可完成：待掃描數據的自動(dòng)裝載和切換；掃描數據高位0的自動(dòng)去除，即自動(dòng)找到第一個(gè)1，并給出標識信號；在使能信號的控制下從高到低自動(dòng)掃描數據，給出掃描結果；掃描結束給出結束信號．

　　4 測試及結論

　　本文提出了一種用于可重組安全芯片的，面積優(yōu)先、多功能、可重組的大數值運算器的實(shí)現方法設計支持的所有功能及規格如表3所示．所有模塊均在ModelSim環(huán)境下通過(guò)了邏輯仿真，并在Xilinx公司的Virtex-Ⅱ系列FPGA產(chǎn)品XC2V6000上經(jīng)過(guò)實(shí)際功能驗證．

　　使用Synopsys公司Design Compiler綜合工具，在臺基電(TSMC)0．25μm工藝和安全芯片要求的20Hz時(shí)鐘主頻下的綜合結果為13 887門(mén)．設計的結果與近年的幾個(gè)大數值運算器的對比見(jiàn)表4．可見(jiàn)本設計雖然運算速度稍慢，但設計規模同比大大降低，完全符合CSTU保密終端安全芯片對面積優(yōu)先的設計要求，速度也在設計允許范圍內．