柏森，周龍福，郭輝，閆兵

（1. 重慶工程學(xué)院軟件學(xué)院，重慶400056；2. 重慶通信學(xué)院信息工程系，重慶400035；3. 61541部隊，北京 100094）

基于隨機(jī)序列統(tǒng)計特性的偽隨機(jī)序列生成方法

柏森1,2，周龍福1，郭輝3，閆兵2

（1. 重慶工程學(xué)院軟件學(xué)院，重慶400056；2. 重慶通信學(xué)院信息工程系，重慶400035；3. 61541部隊，北京 100094）

在現(xiàn)有生成偽隨機(jī)序列的方法中，產(chǎn)生的偽隨機(jī)序列存在均衡性、游程特性不夠好的問題。根據(jù)隨機(jī)序列的統(tǒng)計特性，在騎士巡游問題 SemiHam求解算法的基礎(chǔ)上，提出了基于隨機(jī)序列統(tǒng)計特性的偽隨機(jī)序列生成方法。首先，對棋盤中的格子設(shè)定不同長度的0、1游程值；然后，再用騎士巡游問題SemiHam求解算法產(chǎn)生的Hamilton圈對設(shè)定游程值的棋盤進(jìn)行掃描；最后，取出0、1游程值，得到偽隨機(jī)序列。實驗結(jié)果表明，該算法產(chǎn)生的偽隨機(jī)序列滿足隨機(jī)序列統(tǒng)計特性，且隨機(jī)性較好。

偽隨機(jī)序列；隨機(jī)序列統(tǒng)計特性；SemiHam算法；NIST SP800-22隨機(jī)性測試

1 引言

在數(shù)據(jù)加密的應(yīng)用中，人們希望得到真正的隨機(jī)序列，但能否重復(fù)產(chǎn)生真正的隨機(jī)序列，一直是爭論的問題。由于偽隨機(jī)序列能夠重復(fù)產(chǎn)生和處理[1]，并且具有良好的隨機(jī)特性，在數(shù)據(jù)加密[2]、衛(wèi)星導(dǎo)航[3]、擴(kuò)頻通信[4]、探地雷達(dá)[5]等方面都有廣泛的應(yīng)用。因此，偽隨機(jī)序列的生成方法一直是研究的重點問題之一。

良好的偽隨機(jī)序列應(yīng)具有真隨機(jī)序列的統(tǒng)計特性[6]：偽隨機(jī)序列中0和1的數(shù)量相等或相差1個；游程個數(shù)為序列長度的，長度為l的游程個數(shù)占總游程個數(shù)的。目前產(chǎn)生偽隨機(jī)序列的方法主要有混沌[7～10]、有限域[11]、自動細(xì)胞機(jī)[12]等，但這些方法產(chǎn)生的偽隨機(jī)序列不能完全滿足真隨機(jī)序列的統(tǒng)計特性。文獻(xiàn)[7]給出了基于二維新混沌系統(tǒng)的偽隨機(jī)序列生成方法，利用二維混沌系統(tǒng)產(chǎn)生混沌序列，序列通過取余得到密碼流，十進(jìn)制轉(zhuǎn)化為二進(jìn)制，得到偽隨機(jī)序列。文獻(xiàn)[10]通過Logistic混沌產(chǎn)生混沌序列，設(shè)定閾值量化混沌序列，產(chǎn)生二進(jìn)制序列。文獻(xiàn)[11]用橢圓曲線和跡函數(shù)，通過設(shè)定參數(shù)值產(chǎn)生偽隨機(jī)序列。文獻(xiàn)[12]提出了基于細(xì)胞自動機(jī)的組合偽隨機(jī)序列的生成方法，用一組單個細(xì)胞自動機(jī)產(chǎn)生偽隨機(jī)序列，將序列的一部分采用異或運算進(jìn)行組合，將組合序列與其他序列進(jìn)行異或組合，產(chǎn)生偽隨機(jī)序列。這些方法產(chǎn)生的偽隨機(jī)序列均衡性、游程特性較差，0、1數(shù)量相差較大，不同長度的游程個數(shù)與真隨機(jī)序列的游程個數(shù)有偏差。

本文在騎士巡游問題 SemiHam求解算法隨機(jī)生成Hamilton圈[13]的基礎(chǔ)上，根據(jù)偽隨機(jī)序列統(tǒng)計特性，提出了基于偽隨機(jī)序列統(tǒng)計特性的偽隨機(jī)序列生成方法。該方法首先對棋盤中的格子設(shè)定不同長度的0、1游程值，再用騎士巡游問題SemiHam求解算法產(chǎn)生的 Hamilton圈對設(shè)定游程值的棋盤進(jìn)行掃描，取出0、1游程值，得到偽隨機(jī)序列。

2 騎士巡游問題SemiHam求解算法

在一個棋盤中，求解騎士巡游問題的方法很多[13～16]。文獻(xiàn)[13]中騎士巡游問題求解的SemiHam 算法是在馬步圖中隨機(jī)找出一條Hamilton圈的方法，通過簡單擴(kuò)展（simple extension）、圈擴(kuò)展（cycle extension）和旋轉(zhuǎn)（rotation）的方法，隨機(jī)產(chǎn)生頂點序列，算法流程如圖1所示。

首先，將一個具有N格的棋盤轉(zhuǎn)換為N個頂點的馬步圖和N×N的鄰接矩陣，并將頂點標(biāo)識為0～N?1。其次，隨機(jī)選取一個起始點，通過simple extension的方法，依次在序列首和序列尾擴(kuò)展；當(dāng)序列首和尾有邊連接時（形成圈），通過 cycle extension的方法對圈序列進(jìn)行拆分，并繼續(xù)進(jìn)行簡單擴(kuò)展；當(dāng)simple extension與cycle extension不能進(jìn)行時，進(jìn)行rotation操作，直到簡單擴(kuò)展、圈擴(kuò)展和旋轉(zhuǎn)操作不能進(jìn)行為止。最后，檢查各頂點是否遍歷、序列頭和序列尾是否有邊連接，當(dāng)遍歷各頂點且序列頭和序列尾有邊連接時，則成功；否則，失敗。

簡單擴(kuò)展（simple extension）。簡單擴(kuò)展分為序列頭擴(kuò)展和序列尾擴(kuò)展，如果序列頭的頂點可以跳動到未歷經(jīng)的頂點時，在序列頭隨機(jī)添加未歷經(jīng)的新頂點；如果序列尾的頂點可以跳動到未歷經(jīng)的頂點時，在序列尾隨機(jī)添加未歷經(jīng)的新序列尾頂點。

圈擴(kuò)展（cycle extension）。當(dāng)序列v0v1…vl?1vl尾頂點與序列頭頂點有邊連接時，此序列為一個圈。對序列進(jìn)行拆分，依次檢測各頂點是否可以跳動到未歷經(jīng)的頂點，此頂點一定存在，若存在多個這樣的頂點，則隨機(jī)選取一個頂點 vi，在此處進(jìn)行拆分，vivi?1…v1v0和 vlvl?1…vi+1vi，然后對序列vivi?1…v1v0vlvl?1…vi+1vi進(jìn)行簡單擴(kuò)展。

旋轉(zhuǎn)（rotation）。如果與序列頭、序列尾連接的頂點都在序列中，對序列進(jìn)行旋轉(zhuǎn)操作。序列 v0v1…vl?1vl檢查 v2～vl?1是否有頂點與 v0有邊連接，當(dāng)頂點vi與v0有邊連接時，對v0…vi?1旋轉(zhuǎn)，旋轉(zhuǎn)后的序列為vi?1…v0vi…vl?1vl，對序列進(jìn)行簡單擴(kuò)展和圈擴(kuò)展；檢查序列v0v1…vl?1vl的尾頂點vl，看v1v2…vl?2是否有與尾頂點vl有邊連接，如果頂點 vi與 vl有邊連接時，對 vi+1…vl旋轉(zhuǎn)，旋轉(zhuǎn)后的序列為 v0v1…vivl…vi+1，再進(jìn)行簡單擴(kuò)展和圈擴(kuò)展。

圖1 騎士巡游問題SemiHam求解算法流程

3 基于騎士巡游問題解的偽隨機(jī)序列生成方法

3.1 基本思想

騎士巡游問題是尋找棋盤中的一條Hamilton圈。由于馬步的跳動是按照“日”的方式，行跳一個格子，列跳2個格子；或行跳2個格子，列跳1個格子。當(dāng)棋盤中的格子以黑、白交叉分布時，馬跳動的軌跡也是黑、白交叉的，圖2為棋盤中騎士巡游軌跡的部分顯示。如果一個白、黑格子分別代表一個0游程和1游程，那么，通過騎士巡游路徑組合各格子的游程值，就可以得到具有 n（棋盤格子數(shù)）個游程的序列。騎士巡游問題 SemiHam求解算法是在馬步圖中隨機(jī)生成的一條Hamilton圈，根據(jù)隨機(jī)序列的統(tǒng)計特性，對棋盤中的格子賦不同長度的游程值，按照騎士巡游問題 SemiHam求解算法產(chǎn)生的騎士巡游問題路徑，對棋盤中的格子進(jìn)行掃描，取出游程值，產(chǎn)生偽隨機(jī)序列。

3.2 棋盤的賦值

1) 棋盤賦值路徑

圖3為一個黑、白格子棋盤，其中，白格子代表0游程用0來表示；黑格子代表1游程用1來表示。一串0、1交叉的數(shù)據(jù)串對棋盤進(jìn)行賦值。當(dāng)采用橫向掃描（光柵掃描）的方法對棋盤賦值，列數(shù)為奇數(shù)時，可以正確賦值，黑、白格子交叉即0、1交叉分布，如圖3(a)所示。當(dāng)列數(shù)為偶數(shù)時，棋盤則賦值不正確，0游程和1游程在同一列，如圖3(b)所示，馬在棋盤中跳動時，會出現(xiàn)連續(xù)0或1的情況。所以，不是所有的掃描方法都適合對棋盤進(jìn)行賦值。經(jīng)過對掃描方法的研究[17]，可以按照c、o、a、s、z、b掃描方式進(jìn)行（如圖4所示）。文中采用的掃描方式為c方式（如圖5所示），這種方式對奇、偶數(shù)列都可以正確賦值。

圖2 騎士巡游路徑的部分顯示

圖3 光柵掃描的方式賦值

圖4 掃描方式

圖5 c掃描的方法賦值

2) 棋盤賦值方法

偽隨機(jī)序列是具有隨機(jī)特性的統(tǒng)計特性[6]。序列中0和1的個數(shù)接近相等；序列中長度為1的游程約占游程總數(shù)的，長度為2的游程約占總游程數(shù)的，長度為l的游程約占總游程的（如表1所示）。但在實際應(yīng)用中，偽隨機(jī)序列不可能完全滿足游程的統(tǒng)計特性，在某些長度的游程上存在一點偏差。例如，一個具有25個游程的偽隨機(jī)序列，長度為1的游程個數(shù)為12.5，長度為2的游程個數(shù)為6.25，長度為3的游程個數(shù)為3.125，長度為4的游程個數(shù)為1.562 5，長度為5的游程個數(shù)為0.781 25。當(dāng)完全滿足偽隨機(jī)序列的統(tǒng)計特性時，游程個數(shù)可能會出現(xiàn)小數(shù)的情況。

表1 長度為l的游程個數(shù)占總游程比例

為了滿足隨機(jī)序列的統(tǒng)計特性，在此問題上，做如下處理。首先，確定長度為l的游程數(shù)，統(tǒng)計特性求出的游程個數(shù)除以 2，得到的值通過四舍五入，得出長度為l的0游程的個數(shù)或1游程的個數(shù)。其次，確定游程總數(shù)，當(dāng)游程總數(shù)為偶數(shù)時，0游程和1游程各為游程總數(shù)的；當(dāng)游程總數(shù)為奇數(shù)時，0游程比1游程多1個，多的1個游程值設(shè)為0，在求出的長度為1的0游程數(shù)上加 1即可。通過設(shè)定，上面的例子得到很好的解決，長度為1的游程個數(shù)為13，0游程的個數(shù)為7，1游程的個數(shù)為 6；長度為 2的游程為 6，0游程和1游程的個數(shù)分別為3；長度為3的游程個數(shù)為4，0游程和1游程的個數(shù)分別為2；長度為4的游程個數(shù)為2，0游程和1游程的個數(shù)分別為1；各游程數(shù)相加，得到總的游程個數(shù)為25。通過以上的設(shè)定，0、1的數(shù)量相等或多一個0，不同長度的游程數(shù)滿足統(tǒng)計特性。

根據(jù)統(tǒng)計特性中游程的個數(shù)及不同游程所占比例，對棋盤進(jìn)行賦值。長度為1的游程，首先設(shè)置長度為1的0游程，從第一個白格子開始設(shè)置，每隔3個格子設(shè)置0；長度為1的1游程，在長度為1的0游程后面一個格子賦值1即可。長度為l的0游程，從第一格開始掃描，第一格未賦值的點設(shè)置l個0，每隔2l+1–1個格子設(shè)置l個0，長度為l的1游程，在長度為l的0游程后一格添加即可。

3.3 偽隨機(jī)序列生成方法的步驟

偽隨機(jī)序列生成方法的步驟如下。

Step1 生成一個m×n的賦值棋盤。

設(shè)置棋盤的大小，即棋盤的行數(shù)m和列數(shù)n。計算不同長度的游程個數(shù)，創(chuàng)建一個空數(shù)組Q，并按照3.2節(jié)的方法為Q賦值，Q中的各值為游程的長度。按照c掃描的方式得到m×n的賦值棋盤。

Step2 利用騎士巡游問題SemiHam求解算法生成與棋盤大小相等的頂點序列，轉(zhuǎn)化為騎士巡游路徑。

騎士巡游問題SemiHam求解算法產(chǎn)生的是被標(biāo)識的頂點序列，利用式(1)和式(2)求出馬步圖中的騎士每步所在的位置，得到騎士巡游路徑。

Step3 按照騎士巡游路徑的方式，掃描賦值棋盤，得到偽隨機(jī)序列。

偽隨機(jī)序列的生成原理如圖6所示。

算法舉例：對一個5×6的棋盤進(jìn)行賦值（如圖7(a)所示），利用騎士巡游問題SemiHam求解算法產(chǎn)生的5×6騎士巡游路徑（如圖7(b)所示），騎士巡游路徑對相同大小的賦值棋盤進(jìn)行掃描，得到偽隨機(jī)序列。例如，一個騎士巡游路徑0、8、4、17、28、15、23、27、19、6、2、10、21、29、16、5、9、1、12、25、14、18、26、22、11、3、7、20、24、13。根據(jù)序列路線掃描棋盤賦值圖，得到偽隨機(jī)序列為01010111100110001100111010 10101000011100110001100101。

圖6 偽隨機(jī)序列生成原理

圖7 5×6的棋盤賦值及騎士巡游圈

4 實驗結(jié)果及分析

4.1 實驗結(jié)果

本文算法是在偽隨機(jī)序列統(tǒng)計特性的基礎(chǔ)上，產(chǎn)生賦值棋盤，并通過騎士巡游路徑產(chǎn)生偽隨機(jī)序列。所以，偽隨機(jī)序列中0、1的個數(shù)和不同長度游程的個數(shù)取決于棋盤中的賦值。當(dāng)棋盤中的格子數(shù)為偶數(shù)時，0、1的數(shù)量相等；當(dāng)棋盤中的格子數(shù)為奇數(shù)時，0的數(shù)量比1的數(shù)量多1個。如表2所示，偽隨機(jī)序列的0、1的個數(shù)相等或相差一個，序列的均衡性較好。

表2 偽隨機(jī)序列中0、1的數(shù)量

一個偽隨機(jī)序列在理想的情況下，長度為 l的游程占總游程的。由本文算法產(chǎn)生偽隨機(jī)序列的統(tǒng)計情況如表3所示，長度為l（l 〉1）的游程中游程數(shù)為偶數(shù)，這是為保持序列的均衡性即0、1的數(shù)量相等，設(shè)定不同長度的0游程和1游程的個數(shù)相等。另一個原因，在計算游程個數(shù)時，并不是所有的游程個數(shù)結(jié)果為整數(shù)，可能會出現(xiàn)小數(shù)部分，所以游程個數(shù)并不是完全符合理想的情況。本文算法產(chǎn)生的偽隨機(jī)序列符合隨機(jī)序列的游程特性。

4.2 隨機(jī)性分析

本文算法產(chǎn)生的偽隨機(jī)序列進(jìn)行了隨機(jī)性測試，測試軟件為美國國家標(biāo)準(zhǔn)與技術(shù)研究所的NIST SP800-22測試包，sts-2.1.1測試軟件[18]。測試軟件測試項目為15項，由于每一項測試對序列的長度有要求，只進(jìn)行了其中的部分項目測試。當(dāng)測試值≥ 0.01時，認(rèn)為序列在該項測試中為隨機(jī)的；當(dāng)測試值＜ 0.01時，認(rèn)為序列在該項的測試中為非隨機(jī)的。本文算法在20×35的賦值棋盤上產(chǎn)生 5組偽隨機(jī)序列，用sts-2.1.1測試軟件對產(chǎn)生的偽隨機(jī)序列進(jìn)行測試，測試結(jié)果如表4所示。

由測試結(jié)果可以看出，只有一個測試項未通過測試，大多數(shù)測試值較大，本算法產(chǎn)生的偽隨機(jī)序列的隨機(jī)性較好。Frequency Test測試值為1，表示偽隨機(jī)序列中0和1的個數(shù)相等，序列的均衡性較好。Frequency Test within a Block測試值中4個在0.7以上，其中2個在0.9以上，說明子塊中1的分布與0的分布較為接近。Runs Test測試值相等，表示各序列中的游程個數(shù)相等，測試值為0.747 379，說明序列中游程數(shù)接近真隨機(jī)序列中游程的個數(shù)。Test for the Longest of Ones in a Block測試值3個值大于0.8，說明子塊中最長游程的比例接近真隨機(jī)分布。Serial Test測試值 3個都在0.7以上，說明指定長度的子序列出現(xiàn)的次數(shù)趨于等概。Cumulative Sums Test測試值4個值都在0.7以上，說明0、1的分布較為均勻。Linear Complexity Test測試值為0.000 039小于0.01，說明產(chǎn)生序列的線性移位器較小，序列未達(dá)到隨機(jī)序列的程度。

表3 偽隨機(jī)序列中不同長度的游程個數(shù)

表4 隨機(jī)性測試

4.3 隨機(jī)性比較

文獻(xiàn)[7,8]和文獻(xiàn)[10]是目前較新的偽隨機(jī)序列生成方法，但文獻(xiàn)[7]使用FIPS 140-2進(jìn)行隨機(jī)性測試，不便與本文進(jìn)行比較。文獻(xiàn)[8]使用硬件FPGA產(chǎn)生偽隨機(jī)序列，不好用來與本文算法進(jìn)行比較。因此，選擇與文獻(xiàn)[10]算法進(jìn)行隨機(jī)性比較，分別產(chǎn)生5組長度約為1 400的偽隨機(jī)序列。根據(jù)NIST SP800-22測試標(biāo)準(zhǔn)[18]，利用sts-2.1.1測試軟件進(jìn)行測試。測試結(jié)果如表5所示，測試值為每種算法5組偽隨機(jī)序列的平均值。

表5 隨機(jī)性比較

由表5可以看出，在9項測試中，本文算法有8項測試值大于文獻(xiàn)[10]算法。本文算法在線性復(fù)雜度上小于文獻(xiàn)[10]算法，說明序列復(fù)雜度相對較低，但測試值都在0.5以上，滿足隨機(jī)性要求。從總體隨機(jī)性上看，本文算法好于文獻(xiàn)[10]算法。

5 結(jié)束語

本文基于騎士巡游問題的SemiHam求解算法，設(shè)計了偽隨機(jī)序列生成方法。實驗結(jié)果的對比分析表明，設(shè)計算法產(chǎn)生的偽隨機(jī)序列滿足隨機(jī)序列統(tǒng)計特性，有較好的均衡性和游程特性，且隨機(jī)性較好。當(dāng)棋盤較大時，棋盤的賦值運算較少，運行效率高，但騎士巡游問題SemiHam求解算法求騎士巡游路徑較復(fù)雜，運行效率低。下一步將研究大棋盤的分塊，用騎士巡游問題 SemiHam求解算法產(chǎn)生多條騎士巡游路徑對各分塊進(jìn)行掃描，組合各塊序列，得到更大長度的偽隨機(jī)序列。

[1] 吳資玉, 韓慶文, 通信原理[M]. 北京: 電子工業(yè)出版社, 2008: 316-317. WU Z Y, HAN Q W. Principles of communications[M]. Beijing: Publishing House of Electronics Industry. 2008: 316-317.

[2] HUANG X, YE G. An image encryption algorithm based on hyper-chaos and DNA sequence[J]. Multimedia Tools and Applications, 2014, 72(1): 57-70.

[3] 雷雄俊, 劉光斌. GPS偽隨機(jī)序列的構(gòu)成及應(yīng)用分析[J]. 光通信研究, 2010, 21(6): 64-67. LEI H J, LIU G B. Architecture and applications of GPS pseudo-random sequence[J]. Study on Optical Communications, 2010, 21(6): 64-67.

[4] AHMED Z, CANCES J P, MEGHDADI V. Cryptographic spread spectrum relay communication[C]//Next Generation Mobile Applications, Services and Technologies. 2008: 588-591.

[5] 張群英, 方廣有. 偽隨機(jī)序列編碼脈沖信號在探地雷達(dá)中的應(yīng)用研究[J]. 電子與信息學(xué)報, 2012, 33(2): 424-428. ZHANG Q Y, FANG G Y. The study of pseudo random sequence’s application to GPR[J]. Journal of Electronics & Information Technology, 2012, 33(2): 424-428

[6] 杜小妮. 偽隨機(jī)序列的構(gòu)造及其隨機(jī)性分析[D]. 陜西: 西安電子科技大學(xué), 2008. DU X N. The construction and randomness analysis of pseudo random sequence[D]. Shaanxi: Xidian University, 2008.

[7] 張麗姣, 閔樂泉, 韓雙霜. 二維新混沌系統(tǒng)和偽隨機(jī)數(shù)生成器的設(shè)計[J]. 計算機(jī)工程與設(shè)計, 2014, 35(4): 1178-1182. ZHANG L J, MIN L Q, HAN S S. Design of 2-dimensional novel chaotic system and pseudo-random number generator[J]. Computer Engineering and Design, 2014, 35(4): 1178-1182.

[8] 孫克輝, 葉正偉, 賀少波. 混沌偽隨機(jī)序列發(fā)生器的FPGA設(shè)計與實現(xiàn)[J]. 計算機(jī)應(yīng)用與軟件, 2014, 6(12): 3-7. SUN K H, YE Z W, HE S B. Design and implementation of chaotic pseudo-random sequence generator using FPGA[J]. Computer Applications and Software, 2014, 6(12): 3-7.

[9] 李家標(biāo), 曾以成, 陳仕必, 等. 改進(jìn)型Henon映射生成混沌偽隨機(jī)序列及性能分析[J]. 物理學(xué)報, 2011, 60(6): 126-130. LI J B, ZENG Y C, CHEN S B. Modified Hénon map generated chaotic pseudorandom-bit sequences and performance analysis[J]. Acta Physica Sinica, 2011, 60(6): 126-130.

[10] 葉珍, 臧鴻雁. 基于混沌系統(tǒng)的量化方法及偽隨機(jī)性研究[J].計算機(jī)應(yīng)用研究, 2014, 31(12): 3719-3721. YE Z, ZANG H Y. Research of quantization methods and pseudorandomness based on chaotic systems[J]. Application Research of Computers, 2014, 31(12): 3719-3721.

[11] 花文昭, 韓文報. 基于橢圓曲線的二元偽隨機(jī)序列構(gòu)造與分析[J]. 計算機(jī)工程, 2012, 38(18): 100-102. HUA W Z, HAN W B. Construction and analysis of binary pseudorandom sequences based on elliptic curve[J]. Computer Engineering, 38(18): 100-102.

[12] JESSA M, JAWORSKI M. Producing secure pseudorandom sequences with combined multiplicative congruential generators[C]// Systems, Signals and Image Processing (IWSSIP).2012: 160-163.

[13] NIVASCH G. Experimental results on hamiltonian-cycle-finding algorithms[R]. Weizman Institute, Israel, 2003.

[14] 柏森, 楊曉帆. 求馬步圖 Hamilton 圈的最優(yōu)算法[J]. 計算機(jī)工程與科學(xué), 2000, 22(2): 8-11. BAI S, YANG X F. An optimal algorithm for searching a Hamilton cycle of the knight-tour’s problem[J]. Computer Engineering & Science, 2000, 22(2): 8-11.

[15] DEMAIO J. Which chessboards have a closed knight's tour within the cube[J]. Journal of Combinatorics, 2007, 14(2): 1-9.

[16] BAI S, LIAO X F, QU X H, et al. Generalized knight's tour problem and its solutions algorithm[C]//2006 International Conference on Computational Intelligence and Security. 2006:570-573.

[17] SIVAKUMAR T, VENKATESAN R. A novel approach for image encryption using dynamic scan pattern[J]. IAENG International Journal of Computer Science, 2014, 41(2): 91-101.

[18] RUKHIN A, SOTO J, NECHVATAL J, et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications[R]. Booz-Allen and Hamilton Inc Mclean Va,2001.

Method to generate the pseudo random sequence based on the statistical properties

BAI Sen1,2, ZHOU Long-fu1, GUO Hui3, YAN Bing2
(1. School of Software, Chongqing Institute of Engineering, Chongqing 400056, China; 2. Information Engineering Department, Chongqing Communication Institute, Chongqing 400035, China; 3. Unit 61541 of PLA, Beijing 100094, China)

There are some problems existing in pseudo-random sequence generating methods, such as the weaker proportionality, bad run length characteristic, etc. Hence, based on the SimiHam algorithm in Knight’s tour problem, a pseudo-random sequences generating method was proposed according to the statistical properties of random sequence. First, set runs value 0 and 1 in different length for the grids in chessboard, and then scan the chessboard with Hamilton cycles which are generated by SemiHam algorithm in Knight’s tour problem, At last extract run length values of 0 and 1 and get the pseudo-random sequences. Experimental results show that the pseudo-random sequence generated by the proposed algorithm satisfies the statistical properties of a random sequence and has better randomness.

pseudo-random sequence, statistical properties of a random sequence, SemiHam algorithm, NIST SP800-22 random test

TN919.81

A

10.11 959/j.issn.2096-109x.2017.00125

柏森（1963-），男，四川達(dá)縣人，博士，重慶工程學(xué)院教授、碩士生導(dǎo)師，主要研究方向為信息隱藏、圖像加密。

周龍福（1971-），男，江西臨川人，碩士，重慶工程學(xué)院副教授，主要研究方向為軟件體系結(jié)構(gòu)、數(shù)據(jù)庫、網(wǎng)絡(luò)與系統(tǒng)安全。

郭輝（1982-），男，河南輝縣人，碩士，61541部隊工程師，主要研究方向信息安全。

閆兵（1993-），男，湖南常德人，重慶通信學(xué)院碩士生，主要研究方向信息安全。

2016-10-24；

2016-12-02。通信作者：柏森，baisecq@126.com

國家自然科學(xué)基金資助項目（No.61272043）；重慶市基礎(chǔ)與前沿研究計劃基金資助項目（No.cstc2013jjB40009）；應(yīng)急通信重慶市重點實驗室能力提升基金資助項目（No.cstc2014pt-sy40003）

Foundation Items: The National Natural Science Foundation of China(No.61272043)，Basic & Frontier Project of Chongqing (No.cstc2013jjB40009), Capability Enhancement Foundation of Chongqing Key Laboratory of Emergency Communication (No.cstc2014pt-sy40003)