NBC分組密碼算法的FPGA高速實(shí)現(xiàn)

孟祥興,曹 欣

(北京電子科技學(xué)院電子與通信工程系, 北京 100070)

密碼是我們黨和國(guó)家的命脈,是我國(guó)重要的戰(zhàn)略資源.在智能物聯(lián)背景下的大數(shù)據(jù)信息時(shí)代,數(shù)據(jù)的保密性與安全性顯得更加重要.在全球各國(guó)密碼科研人員的努力下,近年來涌現(xiàn)出各種各樣實(shí)現(xiàn)方式的機(jī)密性、完整性、真實(shí)性和不可否認(rèn)性皆優(yōu)秀的高性能密碼算法.NBC分組密碼算法就是我國(guó)自主研發(fā)的最新密碼算法.

可編程邏輯器件(programmable logic device,PLD)是20世紀(jì)70年代發(fā)展起來的一種新型器件,PLD在簡(jiǎn)化電路設(shè)計(jì)、降低開發(fā)成本、提高系統(tǒng)可靠性等方面起到了重要的作用.現(xiàn)場(chǎng)可編程門陣列(field programmable gate array,FPGA)是美國(guó)Xilinx公司于1985年推出的采用單元型結(jié)構(gòu)的PLD器件.FPGA采用CMOS、SRAM工藝制作,其內(nèi)部由許多獨(dú)立的可編程邏輯單元構(gòu)成,各邏輯單元之間可以靈活地相互連接,具有密度高、速度快、編程靈活、可重新配置等優(yōu)點(diǎn),是目前主流的PLD器件之一.

分組密碼算法是一種對(duì)稱加密算法,其明文信息具有良好的可擴(kuò)展性,不需要密鑰同步,具有較強(qiáng)的適用性.但是,加密速度慢、錯(cuò)誤擴(kuò)散傳播等缺點(diǎn)使其在互聯(lián)網(wǎng)的應(yīng)用較少.因此,快速實(shí)現(xiàn)分組密碼算法成為分組密碼工程應(yīng)用必須解決的問題.結(jié)合FPGA器件的優(yōu)點(diǎn)和分組密碼算法的不足,用FPGA實(shí)現(xiàn)分組密碼算法成為解決分組密碼算法加密速度慢的有效手段,并在工程領(lǐng)域得到了廣泛應(yīng)用.

本文研究NBC分組密碼算法的FPGA高速實(shí)現(xiàn).針對(duì)分組密碼特點(diǎn),結(jié)合有限狀態(tài)機(jī)技術(shù)、非阻塞賦值技術(shù)和流水線技術(shù),用分時(shí)鐘、分塊明文、密鑰輸入的方式對(duì)NBC密碼算法進(jìn)行FPGA編程實(shí)現(xiàn).

1 NBC算法介紹

NBC算法[1]采用改進(jìn)的第二類廣義Feistel結(jié)構(gòu),輪函數(shù)和F函數(shù)如圖1和圖2所示,其中S為16比特的S盒.NBC算法以16比特為基本處理單元,將分組長(zhǎng)度為128比特、密鑰長(zhǎng)度為128比特的NBC算法記為NBC 128/128.

圖1 NBC算法輪函數(shù)

圖2 F函數(shù)(0≤l≤3)

1.1 輪函數(shù)

為保證加解密的一致性,最后一輪不進(jìn)行塊置換.輸入明文為P=X0,輸出密文為C=X32.置換塊為π8=(30147256),其中,3表示輸入的第0塊移到輸出的第3塊的位置,其余依此類推.

1.2 S盒

NBC算法的S盒由基于16級(jí)的非線性反饋移位寄存器(NFSR)來構(gòu)造.記S盒的16比特輸入為S0,S1,…,S15,將該16比特從左至右依次填充至16個(gè)寄存器內(nèi),寄存器迭代20拍后的全體內(nèi)部狀態(tài)即為S盒的輸出.

(1)

(2)

(3)

(4)

{13,14,15}

(5)

寄存器迭代20拍可以保證S盒各分量的代數(shù)次數(shù)都達(dá)到最大值15,并且具有好的差分盒線性性質(zhì).

1.3 密鑰擴(kuò)展算法

NBC 128/128密鑰擴(kuò)展算法的設(shè)計(jì)與S盒類似,采用基于8比特的16級(jí)非線性反饋移位寄存器,引入模28加法代替比特與,增加循環(huán)移位以保證不同字之間的充分混淆,增加輪常數(shù)以避免出現(xiàn)弱密鑰(如全零子密鑰).密鑰擴(kuò)展算法中用到的非線性反饋移位寄存器的狀態(tài)字wj(0≤j≤15)和常數(shù)cl(0≤l≤3)中各比特都是按照高位在前、低位在后的順序存放.

初始種子密鑰為128比特,分成16個(gè)8比特字K=(k0‖k1‖…‖k15).用它們填充密鑰寄存器的初始狀態(tài),即有wj=kj,0≤j≤15.提取密鑰寄存器前64比特作為初始輪的子密鑰,之后寄存器每迭代4拍,輸出一輪輪子密鑰,每次選取密鑰寄存器前64比特作為輪子密鑰.要產(chǎn)生r輪加密的所有輪子密鑰,密鑰寄存器總共需要迭代4(r-1)拍.輪子密鑰的具體產(chǎn)生方式為:對(duì)0≤j≤15,令wj=kj;輸出密鑰寄存器的前64比特作為第0輪的輪子密鑰K0;對(duì)1≤i≤r-1,順序執(zhí)行下列步驟,產(chǎn)生后r-1輪的輪子密鑰Ki.

1) 寄存器迭代4拍,按下列方式更新寄存器狀態(tài):

(w4<<<3)⊕c1

(6)

w7⊕(w9<<<7)⊕c2

(7)

(w14>>>3)⊕c3

(8)

(w3<<<2)⊕c4

(9)

{9,10,11}∪{13,14,15}

(10)

2) 選取密鑰寄存器的前64比特作為第i輪的輪子密鑰:

Ki=(w0‖w1‖w2‖w3‖w4‖w5‖w6‖w7)=

運(yùn)用到的符號(hào)說明見表1.

表1 符號(hào)說明

1.4 算法改進(jìn)

為了方便密碼算法的C語言實(shí)現(xiàn),原始NBC 128/128算法采用大端字節(jié)序設(shè)計(jì).本文使用小端字節(jié)序?qū)BC 128/128密碼算法進(jìn)行FPGA實(shí)現(xiàn),更節(jié)省時(shí)鐘資源[2]、降低邏輯資源耗用.

2 NBC算法的FPGA高速實(shí)現(xiàn)

NBC算法的FPGA實(shí)現(xiàn)主要需要解決以下問題:1) 輸入、輸出數(shù)據(jù)占用引腳過多問題[3];2) 算法各個(gè)過程時(shí)鐘配合問題;3) 邏輯資源塊占用問題;4) 系統(tǒng)整體運(yùn)行頻率問題.本文使用數(shù)據(jù)分塊輸入技術(shù)、有限狀態(tài)機(jī)技術(shù)、流水線技術(shù)設(shè)計(jì)一種高穩(wěn)定性、高頻率、邏輯資源占用少、綜合速度快的NBC 128/128密碼算法FPGA實(shí)現(xiàn).

2.1 分時(shí)鐘輸入設(shè)計(jì)

本研究的輸入明文數(shù)據(jù)為128比特、輸入初始密鑰為128比特.考慮用4個(gè)時(shí)鐘,每次時(shí)鐘輸入32比特明文和32比特密鑰,實(shí)現(xiàn)數(shù)據(jù)分塊輸入效果,效果圖如圖3所示.

圖3 數(shù)據(jù)分塊輸入效果圖

除了輸入數(shù)據(jù)分塊,還考慮輸出數(shù)據(jù)分塊[4],輸出數(shù)據(jù)分塊需要嚴(yán)密的時(shí)鐘控制,要求計(jì)算好在特定的時(shí)鐘下進(jìn)行數(shù)據(jù)輸出.將NBC 128/128的FPGA系統(tǒng)在同一個(gè)時(shí)鐘下重復(fù)調(diào)用n(n∈Z+)次實(shí)現(xiàn)明文為128比特的n倍數(shù)據(jù)加密,也可以在n個(gè)時(shí)鐘下分時(shí)實(shí)現(xiàn)明文為128比特的n倍數(shù)據(jù)加密.本文提出的NBC算法系統(tǒng)頻率高,推薦使用在n個(gè)時(shí)鐘下分時(shí)實(shí)現(xiàn)明文為128比特的n倍數(shù)據(jù)加密的方法以減少硬件的耗用.

2.2 有限狀態(tài)機(jī)設(shè)計(jì)

NBC 128/128密碼算法的復(fù)雜性主要體現(xiàn)在32次迭代輪數(shù)與20次S盒迭代次數(shù)[5].將每一個(gè)迭代輪數(shù)都用FPGA實(shí)現(xiàn)將會(huì)導(dǎo)致FPGA邏輯資源塊占用量過大、系統(tǒng)綜合時(shí)間過長(zhǎng)、系統(tǒng)運(yùn)行頻率低等缺點(diǎn).因此,使用有限狀態(tài)機(jī)技術(shù),用狀態(tài)來控制32次迭代輪數(shù),每一次迭代輪數(shù)實(shí)現(xiàn)一次輪函數(shù),解決了密碼算法的復(fù)雜性問題,將整個(gè)系統(tǒng)輪廓用有限狀態(tài)機(jī)技術(shù)有效實(shí)現(xiàn).系統(tǒng)結(jié)構(gòu)框圖如圖4所示.

圖4 有限狀態(tài)機(jī)狀態(tài)設(shè)計(jì)流程圖

本文使用摩爾型有限狀態(tài)機(jī),整體系統(tǒng)設(shè)計(jì)具有速度高、結(jié)構(gòu)清晰、可靠性高[6]等優(yōu)點(diǎn).

2.3 流水線設(shè)計(jì)

NBC 128/128分組密碼算法采用迭代非線性反饋移位寄存器(nonlinear feedback shift register,NFSR)實(shí)現(xiàn)S盒與密鑰擴(kuò)展.因此S盒與密鑰擴(kuò)展兩個(gè)模塊本身無法采用流水線結(jié)構(gòu)設(shè)計(jì).在S盒與密鑰擴(kuò)展模塊之間進(jìn)行流水線設(shè)計(jì),使得S盒模塊與密鑰擴(kuò)展模塊能夠高速實(shí)現(xiàn),流水線設(shè)計(jì)主要就是把密鑰擴(kuò)展算法的第n+1輪的4次迭代與S盒的第n輪的前4次迭代一起執(zhí)行.S盒第n輪的前5次迭代取出第n+1輪的密鑰,使得密鑰擴(kuò)展算法的實(shí)現(xiàn)在S盒實(shí)現(xiàn)的時(shí)鐘內(nèi)部進(jìn)行,省掉了密鑰擴(kuò)展算法占用的時(shí)鐘,提高了整個(gè)NBC 128/128系統(tǒng)的運(yùn)行頻率.

3 系統(tǒng)仿真及結(jié)果分析

使用Quartus Ⅱ?qū)BC 128/128系統(tǒng)進(jìn)行綜合運(yùn)算,得到系統(tǒng)綜合性能參數(shù)如圖5所示,本設(shè)計(jì)使用更少的邏輯塊實(shí)現(xiàn)了更好的分組加密效果,且NBC分組密碼算法較AES算法更優(yōu).

圖5 系統(tǒng)綜合性能參數(shù)圖

采用時(shí)鐘分段數(shù)據(jù)輸入方法,大大提高了具有同數(shù)量級(jí)端口引腳硬件電路的數(shù)據(jù)吞吐量,整體設(shè)計(jì)電路如圖6所示.電路端口聲明如表2所示.

圖6 整體電路設(shè)計(jì)圖

表2 電路端口聲明

本研究使用流水線技術(shù)和非阻塞賦值技術(shù)[7-8],系統(tǒng)時(shí)鐘頻率得到顯著提高,最高頻率可達(dá)245.58 MHz.將該設(shè)計(jì)模塊并聯(lián)使用時(shí)將達(dá)到更高速的加密效果[9],這在實(shí)時(shí)性要求高的特定工作環(huán)境下有非常高的使用價(jià)值.

在完成FPGA電路設(shè)計(jì)后,利用仿真工具對(duì)該電路模塊進(jìn)行了功能性時(shí)序仿真[10],如圖7所示.結(jié)合C語言程序的運(yùn)行結(jié)果,可以看出該電路模型運(yùn)行結(jié)果準(zhǔn)確無誤.

(a) 數(shù)據(jù)輸入部分

4 結(jié)語

本文通過FPGA高速實(shí)現(xiàn)了國(guó)內(nèi)自主研發(fā)的分組密碼算法NBC 128/128的加密過程,對(duì)NBC 128/128算法的字節(jié)序進(jìn)行了更適用于FPGA的優(yōu)化[11],從算法層面縮減了硬件邏輯塊資源的占用.在FPGA設(shè)計(jì)過程中使用分時(shí)、分塊數(shù)據(jù)輸入技術(shù)、有限狀態(tài)機(jī)技術(shù)、流水線技術(shù)和非阻塞賦值技術(shù)實(shí)現(xiàn)了NBC128/128的高速電路,電路的可擴(kuò)展性能夠滿足明文與密鑰長(zhǎng)度的倍數(shù)增加,大大提高了密碼算法的工作效率及其安全保障[12].本文通過硬件電路時(shí)序仿真工具驗(yàn)證了整體設(shè)計(jì)的可行性和準(zhǔn)確性.