乱数产生器安全性评估

1亂數產生器安全性評估之統計測試SECHW7姓名：翁玉芬學號：893210372Outline安全性評估Chi-Square測試法Kolmogorov-Smirnov(KS)測試法3安全性評估好的亂數產生器週期長不可預測性(Unpredictable)統計測試Chi-Square測試法Kolmogorov-Smirnov(KS)測試法線性複雜度(LinearComplexity)4Chi-Square測試法測試是否接近給定之機率分佈函數(pdf)pdf常假設為UniformDistribution利用Chi-Square測試法求出百分比Y1+Y2+…+Yk=n，且p1+p2+…+pk=1•Yi為i出現之次數•pi為i出現之機率•n為測試之總數•k為所有可能發生事件之個數為使測試更準確，n值必須足夠大•使npi至少為5DegreesofFreedom：v=k－1iiikinpnpYV215Chi-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“AlmostSuspect”•d.0.1p0.2或0.8p0.9“MayBeRandom”•e.0.2p0.3或0.7p0.8“Good”•f.0.3p0.7“Excellent”Chi-Square測試最好做三次以上，每次取樣不同，這樣對於亂度的判斷較準確也較有說服力6Chi-Square測試法(cont.)Ex：同時擲兩顆骰子若共擲144次，將點數出現次數紀錄如下：無法判斷是否公正，只能說有多少機率被動手腳根據Chi-Square:v=k–1=11–1=10查表列為v=10行為V=7得機率介於0.7~0.75判斷為good74)46(8)89(12)1210(8)84(4)42(22222V總點數(i)23456789101112機率(Pi)1/362/363/364/365/366/365/364/363/362/361/36點數(i)23456789101112觀察次數(Yi)241012222921151496期望次數(npi)481216202420161284iiikinpnpYV21規則：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“AlmostSuspect”d.0.1p0.2或0.8p0.9“MayBeRandom”e.0.2p0.3或0.7p0.8“Good”f.0.3p0.7“Excellent”7Kolmogorov-Smirnov(KS)測試法Chi-Square測試法：應用於觀察之數字為有限種類整體上(Global)接近給定pdf之接近程度(如上例)KS測試法：種類無限時，如0~1之間之時數區域上(Local)Chi-Square與KS可能有某些程度上不同Ex：整體上接近給定之pdf，所以Chi-Square測試為”Random”，KS為”Reject”整體上接近給定之pdf，所以Chi-Square測試為”Reject”，KS為”Random”因為在某個區域上可能出現很大之偏差值所以應合併使用8Kolmogorov-Smirnov(KS)測試法(cont.)KS測試法：首先定義F(x)(CDF,CumulativeDistributiveFunction)再定義Fn(x)(EmpiricalDistributiveFunction)假設有n個任意數x1,x2,…,xnKS主要求出Fn(x)間之最大偏差異量，利用偏差量判斷亂度的好壞，因此定義Kn+及Kn-Kn+表Fn(x)大於F(X)之最大偏差量Kn-表Fn(x)小於F(X)之最大偏差量由Kn+及Kn-求出後再經由查表得出機率已確定是否通過KS測試KS對於某一數字遠超過或不足於預測值時，會明顯地顯示出來xdxxpdxxpxF1)()()(nxxxxxFnn)之個數小於()(219附錄：Chi-SquareuseinAMillionRandomDigitsTable210部分Chi-Square分佈表v\Q0.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.0879122.700393.325114.168165.898838.34283102.155852.558213.246973.940304.865186.737219.34182return1return22122)1(22)]2(2[)|(xvtvdttevTvxQ