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