GM-T 0005-2021 清晰版 隨機性檢測規(guī)范

ICS35.030CCSL80中華人民共和國密碼行業(yè)標準代替GM／T0005—2012R2021-10-18發(fā)布2022-05-01實施國家密碼管理局發(fā)布GM／T0005—2021 1范圍 2規(guī)范性引用文件 3術(shù)語和定義 4符號 5隨機性檢測方法 5.1單比特頻數(shù)檢測方法 5.2塊內(nèi)頻數(shù)檢測方法 5.3撲克檢測方法 5.4重疊子序列檢測方法 5.5游程總數(shù)檢測方法 5.6游程分布檢測方法 5.7塊內(nèi)最大游程檢測方法 5.8二元推導(dǎo)檢測方法 5.9自相關(guān)檢測方法 5.10矩陣秩檢測方法 5.11累加和檢測方法 5.12近似熵檢測方法 5.13線性復(fù)雜度檢測方法 5.14Maurer通用統(tǒng)計檢測方法 5.15離散傅立葉檢測方法 6隨機性檢測判定 6.2樣本通過率判定 6.3樣本分布均勻性判定 6.4隨機性檢測結(jié)果判定 附錄A（規(guī)范性）樣本長度及檢測設(shè)置 附錄B（資料性）隨機性檢測原理 附錄C（資料性）隨機性檢測結(jié)果示例 ⅠGM／T0005—2021本文件依據(jù)GB/T1.1—2020給出的規(guī)則起草。本文件代替GM/T0005—2012《隨機性檢測規(guī)范》，對隨機性檢測進行規(guī)范，為二元序列的隨機性檢測工作提供科學(xué)依據(jù)。與GM/T0005—2012相比，除編輯性修改外主要技術(shù)變化如下：元序列的隨機性檢測”（見第1章和2012年版的第1章定義（見2012年版的第2章新增了術(shù)語“樣本集”（見3.6);說明（見第4章第5章和2012年版的第4章均勻性判定要求［見第6章和2012年版的第5章52012B;k2012lBBAn請注意本文件的某些內(nèi)容可能涉及專利。本文件的發(fā)布機構(gòu)不承擔識別這些專利的責任。本文件的附錄A是規(guī)范性附錄。本標準的附錄B、附錄C是資料性附錄。本文件由密碼行業(yè)標準化技術(shù)委員會提出并歸口。本文件起草單位：國家密碼管理局商用密碼檢測中心、中國科學(xué)院軟件研究所、中國科學(xué)院信息工程研究所、北京宏思電子技術(shù)有限責任公司、浙江大學(xué)。本文件主要起草人：羅鵬、毛穎穎、陳華、范麗敏、馬原、李亞威、張文婧、沈海斌、陳美會、朱少峰、張賀、朱雙怡。本文件的歷次版本發(fā)布情況為：—GM/T0005—2012。1GM／T0005—2021本文件規(guī)定了適用于二元序列的隨機性檢測指標和檢測方法。2規(guī)范性引用文件本文件沒有規(guī)范性引用文件。3術(shù)語和定義下列術(shù)語和定義適用于本文件。3.1注：如無特別說明，本文件所指的序列均為二元序列。3.2對二元序列做隨機性檢測時，首先假設(shè)該序列是隨機的，這個假設(shè)稱為原假設(shè)或零假設(shè)，記為H0。3.3用于二元序列檢測的一個函數(shù)或過程，可以通過它來判斷是否接受隨機性原假設(shè)。3.4隨機性檢測中錯誤地判斷隨機序列為非隨機序列的概率。3.5用于隨機性檢測的二元序列。3.6多個樣本的集合。3.7樣本的比特個數(shù)。3.8樣本集中的樣本個數(shù)。2GM／T0005—20213.9隨機性檢測需要設(shè)定的參數(shù)。下列符號適用于本文件。K：通用統(tǒng)計檢測中待檢序列L位子序列個數(shù)。L：通用統(tǒng)計中子序列長度。Li：線性復(fù)雜度檢測中子序列的線性復(fù)雜度。M：矩陣秩檢測中矩陣的行數(shù)。V：統(tǒng)計值。xi：2εi-Σ：求和符號。lnΦQ℃35隨機性檢測方法5.1單比特頻數(shù)檢測方法單比特頻數(shù)檢測是最基本的檢測，用來檢測一個二元序列中0和1的個數(shù)是否相近。隨機序列應(yīng)具有較好的0、1平衡性。單比特頻數(shù)檢測步驟如下。in檢測設(shè)置按附錄A要求，檢測原理見附錄B的B.1。特頻數(shù)檢測，否則未通過單比特頻數(shù)檢測。5.2塊內(nèi)頻數(shù)檢測方法塊內(nèi)頻數(shù)檢測步驟如下。m4GM／T0005—2021Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.2。頻數(shù)檢測，否則未通過塊內(nèi)頻數(shù)檢測。5.3撲克檢測方法數(shù)應(yīng)該接近。撲克檢測步驟如下。i撲克檢測步驟如下。Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.3。檢測，否則未通過撲克檢測。5.4重疊子序列檢測方法類模式出現(xiàn)的概率應(yīng)該接近。重疊子序列檢測步驟如下。ii5GM／T0005—2021iiiiiiiii。第三步：計算第四步：計算,第六步：計算Q_℃alue1=P_℃alue1,Q_℃alue2=P_℃alue2。檢測設(shè)置按附錄A要求，檢測原理見B.4。列檢測。5.5游程總數(shù)檢測方法游程是指序列中由連續(xù)的“0”或者“1”組成的子序列，并且該子序列的前導(dǎo)與后繼元素都與其本身的元素不同。游程總數(shù)檢測主要檢測待檢序列中游程的總數(shù)是否服從隨機性要求。游程總數(shù)檢測步驟如下。n-1εi=0in6GM／T0005—2021檢測設(shè)置按附錄A要求，檢測原理見B.5?？倲?shù)檢測，否則未通過游程總數(shù)檢測。5.6游程分布檢測方法游程分布檢測用于檢測序列中相同長度游程分布是否均勻，隨機的序列中，相同長度的游程數(shù)目應(yīng)該接近一致，且游程長度每增加一比特，游程數(shù)目應(yīng)接近減半。游程分布檢測步驟如下。i。ikQ℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.6。分布檢測，否則未通過游程分布檢測。5.7塊內(nèi)最大游程檢測方法塊內(nèi)最大游程檢測方法分別對塊內(nèi)最大“1”游程和塊內(nèi)最大“0”游程兩種模式進行檢測。將待檢序游程長度，根據(jù)各個子序列中最大“1”游程、最大“0”游程的分布來評價待檢序列的隨機性。7照表B.3的規(guī)則將其歸入相應(yīng)的集合中。iii件附表B.4。Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.7。最大游程檢測，否則未通過塊內(nèi)最大游程檢測。5.8二元推導(dǎo)檢測方法二元初始序列，依次將初始序列中兩個相鄰比特做異或操作，即可得到該序列的一次二元推導(dǎo)序列，長個隨機的序列，無論進行多少次推導(dǎo)，其0、1的個數(shù)都應(yīng)該接近一致。二元推導(dǎo)檢測步驟如下。n－k檢測設(shè)置按附錄A要求，檢測原理見B.8。推導(dǎo)檢測，否則未通過二元推導(dǎo)檢測。8GM／T0005—20215.9自相關(guān)檢測方法列應(yīng)該和將其左移任意位所得的新序列都是獨立的，故其關(guān)聯(lián)程度也應(yīng)該很低，即初始序列與將其左移。自相關(guān)檢測步驟如下。n－d-1檢測設(shè)置按附錄A要求，檢測原理見B.9。關(guān)檢測，否則未通過自相關(guān)檢測。5.10矩陣秩檢測方法矩陣秩檢測用來檢測待檢序列中給定長度的子序列之間的線性獨立性。由待檢序列構(gòu)造矩陣，然后檢測矩陣的行或列之間的線性獨立性，矩陣秩的偏移程度可以給出關(guān)于線性獨立性的量的認識，從而影響對二元序列隨機性好壞的評價。矩陣秩檢測步驟如下。矩陣秩檢測步驟如下。的32位填充。Rii=1NFFN－FM－FM-1小于31的矩陣的個數(shù)。第四步：計算統(tǒng)計值V=十十5776N十十5776N1336N9Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.10。陣秩檢測，否則未通過矩陣秩檢測。累加和檢測方法分別對前向累加和、后向累加和兩種模式進行檢測。前向累加和檢測從待檢序列第1比特開始，逐比特向后計算，后向累加和檢測從待檢序列最后1比特開始，逐比特向前計算，通過判斷待檢序列的各個子序列中最大的偏移（與0之間也就是最大累加和與一個隨機序列應(yīng)具有的最大偏移相比較，以判斷待檢序列的隨機性。累加和檢測步驟如下。ii第四步：計算Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.11。加和檢測，否則未通過累加和檢測。5.12近似熵檢測方法表明待檢序列具有規(guī)則性和連續(xù)性；差異值較大則表明待檢序列具有不規(guī)則性和不連續(xù)性。對任意一GM／T0005—2021近似熵檢測步驟如下。iiiijii制數(shù)值。。Q℃＝P℃檢測設(shè)置按附錄A要求，檢測原理見B.12。似熵檢測，否則未通過近似熵檢測。5.13線性復(fù)雜度檢測方法線性復(fù)雜度檢測用于檢測各等長子序列的線性復(fù)雜度分布是否符合隨機性的要求。將待檢序列劃LiLi線性復(fù)雜度檢測步驟如下：LiiiGM／T0005—2021iiiiiQΨ＝PΨ檢測設(shè)置按附錄A要求，檢測原理見B.13。性復(fù)雜度檢測，否則未通過線性復(fù)雜度檢測。如果待檢序列能被顯著地壓縮，則認為該序列不隨機。Maurer多余位舍棄不用。jLjjjijjjiji。檢測設(shè)置按附錄A要求，檢測原理見B.14。GM／T0005—2021MaurerMaurer5.15離散傅立葉檢測方法離散傅立葉檢測使用頻譜的方法來檢測序列的隨機性。對待檢序列進行傅立葉變換后可以得到尖正常的范圍；如果不正常的尖峰個數(shù)超過了允許值，即可認為待檢序列是不隨機的。離散傅立葉檢測步驟如下：i2εi-1。ff。fjjfjfjj \j。檢測設(shè)置按附錄A要求，檢測原理見B.15。散傅立葉檢測，否則未通過離散傅立葉檢測。6隨機性檢測判定應(yīng)采用第5章規(guī)定的15種隨機性檢測方法和附錄A規(guī)定的檢測設(shè)置對二元序列樣本集進行隨機性檢測。一種隨機性檢測方法對應(yīng)至少一個隨機性檢測項目，其中如某一項隨機性檢測方法采用不同檢測參數(shù)設(shè)置（詳見附錄A或具有不同檢測模式（如塊內(nèi)最大游程檢測方法、累加和檢測方法或具GM／T0005—2021有多個統(tǒng)計值（如重疊子序列檢測方法應(yīng)作為單獨的隨機性檢測項目進行檢測，并分別對二元序列樣本集的每個檢測項目的樣本通過率、分布均勻性進行合格判定。比如累加和檢測方法包括前向累加和、后向累加和兩種模式，前向累加和、后向累加和應(yīng)作為2個獨立的檢測項目進行檢測，并分別對二元序列樣本集中前向累加和、后向累加和的樣本通過率、分布均勻性進行合格判定。本文件確定二元序列樣本集中的樣本數(shù)量為1000。6.2樣本通過率判定集通過該項檢測，否則未通過此項檢測。例如，樣本數(shù)量為1000個，則通過該檢測項目的樣本個數(shù)應(yīng)大于或等于981。6.3樣本分布均勻性判定i=10。6.4隨機性檢測結(jié)果判定當所有隨機性檢測項目的檢測結(jié)果同時滿足6.2規(guī)定的樣本通過率判定和6.3規(guī)定的樣本分布均勻性判定時，該二元序列樣本集通過本文件的隨機性檢測，否則未通過隨機性檢測。GM／T0005—2021附錄A（規(guī)范性）樣本長度及檢測設(shè)置A.120000比特樣本使用的檢測方法與檢測參數(shù)長度為20000比特的樣本按照表A.1的隨機性檢測方法和檢測參數(shù)進行隨機性統(tǒng)計檢測。表A.120000比特樣本檢測設(shè)置序號隨機性檢測方法檢測參數(shù)1單比特頻數(shù)檢測 2塊內(nèi)頻數(shù)檢測m=10003撲克檢測m=4,84重疊子序列檢測m=3,55游程總數(shù)檢測—6游程分布檢測 7塊內(nèi)最大游程檢測m=1288二元推導(dǎo)檢測k=3,79自相關(guān)檢測d=2,8,16累加和檢測—近似熵檢測m=2,5離散傅立葉檢測—A.21000000比特樣本適用的檢測方法與檢測參數(shù)長度為1000000比特的樣本按照表A.2的隨機性檢測方法和檢測參數(shù)進行隨機性統(tǒng)計檢測。表A.21000000比特樣本檢測設(shè)置序號隨機性檢測方法檢測參數(shù)1單比特頻數(shù)檢測 2塊內(nèi)頻數(shù)檢測m=100003撲克檢測m=4,84重疊子序列檢測m=3,55游程總數(shù)檢測—6游程分布檢測—7塊內(nèi)最大游程檢測m=10000表A.21000000比特樣本檢測設(shè)置（續(xù)）序號隨機性檢測方法檢測參數(shù)8二元推導(dǎo)檢測k=3,79自相關(guān)檢測矩陣秩檢測—累加和檢測 近似熵檢測m=2,5線性復(fù)雜度檢測m=500,1000通用統(tǒng)計檢測L=7,Q=1280離散傅立葉檢測 A.3100000000比特樣本檢測建議長度為100000000比特的樣本按照表A.3的隨機性檢測方法和檢測參數(shù)進行隨機性統(tǒng)計檢測。表A.3100000000比特樣本檢測設(shè)置序號隨機性檢測方法檢測參數(shù)1單比特頻數(shù)檢測 2塊內(nèi)頻數(shù)檢測m=1000003撲克檢測m=4,84重疊子序列檢測m=3,5,75游程總數(shù)檢測—6游程分布檢測—7塊內(nèi)最大游程檢測m=100008二元推導(dǎo)檢測k=3,7,159自相關(guān)檢測矩陣秩檢測 累加和檢測 近似熵檢測m=5,7線性復(fù)雜度檢測m=5000通用統(tǒng)計檢測L=7,Q=1280離散傅立葉檢測—GM／T0005—2021附錄B（資料性）隨機性檢測原理B.1單比特頻數(shù)檢測單比特頻數(shù)檢測是最基本的檢測，用來檢測一個二元序列中0和1的個數(shù)是否相近。已知一個長其統(tǒng)計值V應(yīng)服從標準正態(tài)分布：B.2塊內(nèi)頻數(shù)檢測一一m該統(tǒng)計量應(yīng)該服從自由度為N的χ2分布。B.3撲克檢測i的個數(shù)是否接近。B.4重疊子序列檢測類模式出現(xiàn)的概率應(yīng)接近。iiiiii2mii2mii：，。B.5游程總數(shù)檢測游程是二元序列的一個子序列，由連續(xù)的0或者1組成，并且其前導(dǎo)和后繼元素都與其本身的元素不同。游程總數(shù)檢測主要檢測待檢序列中游程的總數(shù)是否服從隨機性要求。應(yīng)服從標準正態(tài)分布。B.6游程分布檢測i2-i。iikiB.7塊內(nèi)最大游程檢測將待檢序列劃分成N個等長的子序列，根據(jù)各個子序列中最大“1”／“0”游程的分布來評價待檢序列的隨機性。ii概率iiGM／T0005—2021nm≥1288≥6272≥750000表B.2K的取值m8K356表B.3集合定義規(guī)則對應(yīng)集合m=8m=128m=10000集合0≤1≤4≤10集合125集合236集合3≥47集合48集合5≥9集合6≥16素個數(shù)℃3加1。iim=8m=128m=100000123456B.8二元推導(dǎo)檢測GM／T0005—2021B.9自相關(guān)檢測列應(yīng)該和將其左移任意位所得的新序列都是獨立的，故其關(guān)聯(lián)程度也應(yīng)該很低。n－d-1為時延。B.10矩陣秩檢測矩陣秩檢測用來檢測待檢序列中給定長度的子序列之間的線性獨立性。由待檢序列構(gòu)造矩陣，然后檢測矩陣的行或列之間的線性獨立性，矩陣秩的偏移程度可以給出關(guān)于線性獨立性的量的認識，從而影響對序列隨機性好壞的評價。FFMM-1M-1M=V=十十5776N十十5776N2888N矩陣概率，N為由序列構(gòu)造的矩陣的總個數(shù)。累加和檢測將待檢序列的各個子序列中最大的偏移（與0之間也就是最大累加和與一個隨機序列應(yīng)具有的最大偏移相比較，以判斷待檢序列的最大偏移是過大還是過小。實際上，隨機序列的最大偏移應(yīng)該接近0，所以累加和不能過大，也不能過小（累加和可以是負數(shù)）。根據(jù)最大偏移值來判斷待檢序列的隨機程度。i表B.5累加和的計算前向累加和模式后向累加和模式SS2=x1+x2:SK＝x1+x2+…+xK:Sn＝x1+x2+…+xK+…+xnSS::Sn＝xn＋xn-1+…+xn－K+1+…+x1GM／T0005—2021iP十∝十∝iB.12近似熵檢測i疊子序列，令jilili1ii。B.13線性復(fù)雜度檢測ii iTiiiiiiiGM／T0005—2021ii：著地壓縮，則認為該序列是不隨機的，因為隨機序列是不能被顯著壓縮的。通用統(tǒng)計檢測可以用來檢測待檢序列多方面的特性，但這并不意味著通用統(tǒng)計檢測是前面幾個檢測的拼裝，通用統(tǒng)計檢測完全采取了和其他檢測所不同的方法，可以檢測待檢序列某些統(tǒng)計上的缺陷。一個序列可以通過通用統(tǒng)計檢測當且僅當這個序列是不可壓縮的。通用統(tǒng)計檢測需要的數(shù)據(jù)量很大，它將序列分成長度為L的子序列，然后將待檢序列分成兩部分：LL首先，從頭開始遍歷初始序列（以塊為單位找到每一個L位模式在初始序列中最后出現(xiàn)的位置（塊號如果一個L位模式在初始序列中沒有出現(xiàn)，那么將其位置設(shè)置為0；此后，從頭開始遍歷檢測序列，每一次都會得到一個L位子序列，計算這個子序列所在的位置與其前面最后一次出現(xiàn)的位置差，也果相加。這樣，就可以得到統(tǒng)計值：計算期望值：十∞fn-L驗的次數(shù)，那么有：∞標準差按如下計算：LKGM／T0005—2021B.15離散傅立葉檢測離散傅立葉變換檢測使用頻譜的方法來檢測序列的隨機性。對待檢序列進行傅立葉變換后可以得入不正常的范圍；如果不正常的尖峰個數(shù)超過了允許值，即可認為待檢序列是不隨機的。kji≡\。 jj jj\準正態(tài)分布。附錄C（資料性）隨機性檢測結(jié)果示例Cn=128輸出：P_Ψalue=0.215925,Q_Ψalue=0.892038C2n=100m=10V=7.200輸出：P_Ψalue=0.706438,Q_Ψalue=0.706438C.3撲克檢測n=128m=4輸出：P_Ψalue=0.213734,Q_Ψalue=0.213734C4n=128m=2輸出：P_Ψalue1=0.436868;P_Ψalue2=0.723Q_Ψalue1=0.436868;Q_ΨaC5n=128GM／T0005—2021V=0.494817輸出：P_Ψalue=0.620729,Q_Ψalue=0.310364C60001001111010110100000001101011111001100111001101101100010110010n=128輸出：P_Ψalue=0.970152,Q_Ψalue=0.970152C7(1)塊內(nèi)最大“1”游程檢測0001001111010110100000001101011111001100111001101101100010110010n=128輸出：P_Ψalue=0.180598,Q_Ψalue=0.180598(2)塊內(nèi)最大“0”游程檢測0001001111010110100000001101011111001100111001101101100010110010n=128輸出：P_Ψalue=0.839299,Q_Ψalue=0.839299C8000100111101011010000000110101111100110011100110110