一種基于多維數字鋸齒混沌的偽隨機序列發(fā)生器及其性能分析

王傳福 呂植成

（湖北經濟學院信息工程學院 湖北武漢 430205）

混沌是一種復雜的非線性動力學系統(tǒng)，具有初值敏感性、軌道遍歷性、非周期性等特點[1]，由于這些特性與香濃提出的混淆與擴散相一致[2]，因此利用混沌系統(tǒng)被認為是構造偽隨機序列的一種新型設計方法。混沌系統(tǒng)可被分為連續(xù)混沌系統(tǒng)和離散混沌系統(tǒng)。對數字系統(tǒng)來說，連續(xù)混沌系統(tǒng)需要先離散化再數字化。連續(xù)混沌系統(tǒng)離散化常用的方法有歐拉法[3]和龍格庫塔法[4]。與連續(xù)混沌系統(tǒng)相比，離散混沌系統(tǒng)的數字化更簡單，并且更適用于數字偽隨機序列發(fā)生器。但由于有限字長效應，數字混沌系統(tǒng)的混沌特性逐漸退化，并且表現(xiàn)出短周期性和多周期性[5-8]。混沌系統(tǒng)也被分為高維混沌系統(tǒng)和低維混沌系統(tǒng)。低維混沌系統(tǒng)實現(xiàn)效率高，資源消耗小。常用的低維混沌系統(tǒng)有Logistic映射[9]，Henon映射[10]，鋸齒混沌[11]等。低維數字混沌系統(tǒng)的混沌特性退化較為嚴重，輸出序列難以保證具有較大的周期[5,7,8]。高維混沌系統(tǒng)具有更復雜的非線性動力學行為，但具有硬件實現(xiàn)資源消耗大，運行速度低等缺陷。

為了使數字混沌序列發(fā)生器利用較少的計算復雜度產生具有較大周期的輸出序列，多種簡單數字混沌相結合的形式得到了深入的研究。與其它低維離散混沌相比，鋸齒混沌具有非常簡單的運算形式，并且其輸出值在0和1之間，容易進行數字化處理。鋸齒混沌的多種組合方式同時得到了深入的研究[12-16]。在硬件實現(xiàn)中，乘法運算占用硬件資源較多，且對硬件實現(xiàn)的速度性能有較大的限制[17-21]。

為了進一步提高輸出序列的周期，本文在保證低資源消耗的前提下，利用簡單的鋸齒混沌為基本模型，設計出一種基于多維數字鋸齒混沌的偽隨機序列發(fā)生器。為了減少計算復雜度，多維數字鋸齒混沌的參數都被定義為2的倍數。與其它多種組合的鋸齒混序列發(fā)生器相比，一種簡單的非線性除法運算被引入，可以明顯增加偽隨機序列的周期，并且更逼近最大周期的上限。經驗證，本文設計的基于多維數字鋸齒混沌的偽隨機序列發(fā)生器輸出序列的周期得到極大提升，并能通過NIST套件的隨機性測試。本文第一部分介紹了數字鋸齒混沌。第二部分提出了一種基于數字多維鋸齒混沌的偽隨機序列發(fā)生器。最后一部分對全文做了總結。

一、數字鋸齒混沌

鋸齒混沌是一種廣泛運用的混沌系統(tǒng)，它被定義為：

由于鋸齒混沌輸出的全是小數，因此數字化后的鋸齒混沌更利于硬件實現(xiàn)。小數xn的N比特定點數n表示為

式（1）轉化到數字域上，并兩邊同乘2N可以得到式

將式（2）帶入式（3）可以得到數字鋸齒混沌（4）

數字化的鋸齒混沌的最大周期Tmax=M/4。常用的數字鋸齒混沌的參數如表1所示。

表1 數字鋸齒混沌的參數

數字鋸齒混沌輸出值是整數值。在進行隨機性測試前需要被量化。量化方法為：輸出值大于等于M/2，輸出為1；輸出值小于M/2，輸出為0。NIST 套件是美國國家標準與技術研究院測試偽隨機序列隨機性的標準檢測工具，共有15種測試項目。當NIST 套件輸入為Q 個K 比特長的序列時，返回實驗結果u-value 和ration。當u-value 大于10-4時，說明所有待測數據能夠通過NIST 套件測試，并且該測試序列具有較好的隨機性。本文針對β= 30517578125，M= 235的數字鋸齒混沌，選取其產生的100 條長度為2000000 比特的序列進行測試。數字鋸齒混沌輸出序列的隨機性測試如表2所示。

表2 當β = 30517578125，M = 235時，數字鋸齒混沌的隨機性測試

在表2中，NonOverlappingTemplate的u-vale明顯小于10-4，未能通過NIST 套件測試，其輸出序列的隨機性較低。利用FPGA進行硬件實現(xiàn)的資源消耗如表3所示。

表3 數字鋸齒混沌硬件資源消耗表

吞吐量是輸出比特與主頻的乘積。數字鋸齒混沌每個周期只能輸出1 比特序列。因此，利用FPGA 實現(xiàn)的數字鋸齒混沌的吞吐量為72.97M/S。

二、基于數字多維鋸齒混沌的偽隨機序列發(fā)生器

雖然數字鋸齒混沌的偽隨機特性并不理想，但是數字鋸齒混沌系統(tǒng)十分簡單。因此，本文就以數字鋸齒混沌為基本模型構造了多維數字鋸齒混沌，并分析了基于數字多維鋸齒混沌的偽隨機序列發(fā)生器的性能。

（一）定點數上的快速算術運算。算術運算主要包括加法運算，減法運算，乘法運算和除法運算。除法運算相對比較繁瑣。因此，在運算過程中除法運算需要盡量避免。乘法是常用的非線性運算操作，但是乘法計算的復雜度較高，容易產生更多資源消耗。若以2的倍數作為乘數或除數時會更為簡單，當乘數是2的倍數時，乘數2n使被乘數左移n位，低位由0填補；當除數是2 的倍數時，除數2n使被除數右移n位，高位由0 填補。乘法和除法的運算可轉化為移位運算。因此，計算量可以得到較大優(yōu)化。與減法相比，加法運算更容易，復雜度更小。因此，本文選用加法運算和2的倍數的乘法運算及除法運算來設計基于數字鋸齒混沌的偽隨機序列發(fā)生器。

（二）多維數字鋸齒混沌。本文將多個一維鋸齒混沌組合形成多維的鋸齒混沌迭代方程。多維鋸齒混沌方程為：

其中M= 1，Pn被定義為(xm-1n,xm-2n,xm-3n,xm-4n, ···,x2n,x1n)，β是m×m的矩陣。

由表1可知，每個數字鋸齒混沌周期性與β的周期性有關，為增大輸出周期，減少計算復雜度，式（6）β中的元素被固定為2 的指數。為了進一步降低計算復雜度，β中每行至多有兩個非零元素。根據以上考慮，特殊的參數矩陣β如下所示

參數矩陣β中元素。

（三）周期分析。周期是偽隨機序列非常重要的一個性質。將式（2）帶入式（5）中進行數字化處理，可得到多維數字鋸齒混沌。本文以m= 6 時的多維數字鋸齒混沌為例，進行周期分析。不同精度下的6維數字鋸齒混沌序列發(fā)生器輸出序列周期如表4所示。

表4 6維數字鋸齒混沌輸出序列周期分析

在表4中，T為本文提出的6維數字鋸齒混沌輸出序列的周期，隨著位數精度的增大，偽隨機序列T的周期急劇增大。T1為一維組合鋸齒混沌輸出序列的周期[16]，T2為加入了擾動的一維組合鋸齒混沌輸出序列的周期[17]。Ti是同等條件下輸出序列周期的上限。由參數m和N構成的組合鋸齒混沌能夠產生的大周期為2Nm- 1。對三種鋸齒混沌輸出序列的周期性進行比較，利用本文方案產生序列的周期T明顯比T1和T2大，并且更接近理想周期。

（四）隨機性分析。本文對6維數字鋸齒混沌輸出的序列進行了隨機性測試。將輸出的x1n序列分為100 條周期長度為2000000的多組序列，一同進行NIST套件測試。為了與表2進行對比，系統(tǒng)精度N分別選取為12、23和35。

由表5可知，當系統(tǒng)精度N分別選取12、23和35時，輸出的序列都通過了NIST 套件的測試。當N為35 時，在與表2 相同精度下，6維數字鋸齒混沌輸出序列的u-value明顯高于表2中的數值，該數據表明6維數字鋸齒混沌輸出的序列具有更高的隨機性和安全性。

表5 x1n的隨機性測試

表6 當N = 35時，6維數字鋸齒混沌硬件消耗

（五）硬件性能分析。數字鋸齒混沌包含乘法運算，隨著計算精度N的增加，硬件資源消耗急劇增大。在同樣系統(tǒng)精度N與迭代次數n的情況下，本文提出的6維數字鋸齒混沌中的兩個加法運算可以在同一個時鐘周期內實現(xiàn)，在硬件實現(xiàn)上可以并行運算，具有非常高的并行運算效率。其它兩種方案是順序計算的結構[16,17]，需要多個加法運算周期。因此，本文提出的6維數字鋸齒混沌硬件實現(xiàn)速度比其它兩種方案更快且資源實現(xiàn)更小。在N= 35時，本文提出方案硬件消耗和輸出序列吞吐量如下表所示。

（六）密鑰空間分析。密鑰空間越大抵抗暴力攻擊的能力越強。目前，密鑰空間為2128時足夠抵抗現(xiàn)有計算機的暴力攻擊。在多維鋸齒混沌（5）中，N和m是兩個可根據實際情況更改的參數，通過改變N和m可以改變密鑰空間的大小，多維鋸齒混沌（5）密鑰空間為2Nm。

（七）實現(xiàn)方法。在硬件實現(xiàn)方面，本文選用的FPGA芯片是Altera 廠家的CycloneII-EP2C70F896C8 芯片。仿真軟件為QuartusII，且版本號為13.0。測試所用的計算機為Win10系統(tǒng)，芯片為Intel CoreI5-4460，CPU 為3.20GHz。在NIST 測試方面，NIST測試軟件型號為STS-2.1.2，Block frequency 測試中的分塊長度為128，NonOverlappingTemplate 測試中的分塊長度為9，OverlappingTemplate測試中的分塊長度為9，ApproximateEntropy測試分塊長度為10，Serial測試中的分塊長度為16，LinearComp lexity測試分塊長度為500。

三、結語

數字化后的鋸齒混沌的隨機性并不理想，并且輸出序列的周期隨參數選取的不同而不同，具有多周期和短周期特性。本文利用簡單的鋸齒混沌構造出了一種基于數字多維鋸齒混沌的偽隨機序列發(fā)生器，該偽隨機序列發(fā)生器具有并行結構，硬件實現(xiàn)資源消耗較少，輸出序列周期大，且每個輸出序列隨機性都通過了NIST套件的測試，結果顯示該輸出序列具有較高的隨機性和安全性。