乱数产生器安全性评估.ppt

1,亂數產生器安全性評估之統計測試,SECHW7姓名：翁玉芬學號：89321037,2,Outline,安全性評估Chi-Square測試法Kolmogorov-Smirnov(KS)測試法,3,安全性評估,好的亂數產生器週期長不可預測性(Unpredictable)統計測試Chi-Square測試法Kolmogorov-Smirnov(KS)測試法線性複雜度(LinearComplexity),4,Chi-Square測試法,測試是否接近給定之機率分佈函數(pdf)pdf常假設為UniformDistribution利用Chi-Square測試法求出百分比Y1+Y2+Yk=n，且p1+p2+pk=1Yi為i出現之次數pi為i出現之機率n為測試之總數k為所有可能發生事件之個數為使測試更準確，n值必須足夠大使npi至少為5DegreesofFreedom：v=k1,5,Chi-Square測試法(cont.),依Chi-Square分布表查列為v、行為V，得機率p依規則判斷：規則：a.0p0.01或0.99p1“Reject”b.0.01p0.05或0.95p0.99“Suspect”c.0.05p0.1或0.9p0.95“AlmostSuspect”d.0.1p0.2或0.8p0.9“MayBeRandom”e.0.2p0.3或0.7p0.8“Good”f.0.3p0.7“Excellent”Chi-Square測試最好做三次以上，每次取樣不同，這樣對於亂度的判斷較準確也較有說服力,6,Chi-Square測試法(cont.),Ex：同時擲兩顆骰子若共擲144次，將點數出現次數紀錄如下：無法判斷是否公正，只能說有多少機率被動手腳根據Chi-Square:v=k1=111=10查表列為v=10行為V=7得機率介於0.70.75判斷為good,規則：a.0p0.01或0.99p1“Reject”b.0.01p0.05或0.95p0.99“Suspect”c.0.05p0.1或0.9p0.95“AlmostSuspect”d.0.1p0.2或0.8p0.9“MayBeRandom”e.0.2p0.3或0.7p0.8“Good”f.0.3p0.7“Excellent”,7,Kolmogorov-Smirnov(KS)測試法,Chi-Square測試法：應用於觀察之數字為有限種類整體上(Global)接近給定pdf之接近程度(如上例)KS測試法：種類無限時，如01之間之時數區域上(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,CumulativeDistributiveFunction)再定義Fn(x)(EmpiricalDistributiveFunction)假設有n個任意數x1,x2,xnKS主要求出Fn(x)間之最大偏差異量，利用偏差量判斷亂度的好壞，因此定義Kn+及Kn-Kn+表Fn(x)大於F(X)之最大偏差量Kn-表Fn(x)小於F(X)之最大偏差量由Kn+及Kn-求出後再經由查表得出機率已確定是否通過KS測試KS對於某一數字遠超過或不足於預測值時，會明顯地顯示出來,9,附錄：Chi-SquareuseinAMillionRandomDigitsTable2,10,部分Chi-Square分佈表,vQ0.9950.990.9750.950.90.750.51(-5)3.92704(-4)1.57088(-4)9.82069(-3)3.932140.01579080.1015310.4549372(-2)1.00251(-2)2.01007(-2)5.063560.1025870.2107200.5753641.386293(-2)7.172120.1148320.2157950.3518460.5843751.2125342.3659740.2069900.2971100.3844190.7107211.0636231.922553.3567050.4117400.5543000.8312111.454761.610312.674604.3514660.6757270.8720851.2373471.635392.204133.454605.3481270.9892651.2390431.689872.167352.833114.254856.3458181.3444191.6464822.179732.732643.489545.070047.3441291.7349262