許穎媚 匡碧琴

（1．廣東省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510000；2．廣東省計(jì)算技術(shù)應(yīng)用研究所，廣東 廣州 510000）

1 引言

隨著信息化的發(fā)展，搖號(hào)系統(tǒng)的應(yīng)用范圍無處不在。搖號(hào)上學(xué)系統(tǒng)、抽獎(jiǎng)?chuàng)u號(hào)系統(tǒng)、保障性住房搖號(hào)、新車上牌搖號(hào)等都是以公平性為基礎(chǔ)保障電子政務(wù)的公信力。搖號(hào)系統(tǒng)的公平性需要從技術(shù)角度進(jìn)行驗(yàn)證。

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

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

2 搖號(hào)系統(tǒng)隨機(jī)數(shù)的構(gòu)造

搖號(hào)系統(tǒng)的隨機(jī)數(shù)通常由隨機(jī)函數(shù)種子生成。種子是生成偽隨機(jī)數(shù)的初始使用值，生成的機(jī)制是將種子的值通過一定算法轉(zhuǎn)化為隨機(jī)數(shù)空間中的某個(gè)點(diǎn)，依次產(chǎn)生的偽機(jī)數(shù)均勻分布在這個(gè)空間中。因此采用相同的隨機(jī)函數(shù)生成器和種子會(huì)產(chǎn)生可預(yù)測(cè)的隨機(jī)數(shù)。通常隨機(jī)函數(shù)是給定的，搖號(hào)系統(tǒng)要保證生成的隨機(jī)序列具備不可預(yù)測(cè)性需要保證種子本身具備隨機(jī)性和不可預(yù)測(cè)性。所以實(shí)際使用中，搖號(hào)系統(tǒng)以當(dāng)前時(shí)間為種子，保證前向不可預(yù)測(cè)性和后向不可預(yù)測(cè)性，即通過已生成的序列無法預(yù)測(cè)后續(xù)的輸出序列，也無法得出種子。搖號(hào)系統(tǒng)的隨機(jī)數(shù)區(qū)間則根據(jù)搖號(hào)規(guī)模自由制定。

3 近似熵檢測(cè)

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

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

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

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

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

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

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

近似熵檢測(cè)參數(shù)m的取值參考標(biāo)準(zhǔn)應(yīng)為m=2,5，檢測(cè)時(shí)需將隨機(jī)序列轉(zhuǎn)化為二元序列，二元序列是指由“0”和“1”組成的比特串，并計(jì)算m和m+1的重疊子序列出現(xiàn)的頻數(shù)來檢測(cè)隨機(jī)性。

4 基于近似熵的搖號(hào)系統(tǒng)隨機(jī)數(shù)檢測(cè)

對(duì)搖號(hào)系統(tǒng)的檢測(cè)實(shí)際是對(duì)搖號(hào)系統(tǒng)生成的偽隨機(jī)數(shù)采用近似熵進(jìn)行檢測(cè)。搖號(hào)系統(tǒng)將隨機(jī)函數(shù)生成的隨機(jī)數(shù)作為派位號(hào)。本文以某區(qū)公辦小學(xué)電腦搖號(hào)系統(tǒng)為例，闡述搖號(hào)系統(tǒng)通過近似熵檢測(cè)驗(yàn)證隨機(jī)數(shù)的公平性與安全性以及基于隨機(jī)數(shù)的搖號(hào)過程。該搖號(hào)系統(tǒng)采用數(shù)據(jù)庫管理數(shù)據(jù)，通過對(duì)數(shù)據(jù)庫訪問獲取需要搖號(hào)的學(xué)生和學(xué)校數(shù)據(jù)，隨機(jī)數(shù)的生成服務(wù)于搖號(hào)過程，驗(yàn)證模塊與搖號(hào)模塊相互獨(dú)立以保證耦合性，其服務(wù)架構(gòu)如圖1所示。

圖1 隨機(jī)序列服務(wù)架構(gòu)

在搖號(hào)系統(tǒng)生成偽隨機(jī)序列后，將偽隨機(jī)序列轉(zhuǎn)化為二元序列進(jìn)入驗(yàn)證模塊進(jìn)行近似熵檢測(cè)，通過近似熵檢測(cè)則進(jìn)入搖號(hào)過程，未通過檢測(cè)則退出系統(tǒng)，流程如圖2所示。

圖2 近似熵檢測(cè)和搖號(hào)過程

本文按照近似熵檢測(cè)代碼思想，分別以序列長(zhǎng)度n=100、200為樣本規(guī)模，樣本數(shù)據(jù)為某區(qū)公辦小學(xué)電腦搖號(hào)系統(tǒng)隨機(jī)函數(shù)生成的隨機(jī)序列轉(zhuǎn)化的等價(jià)二元序列。實(shí)驗(yàn)參數(shù)取m=2,5進(jìn)行計(jì)算，所有的算法過程在Windows系統(tǒng)采用python實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果如表1所示，表明搖號(hào)系統(tǒng)的隨機(jī)數(shù)通過了近似熵檢測(cè)，說明搖號(hào)系統(tǒng)的隨機(jī)數(shù)具備可驗(yàn)證性。

表1 近似熵檢測(cè)結(jié)果

5 結(jié)語

本文基于近似熵檢測(cè)法驗(yàn)證搖號(hào)系統(tǒng)生成的隨機(jī)數(shù)，并以某區(qū)公辦小學(xué)電腦搖號(hào)系統(tǒng)為例闡述近似熵檢測(cè)法在搖號(hào)系統(tǒng)中的使用過程。實(shí)驗(yàn)結(jié)果表明搖號(hào)系統(tǒng)隨機(jī)數(shù)具備可驗(yàn)證性、隨機(jī)性和不可預(yù)測(cè)性，為保障搖號(hào)系統(tǒng)的公平性和安全性提供理論基礎(chǔ)。隨機(jī)性檢測(cè)標(biāo)準(zhǔn)中還有其他檢測(cè)項(xiàng)，下一步的主要工作將是研究適用于搖號(hào)系統(tǒng)大量隨機(jī)序列檢測(cè)的高效算法。