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

亂數產生器安全性評估之統計測試 SEC HW7 姓名：翁玉芬 學號Outline 安全性評估 Chi-Square 測試法 Kolmogorov-Smirnov (KS)測試法 安全性評估 好的亂數產生器 週期長 不可預測性(Unpredictable) 統計測試 Chi-Square測試法 Kolmogorov-Smirnov (KS)測試法 線性複雜度(Linear Complexity) Chi-Square 測試法 測試是否接近給定之機率分佈函數(pdf) pdf常假設為Uniform Distribution 利用Chi-Square 測試法求出百分比 Y1+Y2+…+Yk = n ，且 p1+p2+…+pk = 1 Yi為i出現之次數 pi為i出現之機率 n為測試之總數 k為所有可能發生事件之個數 為使測試更準確，n值必須足夠大 使npi至少為5 Degrees of Freedom：v = k－1 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 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” Chi-Square 測試最好做三次以上，每次取樣不同，這樣對於亂度的判斷較準確也較有說服力 Chi-Square 測試法　(cont.) Ex：同時擲兩顆骰子 若共擲144次，將點數出現次數紀錄如下： 無法判斷是否公正，只能說有多少機率被動手腳 根據Chi-Square : v = k – 1 = 11 – 1 = 10 查表列為v = 10 行為V = 7得機率介於0.7 ~ 0.75 判斷為good Kolmogorov-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” 因為在某個區域上可能出現很大之偏差值 所以應合併使用 Kolmogorov-Smirnov (KS)測試法 (cont.) KS測試法： 首先定義F(x) (CDF, Cumulative Distributive Function) 再定義Fn(x) (Empirical Distributive Function) 假設有n個任意數x1, x2,…, xn KS主要求出Fn(x)間之最大偏差異量，利用偏差量判斷亂度的好壞，因此定義Kn+及Kn- Kn+表Fn(x)大於F(X)之最大偏差量 Kn-表Fn(x)小於F(X)之最大偏差量 由Kn+及Kn-求出後再經由查表得出機率已確定是否通過KS測試 KS對於某一數字遠超過或不足於預測值時，會明顯地顯示出來 附錄：Chi-Square use in A Million Random DigitsTable 2 部分Chi-Square 分佈表 v\Q 0.995 0.99 0.975 0.95 0.9 0.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