VIVS準混沌算法的初值敏感性檢驗方法

龍德浩,陳志清

(1.四川大學,成都 610064;2.成都大學,成都 610106)

1 引 言

1963年,Lorenz在研究天氣預報方程時發現了混沌現象。隨后,混沌算法以其獨特的初值敏感性深深地吸引著一代又一代學者,直到今天。因為初值敏感性涉及的面較寬,涵蓋自然、政治、經濟等學科領域。就抗干擾而言,初值敏感性強意味著能同時提高定位系統的速度分辯能力和距離分辯能力;能有效抑制擴頻通信的地址干擾和人為相關干擾;對信息安全而言,是反“相關分析”、反密碼丟失的根本方法;對弱信號接收,例如無線探礦、深空通信等,是一條全新的數字編碼思路。因此,人們希望找到一種新的編碼方法,它既具有經典混沌算法獨特的初值敏感性,又能克服經典混沌算法難以克服的“同步難”問題。到如今,混沌理論經歷了上世紀70年代的“機理”、80年代的“建模”、90年代及其隨后的“應用”研究,已逐步邁向應用,特別是變初值變結構(VIVS)準混沌算法[1-4]克服了經典混沌算法的“同步難”問題。至于初值敏感性,不同領域、不同學者,其理解是不盡相同的。催化化學家把它理解為“催化劑”,只需添加極少量的“催化劑”,即可使化學反應的速率提高百倍、千倍、萬倍……就通信而言,我們把它理解為:任意鄰近的初值產生的0/1混沌序列都是彼此無關的,進而是統計獨立的。然而,在用數學語言表達此定義時,卻遇到了互相關函數絕對極大值的“統計分布難”問題。盡管極值分布理論在上世紀60年代早有定論,但由經典的3種分布類型[5]所導出的結果,偏離物理概念較遠。不得已我們擬議了“雙序列平面圖解法”,這種方法簡單、直觀,但只能定性[6]。定性檢驗結果表明,VIVS編碼算法具有初值敏感性,故簡記為VIVS準混沌算法。如何定量地檢驗編碼(含混沌)算法的初值敏感性呢?工程應用專家很關心這個問題。然而,近半世紀過去了,至今仍未解決。筆者近兩年基于Г л й в е н к о極限定理[7],再次探討了通用編碼算法的初值敏感性檢驗方法,旨在拋磚引玉。

2 通用編碼算法的初值敏感性檢驗方法

2.1 初值敏感性檢驗方法的定義

我們擬議的初值敏感性檢驗方法的定義包含5個步驟。

(1)首先,給定任意鄰近初值矩陣

共計m+1行,v列。其中,ii,j(i=1,2,…,m+1;j=1,2,…,v)的取值決定于被檢編碼算法所采用的數制。但無論哪種數制,任意相鄰兩行的數值都必須盡量接近,例如,彼此相鄰1 bit。而后把這組初值I逐行代入待檢編碼算法,從而生成待檢數據矩陣

共計 m+1行,n 列。其中,ai,j=′0′或′1′;i=1,2,…,m+1;j=1,2,…,n。n=2 000～3 000,不宜太長,因為初值敏感性總是發生在啟動編碼算法的初始階段;但也不能太短,否則無法檢驗到某些算法存在的初值敏感性的過渡過程。m=2 000～8 000,旨在使所求的經驗分布更接近于母體的理想概率分布。

(2)求出矩陣J中任意一行,例如第i行的自相關函數,而后除以序列的長度n,即得歸一化自相關函數矢量b11。

(3)依次求出矩陣J中相鄰兩行的互相關函數

共計m行,n列。

(4)將C以“同一 n”標準化之,即得標準化互相關函數矩陣

而后取絕對值,再取極大值,即得R的絕對極大值矢量

并稱之為待檢編碼算法的“初值敏感性檢驗樣本”,記為 b12。這樣,一切可能 b12的總體,就是初值敏感性檢驗的樣本空間 Ψ;當I給定時,b12即為總體Ψ的一組觀測值。因為b12是一個絕對極大值向量,故本文提出的初值敏感性檢驗方法實質上屬于極大值檢驗范疇。鑒于此,初值敏感性檢驗的首要任務就是求“b12不大于預先給定的門限值th”這一事件的概率。為此,必須先求出總體 Ψ的概率分布。

(5)由 Г л й в е н к о極限定理得知 :當 m 很大時 ,總體 Ψ觀測值b12的經驗分布,就是母體 Ψ的良好的近似概率分布。這樣,有了母體 Ψ的概率分布,即可求出上述“事件”的概率及其相關參數。

2.2 初值敏感性檢驗步驟

這個“檢驗步驟”實質上是編寫“通用編碼算法初值敏感性檢驗程序”的流程圖。

第一,依照2.1節,求初值敏感性檢驗的觀測值矢量 b12;第二,求 b12的升序結構;第三,求初值敏感性檢驗樣本空間 Ψ的概率分布;第四,求b12不大于門限值th的概率;第五,求 b12大于門限值 th的概率;第六,求門限值 th在b12升序結構中的位置;第七,求 b12中任意一點,例如極大值、中位置等的概率;第八,求 b12的極大值;第九,求 b12的樣本平均值;第十,求 b12的統計平均值;第十一,求b12的樣本標準差;第十二,求b12的統計標準差。

2.3 初值敏感性檢驗的判決準則

設門限值 th=0.1000∈b12。如果觀測值 b12不大于門限值th的概率為

或 其“補”概率為

則產生此被檢序列的編碼算法具有初值敏感性;反之亦然。

3 通用編碼算法初值敏感性檢驗文件

按照第2.2節的“檢驗步驟”,逐一寫出“通用編碼算法初值敏感性檢驗”文件

的參數:主文件名:dh-nist-Lsinitsensibility31,計算機語言:matlab;輸入矩陣的行數:N-pattern,2 000～8 000;調用子函數的符號:F,matlab語言調用自編功能函數的符號;輸入數據文件名:c3.mat,一切符合式(1)和式(2)要求的matlab(0,1)數據文件;輸入矩陣的列數:n,2 000～3 000;最大相關時間:k,k=n,2 000～3 000;任意指定的數值:n1,n1∈b12,檢驗者感興趣的數值,例如中位數、極大值、極小值等;初值敏感性門限值:th∈b12,隨工程要求而定,本例th=0.1000;反饋矢量和頻率:[g,ni],ni為所求的b12的密度函數,g為所求的功能參數矢量。

4 VIVS準混沌算法初值敏感性檢驗

(1)調用初值敏感性檢驗通用文件

(2)VIVS-c6001.b12樣本觀測值的數據結構

被檢母體 Ψ的本次觀測值VIVS-c6001.b12的數據結構(參見2.2節的檢驗步驟)為

其圖像如圖1所示。

圖1 彼此相鄰1 bit的VIVS-c6001.b12的升序圖Fig.1 Sorting chart of VIVS-c6001.b12 adjacent to each other 1 bit

由圖1可知,VIVS準混沌算法的互相關函數的絕對極大值共計2 000個,最大值劣于0.12,即互相關系數較小。

(3)VIVS-c6001.b12母體 Ψ的概率密度函數(數字式)及其參數[g,ni]

母體 Ψ的觀測值VIVS-c6001.b12的經驗分布函數(見2.2節的檢驗步驟)為

其圖像如圖2所示。

圖2 彼此相鄰1 bit的VIVS-c6001.ni概率密度Fig.2 Probability density of VIVS-c6001.ni adjacent to each other 1 bit

由 Г л й в е н к о極限定理得知 ,因為觀測值 VIVS-c6001.b12的數據量較大,等于2 000,故其經驗分布VIVS-c6001.ni是總體 Ψ的概率密度的一個良好近似。由此,即可求出與VIVS準混沌算法有關的幾個主要參數,如表1所示(見2.2節的檢驗步驟)。

表1 VIVS準混沌算法初值敏感性檢驗主要結果Table 1 Sensitivity of the initial value with VIVS quasi-chaos algorithm

(4)初值敏感性樣本值VIVS-c6001.b12不大于門限值th=0.100 0的概率是

5 結 論

由式(8)得知,對于任意給定的彼此相鄰1 bit的初值矩陣I產生的樣本VIVS-c6001.b12不大于給定門限電平 th=0.100 0的概率為0.985 5,大于0.95,故依據判決準則式(6),被檢驗的VIVS準混沌算法以概率0.985 5具有初值敏感性,從而為證明VIVS準混沌算法滿足Shannon完全保密性定理的充要條件和探索大容量CDMA碼族奠定了理論基礎,節省了大量的計算時間。

[1]陳志清,龍德浩.復合迭代算法及其應用[J].四川大學學報(自然科學版),1997,34(5):621-628.CHEN Zhi-qing,L ONG De-hao.Composite iterative algorithm andits application[J].Journal of Sichuan University(Natural Science Edition),1997,34(5):621-628.(in Chinese)

[2]陳志清,龍德浩.二重變初值流密碼算法[J].四川大學學報(自然科學版),1997,34(6):791-800.CHEN Zhi-qing,LONG De-hao.Double Varying Initial Values Stream Cipher Algorithms[J].Journal of Sichuan University(Natural Science Edition),1997,34(6):791-800.(in Chinese)

[3]陳志清,龍德浩.變初值變結構準混沌:密碼學發展的新方向[J].大自然探索,1997,16(4):46-49.CHEN Zhi-qing,LONG De-hao.Varying Initial Conditions/Varying Structure Quasi-Chaotic Cipher Streams:A New Direction in Cryptography[J].Discovery of Nature,1997,16(4):46-49.(in Chinese)

[4]陳志清,龍德浩.變初值/變結構準混沌滾動密鑰發生器[J].電訊技術,1997,37(6):48-52.CHEN Zhi-qing,LONG De-hao.Change the initial value/variable structure quasi-chaos scroll key generator[J].Telecommunications Engineering,1997,37(6):48-52.(in Chinese)

[5]陳希孺.數理統計引論[M].北京:科學出版社,1981:534.CHEN Xi-ru.Mathematical Statistics Introduction[M].Beijing:Science Press,1981:534.(in Chinese)

[6]陳志清,龍德浩.變結構密碼算法[J].四川大學學報(自然科學版),1998,35(2):210-217.CHEN Zhi-qing,LONG De-hao.Variable structure cryptographic algorithms[J].Journal of Sichuan University(Natural Science),1998,35(2):210-217.(in Chinese)

[7]茆詩松,程依明,濮曉龍.概率論與數理統計教程[M].北京:高等教育出版社,1983:229.MAO Shi-song,CHENG Yi-ming,PU Xiao-long.Probability and Statistics tutorial[M].Beijing:Higher Education Press,1983:229.(in Chinese)

[8]龍德浩.編碼識別汽車防撞雷達[J].電訊技術,2009,49(7):41-46.LONG De-hao.Encoding recognition automotive collision avoidance radar[J].Telecommunications Engineering,2009,49(7):41-46.(in Chinese)