《乱数产生器安全性评估》由会员分享，可在线阅读，更多相关《乱数产生器安全性评估（10页珍藏版）》请在金锄头文库上搜索。
1、1,亂數產生器安全性評估 之統計測試,SEC HW7 姓名：翁玉芬 學號：89321037,2,Outline,安全性評估 Chi-Square 測試法 Kolmogorov-Smirnov (KS)測試法,3,安全性評估,好的亂數產生器 週期長 不可預測性(Unpredictable) 統計測試 Chi-Square測試法 Kolmogorov-Smirnov (KS)測試法 線性複雜度(Linear Complexity),4,Chi-Square 測試法,測試是否接近給定之機率分佈函數(pdf) pdf常假設為Uniform Distribution 利用Chi-Square 測試法求出
2、百分比Y1+Y2+Yk = n ，且 p1+p2+pk = 1 Yi為i出現之次數 pi為i出現之機率 n為測試之總數 k為所有可能發生事件之個數 為使測試更準確，n值必須足夠大 使npi至少為5 Degrees of Freedom：v = k1,5,Chi-Square 測試法 (cont.),依Chi-Square分布表查列為v、行為V，得機率p依規則判斷： 規則： a. 0 p 0.01 或 0.99 p 1 “Reject” b. 0.01 p 0.05 或 0.95 p 0.99 “Suspect” c. 0.05 p 0.1 或 0.9 p 0.95 “Almost Suspec
3、t” d. 0.1 p 0.2 或 0.8 p 0.9 “May Be Random” e. 0.2 p 0.3 或 0.7 p 0.8 “Good” f. 0.3 p 0.7 “Excellent” Chi-Square 測試最好做三次以上，每次取樣不同，這樣對於亂度的判斷較準確也較有說服力,6,Chi-Square 測試法 (cont.),Ex：同時擲兩顆骰子若共擲144次，將點數出現次數紀錄如下：無法判斷是否公正，只能說有多少機率被動手腳 根據Chi-Square :v = k 1 = 11 1 = 10 查表列為v = 10 行為V = 7得機率介於0.7 0.75 判斷為good,規
4、則： a. 0 p 0.01 或 0.99 p 1 “Reject” b. 0.01 p 0.05 或 0.95 p 0.99 “Suspect” c. 0.05 p 0.1 或 0.9 p 0.95 “Almost Suspect” d. 0.1 p 0.2 或 0.8 p 0.9 “May Be Random” e. 0.2 p 0.3 或 0.7 p 0.8 “Good” f. 0.3 p 0.7 “Excellent”,7,Kolmogorov-Smirnov (KS)測試法,Chi-Square 測試法： 應用於觀察之數字為有限種類 整體上(Global)接近給定pdf之接近程度(如
5、上例) KS 測試法： 種類無限時，如0 1 之間之時數 區域上(Local) Chi-Square與KS可能有某些程度上不同 Ex： 整體上接近給定之pdf，所以Chi-Square測試為”Random”，KS為”Reject” 整體上接近給定之pdf，所以Chi-Square測試為”Reject”，KS為”Random” 因為在某個區域上可能出現很大之偏差值 所以應合併使用,8,Kolmogorov-Smirnov (KS)測試法 (cont.),KS測試法： 首先定義F(x) (CDF, Cumulative Distributive Function)再定義Fn(x) (Empiric
6、al Distributive Function) 假設有n個任意數x1, x2, xnKS主要求出Fn(x)間之最大偏差異量，利用偏差量判斷亂度的好壞，因此定義Kn+及Kn- Kn+表Fn(x)大於F(X)之最大偏差量 Kn-表Fn(x)小於F(X)之最大偏差量 由Kn+及Kn-求出後再經由查表得出機率已確定是否通過KS測試 KS對於某一數字遠超過或不足於預測值時，會明顯地顯示出來,9,附錄： Chi-Square use in A Million Random Digits Table 2,10,部分Chi-Square 分佈表,vQ 0.995 0.99 0.975 0.95 0.9 0
7、.75 0.5 1 (-5)3.92704 (-4)1.57088 (-4)9.82069 (-3)3.93214 0.0157908 0.101531 0.454937 2 (-2)1.00251 (-2)2.01007 (-2)5.06356 0.102587 0.210720 0.575364 1.38629 3 (-2)7.17212 0.114832 0.215795 0.351846 0.584375 1.212534 2.36597 4 0.206990 0.297110 0.384419 0.710721 1.063623 1.92255 3.35670 5 0.411740
8、0.554300 0.831211 1.45476 1.61031 2.67460 4.35146 6 0.675727 0.872085 1.237347 1.63539 2.20413 3.45460 5.34812 7 0.989265 1.239043 1.68987 2.16735 2.83311 4.25485 6.34581 8 1.344419 1.646482 2.17973 2.73264 3.48954 5.07004 7.34412 9 1.734926 2.087912 2.70039 3.32511 4.16816 5.89883 8.34283 10 2.15585 2.55821 3.24697 3.94030 4.86518 6.73721 9.34182return 1return 2,
