基於隨機置換的偽隨機序列的隨機性檢測方法

2023-04-30 06:55:11

專利名稱：：基於隨機置換的偽隨機序列的隨機性檢測方法
技術領域：
：本發明屬於檢測領域，特別涉及偽隨機序列的隨機性檢測方法，可用於擴頻通信系統中的調製解調，流密碼系統中的密鑰流生成等。
背景技術：
：通過隨機數發生器產生的偽隨機序列，其隨機性直接影響到應用的安全性，因此要判斷該應用是否安全，必須要先保證該偽隨機序列的隨機性性能良好，而對偽隨機序列的隨機性檢測一直都是序列隨機性檢測中的難點。要檢測一個序列是否擁有真正隨機序列的特性可以從幾個方面考慮1)周期性特徵；2)序列中符號"0"和"1"出現的比例;3)序列中的遊程的分布情況；4)序列的異相自相關函數；5)序列的複雜度，例如線性複雜度；6)序列的可壓縮情況；為了測試一個序列是否滿足隨機序列的這些性質而提出了多種具有針對性的隨機性檢測方法，例如二元矩陣秩測試和頻譜測試可以測試序列的周期特性；頻率測試和分塊頻率測試可以測試序列中符號"0"和"1"出現的比例；線性複雜度測試、最大階複雜度測試和二階複雜度測試可以測試序列的複雜度。相應的測試存在六十多種，然而，它們都只能是針對隨機性的某些性質進行測試，也就是說每個測試的通過只能說明該序列滿足某個隨機特性，但並不能確保它還符合其他的特性，即都存在局限性和片面性，這些測試對序列的隨機性只能起到必要條件的說明。
發明內容本發明的目在於針對現有的對序列的隨機性檢測技術，都是從研究原序列的特性的角度出發而進行檢測而存在的問題，提出一種偽隨機序列的隨機性檢測方法，在不影響原序列的隨機性的基礎上，通過這些線性變換處理改變原序列的一些排列性質，以克服現有技術在隨機性檢測問題上的局限性和片面性，提高對原序列更加全面的測試效果。為實現上述目的，本發明根據隨機序列經過一定的處理之後仍是隨機序列的原則，對一系列對偽隨機序列進行處理，具體方案如下技術方案一一種基於隨機置換的偽隨機序列的隨機性檢測方法，包括如下過程(1)設置待測二元序列為ai，a2，...，，長度為n;(2)對待測序列求逆，得到逆序列為an，an—p...，&1;(3)對逆序列用Cram6r-vonMises測試方法進行統計，得到逆序列的統計值《=;+-，n為採樣點，Xl(i)為根據逆序列構造的一個服從標準正態分布的統計量，F(X1(i))為標準正態分布函數；(4)通過Cram6r-vonMises測試方法，選定一個分位點a(0<a<l)，構造標準統計值Mv2-A^:(i^力—F飛勾)2血，^為a對應的標準正態分布變量，F(x)為待測分布函數，F*(x)為標準正態分布函數，F(x)服從與F*(x)對應的隨機特性；(5)將逆序列的統計值1\與標準統計值Nw2進行比較，若1\小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性。技術方案二一種基於隨機置換的偽隨機序列的隨機性檢測方法，包括如下過程1)設置待測二元序列為ai，a2，...，an，長度為n;2)對待測序列取反，得到反序列為ai，a2，...，an，其中ai=(l+a^mod2，1《i《n;3)對反序列用Cram6r-vonMises測試方法進行統計，得到反序列的統計值T2=y^+g[|^-i^JC2(,.))]，N為採樣點，x犯)為根據反序列構造的一個服從標準正態分布的統計量，F(X2(i))為標準正態分布函數；4)通過Cram6r-vonMises測試方法，選定一個分位點a(0<a設置待測二元序列為ai，a2，...，an，長度為n;〈2>對待測序列進行隨機交織取一個隨機交織器S為從集合{iI1《i《n}到其自身的一一映射，將其記為S(j)=i，其中，1《i《n，1《j《n;利用隨機交織器S對序列ai，a2，...，an進行交織，得到隨機交織序列as(1)，as(2)，...，as(n);〈3>對隨機交織序列用Cram6r-vonMises測試方法進行統計，得到隨機交織序列的統計值7;》[醫-^(義3(,.))]，N為採樣點，x細為根據隨機交織序列構造的一個服從標準正態分布的統計量，F(x^))為標準正態分布函數；〈4>通過Cram6r-vonMises測試方法，選定一個分位點a(0<a將隨機交織序列的統計值T3與標準統計值Nw2進行比較，若T3小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性。本發明由於對待測序列先進行求逆或取反或隨機交織處理之後得到逆序列或反序列或隨機交織序列，將原待測序列和處理後得到的序列分別進行Cram6r-vonMises檢驗，仿真結果表明本發明具有如下優點A.原待測序列經過Cram6r-vonMises檢驗的結果是序列滿足隨機特性，處理後得到的序列的檢驗結果是序列不具有隨機性，綜合這兩個檢驗結果可以得到原待測序列不具有隨機性的檢驗結果，不同於原方法只直接對原待測序列進行檢驗的序列滿足隨機特性的檢驗結果，由此解決了原方法在檢驗結果上的局限性和片面性；B.當兩個檢驗結果都是序列具有隨機性或者序列不具有隨機性時，本發明提出的方法比原方法得到的檢驗結果多經過了一次對處理後的序列進行檢驗，使得這個檢驗結果更加全面。具體實施例方式實施例一，通過對待測序列求逆實現偽隨機序列的隨機性檢測。具體步驟如下步驟一，輸入待測序列ai，a2，...，an，n=106。步驟二，求待測序列ai，a2，...，an的逆序列，得到an，步驟三，對逆序列用Cram6r-vonMises測試方法進行統計a)將長度為106的逆序列an，an—n...，&1分成長度為10000的100個小分組，記m=10000，N=100，其中10000和100為任選;b)設Xlij表示第i個小分組中第j個比特，i=1，2，L，N，j=1，2，L，m，構造統c)將x1(i)按從小到大進行排序x1(1)《x1(2)《L《x1(N);d)將x他帶入；-A+gfl^-i^XK,.):);!，求出逆序列的統計值L，F(x他)為標準正態分布函數。步驟四，選定分位點a和分組N，利用下式得到對應的標準統計值Mv、Wj:CF(x)-i^0:))2血，Xa為a對應的標準正態分布變量，F、x)為標準正態分布函數，F(x)服從與F、x)對應的隨機特性，例如選定a=0.05，N=100，則標準統計值為Nw2=0.220;選定a=0.05，N=10，則標準統計值為Nw2=0.212;選定a=0.01，N=100，則標準統計值為Nw2=0.340;選定不同的分位點a和N對應不同的標準統計值，可得到表1所述的標準統計值。表1:標準統計值tableseeoriginaldocumentpage7步驟五，將1\與選定的標準統計值進行比較，若1\小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性，例如1\小於標準統計值0.220時，待測序列ai，a2，...，an滿足隨機特性，反之待測序列ai，a2，...，an不具有隨機特性。實施例二，通過對待測序列求反實現偽隨機序列的隨機性檢測。具體步驟如下步驟l，輸入待測序列ai，a2，，an，n=106。步驟2，求待測序列ai，a2，，an的反序列，得到a"a2，...，，其中^=(l+a》mod2，1《i《n。步驟3，對反序列用Cram6r-vonMises測試方法進行統計1)將長度為106的反序列ai，a2，，an分成長度為50000的20個小分組，記m=50000，N=20，其中50000和20為任選；2)設x2ij表示第i個小分組中第j個比特，i=1，2，L，N，j=1，2，L，m，構造統計,2(z)=*2%2').;3)將x2(i)按從小到大進行排序x2(1)《x2(2)《L《x2(N);4)將x2(i)帶入72=^+g[祭—F(X2(,.))]，求出反序列的統計值T2，F(x2(i))為標準正態分布函數。步驟4，選定分位點a和分組N，利用下式得到對應的標準統計值Mv2-A^:(F(x)-i^(x))2^:，Xa為a對應的標準正態分布變量，F、x)為標準正態分布函數，F(x)服從與F、x)對應的隨機特性，例如選定a=0.01，N=20，則標準統計值為Nw2=0.330;選定a=0.05，N=30，則標準統計值為Nw2=0.218;選定a=0.05，N=60，則標準統計值為Nw2=0.220;選定不同的分位點a和N對應不同的標準統計值，可得到表1所述的標準統計值。步驟5，將T2與選定的標準統計值進行比較，若T2小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性，例如T2小於標準統計值0.330時，待測序列ai，a2，...，an滿足隨機特性，反之待測序列ai，a2，...，an不具有隨機特性。實施例三，通過對待測序列進行隨機交織實現偽隨機序列的隨機性檢測。具體步驟如下步驟A，輸入待測序列ai，a2，...，an，n=106。步驟B，對待測序列ai，a2，...，an進行隨機交織。〈B1>根據待測序列長度n，初始化集合I={l，2，L，n}，從集合I中隨機選擇一個整數Sl記為S(l)，同時將Sl從集合I中刪除，得到的新的集合記為L;〈B2>在第k步，從集合Ik—!={sGI，s-Sl，L，sk—J中隨機選擇一個整數sk記為S(k)，同時將sk從集合Ik—工中刪除，得到的新的集合記為Ik，k=2，3，L，n;〈B3>當k=n時，得到S(n)，隨機交織完畢；〈B4>根據以上得到的S(1)，S(2)，L，S(n)，得到隨機交織序列as(1)，as(2)，...，as(n)。步驟C，對隨機交織序列用Cram6r-vonMises測試方法進行統計CI)將長度為106的隨機交織序列as(1)，as(2)，...，as(n)分成長度為105的10個小分組，記m=105，N=10，其中105和10為任選;C2)設x3ij表示第i個小分組中第j個比特，i=1，2，L，N，j=1，2，L，m，構造統C3)將x3(i)按從小到大進行排序x3(1)《x3(2)《L《x3(N);C4)將x細帶入:T34+》^一F(x糾)]，求出隨機交織序列的統計值T3，F(x3(i))為標準正態分布函數。步驟D，選定分位點a和分組N，利用下式得到對應的標準統計值My2-iV廣(F(x)-F>))2^，Xa為a對應的標準正態分布變量，F、x)為標準正態分布函數，F(x)服從與F、x)對應的隨機特性，例如選定a=0.01，N=10，則標準統計值為Nw2=0.320;選定a=0.01，N=30，則標準統計值為Nw2=0.330;選定a=0.01，N=60，則標準統計值為Nw2=0.330;選定不同的分位點a和N對應不同的標準統計值，可得到表1所述的標準統計值；步驟E，將T3與選定的標準統計值進行比較，若T3小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性，例如T3小於標準統計值0.320時，待測序列ai，a2，...，an滿足隨機特性，反之待測序列ai，a2，...，an不具有隨機特性。權利要求一種基於隨機置換的偽隨機序列的隨機性檢測方法，包括如下過程(1)設置待測二元序列為a1，a2，...，an，長度為n；(2)對待測序列求逆，得到逆序列為an，an-1，...，a1；(3)對逆序列用Cramér-vonMises測試方法進行統計，得到逆序列的統計值N為採樣點，x1(i)為根據逆序列構造的一個服從標準正態分布的統計量，F(x1(i))為標準正態分布函數；(4)通過Cramér-vonMises測試方法，選定一個分位點α(0＜α＜1)，構造標準統計值xα為α對應的標準正態分布變量，F(x)為待測分布函數，F*(x)為標準正態分布函數，F(x)服從與F*(x)對應的隨機特性；(5)將逆序列的統計值T1與標準統計值Nw2進行比較，若T1小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性。2.—種基於隨機置換的偽隨機序列的隨機性檢測方法，包括如下過程1)設置待測二元序列為A，a2，...，a。，長度為n;2)對待測序列取反，得到反序列為ai，a2，...，an，其中ai=(l+ai)mod2，1《i《n;3)對反序列用Cram6r-vonMises測試方法進行統計，得到反序列的統計值formulaseeoriginaldocumentpage0T22[^-屍(義2(,.))]，N為採樣點，^(i)為根據反序列構造的一個服從標準正態分布的統計量，F(x2(i))為標準正態分布函數；4)通過Cram6r-vonMises測試方法，選定一個分位點a(0<a設置待測二元序列為A，a2，...，，長度為n;〈2>對待測序列進行隨機交織隨機交織器S為從集合U11《i《n}到其自身的一一映射，將其記為S(j)=i，其中，1《i《n，1《j《n;利用隨機交織器S對序列ai，a2，...，an進行交織，得到隨機交織序列as(1)，as(2)，...，as(n);〈3>對隨機交織序列用Cram6r-vonMises測試方法進行統計，得到隨機交織序列的統計值K=I^+g[祭—，N為採樣點，X3(i)為根據隨機交織序列構造的一個服從標準正態分布的統計量，F(x^))為標準正態分布函數；〈4>通過Cram6r-vonMises測試方法，選定一個分位點a(0<a<1)，構造標準統計值Mv2-^廣CF(I)-i^(X))^，Xa為a對應的標準正態分布變量，F(x)為待測分formulaseeoriginaldocumentpage2布函數，F*(x)為標準正態分布函數，F(x)服從與F*(x)對應的隨機特性；〈5>將隨機交織序列的統計值T3與標準統計值Nw2進行比較，若T3小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性。全文摘要本發明公開了一種基於隨機置換的偽隨機序列的隨機性檢測方法，它屬於檢測領域，主要解決現有的隨機性檢測方法中存在的局限性和片面性的問題。其檢測步驟是對待測序列進行一系列的隨機置換處理，如求逆或取反或隨機交織；將隨機置換處理後得到的逆序列或反序列或隨機交織序列用Cramér-vonMises檢測方法進行統計，得到對應序列的統計值，將對應序列的統計值與選定的標準統計值進行比較，若統計值小於該標準統計值，則待測序列滿足隨機特性，反之待測序列不具有隨機特性。本發明使得偽隨機序列的隨機性檢測在檢測結果上更加全面，可應用於保密通信、航空航天、測距、密碼學和自動控制領域。文檔編號H04L25/03GK101697533SQ20091021844公開日2010年4月21日申請日期2009年10月21日優先權日2009年10月21日發明者殷浩,陳秋麗,馬文平申請人:西安電子科技大學;