【文档说明】乱数产生器安全性评估.pptx,共(10)页,70.117 KB,由精品优选上传
转载请保留链接:https://www.ichengzhen.cn/view-288642.html
以下为本文档部分文字说明:
亂數產生器安全性評估之統計測試SECHW7姓名:翁玉芬學號:893210371Outline⚫安全性評估⚫Chi-Square測試法⚫Kolmogorov-Smirnov(KS)測試法2安全性評估⚫好的亂數產生器週期長不可預測性
(Unpredictable)⚫統計測試Chi-Square測試法Kolmogorov-Smirnov(KS)測試法⚫線性複雜度(LinearComplexity)3Chi-Square測試法⚫測試是否接近給定之機率分佈函數(pdf)pd
f常假設為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−=4Chi-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→“MayBeRa
ndom”•e.0.2p0.3或0.7p0.8→“Good”•f.0.3p0.7→“Excellent”Chi-Square測試最好做三次以上,每次取樣不同,這樣對於亂度的判斷較準確也較有說服力5Chi-Square測試法(cont.)⚫Ex:同時擲兩顆
骰子若共擲144次,將點數出現次數紀錄如下:無法判斷是否公正,只能說有多少機率被動手腳根據Chi-Square:⚫⚫v=k–1=11–1=10⚫查表列為v=10行為V=7得機率介於0.7~0.7
5⚫判斷為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)2345678910
1112觀察次數(Yi)241012222921151496期望次數(npi)481216202420161284()iiikinpnpYV21−=規則:a.0p0.01或0.99p1→“Reject”b.0.01p0.05或0.95p0.99→“Suspe
ct”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”6Kolmogorov-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”⚫
因為在某個區域上可能出現很大之偏差值所以應合併使用7Kolmogorov-Smirnov(KS)測試法(cont.)⚫KS測試法:首先定義F(x)(CDF,CumulativeDistributiveFunction)再定義Fn(x)(EmpiricalDistributi
veFunction)⚫假設有n個任意數x1,x2,…,xnKS主要求出Fn(x)間之最大偏差異量,利用偏差量判斷亂度的好壞,因此定義Kn+及Kn-⚫Kn+表Fn(x)大於F(X)之最大偏差量⚫Kn-表Fn(x)小於F(X)之最大偏差量由Kn+及Kn-求出後再經由
查表得出機率已確定是否通過KS測試⚫KS對於某一數字遠超過或不足於預測值時,會明顯地顯示出來−−==xdxxpdxxpxF1)()()(nxxxxxFnn)之個數小於()(21=8附錄:Chi-SquareuseinAMillionRandomDigi
tsTable29部分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.45
49372(-2)1.00251(-2)2.01007(-2)5.063560.1025870.2107200.5753641.386293(-2)7.172120.1148320.2157950.3518460.5
843751.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.0700
47.3441291.7349262.0879122.700393.325114.168165.898838.34283102.155852.558213.246973.940304.865186.737219.34182return1return
2−−−=2122)1(22)]2(2[)|(xvtvdttevTvxQ10