通過重疊字計數的在線隨機性測試的製作方法
2023-05-06 11:41:26
專利名稱：通過重疊字計數的在線隨機性測試的製作方法
技術領域：
本發明涉及隨機數發生器的領域，並且具體涉及用於實時分析所生成的隨機數的統計質量的數字數據處理設備和方法。
背景技術：
智慧卡典型地是一種信用卡大小的塑料卡，包括嵌入在上面地能夠實現各種交易的微處理器。此卡可以包括用於執行各種加密算法的加密模塊，以便與其它接口即讀卡終端交換信息。利用加密模塊，將信號從此卡路由發送到此卡外的許多金屬觸點，這些觸點與讀卡終端的相同觸點形成物理接觸。
在加密模式期間，隨機數發生器以某種形式的密碼術被用於提供消息的安全傳輸，以使得只有預定的接收端才能理解由一個授權發送端發送的消息(即，語音或數據)。然而，由於未經授權的接收機和未經授權的發射機變得越來越精通對消息加密中使用的隨機數的生成過程的破譯，為了安全通信而變得迫切需要生成不可預測的隨機數。
除了由於未經授權方造成的洩密之外，隨機數發生器在操作期間還可以生成非隨機數。例如，隨機數發生器的硬體部件在一段時間期間內生成一系列1和0時會發熱。生成1比特所消耗的功率比0比特要多。如果生成一長串1比特，電路就會變熱。此時，如果此電路在它是熱的時生成1比特，此電路將「閉鎖」，即，它幾乎始終生成1比特而很少生成0比特。如果電路在熱時生成0比特，則會出現不同的效果。在這種情況下，極少出現一長串1比特，這構成一種非隨機特性。在密碼應用中這可能會造成災難性後果將洩密。因此，在執行隨機性測試時，需要檢測硬體竄改和檢測電路的故障。
發明內容
本發明檢測上述及其它問題，並通過提供用於在線隨機性測試的方法和設備來提供附加益處，以致所生成的隨機數不容易受到來經授權方的密碼分析的影響。
按照本發明的一方面，提供用於在生成隨機數時測試隨機性的一種方法。該方法包括以下步驟生成二進位比特的隨機序列；在計算每個可能的k比特長度塊的出現的平均數時，將k比特預定塊應用於重疊計數運算；和確定每個k比特塊的出現頻率是否在預定的接受範圍(acceptance range)之內。該方法進一步包括以下步驟一旦確定至少一個k比特預定塊的出現頻率落在預定的接受範圍之外，通知所生成的隨機序列不夠隨機；並且在至少一個k比特預定塊落在預定的接受範圍之外時，生成新的一組隨機數。
按照本發明的另一方面，提供用於測試隨機數發生器的輸出的一種方法。該方法包括以下步驟(a)利用隨機數發生器生成一系列二進位比特；(b)以預定的時間間隔為每個可能的k比特預定塊執行和跟蹤重疊計數運算；(c)以預定的時間間隔為每個跟蹤的重疊計數運算計算指數平均值A；(d)將計算的指數平均值與一個預定的接受範圍進行比較；和(e)在計算的指數平均值落在預定的接受範圍之內時，確定所生成的二進位數足夠隨機。該方法進一步包括以下步驟重複步驟(a)-(d)，直至任何計算的指數平均落在預定的接受範圍之外；在步驟(d)中的測試重複地不大於一個門限值時，通知生成了非隨機數；並且在步驟(d)中的測試重複地不大於一個預定次數時，生成新的一組隨機數。
按照本發明的再一方面，提供用於測試隨機數序列的隨機性的一種設備。該設備包括隨機數發生器單元，用於生成基本上隨機的二進位比特序列；和檢測器單元，耦合到隨機數發生器單元的輸出，用於檢測生成的隨機序列是否足以不可預測，其中將k比特預定塊應用於重疊指數計數運算，一次一個，以計算每個可能的k比特塊出現的平均數，其中如果任何一個指數累加器的輸出A落在其預定的接受範圍之外，確定生成的隨機序列是非隨機的。該設備還包括耦合到隨機數發生器單元和檢測器單元的輸出的轉換單元，用於在生成的隨機序列被確定為足夠隨機時傳送生成的隨機序列以便後續應用，以及用於在任何指數累加器的值A落在其預定的接受範圍之外時發送一個報警信號的裝置。
另一方面是本發明可以根據具體應用的需要而利用硬體、軟體或硬體和軟體的組合來實現。
再一方面是本發明可以按簡單、可靠和廉價的實施方式來實現。
又一方面是本發明增加被嵌入智慧卡中的隨機數發生器的安全性。
根據以下對附圖所示的最佳實施例的更詳細描述將理解本發明的上述及其它特徵和優點。
圖1表示按照本發明一個實施例的隨機生成模塊的一個簡化方框圖2顯示表示按照本發明一個實施例的隨機序列的重疊計算的示意圖；和
圖3是表示按照本發明的一個實施例測試生成的隨機數的統計特性的操作步驟的流程圖。
具體實施例方式
在以下的說明中，為了解釋而非限制的目的，提出了具體細節，例如具體結構、接口、技術等等，以提供對本發明的全面理解。然而，本領域的技術人員將理解，在脫離這些具體細節的其它實施例中可以實現本發明。為了簡明起見，省略了對公知設備、電路和方法的詳細描述，以免不必要的細節妨礙對本發明的描述。
圖1表示按照本發明一個實施例的一種隨機發生系統10的功能框圖，用於測試所生成的隨機數的某些統計特性。系統10包括隨機數發生模塊(RG)12、檢測器14和轉換器16.RG模塊12可用於輸出一系列隨機數。應該注意到生成隨機數在現有技術中是公知的，並且可以利用各種方式來執行。檢測器14按照預定的標準(如下所解釋的)檢測由RG 12輸出的生成隨機數的隨機性；如果通過的話，轉換器16就允許生成的隨機數用於後續應用，例如使用由RG 12提供的隨機數的任何電路、系統、處理、應用等等。轉換器16在檢測器14的控制下被去激活，以便在生成的隨機數被認為不夠隨機時停止發送所生成的隨機數。轉換器16可以代表至一個密碼系統、音頻和視頻噪聲發生器、電腦程式或其它設備和程序的輸入。例如，隨機數發生系統10可用於提供安全數據，此數據在密碼協議中被用於建立在發送端和授權接收端之間的機密通信的密碼密鑰，類似於在公知的Diffie-Hellman安全共享協議中。隨機數可用於生成密碼密鑰來加密或解密消息分段，因此允許預定的接收機理解發送的消息。除了加密信號的形成之外，按照本發明技術的隨機數的測試還可以用於其中使用隨機數的其它實施中，即，賭博、仿真、統計抽樣等等。
如果在給出一個或多個隨機數的情況下所生成的隨機序列之中的任何一個其它比特不可能利用超過50％的概率預測到，則認為隨機數發生器是安全的。因此，本發明的密鑰原理包括對在給出一個或多個隨機數的情況下測試RG模塊12。特別地，利用檢測器14分析所生成的隨機序列的輸出，以確保所生成的隨機數將不可由未經授權方預測到。
現在，將參照圖2和3具體描述對隨機序列的統計質量的測試。
參見圖2，按照本發明的一個實施例在RG模塊12操作的同時對隨機數進行實時測試以確保生成的隨機數是合適的。這樣，易於利用軟體來實現本發明，其中將微處理器和隨機序列發生器集成在一個設備例如智慧卡內，因而測試僅僅需要幾行(line)附加代碼和很小的存儲器。通過初始化指數平均累加器來開始隨機性測試。如圖2中所示，由RG模塊12生成的隨機值的連續流經歷重疊計算運算，其中預置比特塊k被輸入到一個環形緩衝器，以輔助執行指數平均計算。通過將1加到相應的累加器A和將0加到其它累加器來更新隨機序列的每個k比特塊出現的平均數，一次一個，同時將它們全部縮減一個固定係數α(如下所解釋的)。因而，本發明使用包含所有可能的不同k比特塊的出現頻率的多個累加器。注意，給每個累加器分配一個初始值。例如，如果k＝3，隨機序列的第一塊就是(0，1，1)，相應的二進位值是3。應注意，為了便於說明，k的值被設定為3。因此，應該理解附圖中的k值不應該對本發明的範圍構成限制。隨機序列的第二塊是(1，1，0)，相應的二進位值是6。對於第三隨機序列塊(1，0，1)，相應的二進位值是5。每當生成新的隨機比特時，以面收集的比特塊向右移位，最左的一個比特被捨棄，並在右邊附加新的一比特。這樣，確定選擇用於計算每個k比特塊的出現次數的累加器所需的k比特的重疊塊。
在本實施例中，每當生成新的k比特塊並且在被索引的累加器A被更新的同時計算相應的二進位索引值時，確定所生成的隨機數是否足夠隨機，以致塊出現次數大致相同。也就是說，所有可能的k比特字在序列中出現的頻率應該大致相同。為此，將一個預定範圍值與每個累加器的值進行比較。如果在指數平均值計算過程期間任何一個累加器的值落在預定範圍之外，則推斷所生成的隨機數對於未經授權方將是可預測的。
注意，本發明可應用於實時測試隨機序列，舊的塊計數值應具有逐漸縮小或沒有影響。也就是說，評價隨機序列的統計質量的測試連續運行，因而必須周期性清除計數器。具有按照本發明的技術可以實施的各種計數方法；然而，如下所述，在重疊計數運算期間最好使用指數平均。
如果每當生成隨機數時使用累加器A來獲得一個平均出現值，將落在0與1之間的一個係數α(0＜α＜1)乘以A並隨後加上一個指示值bAnew＝α·Aold+b。在計數應用中，如果事件發生，b＝1，否則設置為0。為了得到有用的平均效果，α的值被選擇為接近1，α＝1-1/n，n＞＞1。在這種情況下，logα≈1-/n並且平均比特的半衰期是k≈n·log2≈0.30103·n。在n比特之後，最早一比特的加權變成了(1-1/n)n≈1/e≈0.367879。這裡，e是自然對數的底(歐拉(Euler)常數)，因此項n變成一比特的自然壽命。如果所有比特都是1，則累加器值為1+α+α2+...＝1/(1-α)＝n，而如果所有比特是0，則累加器值是0。注意，指數平均的預期值是各個比特的預期值的指數平均值1/2+1/2α+1/2α2+...＝n/2。如果每個其它比特是1，則累加器值在1+α2+α4+...＝1/(1-α2)和α+α3+α5+...＝α/(1-α2)之間交替改變，這些值非常接近1/2間隔[n/(2n-1)]，其平均值也是(1+α)/2(1-α2)＝n/2。
如上所述，指數平均用於在累加器隨著一定的0＜α＜1係數遞減時清除計數器；因而，累加器在運算模式期間從不會變得太大。每當對每個累加器執行指數平均時，將指數平均的值與如下所述導出的預定接受範圍進行比較。
容易看出，如果序列R真是隨機的，特定的k比特塊在長度為n的序列中出現的次數就會接近正常分布，其中μ＝n/2k+1，而注意，單個無偏置隨機比特的標準偏差是σ＝1/2。因而，標準動量D2的平方是如下的線性函數
D2(b0+αb1+α2b2+...)＝D2(b0)+αD2(b1)+α2D2(b2)+...＝1/4+1/4α+1/4α2+...＝n/4.
結果，利用隨機0/1比特的參數α＝1-1/n(自然壽命n)的指數平均的標準偏差是這與n元素的算數平均值的標準偏差相同。因此，每個塊的出現次數應該落入此間隔，
具有以下概率
足以，在測試隨機序列的統計特性時，塊出現的數必須大致相同。此處，「大致」的意思是提取其塊出現必須落在之間的n個採樣。常數c控制所有序列落入該間隔內的百分數(c/2＝1時得到68.3％，c/2＝2時得到95.4％，c/2＝3時得到99.7％等)。k和n的值是由操作人員預選或預定的，以致可以優化在複雜性和測試強度之間良好的折衷。注意此處獲得用於測試非隨機性的預定範圍是利用具有非常已知的隨機數源的擴展模擬來確定的。
如果指數平均累加器落在預定範圍之外，則表明該序列呈現不規則字分布。隨後，可以向用戶發出警告，以通知該序列可能不是隨機的或容易被未經授權方進行密碼分析。或者，可以設置一個門限值，以便在測試反覆失敗時通知用戶。這樣，能夠利用一組隨機序列來啟動指數平均限制，以確定生成的隨機序列是否落在可由操作人員控制設置的接受範圍之間，這樣就能確定所生成的隨機序列能否可被未經授權方預測。另外，根據計算的指數平均值在預定的接受範圍上的分布能實現隨機性測試的另一步驟。也就是說，指數平均值必須均勻地落在預定的接受範圍之內。每當計算指數平均值時，監視它落在接受範圍的哪一部分，例如接受範圍的左半部或右半部。如果落在左半部的頻率大致等於右半部，則可以利用這一參數來指示所生成的隨機數將是不可預測的。
圖3是表示按照本發明測試隨機序列的統計質量的操作步驟的流程圖。矩形單元代表計算機軟體指令，而菱形單元代表影響利用矩形單元代表的計算機指令的執行的計算機軟體指令。或者，處理和決定框代表利用功能等效電路例如數位訊號處理器電路或專用集成電路(ASIC)所執行的步驟。應該注意到，許多例行程序單元例如環路的初始化和變量以及臨時變量的使用都沒有表示。本領域技術人員將認識到，除非另有指示，所述的步驟順序僅僅是示意性的，並且在本發明的範圍內還可以改變。
最初地，在步驟100由操作人員預定或預選(等式1中)k，n和c值和重置計數器。然後，在步驟110獲得一個k比特塊，並且接著在步驟120執行指數平均計數。每當生成一個新的隨機比特，就將以前收集的比特塊向右移位，並捨棄最左邊的一比特，同時在右邊附加新的一比特。所得的塊作為二進位數用於在2k個累加器之間對累加器A進行索引。在步驟140，如果指數平均累加器的值偏離了在步驟100中選擇的接受範圍，則在步驟160中確定隨機序列中出現了不規則分布並將計數器遞增1。否則，在步驟150將計數器復位並返回到步驟110。如果步驟180中不規則分布出現的次數超過了預定門限次數，則在步驟200提供對這樣的故障的通知。或者，可以捨棄所生成的隨機數，並且可以開始生成新隨機數的整個處理程序。
上述的各個步驟可以通過將它們編程為在應用程式中包括的功能來實施，並且本領域普通的程式設計師能利用諸如C、Visual Basic、Java、Perl、C++等語言的常規編程技術來實現。在示例性實施例中，圖3中所述的方法可以(利用C程式語言)編制如下。
MS Visual C代碼
/******************************************************************\* Wordcnt.c* Wordcnt＜#random bits＞＜bit generator type＞＜bitgenerator param＞* Generates test bits* Exponential frequencies of all 4 bit words(overlapping)* Prints test statistics* Wordcnt 1e6 1 0000100110101111->4050 4156** Wordcnt 1e6 0 0.48-＞* Too large bias of 4-bit word frequencies at bit 448551(2681 8201)* 3281* 4119* 3827* 4805* 3793* 4135* 4176* 5240* 4112* 3982<!-- SIPO -->* 4203* 5055* 4564* 5013* 5189* 8201*\******************************************************************/#include＜stdio.h＞#include＜stdlib.h＞#define WDLEN 4#define WDNMB (1＜＜WDLEN)#define WDMASK (WDNMB-1)#define NA 10#define SA 6//A factor of 0.5-2 tolerance:(experimental values)#define LO10 (1＜＜(NA-WDLEN+SA-1))#define HI10 (1＜＜(NA-WDLEN+SA+1))#define MAX(A,B)((A)>(B) (A):(B))#define MIN(A,B)((A)<(B) (A):(B))typedef unsigned＿int16 uint14;//min precision to storeHI10(14bit)//enough for calculations w/o overflow//External function prototypesvoid BitGenInit(int argc,char *argv[]);unsigned int NextBit;int main(int argc,char *argv[])<!-- SIPO -->{int i,j,word=0,n=(int)atof(argv[1]);uint14 ax,a[WDNMB],amax=LO10,amin=HI10;if(argc＜4){printf("Usage:Wordcnt＜#random bits＞＜bit generator type＞＜bit generator params...＞\n");putchar(′\a′); //rings the bellexit(1);}BitGenInit(argc,argv);ax=1＜＜(NA-WDLEN+SA); //Initialize all averagevalues with ideal pastfor(i=0;i＜WDNMB;++i)a[i]=ax;for(i=1;i＜WDLEN;++i)word=(word＜＜1)+NextBit;for(i=WDLEN;i＜=n;++i){for(j=0;j＜WDNMB;++j)a[j]-=(a[j]＞＞NA);word=((word＜＜1) WDMASK)+NextBit;a[word]+=(1＜＜SA); //a[.]＜=2^13,adding 2^6gives no overflow!for(j=0;j＜WDNMB;++j){amax=MAX(a[j],amax);amin=MIN(a[j],amin);}if(amin＜LO10||amax＞HI10){printf("Too large bias of 4-bit word frequencies at bit%u(%u %u)\n",i,amin,amax);for(j=0;j＜WDNMB;++j)printf("%u\n",a[j]);exit(2);}}printf("Min Max of exponential word frequencies=%u %u\n",amin,amax);}
儘管已經示出和描述了本發明的最佳實施例，但是本領域的技術人員將理解，無需脫離本發明的真實範圍而可以進行各種各樣的變化和修改以及對其元件進行等效替換。另外，可以在不脫離核心範圍的條件下進行許多修改以適應具體情況和本發明的教導。因此，打算本發明不限於作為期望用於實現本發明的最佳模式公開的具體實施例，並且本發明應該包括落入所附的權利要求書範圍內的所有實施例。
權利要求
1.用於在生成隨機數時測試隨機性的一種方法，該方法包括以下步驟
生成二進位比特的隨機序列；
在計算每個預定塊出現的平均數時，以預定的k比特塊間隔將所述生成的隨機序列應用於指數重疊計數運算A；和
通過將所述指數重疊計數運算A的輸出與一個預定的接受範圍進行比較，確定所述生成的隨機序列是否足夠隨機。
2.按照權利要求1的方法，還包括以下步驟在所述指數重疊計數運算A的輸出落在所述預定的接受範圍之間時，確定所述生成的序列足夠隨機。
3.按照權利要求1的方法，還包括以下步驟在所述指數重疊計數運算A的輸出落在所述預定的接受範圍之外時，通知所述生成的隨機序列不夠隨機。
4.按照權利要求3的方法，還包括以下步驟在所述指數重疊計數運算A的輸出落在所述預定的接受範圍之外時，生成新的一組隨機序列。
5.按照權利要求1的方法，其中按照以下等式更新所述指數平均計數運算A
Anew＝α·Aold+b，
其中α＝1-1/n，而α落在0和1之間(0＜α＜1)，並且其中在k比特塊的二進位值出現時，b＝1，否則b＝0。
6.按照權利要求1的方法，其中每當通過從所述預定k比特塊中捨棄最左邊的比特並將新的隨機比特附加在所述預定k比特塊的右邊來生成所述新的隨機比特時，執行所述指數重疊計數運算。
7.按照權利要求5的方法，其中如下定義所述預定的接受範圍
其中選擇c以獲得期望的安全門限電平。
8.用於測試隨機數發生器的輸出的一種方法，該方法包括以下步驟
(a)使用所述隨機數發生器生成連續的二進位比特流；
(b)對於每個比特，以預定的時間間隔對預定的k比特塊執行和跟蹤重疊指數計數運算，以獲得相應的頻率值；
(c)將所有所述計算的指數平均值A與一個預定的接受範圍進行比較；和
(d)在任何一個所述計算的指數平均值落在所述預定的接受範圍之外時，確定所述生成的二進位數是非隨機的。
9.按照權利要求8的方法，還包括以下步驟
重複所述步驟(a)-(c)，直至任何所述計算的指數平均值落在所述預定的接受範圍之外。
10.按照權利要求9的方法，還包括以下步驟在所述計算的指數平均值重複落在所述預定的接受範圍之外大於一個預定次數時，通知生成了非隨機數。
11.按照權利要求9的方法，還包括以下步驟在所述計算的指數平均值重複落在所述預定的接受範圍之外大於一個門限值時，生成新的一組隨機數。
12.按照權利要求8的方法，其中所述隨機數發生器被嵌入在智慧卡內。
13.按照權利要求8的方法，其中所述指數平均值A被定義為
Anew＝α·Aold+b，
其中α＝1-1/n，而α落在0和1之間(0＜α＜1)，
如果在所述步驟(b)中k比特塊的二進位值出現，則b是包括1的值，否則b是包括0的值。
14.按照權利要求8的方法，其中每當通過從所述預定的k比特塊中捨棄最左邊的比特並將新的隨機比特附加在所述預定的k比特塊的右邊來生成新的隨機比特時，執行所述指數重疊計數運算。
15.按照權利要求13的方法，其中如下定義所述預定的接受範圍
其中選擇c以獲得期望的安全門限電平。
16.用於測試隨機數序列的隨機性的一種設備，包括
隨機數發生器單元(12)，用於生成基本上隨機的二進位比特序列；和
檢測器單元(14)，耦合到所述隨機數發生器單元(12)的輸出，用於檢測所述生成的隨機序列是否足夠隨機，
其中以預定的k比特塊間隔將所述生成的隨機序列應用於指數重疊計數運算A，以計算每個所述預定塊出現的平均數，和其中如果所述指數重疊計數運算A的輸出落在一個預定的接受範圍之外，則確定所述生成的隨機序列不夠隨機。
17.按照權利要求16的設備，還包括一個轉換器單元(16)，耦合到所述隨機數發生器單元(12)和所述檢測器單元(14)的輸出，用於在所述生成的隨機序列被確定為足夠隨機時傳送所述生成的隨機序列以便後續應用。
18.按照權利要求16的設備，還包括用於在所述指數重疊計數運算A的輸出落在所述預定的接受範圍之外時發送報警信號的裝置。
19.按照權利要求16的設備，其中根據以下等式來計算所述指數重疊計數運算A
Anew＝α·Aold+b，
其中α＝1-1/n，並且α落在0和1之間(0＜α＜1)，
如果k比特塊的二進位值出現，則b＝1，否則b＝0，並且
由操作人員初始地設置Aold。
20.按照權利要求19的設備，如下定義所述預定的接受範圍
其中選擇c以獲得期望的安全門限電平。
21.一種機器可讀媒體，在其上面存儲有代表指令序列的數據，並且所述指令序列在由處理器執行時使得該處理器
生成二進位比特的隨機數流；
對於每個比特，以預定的時間間隔對預定k比特塊計算和跟蹤指數重疊計數運算，以獲得一個相應的二進位值；並且
將所有所述計算的指數平均值A與一個預定的接受範圍進行比較，以確定所述生成的隨機數是否足夠隨機。
22.按照權利要求21的機器可讀媒體，其中在所述計算的指數平均值落在所述預定的接受範圍之外時，所述生成的二進位數不夠隨機。
23.按照權利要求21的機器可讀媒體，其中所述指數平均A被如下定義
Anew＝α·Aold+b，
其中α＝1-1/n，並且α落在0和1之間(0＜α＜1)，
如果k比特塊的二進位值出現，則b是包括1的值，否則b是包括0的值。
24.按照權利要求21的機器可讀媒體，其中每當通過從所述預定的k比特塊中捨棄最左邊的比特並將新的隨機比特附加在所述預定的k比特塊的右邊來生成新的隨機比特時，執行所述重疊計數運算。
25.按照權利要求23的機器可讀媒體，其中如下定義所述預定的接受範圍
其中選擇c以獲得期望的安全門限電平。
全文摘要
本發明是用於實時測試利用隨機數發生器生成的隨機數的方法和設備。在生成隨機數時，重疊的k比特塊一次一個地經歷指數計數運算，其中通過捨棄前一k比特塊中最左邊的比特並在其右邊附加一個新的隨機比特以形成新的k比特塊來執行指數運算，從而保持塊的大小。這一k比特塊的二進位值被用於在重疊計數運算期間執行累加器選擇。指數平均的所有輸出與一個預定的接受範圍進行比較，以確定利用隨機數發生器所生成的比特是否足夠隨機。
文檔編號G06F7/58GK1802629SQ0380433
公開日2006年7月12日 申請日期2003年2月5日 優先權日2002年2月21日
發明者L·哈爾斯 申請人:皇家飛利浦電子股份有限公司