可重組多功能大數(shù)運(yùn)算器的小規(guī)模硬件實(shí)現(xiàn)
隨著各種加解密算法密鑰長度的逐步增加,在一些具有安全性需求的芯片設(shè)計(jì)中,大規(guī)格數(shù)據(jù)運(yùn)算的硬件實(shí)現(xiàn)已成為硬件設(shè)計(jì)的主要考慮因素和設(shè)計(jì)難點(diǎn).比如RSA等基于大數(shù)分解的公鑰密碼算法,雖然目前密鑰長度已達(dá)1024位,但是仍然不能避免將被破解的厄運(yùn),致使密鑰還需進(jìn)一步增加.這種運(yùn)算規(guī)格的增長不僅使加解密運(yùn)算速度降低,而且增加了硬件實(shí)現(xiàn)的難度.
目前國內(nèi)外對大數(shù)值運(yùn)算器的研究,主要集中在大數(shù)模冪乘運(yùn)算的實(shí)現(xiàn)上,其數(shù)學(xué)表達(dá)式為S=ABmodN.大數(shù)模冪乘一般用模平方和模乘來實(shí)現(xiàn);對于一個(gè)指數(shù)B,模平方的次數(shù)是固定的,而模乘的次數(shù)是可以優(yōu)化的.因此可在以下兩方面考慮運(yùn)算加速:(1)減少模乘次數(shù);(2)提高大數(shù)模乘速度.針對第一種方案提出的加速算法有m進(jìn)制方法、加法鏈法、Yacobi法;針對第二種方案有估商型系列算法和Montgomery系列算法_.以上各種方案或者需要預(yù)計(jì)算,占用較大的存儲空間,或者需要設(shè)置專門的乘法單元,都是在犧牲規(guī)模的前提下提高運(yùn)算速度.在對規(guī)模要求嚴(yán)格的安全芯片中,以上方法不再適用.而且,它們也并未涉及其他運(yùn)算(如加、減、乘、除等四則運(yùn)算)的大規(guī)格實(shí)現(xiàn)方法.
根據(jù)保密終端安全芯片CSTU(China secureterminal unit,國家密碼委員會審批項(xiàng)目,產(chǎn)品型號SSX11)對運(yùn)算速度要求不高(主頻20 MHz)、對規(guī)模要求嚴(yán)格的設(shè)計(jì)需求,提出了一種小規(guī)模的大數(shù)值運(yùn)算器設(shè)計(jì)方法.基于加法操作,在掃描鏈的配合下,全部用邏輯電路實(shí)現(xiàn)了包括加減乘除及模乘、模冪乘等多種運(yùn)算功能,各功能支持的運(yùn)算規(guī)格從8位一直擴(kuò)展到2048位.經(jīng)綜合驗(yàn)證,在20MHz的主頻下,設(shè)計(jì)規(guī)模只有13887門,完全適用于CSTU安全體系的面積優(yōu)先的設(shè)計(jì)要求.
1 CSTU 安全芯片體系結(jié)構(gòu)簡介
隨著人們對安全需求的不斷增加,采用固定或單一加解密算法的產(chǎn)品已經(jīng)無法滿足人們的需求,目前的安全產(chǎn)品需要經(jīng)常更換加解密算法甚至改變整個(gè)安全策略.適應(yīng)這種需求常用的方法是在基本運(yùn)算器之上,使用軟件編程的方式靈活的實(shí)現(xiàn)算法的轉(zhuǎn)換.但是面對不斷升級的軟件破解技術(shù)的挑戰(zhàn),以及軟件方式的低速率性,各種加解密算法也由軟件實(shí)現(xiàn)向硬件電路實(shí)現(xiàn)過渡.為解決這一矛盾.可支持多種加解密算法的硬件安全產(chǎn)品就應(yīng)運(yùn)而生,其中基于可重組方式設(shè)計(jì)的安全芯片無疑又具有領(lǐng)先優(yōu)勢.
CSTU保密終端安全芯片采用了可重組設(shè)計(jì)思想,綜合分析了當(dāng)前大量使用的DES,AES,IDEA,RSA,MD5等十余種加解密算法的實(shí)現(xiàn)過程,支持對稱、公鑰、摘要密碼算法及用戶隱秘算法,提供這些算法實(shí)現(xiàn)所需的IP平臺,不同的用戶可以根據(jù)自己的需要在平臺上進(jìn)行二次開發(fā),形成自己定義的安全算法及策略.
CSTU安全芯片可用于保密電話、安全卡證或移動安全終端等產(chǎn)品中,這些產(chǎn)品的共同特點(diǎn)是對規(guī)模要求比較嚴(yán)格,對公鑰密碼算法的速度要求不高.為提供對公鑰密碼算法和數(shù)字簽名算法的支持,大數(shù)運(yùn)算器成為CSTU安全體系中關(guān)鍵的核心IP.根據(jù)實(shí)際需求,本設(shè)計(jì)在滿足硬件規(guī)模盡可能小同時(shí)支持盡可能多的運(yùn)算功能和多種規(guī)格的數(shù)據(jù)運(yùn)算的條件下,最終保證整個(gè)系統(tǒng)的靈活性.
2 算法分析
2.1 模冪乘算法分析
模冪乘運(yùn)算采用平方乘算法,將模冪乘運(yùn)算轉(zhuǎn)化為模乘和模平方運(yùn)算實(shí)現(xiàn).
平方-乘算法:一般地,求S=ABmodN,其中AN,BN;將指數(shù)B表示為二進(jìn)制,即
觀察算法,由于指數(shù)B化為二進(jìn)制后的長度不確定,多數(shù)情況下高位會存在很多個(gè)0.如果完全按照該算法實(shí)現(xiàn),指數(shù)B從最高位起開始運(yùn)算,在第一個(gè)1出現(xiàn)以前,雖進(jìn)行了多次運(yùn)算,但D的值一直為1;當(dāng)B出現(xiàn)第一個(gè)1后才進(jìn)入有效的模乘運(yùn)算.在具體實(shí)現(xiàn)時(shí),設(shè)計(jì)專門的電路從高到低掃描指數(shù)B的每一位,當(dāng)在找到第一個(gè)1之前,不做任何運(yùn)算,找到第一個(gè)1時(shí),使D=A,以后根據(jù)每次掃描的6[i]值,調(diào)用模乘實(shí)現(xiàn)運(yùn)算.
經(jīng)過對多種公鑰加解密算法的分析——如RSA算法,通常公鑰的有效位較短,而私鑰有效位較長.加密中的模冪乘運(yùn)算,指數(shù)有效位很少,所以上面的改進(jìn)可大大減少模乘次數(shù),加快加密過程.以目前常用的私鑰和模數(shù)1 024 bit,公鑰128bit情況為例,采用上述改進(jìn)可減少896次不必要的模乘.解密過程使用中國余數(shù)定理(CRT),可有效降低解密指數(shù)的長度,整個(gè)算法的執(zhí)行效率得到進(jìn)一步提高.
2.2 模乘及模加的實(shí)現(xiàn)方法
模乘采用改進(jìn)的Blakley加法型算法,原理與平方-乘算法類似,核心是將模乘轉(zhuǎn)化為模加實(shí)現(xiàn).如通常S=(A×B)modN,AN,BN可以按如下方式考慮.
將B表示成二進(jìn)制:
由上式可知,可以像平方一乘算法一樣,將模乘轉(zhuǎn)化為模加實(shí)現(xiàn).
一般模加運(yùn)算表示為S=(A+B)modN,觀察以上模乘及模冪乘算法原理描述,可知在其調(diào)用的模加運(yùn)算中,因?yàn)锳N且BN,則(A+B)2N,所以,
因此考慮在運(yùn)算中同時(shí)計(jì)算(A+B)和(A+B-N)兩個(gè)結(jié)果,運(yùn)算完成后通過判斷加法器與減法器的進(jìn)位輸出(CO)與借位輸出(BO).決定哪個(gè)為本次模加的正確結(jié)果.同上,A,B,N均為l位的二進(jìn)制數(shù),若CO=1,則說明(A+B)為l+1位二進(jìn)制數(shù),必大于l位的N;若CO=0,則(A+B)和N同為l位,當(dāng)BO=1時(shí)(A+B)N,當(dāng)BO=0時(shí)N≤(A+B).
從而可以在一次運(yùn)算中完成加法和求模過程,使模加的運(yùn)算速度提高1倍.
2.3 其他功能實(shí)現(xiàn)
經(jīng)過對多種公鑰加解密算法及簽名算法的分析,為提高芯片整體靈活性本設(shè)計(jì)還給出了對乘法、除法、求模、模加法逆、開方幾種常用運(yùn)算的支持.同樣選擇基于加減運(yùn)算的算法實(shí)現(xiàn),充分考慮算法對掃描鏈等已有邏輯資源的服用,設(shè)計(jì)出符合產(chǎn)品運(yùn)算速度的面積最小化的系統(tǒng).表1列出系統(tǒng)實(shí)現(xiàn)的其他功能模塊采用的算法名稱、詳細(xì)算法及相關(guān)文獻(xiàn).
3 設(shè)計(jì)實(shí)現(xiàn)
以一個(gè)可以完成32位規(guī)格加、減、模加、增減量、移位等基本功能的ALU為基本運(yùn)算單元,在掃描鏈邏輯的控制下,可以完成乘、除、開方、模乘、模冪乘等多種復(fù)雜運(yùn)算.設(shè)計(jì)結(jié)構(gòu)如圖1所示.大數(shù)值運(yùn)算器的外接口信號分以下三類.(1)控制:功能,規(guī)格以及源、目的指示;(2)數(shù)據(jù):來自體RAM的源操作數(shù),運(yùn)算結(jié)果到RAM的反饋;(3)狀態(tài):運(yùn)算結(jié)束,對體系相應(yīng)狀態(tài)寄存器的控制信號.
基本運(yùn)算單元(ALU):可在單周期內(nèi)完成32位加減、增(減)量、模加、左右移一位功能,其核心結(jié)構(gòu)如圖2所示,由輸入選通控制MUX-IN,32位加法器ADD,32位減法器SUB,移位邏輯SF和輸出選通控制MUX-OUT組成.
各功能在ALU中的具體實(shí)現(xiàn)方式見表2:
功能控制邏輯:完成各個(gè)功能的控制,可分為簡單功能和復(fù)雜功能兩類不同的控制.
1)簡單功能:32位規(guī)格以上的加減、模加、增(減)量、移位功能.功能實(shí)現(xiàn)通過多周期迭代調(diào)用ALU相應(yīng)功能實(shí)現(xiàn),多次調(diào)用間保持進(jìn)/借位傳遞.
2)復(fù)雜功能:模乘、模冪乘、乘除、開方功能.根據(jù)算法原理設(shè)計(jì)狀態(tài)機(jī),根據(jù)掃描鏈邏輯的配合信號,通過調(diào)用簡單功能實(shí)現(xiàn)運(yùn)算.
掃描鏈邏輯:當(dāng)功能控制邏輯在完成復(fù)雜功能時(shí),驅(qū)動掃描鏈邏輯動作.核心電路為32位的移位寄存器,掃描鏈邏輯可完成:待掃描數(shù)據(jù)的自動裝載和切換;掃描數(shù)據(jù)高位0的自動去除,即自動找到第一個(gè)1,并給出標(biāo)識信號;在使能信號的控制下從高到低自動掃描數(shù)據(jù),給出掃描結(jié)果;掃描結(jié)束給出結(jié)束信號.
4 測試及結(jié)論
本文提出了一種用于可重組安全芯片的,面積優(yōu)先、多功能、可重組的大數(shù)值運(yùn)算器的實(shí)現(xiàn)方法設(shè)計(jì)支持的所有功能及規(guī)格如表3所示.所有模塊均在ModelSim環(huán)境下通過了邏輯仿真,并在Xilinx公司的Virtex-Ⅱ系列FPGA產(chǎn)品XC2V6000上經(jīng)過實(shí)際功能驗(yàn)證.
使用Synopsys公司Design Compiler綜合工具,在臺基電(TSMC)0.25μm工藝和安全芯片要求的20Hz時(shí)鐘主頻下的綜合結(jié)果為13 887門.設(shè)計(jì)的結(jié)果與近年的幾個(gè)大數(shù)值運(yùn)算器的對比見表4.可見本設(shè)計(jì)雖然運(yùn)算速度稍慢,但設(shè)計(jì)規(guī)模同比大大降低,完全符合CSTU保密終端安全芯片對面積優(yōu)先的設(shè)計(jì)要求,速度也在設(shè)計(jì)允許范圍內(nèi).
評論