單比特遊程頻率的在線隨機性測試的製作方法
2023-06-03 14:11:16
專利名稱：單比特遊程頻率的在線隨機性測試的製作方法
背景技術：
發明領域 本發明涉及隨機數生成器領域，具體來講，涉及用於生成真二進位隨機序列的數字數據處理設備和方法。
相關技術描述 在這個計算機年代裡，隨機數生成器是十分重要的。在實際應用中很難生成真隨機序列。例如，當隨機數生成器的硬體部件在一定時間期間上生成一連串的1和0的序列時，它內部將產生熱量。生成1比特比生成0比特消耗更多功率。照此，如果生成1比特的長序列，那麼電路將變熱。由此，如果電路變熱時生成1比特，則電路將「閉鎖」，並且主要生成1比特，而生成很少的0比特。如果電路變熱時生成0比特，那麼可能會出現不同的效果。在該情況下，1比特的長子序列變得非常稀少，並且構成非隨機的屬性。在長子序列偶爾包含相等比特長的0和1的隨機序列中，偏離的0/1頻率誤差將具有破壞安全性的災難性結果。
因此，當執行隨機性測試時，需要硬體竄改和元件故障的檢測。常規的隨機性測試通過對所生成的隨機數序列大量的統計測試執行，諸如X2測試、Δ測試等。然而，由於這種測試需要大量的計算處理功率，因此實時執行它是費用浩大的。
發明內容
本發明克服了上述問題，並且通過提供了用於提供在線隨機性測試的方法和設備而提供了更多優點，以確保所生成的隨機數較不容易被未授權方進行加密分析。
依照本發明的一方面，提供了用於測試隨機性的方法。所述方法包括以下步驟生成隨機二進位比特的連續流；將生成的隨機比特應用於指數單比特遊程頻率運算中，以計算單比特遊程長度值範圍的平均單比特遊程頻率值；並且，通過比較指數單比特遊程頻率運算的輸出與預定驗收範圍(acceptance range)來確定生成的隨機比特是否是充分隨機的，其中所述指數單比特遊程頻率運算涉及識別在一行中具有全部為0或者1的比特子序列之一的多個子序列。所述方法還包括以下步驟當任何平均單比特遊程頻率值重複地超出(falloutside)預定驗收範圍達預定次數以上時，確定生成的隨機比特是不充分地隨機的；當任何平均單比特遊程頻率值重複地超出預定驗收範圍達預定次數以上時，通知生成的隨機比特是不充分地隨機的；當任何平均單比特遊程計數重複地超出預定驗收範圍達預定次數以上時，生成一個新的隨機二進位比特組；並且，當確定生成的隨機比特是不充分地隨機之時，拒絕生成的隨機比特用於後續的應用。
依照本發明的另一個方面，提供了一種用於評估隨機數生成器生成的隨機數的方法。所述方法包括以下步驟(a)利用隨機數生成器生成隨機比特流；(b)將生成的隨機比特應用於單比特遊程長度運算；(c)將單比特遊程長度運算的輸出應用於指數平均，以獲得單比特遊程長度範圍的平均單比特遊程頻率值；(d)比較平均單比特遊程頻率值與預定驗收範圍；以及，(e)確定任何平均單比特遊程頻率值是否超出預定驗收範圍達預定次數以上。所述方法還包括以下步驟重複步驟(a)-(e)，直到任意平均單比特遊程頻率值都超出預定驗收範圍；當重複步驟(a)-(e)達預定次數以上時，通知生成的數字是不充分地隨機的。當任何平均單比特遊程頻率值超出預定驗收範圍達預定次數以上時，認為生成的隨機比特是不充分地隨機的。
依照本發明的再一方面，提供了一種用於評估由隨機數生成器生成的隨機數的設備。所述設備包括用於生成包括二進位比特的隨機序列的裝置；用於根據指數單比特遊程頻率運算來檢測所生成的隨機序列是否是不充分地隨機的裝置；以及，用於當確定所生成的隨機序列是不充分地隨機之時，為後續的應用控制所生成的隨機序列流的裝置，其中執行所述指數單比特遊程頻率運算，以便對所生成的隨機序列計算單比特遊程長度範圍的平均數單比特遊程頻率值，並且其中，如果指數單比特遊程運算的任意輸出重複地超出預定驗收範圍達預定次數以上，那麼確定所生成的隨機序列是不充分地隨機的。所述設備還包括用於當任意平均單比特遊程頻率值重複地超出預定驗收範圍達預定次數以上時，發送所生成的隨機序列是不充分地隨機的報警信號的裝置，以及用於當任意平均單比特遊程頻率值重複地超出預定驗收範圍達預定次數以上時，生成一個新的隨機比特組的裝置。
又一個方面在於本發明可以為特定應用來根據需要依照硬體、軟體或者硬體和軟體的組合來實現。
此外，本發明能夠以簡單、可靠並且廉價的設備來實現。
當結合附圖閱讀以下詳細說明時，這些及其他優點將對所述領域技術人員變得更加顯而易見。
附圖簡述
圖1舉例說明了依照本發明實施例的隨機數生成模塊的簡化框圖； 圖2示出了示出依照本發明實施例對隨機數序列執行隨機性測試的圖表；以及， 圖3是舉例說明依照本發明實施例測試所生成的隨機數統計量的操作步驟的流程圖。
實施例詳述 在隨後的描述中，為了說明的目的而不是限制，敘述了特定細節，諸如特定體系結構、界面、技術等，以便提供對本發明的徹底的了解。然而，對於本領域技術人員顯而易見的是，本發明可以依照脫離這些特定細節的其他實施例實施。為了簡明並且清楚，省略了對眾所周知的設備、電路以及方法的詳細說明，免得因不必要的細節而使本發明的描述模糊。
圖1舉例說明了依照本發明示範性實施例的隨機數生成系統10的簡化框圖。系統10包括隨機數生成器(RG)12，檢測器14和開關16。應注意的是，術語「隨機數」指的是任何二進位信號序列，高斯型曲線或者信號的任何其他分布，表示0和1之間的數的信號序列，表示十進位數的信號序列，或者包括所希望的隨機性的任何其他形式。
在操作中，RG 12可操作來輸出一連串隨機數。應該注意的是，此公開內容中的RG 12指的是任何可以生成信號的設備，所述信號可以依照任何常規的或者非常規的方式轉換為二進位比特序列。當生成隨機數時，檢測器14依照預定標準(稍後解釋)檢測RG 12是否生成充分隨機的序列。當檢測器14認為所生成的隨機數是不充分地隨機之時，開關16停止所生成的隨機數流。然而，如果確定它們是真隨機的，那麼開關16允許所生成的隨機數字用於後續的應用，諸如任何電路、系統、處理、投機應用、模擬、統計抽樣、Diffie-Hellman密鑰交換等等，這些使用由RG 12提供的隨機數。由此，開關16可以表示到加密系統，音頻或者視頻噪聲發生器，電腦程式或者其他設備和過程的輸入。
現在，參照圖2和3，就確定所生成的隨機數是否是充分地隨機的而進行詳細描述。
參照圖2，依照本發明實施例，當RG 12處於運行中時，實時地測試隨機數，以確保所生成的隨機數是充分地隨機的。在運行中，由RG 12生成隨機比特的連續流。同時，檢測器14計算隨機比特流的單比特遊程頻率。特別地，檢測器14檢測長度k的全部子序列，在一行中具有0或者1的子序列。在檢測模式期間，每當生成新的隨機比特時，就檢驗該新比特是否繼續在前的單比特遊程。如果所述新比特不同於在前的比特，那麼確定遊程長度k。例如，如圖2所示，當生成隨機比特的連續流時，三個連續的0的S3(由P6、P7和P8表示)以及四個連續的1的T4(由P2、P3、P4和P5表示)可以由檢測器14觀察到。
在所述實施例中，單比特遊程計數過程連續地運行。照此，必須周期地清除計數器或者累加器A以避免溢出。為此目的，在本發明中，使用了指數平均，其中在執行計數加法以前，累加器A以一確定的0＜α＜1因子而減少，因此，它永遠不會變得太大。也就是說，為了節省存儲和執行時間，在本發明中應用了對自相關計算的指數平均。指數平均具有這樣的屬性，每當在累加器A中更新平均數時，舊的平均值將具有減小的效果。應該注意的是，存在各種計數法，它們可以依照本發明的技術實現；然而優選的是，使用指數平均，如下所述。
所述指數平均依照下列方式工作。每當讀取數值b時，將0和1之間的係數α(0＜α＜1)乘到累加器A，然後將b與之相加Anew＝α·Aold+b。為了具有有用的平均效果，α的值選擇為接近1，α＝1-1/n，n＞＞1。在該情況下，loga≈-1/n和平均比特的半衰期是k≈n·log2≈0.30103·n。在n步驟之後，最舊的平均值的權重變成(1-1/n)n≈1/e≈0.367879。這裡，e是自然對數的底數(歐拉常數)，如此可以將項n稱為平均值的自然壽命。如果將平均的全部值是1，那麼累加器的值是1+α+α2+...＝1/(1-α)＝n，而如果全部比特是0，那麼累加器的值是0。應注意的是，指數平均的預期值是各個隨機變量的期望值的指數平均。如果它們是均勻分布的二進位比特，則預期值是1/2+1/2α+1/2α2+...＝n/2。
如上所述，當累加器以確定的0＜α＜1因子而減少時，指數平均用作清除計數器；由此在操作模式期間，累加器決不會變得太大。一旦為每個累加器執行指數平均，則將指數平均的值與預定驗收範圍相比較。也就是說，通過比較每個累加器的值與預定驗收範圍值，確定生成的隨機數模式是否是充分地隨機的。如果在平均處理過程期間、任何累加器的值都超出預定範圍值，那麼可以推斷所生成的隨機數往往不是不可預知的。這裡，可以設置閾值，當測試重複失敗時通知用戶。
為幫助理解推導預定驗收範圍，使用了以下數學式。在長度為n的所有2n比特序列的列表中，存在2n-k-2個全部是『0』的長度k的子序列，其起始於任意的固定比特位置2，3，...，n-k。由此，在長度n的一些比特序列中，存在比特『0』的(n-k-1)·2n-k-2可能的長度k的遊程。在一些長度為n的比特序列的開始，存在2n-k-1個全部為『0』的子序列。最後出現相同數目的子序列，其合計達到2n-k。同時，如果k≤n-2，那麼在長度n的比特序列中，存在比特『0』的(n-k+3)·2n-k-2個長度k的遊程。如果k＝n-1，那麼存在兩個這種子序列，並且如果k＝n，只存在一個這種子序列。如果k足夠小，那麼遊程的數目可以大於長度n的序列的數目。應注意的是，對於比特『1』的長度k的遊程的數目同樣如此。
檢查n個比特，比特『0』的k長度遊程的期望值是(n-k+3)/2k+2，與比特『1』的k長度遊程的期望值相同。因此，可以通過設置以(n-k+3)/2k+2為中心的邊界來選擇預定驗收範圍。由此，外邊界可以表示為[(n-k+3)/2k+2-α，(n-k+3)/2k+2+b]。根據從與已知的、良好資源的隨機數的大量模擬中獲得的數據可以有選擇地調節確切的邊界，其中可以獲得理想的單比特遊程的頻率。這種隨機序列可以購買到，並且例如可以從各種網絡資源下載，包括「www.fourmilab.ch/hotbits」和「lavarand.sgi.com」。由此，操作者有選擇地設置用於測試的實際範圍，以便就所生成的隨機序列是否可被未授權方預測而言，可以選擇不同的靈敏度。
圖3是舉例說明依照本發明實施例測試隨機序列統計質量的操作步驟的流程圖。矩形單元表明計算機軟體指令，而菱形單元表示影響由矩形方塊表示的計算機軟體指令的執行的計算機軟體指令。作為選擇，處理和判定塊表示由功能等效電路執行的步驟，所述電路諸如數位訊號處理機電路或者專用集成電路(ASIC)。應該注意的是，諸如循環和變量的初始化的許多例行程序單元和臨時變量的使用沒有示出。本領域中普通技術人員將理解的是，在此除非另有說明，否則描述的步驟的特定順序只是說明性的，並且可以變化，而不脫離本發明的精神。
在步驟100，對隨機數生成器12生成的隨機二進位比特的連續流進行隨機性測試。在步驟120，生成的隨機比特受到單比特遊程確定處理，然後將單比特遊程的長度k存儲在累加器中。每當發現單比特遊程時，更新一組指數平均單比特遊程頻率值，其計數特定單比特遊程的長度已經出現的頻率。全部指數平均單比特遊程頻率值都減小因子α(0＜α＜1)，而只有對應於單比特遊程長度k的那個加1。
在步驟140，在每個累加器中執行指數平均運算，以便舊的平均單比特遊程頻率值將具有減少的效果。在步驟160，將指數平均運算之後的平均單比特遊程頻率值與它們相應的預定驗收範圍相比較。如果每個累加器A中任意的值超出預定驗收範圍，那麼在步驟200確定已經檢測到在真隨機序列中不期望的這種模式，並且計數器加1。否則，在步驟180重置計數器，並且返回到步驟100，以進一步處理隨機數。在步驟220，如果計數器的值大於閾值，那麼在步驟240發送所生成的隨機數不是充分地隨機的通知。作為選擇，可以置開關16無效，以便為後續的應用停止隨機數流，或者可以丟棄所生成的隨機數，並且在步驟240，可以開始生成新的隨機數的整個處理過程。最後，如果在步驟220計數器的值沒有超過閾值，則處理過程返回到步驟100。
如上所述的各種步驟可以通過將它們編程為函數，且併入應用程式內來實現，並且本領域的普通程式設計師可以利用慣用的編程技術來實現，例如使用C、Visual Basic、Java、Perl、C++等等來實現。在示範性實施例中，在圖3中描述的方法可能如下構造(利用C程序設計語言)。為簡單起見，我們利用浮點運算實現測試。
AppondixMS Visual C code /******************************************************************\ * RunFreq.c * RunFreq＜#random bits＞＜bit generator type>＜bit generator param＞ * 生成測試位 * 0或1的所有K-遊程的指數頻率(K＝2..8) * 列印測試統計 * Rem使用浮點運算 * 遵循把Bit Avg.c轉換到固定點的例子 * 如果總和只是在每第k次迭代才被減少，則就達到了長度l * RunFreq 3e7 0 0.5 -＞ * 沒有更大的遊程偏置 * 101.595 155.876 * 96.4734 158.746 * 96.3919 160.404 * 96.9115 160.165 * 101.7 160.119 * 99.1938 160.788 * 104.392 158.286 * 97.374 160.544 * * 版本.1.0 04/17/01；由Laszlo Hars創建 * \******************************************************************/ #include＜stdio.h＞ #include #define MAXFULLRUN 10 #define MAXRUN2(MAXFULLRUN-2) #define MAX(A，B)((A)＞(B)？(A):(B)) #define MIN(A，B)((A)＜(B)？(A):(B))<!-- SIPO --> //外部函數原型void BitGenInit(int argc，char*argv[])；unsigned int NextBit；int main(int argc，char*argv[]){int b0，b1，rl，i，j，n＝(int)atof(argv[1])；doublea[MAXRUN2]＝{125.0，125.0，125.0，125.0，125.0，125.0，125.0，125.0}，//ideal pastl[MAXRUN2]＝{95.00，95.00，95.00，95.00，95.00，95.00，95.00，95.00}，//LO limit＝ideal/1.32h[MAXRUN2]＝{165.0，165.0，165.0，165.0，165.0，165.0，165.0，165.0}，//HI limit＝ideal*1.32x[MAXRUN2]＝{0.0，0.0，0.0，0.0，0.0，0.0，0.0，0.0}，// 調試用最大值，求值y[MAXRUN2]＝{1e9，1e9，1e9，1e9，1e9，1e9，1e9，1e9}，// 調試用最小值，求值w[MAXRUN2]＝{0.99609375，0.998046875，0.9990234375，0.99951171875，0.999755859375， 0.9998779296875，0.99993896484375，0.99993896484375}；// 乘＝1-1/2^(8..14，14)if(argc＜4){ printf(″UsageRunFreq＜#random bits＞＜bit generator type>＜bit generatorparams...>\n″)； putchar(′\a′)； // 振鈴 exit(1)；}BitGenInit(argc，argv)；b0＝NextBit；rl＝-1； //rl＝0runlength＝2for(i＝1；i＜n；++i){ b1＝NextBit；<!-- SIPO --> if(b0＝＝b1){++rl；continue；}// 一個遊程之內{這裡能夠檢查遊程是否太長} if(rl＜0){b0＝b1；continue；}// 太短的遊程 rl＝MIN(rl，MAXRUN2-1)；// 把所有長的遊程聚在一起 for(j＝0；j＜MAXRUN2；++j){ a[j]＝a[j]*w[j]+(j＝＝rl)； x[j]＝MAX(a[j]，x[j])；// 用於調試，賦值 y[j]＝MIN(a[j]，y[j])；// 用於調試，賦值 if(a[j]＜l[j]‖a[j]＞h[j]){ printf(″Too large bias of ％d-run of bits ％d at bit ％d\n″，rl+2，b0，i)； exit(2)；} } b0＝b1； rl＝-1； } printf(″No large bias of runs\n″)； for(j＝ 0；j＜MAXRUN2；++j)printf(″％g ％g\n″，y[j]，x[j])；//顯示調試結果，賦值 } 雖然已經舉例說明並且描述了本發明的優選實施例，但是本領域技術人員可以理解的是，在不脫離本發明的真正範圍的情況下，可以作出各種改變和修改，並且對本發明的單元進行等效代替。具體來講，除了指數平均，還可以使用其他類型的普通平均、分組平均值、重啟平均等等。另外，在不脫離本發明的中心範圍的情況下，可以作出許多修改來適用於特定情況和本發明的講授。因此，不能將本發明限制為依照用於執行本發明的最佳方式公開的特定實施例，而是本發明包括屬於所附權利要求書的範圍內的所有實施例。
權利要求
1.一種用於當生成隨機數時測試隨機性的方法，所述方法包括以下步驟
生成隨機二進位比特的連續流；
將所述生成的隨機比特應用於指數單比特遊程頻率運算，以計算單比特遊程長度值範圍的平均單比特遊程頻率值；並且，
通過比較所述指數單比特遊程頻率運算的輸出與預定驗收範圍來確定所述生成的隨機比特是否是充分地隨機的。
2.如權利要求1所述的方法，還包括以下步驟當任何平均單比特遊程頻率值重複地超出所述預定驗收範圍達預定次數以上時，確定所述生成的隨機比特是不充分地隨機的。
3.如權利要求1所述的方法，還包括以下步驟當任何平均單比特遊程頻率值重複地超出所述預定驗收範圍達預定次數以上時，通知所述生成的隨機比特是不充分地隨機的。
4.如權利要求1所述的方法，還包括以下步驟當任何平均單比特遊程計數重複地超出所述預定驗收範圍達預定次數以上時，生成一個新的隨機二進位比特組。
5.如權利要求1所述的方法，其中所述指數單比特遊程頻率運算涉及識別在一行中具有全部為0或者1比特子序列之一的多個子序列。
6.如權利要求1所述的方法，還包括以下步驟當確定生成的隨機比特是不充分地隨機之時，拒絕所述生成的隨機比特用於後續的應用。
7.一種用於評估由隨機數生成器生成的隨機數的方法，所述方法包括以下步驟
(a)利用所述隨機數生成器生成隨機比特流；
(b)將所述生成的隨機比特應用於單比特遊程長度運算；
(c)將所述單比特遊程長度運算的輸出應用於指數平均，以獲得單比特遊程長度範圍的平均單比特遊程頻率值；
(d)比較平均單比特遊程頻率值與預定驗收範圍；以及，
(e)確定任何平均單比特遊程頻率值是否超出所述預定驗收範圍達預定次數以上。
8.如權利要求7所述的方法，還包括以下步驟當任意所述平均單比特遊程頻率值超出所述預定驗收範圍達預定次數以上時，確定所述生成的隨機比特是不充分地隨機的。
9.如權利要求7所述的方法，進一步包括步驟
重複所述步驟(a)-(e)，直到任何平均單比特遊程頻率值都超出所述預定驗收範圍。
10.如權利要求9所述的方法，還包括以下步驟當所述步驟(a)-(e)被重複所述預定次數以上時，通知生成了不充分地隨機的數。
11.如權利要求9所述的方法，還包括以下步驟當所述步驟(a)-(e)被重複所述預定次數以上時，生成一個新的隨機數組。
12.如權利要求7所述的方法，其中所述指數單比特遊程頻率運算涉及識別在一行中具有全部為0或者全部為1比特之一的多個子序列。
13.一種用於評估由隨機數生成器生成的隨機數的設備，包括
用於生成包括二進位比特的隨機序列的裝置(12)；
用於根據指數單比特遊程頻率運算來檢測所述生成的隨機序列是否是不充分地隨機的裝置(14)；以及，
用於當確定所述生成的隨機序列是不充分地隨機之時，為後續的應用控制所述生成的隨機序列流的裝置(16)，
其中執行所述指數單比特遊程頻率運算，以便對所述生成的隨機序列計算單比特遊程長度範圍的平均數單比特遊程頻率值，並且其中，如果所述指數單比特遊程運算的任意輸出重複地超出一個預定驗收範圍達預定次數以上，那麼確定所生成的隨機序列是不充分地隨機的。
14.如權利要求13所述的設備，還包括用於當任何平均單比特遊程頻率值重複地超出所述預定驗收範圍達預定次數以上時，發送所述生成的隨機序列是不充分地隨機的報警信號的裝置。
15.如權利要求13所述的設備，還包括用於任何所述平均單比特遊程頻率值重複地超出所述預定驗收範圍達預定次數以上時，生成一個新的隨機比特組的裝置。
16.如權利要求13所述的設備，其中所述指數單比特遊程頻率運算包括識別在一行中具有全部為0或者全部為1比特之一的多個子序列。
17.一種機器可讀介質，其上存儲有表示指令序列的數據，並且所述指令序列當由處理器執行時，令處理器執行
處理隨機比特的連續流；
對所述生成的隨機比特執行指數單比特遊程頻率運算，以計算單比特遊程長度範圍的平均單比特遊程頻率值；並且，
通過比較所述指數單比特遊程頻率運算的輸出與預定驗收範圍來確定所述生成的隨機數是否是不充分地隨機的。
18.如權利要求17所述的存儲介質，其中當任何平均單比特遊程頻率值超出所述預定驗收範圍時，確定所述生成的隨機數是不充分地隨機的。
19.如權利要求17所述的存儲介質，其中當任何平均單比特遊程頻率值超出所述預定驗收範圍時，所述處理器進一步運行以處理一個新的隨機比特組。
20.如權利要求17所述的存儲介質，其中所述指數單比特遊程頻率運算包括識別在一行中具有全部為0或者全部為1比特之一的多個子序列。
全文摘要
本發明是用於實時測試由隨機數生成器生成的隨機數的方法和設備。利用所述隨機數生成器生成隨機比特流，然後所生成的隨機比特流接受單比特遊程長度運算，其中在一行具有全部為0或全部為1比特的多個子序列被識別。將所述單比特遊程長度計算的輸出應用於指數平均，以便獲得單比特遊程長度範圍的出現率或頻率的平均數。將單比特遊程長度與預定驗收範圍相比較，由此如果任何平均單比特遊程頻率值重複地超出預定驗收範圍達預定次數以上，那麼確定所生成的隨機比特是不充分地隨機的。
文檔編號G06F7/58GK1643493SQ03806860
公開日2005年7月20日 申請日期2003年2月26日 優先權日2002年3月26日
發明者L·哈爾斯 申請人:皇家飛利浦電子股份有限公司