一種新型序列密碼的設計與實現

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

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

1 引言

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

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

2 常見組合發生器的結構與特點

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

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

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

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

圖1 三種參考算法的基本結構

3 新型序列密碼算法

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

3.1 對參考算法的改進

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

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

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

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

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

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

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

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

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

3.2 短移位寄存器級聯的基本原理

短移位寄存器級聯的基本原理如圖2所示。

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

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

圖2 短移位寄存器級聯示意圖

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

3.3 動態反饋

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

圖3 DFP簡易原理圖

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

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

4 硬件實現與結果分析

4.1 硬件實現的基本結構

三種參考算法生成的密鑰流的數據類型不同，其中FL和Grain－128實現的是比特加密，LS算法實現的是雙字加密。因此硬件實現的結構圖如圖4所示。

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

4.2 系統工作流程

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

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

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

圖4 序列密碼的結構圖

4.3 FPGA實現與結果分析

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

表1 幾種參考算法的比較

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

5 結論

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

參考文獻:

［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相結合的密鑰流生成器［J］.計算機工程，2007，33(5):32－35.

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

［5］王相生.序列密碼設計與實現的研究［D］.北京:中國科學院，2001:28－55.