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

王傳福 呂植成

（湖北經(jīng)濟(jì)學(xué)院信息工程學(xué)院 湖北武漢 430205）

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

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

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

一、數(shù)字鋸齒混沌

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

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

式（1）轉(zhuǎn)化到數(shù)字域上，并兩邊同乘2N可以得到式

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

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

表1 數(shù)字鋸齒混沌的參數(shù)

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

表2 當(dāng)β = 30517578125，M = 235時(shí)，數(shù)字鋸齒混沌的隨機(jī)性測試

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

表3 數(shù)字鋸齒混沌硬件資源消耗表

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

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

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

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

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

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

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

參數(shù)矩陣β中元素。

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

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

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

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

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

表5 x1n的隨機(jī)性測試

表6 當(dāng)N = 35時(shí)，6維數(shù)字鋸齒混沌硬件消耗

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

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

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

三、結(jié)語

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