一種新型序列密碼的設(shè)計與實現(xiàn)

趙 培，趙景琰，金鷹翰，趙 穎，王進祥

(哈爾濱工業(yè)大學(xué)微電子中心，哈爾濱150001)

1 引言

序列密碼實現(xiàn)簡單、加密速度快、沒有或只有有限的傳播錯誤，在網(wǎng)絡(luò)安全等領(lǐng)域有著重要的應(yīng)用。LFSR能產(chǎn)生具有良好統(tǒng)計特性的m序列，但其線性復(fù)雜度低，直接使用不能抵御已知的明文攻擊，所以LFSF不能用作密鑰發(fā)生器而通常作為密鑰發(fā)生器的驅(qū)動部分。由于LFSR的理論已經(jīng)成熟，驅(qū)動部分的設(shè)計相對容易，故非線性組合部分的設(shè)計便成為了密鑰流生成器的重點和難點，因此LFSR與FCSR、FCSR與鐘控發(fā)生器等相結(jié)合的組合生成器成為了目前的研究熱點。

設(shè)計提出一種將LFSR、NFSR和FCSR相結(jié)合的序列生成器結(jié)構(gòu)，該結(jié)構(gòu)包含了 LFSR、FCSR和NFSR的良好代數(shù)特性，能夠獲得更大的混淆，因此更加難以被分析和破解。采用Verilog HDL建模，并在FPGA實現(xiàn)與驗證，結(jié)果表明該算法消耗資源少、加密速度快，可以應(yīng)用于網(wǎng)絡(luò)安全等領(lǐng)域。

2 常見組合發(fā)生器的結(jié)構(gòu)與特點

［2，3－4］中所提出的算法。文獻［3］提出了基于FCSR和LFSR相結(jié)合的密鑰流生成算法，其特點是結(jié)合了FCSR和LFSR的良好代數(shù)特性，產(chǎn)生的序列具有較好的偽隨機性，在此將其簡稱為FL算法;參考文獻［4］提出的算法基于LFSR并借鑒了DES等分組密碼的設(shè)計思想，其特點是能產(chǎn)生較好的非線性偽隨機序列，簡稱其為LS算法。文獻［2］提出的Grain－128屬于應(yīng)用了NFSR的非線性前饋發(fā)生器。

FL算法的基本結(jié)構(gòu)如圖1(a)所示。該生成器的左半部分由4個LFSR進行帶進位加后輸出序列，并以鐘控方式驅(qū)動右半部分4個FCSR。當左半部分輸出1時，各個FCSR進行移位操作，否則各半部分保持上一次的輸出。最后將左右兩個部分的輸出結(jié)構(gòu)進行異或運算。由于利用了帶進位加打破了LFSR的代數(shù)特性，而用異或運算攪亂了FCSR的代數(shù)特性，因此該密鑰發(fā)生器具有良好的混淆特性和偽隨機性。但是該算法中的LFSR級數(shù)分別為13，17，19，23，經(jīng)查證23不是梅森素數(shù)，因此易造成周期較小;另外由于密鑰長度較短，易于被分析和破解。

LS算法的基本結(jié)構(gòu)如圖1(b)所示。該算法為了增強密鑰的非線性，使用了:①依賴數(shù)據(jù)的循環(huán)移位;②S盒;③循環(huán)結(jié)構(gòu);因此該算法具有較高的非線性。另外該算法借鑒了分組密碼的設(shè)計思想，可以實現(xiàn)雙字的加密，因此具有較高的加密速度。但是DES算法里面的S盒子已經(jīng)不夠強壯，加密強度不高;以及該設(shè)計方案在K1的低五位全為零時，存在循環(huán)失效的危險。

Grain算法的基本結(jié)構(gòu)如圖1(c)所示。該算法的顯著特點是硬件實現(xiàn)占用資源少、功耗較低、加密速度快。該經(jīng)典算法的不足之處在于密鑰流僅有84bit，隨著計算機的發(fā)展，可以通過足夠長度的密文分析出密鑰，因此算法的保密密鑰長度需要加長，以提高序列的保密性。

圖1 三種參考算法的基本結(jié)構(gòu)

3 新型序列密碼算法

針對目前序列密碼發(fā)生器大多基于線性反饋移位寄存器以及上述參考組合序列密碼的缺點，提出了一種通過將短移位寄存器級聯(lián)在一起成為較長移位寄存器，通過引入控制信號控制多選器，配合各個移位寄存器的非線性組合函數(shù)，實現(xiàn)不同的加密算法。不但可以實現(xiàn)上述的三種參考算法，并且可以實現(xiàn)三種參考算法的混合加密，大大提高了傳輸數(shù)據(jù)的混淆度和數(shù)據(jù)的保密性。

3.1 對參考算法的改進

針對FL算法、FS算法和Grain－128算法的不足，在保留原算法細想的基礎(chǔ)上對其做如下修改:

(1)將 FL算法的四個 LFSR級數(shù)從13，17，19和23 改為17，19，31 和61

(2)將FL算法的四個FCSR級數(shù)從17，18，19和20增加為22，23，25和26

(3)LS算法的的四個LFSR可直接采用FL算法的LFSR，最后增加一個13級的LFSR即可，因此LFSR 的級數(shù)為 13，17，19，31，61

(4)增加一個19級的移位寄存器與其余5個LFSR級聯(lián)，構(gòu)成Grain－128算法的128級LFSR

(5)將DES算法的S盒替換為SNOW2.0的S盒，并同時將密鑰K2生成模塊也對應(yīng)的替換為32bits，并去掉擴展函數(shù)模塊

(6)將k1循環(huán)左移mod32位，并將結(jié)果賦值給密鑰K2生成模塊的輸入和k1，若k1mod32為0，將結(jié)果或32’h0000001f后再賦值給密鑰K2生成模塊的輸入和k1

(7)Grain－128的初始密鑰由84位增加為128位

其中改進(1)(2)(7)的目的是增大序列的周期，以提高數(shù)據(jù)的保密性;改進(3)(4)的目的是實現(xiàn)資源的重復(fù)利用，以減少硬件消耗;改進(5)的目的采用保密性更強的SNOW2.0盒子，提高序列的非線性;改進(6)的目的是克服了在特定情況下的加密失效。如此設(shè)計的目的不但可以增大序列的周期而且也可以實現(xiàn)硬件資源的復(fù)用。

3.2 短移位寄存器級聯(lián)的基本原理

短移位寄存器級聯(lián)的基本原理如圖2所示。

當ctrl為低電平時，移位寄存器1和移位寄存器2由其各自的反饋函數(shù)f1(x)和f2(x)決定其性質(zhì)。2個移位寄存器最右邊的狀態(tài)s10和s20輸出經(jīng)非線性組合A輸出z1，z=z1。此時完成的是一種非線性組合序列發(fā)生器算法。

當ctrl為高電平時，移位寄存器1和2級聯(lián)成為一個新的較長移位寄存器，由饋函數(shù)f3(x)確定其性質(zhì)，從移位寄存器3上引出相應(yīng)的多個抽頭經(jīng)非線性組合B輸出，此時完成的是前饋發(fā)生器功 能。

圖2 短移位寄存器級聯(lián)示意圖

FL算法和LS算法可以直接使用上述短移位寄存器實現(xiàn)，而Grain－128算法需要將移位寄存器級聯(lián)才能實現(xiàn)。Grain－128算法需要128級NFSR以及128級的LFSR，其中128級的NFSR直接由FL算法和LS算法共同使用的4個LFSR級聯(lián)構(gòu)成;128級的LFSR由FL算法的4個FCSR以及FL算法的第5個LFSR和新增的19級移位寄存器級聯(lián)而成，這樣有利用減少硬件資源的消耗。

3.3 動態(tài)反饋

為進一步加強數(shù)據(jù)的加密強度，對線性反饋移位寄存器引入動態(tài)反饋多項式(DFP)，同樣由控制密鑰控制其反饋多項式的選擇。其簡易原理如圖3所示。

圖3 DFP簡易原理圖

在本設(shè)計中，Grain－128的LFSR采用其自定義的本原多項式;FL算法和LS算法共同使用的4個LFSR采用動態(tài)反饋的本原多項式，其中17級的LFSR具有三個本原反饋多項式、19級的LFSR具有2個本原反饋多項式、31級的LFSR具有6個本原反饋多項式、61級的LFSR具有2個本原反饋多項式。采用控制信號，控制反饋多項式的選擇，使得該設(shè)計可以實現(xiàn)三種73類不同的加密算法。

采用短移位寄存器級聯(lián)的結(jié)構(gòu)，實現(xiàn)寄存器資源的復(fù)用，不但有利用減小寄存器資源的消耗，而且可使設(shè)計變的更加靈活。使得設(shè)計不但可以實現(xiàn)特定的加密算法，而且在混合加密時，由于動態(tài)反饋多項式的存在使得序列的偽隨機性、混淆度和保密性都增大了，更加難以被分析和破解。

4 硬件實現(xiàn)與結(jié)果分析

4.1 硬件實現(xiàn)的基本結(jié)構(gòu)

三種參考算法生成的密鑰流的數(shù)據(jù)類型不同，其中FL和Grain－128實現(xiàn)的是比特加密，LS算法實現(xiàn)的是雙字加密。因此硬件實現(xiàn)的結(jié)構(gòu)圖如圖4所示。

其中KeyIV_REG模塊主要完成密鑰和初始變量的注入;KSG是設(shè)計的主體部分，其主要功能是接收通過KeyIV_REG注入的密鑰和初始變量，按設(shè)計的算法產(chǎn)生相應(yīng)的密鑰流，并控制其他兩個模塊正常工作;EncryFun模塊負責(zé)進行具體的加密解密運算。

4.2 系統(tǒng)工作流程

在設(shè)計時引入強制控制信號，在該信號的控制下，通過配置移位寄存器可以實現(xiàn)三種參考算法中的任意一種。

FL和Grain－128算法實現(xiàn)的是bit加密，而LS算法實現(xiàn)的是雙字加密，因此易知在混合加密時，該設(shè)計并沒有一直在讀取外部數(shù)據(jù)。

下面簡述混合加密的基本工作過程:在上電復(fù)位后KeyIV_REG開始接收外部32bits的數(shù)據(jù)，并開始密鑰和初始變量的注入，控制信號也完成初始化;KSG模塊接收到密鑰和初始化變量，初始化內(nèi)部所有的移位寄存器，并按照控制信號的要求(加密算法以及何種動態(tài)反饋)，配置出密鑰流的數(shù)據(jù)通路，產(chǎn)生相應(yīng)的密鑰流，并根據(jù)當前的加密算法和運行狀態(tài)，輸出信號標志何時可以重新讀入下一組加密數(shù)據(jù);EncryFun利用KSG模塊產(chǎn)生的密鑰流來加密KeyIV_REG接收的數(shù)據(jù)。由分析可知FL和Grain－128算法產(chǎn)生的密鑰流是bit形式的，而LS算法產(chǎn)生的密鑰流為32bits，因此EncryFun要根據(jù)控制信號的要求決定是否對接收到的密鑰流進行串并轉(zhuǎn)換，之后再對數(shù)據(jù)進行加密。當前數(shù)據(jù)加密結(jié)束時，在KSG模塊將控制信號與內(nèi)部寄存器進行異或運算，對控制信號進行更新;利用更新后的控制信號，確定下一組數(shù)據(jù)的加密算法，開始下一組數(shù)據(jù)的加密，使得整個數(shù)據(jù)的加密過程中各種加密算法“亂序”的對數(shù)據(jù)進行加密，以使加密序列難以被分析和破解。

圖4 序列密碼的結(jié)構(gòu)圖

4.3 FPGA實現(xiàn)與結(jié)果分析

本設(shè)計采用Verilog HDL進行建模，在經(jīng)過功能仿真之后按照修改后的設(shè)計參數(shù)，在Altera Cyxlone II系列的EP2C35F672C6 FPGA芯片上進行了硬件實現(xiàn)，實現(xiàn)結(jié)果表明算法功能具有較快的加密解密速度(時鐘頻率最高可達109.52MHz)，達到了設(shè)計要求。在相同約束條件下幾種算法性能的比較如表1所示。

表1 幾種參考算法的比較

通過分析可知，該算法具有較高的運算速度(100MHz以上)，LE資源消耗與三種參考算法消耗資源的總和相當，這是因為Grain－128算法資源消耗少(主要是FL和LS算法資源消耗大)，在將移位寄存器級聯(lián)時在設(shè)計中加入較多的選擇器，因此造成了資源消耗相當?shù)慕Y(jié)果。由于設(shè)計考慮了寄存器資源的重復(fù)利用，因此寄存器資源減小的較為明顯。雖然該設(shè)計并沒有顯著減小資源消耗，但該設(shè)計可產(chǎn)生3類(73種)不同的加密算法，而且在混合加密時可大大降低數(shù)據(jù)被分析和破解的幾率。若單獨實現(xiàn)三種算法不但不會節(jié)省資源而且對加密數(shù)據(jù)的安全性沒有任何改進。

5 結(jié)論

在參考三種具有代表性的序列密碼基礎(chǔ)上，設(shè)計實現(xiàn)了一種可控的，將短移位寄存器級聯(lián)成長移位寄存器，通過控制密鑰選擇反饋以改變加密方式的新型序列密碼發(fā)生器。該序列密碼發(fā)生器可以產(chǎn)生多種加密算法，加密速度較快、資源消耗相對較少，在混合加密時可產(chǎn)生偽隨機性很強的序列。該算法具有多種變形，可以應(yīng)用于網(wǎng)絡(luò)安全等領(lǐng)域。

參考文獻:

［1］C E Shannon.Communication Theory of Secret System［M］.Bell Syst.Tech.J.1949，28:656 －715.

［2］M Hell，T Johansson，A Maximov.A Stream Cipher Proposal:Grain－128.IEEE International Symposium on Information Theory［R］.Seattle，2006:1614 －1618.

［3］鄭宇，何大可，唐小虎，等.基于FCSR和LSFR相結(jié)合的密鑰流生成器［J］.計算機工程，2007，33(5):32－35.

［4］李昌剛，張昕，朱芳來，等.一種新的密鑰流發(fā)生器設(shè)計算法［J］.計算機工程，2007，33(10):138 －140.

［5］王相生.序列密碼設(shè)計與實現(xiàn)的研究［D］.北京:中國科學(xué)院，2001:28－55.