基于近似熵的搖號系統隨機性安全檢測研究

許穎媚 匡碧琴

（1．廣東省高性能計算重點實驗室，廣東 廣州 510000；2．廣東省計算技術應用研究所，廣東 廣州 510000）

1 引言

隨著信息化的發展，搖號系統的應用范圍無處不在。搖號上學系統、抽獎搖號系統、保障性住房搖號、新車上牌搖號等都是以公平性為基礎保障電子政務的公信力。搖號系統的公平性需要從技術角度進行驗證。

從技術角度看，搖號系統的公平性取決于隨機數發生器生成的隨機序列。隨機序列在信息安全領域用來增強安全性[1]，因此隨機性的質量直接影響搖號系統的安全問題。隨機性分為3類：統計學偽隨機性、密碼學安全偽隨機性、真隨機性。統計學安全偽隨機性基于統計學的概念，定義為在生成的隨機比特流序列中“1”出現的頻率和“0”出現的頻率一致。密碼學安全偽隨機性基于密碼學的概念，定義為通過給定隨機序列的隨機生成算法和一部分序列不能推算出隨機序列的剩余部分。真隨機性基于物理現象產生，其隨機序列是不可重現的?；谏鲜龆x，生成的隨機序列分為真隨機序列和偽隨機序列。真隨機序列可通過硬件使用電子元件的噪音生成，對技術要求比較高。偽隨機序列由計算機的隨機函數和種子產生，滿足統計學/密碼學安全偽隨機性的定義標準。在某種程度上，偽隨機序列是可以通過標準方法進行檢測的。而實際應用中，搖號系統的隨機數就是偽隨機序列。對搖號系統的偽隨機序列進行檢測可驗證隨機序列的質量[2]。

對搖號系統的檢測研究中，文獻[3,4]采用基于插值多項式的可驗證隨機數生成方案實現搖號系統的公平性檢測。該檢測方法滿足可參與性、可驗證性的要求，但該方法從用戶是否參與隨機數的生成過程進行驗證，前提是在用戶需要驗證的情況下去驗證。而搖號系統的使用往往是先通過第三方檢測再進行搖號，因此上述方法不利于實際使用。文獻[5]運用獨立同分布的中心極限定理配合歷史的雙色球開獎數據驗證彩票的隨機性，該方法通過分析大量的歷史數據采用X2-分布檢驗，不適用于搖號系統單次使用的隨機性檢測。目前國際上通用的檢測方法是將多種隨機性檢測算法組成檢測套件，文獻[6]采用NIST統計測試套件進行檢測并在套件的機上實現優化以此提升運算速率。近年來，近似熵檢測成為我國的隨機性檢測標準之一。因此，本文將近似熵應用在電子搖號系統的隨機性檢測中，并以某區公辦小學電腦搖號系統為例說明近似熵檢測方法對搖號隨機數的可驗證性，保證搖號系統的公平性與安全性。

2 搖號系統隨機數的構造

搖號系統的隨機數通常由隨機函數種子生成。種子是生成偽隨機數的初始使用值，生成的機制是將種子的值通過一定算法轉化為隨機數空間中的某個點，依次產生的偽機數均勻分布在這個空間中。因此采用相同的隨機函數生成器和種子會產生可預測的隨機數。通常隨機函數是給定的，搖號系統要保證生成的隨機序列具備不可預測性需要保證種子本身具備隨機性和不可預測性。所以實際使用中，搖號系統以當前時間為種子，保證前向不可預測性和后向不可預測性，即通過已生成的序列無法預測后續的輸出序列，也無法得出種子。搖號系統的隨機數區間則根據搖號規模自由制定。

3 近似熵檢測

隨機數的檢測可依據國家密碼管理局標準GM/T 0005-2012和NIST測試標準。近似熵檢測作為GM/T 0005-2012中的一種統計檢測項目，判斷依據是分析待檢測序列是否具有較強的規則性，適用于搖號系統隨機序列的不規則性分析。近似熵檢測的原理是通過比較m位可重疊子序列模式的頻數和m+1位可重疊子序列模式的頻數來判定隨機性[7]。假設模式，則Yi(m)在待檢測序列中出現的相對頻數為：，=π，πi表示l=(i1,i2,…,im)在待檢測序列中出現的相對頻率。其中，近似熵檢測對參數n和m的要求為：m＜-2。整體算法過程如下：

（1）將二元序列ε的前m-1位數據添加到序列末尾形成新序列ε'，則新序列ε'長度為n'=n+m-1。

（2）計算新序列ε'中的所有2m個m位子序列模式出現的頻數vi1i2…im，針對所有的j(0≤j≤2m-1)計算。

（4）用m+1替換m重復步驟（1）到（3）獲得計算后的φ(m+1)。

（5）計算熵ApEn(m) =φ(m)-φ(m+1)，ApEn(m)的值越大表示檢測序列具有不規則性和不連續性；反之，值越小表示檢測序列具有規則性和連續性。

（6）計算統計值V=2n[ln2-ApEn(m)]。

（7）最后計算度量指標p-value的值，計算公式為：p-value=igamc，其中igamc表示不完全伽馬函數（Incomplete Gamma Function），將度量指標p-value與顯著性水平α進行比較，依據標準α設為0.01，若p-value≥α，則認為通過近似熵檢測；否則，不通過檢測。

近似熵檢測參數m的取值參考標準應為m=2,5，檢測時需將隨機序列轉化為二元序列，二元序列是指由“0”和“1”組成的比特串，并計算m和m+1的重疊子序列出現的頻數來檢測隨機性。

4 基于近似熵的搖號系統隨機數檢測

對搖號系統的檢測實際是對搖號系統生成的偽隨機數采用近似熵進行檢測。搖號系統將隨機函數生成的隨機數作為派位號。本文以某區公辦小學電腦搖號系統為例，闡述搖號系統通過近似熵檢測驗證隨機數的公平性與安全性以及基于隨機數的搖號過程。該搖號系統采用數據庫管理數據，通過對數據庫訪問獲取需要搖號的學生和學校數據，隨機數的生成服務于搖號過程，驗證模塊與搖號模塊相互獨立以保證耦合性，其服務架構如圖1所示。

圖1 隨機序列服務架構

在搖號系統生成偽隨機序列后，將偽隨機序列轉化為二元序列進入驗證模塊進行近似熵檢測，通過近似熵檢測則進入搖號過程，未通過檢測則退出系統，流程如圖2所示。

圖2 近似熵檢測和搖號過程

本文按照近似熵檢測代碼思想，分別以序列長度n=100、200為樣本規模，樣本數據為某區公辦小學電腦搖號系統隨機函數生成的隨機序列轉化的等價二元序列。實驗參數取m=2,5進行計算，所有的算法過程在Windows系統采用python實現。實驗結果如表1所示，表明搖號系統的隨機數通過了近似熵檢測，說明搖號系統的隨機數具備可驗證性。

表1 近似熵檢測結果

5 結語

本文基于近似熵檢測法驗證搖號系統生成的隨機數，并以某區公辦小學電腦搖號系統為例闡述近似熵檢測法在搖號系統中的使用過程。實驗結果表明搖號系統隨機數具備可驗證性、隨機性和不可預測性，為保障搖號系統的公平性和安全性提供理論基礎。隨機性檢測標準中還有其他檢測項，下一步的主要工作將是研究適用于搖號系統大量隨機序列檢測的高效算法。