密码算法安全测试方法

安全程序设计方法——密码算法安全测试方法黄玉划[e-mail]12-118目的了解常用密码算法及其性能，会“使用”密码算法。会“选用”密码算法进行网络安全设计。密码管理办法需要使用密码技术手段加密保护信息安全的单位和部门，必须按照国家密码管理规定，使用国家密码管理委员会指定单位研制生产的密码，不得使用自行研制的密码，也不得使用从国外引进的密码。我国发展和管理密码实行“统一领导、集中管理、定点研制、专控经营、满足使用”的20字方针。选用算法时，最好选用公开算法。公开算法已受到很多公开的研究分析和攻击验证，其强度和可靠性通常更优。选用公钥密码完成密钥加密分配和各种密码协议的工作；选用对称密码加密数据。密码算法的选用依据——密码测试与分析1依赖性(扩散与混乱)测试；2频率测试；3动向(Run)测试；4二进制矩阵秩测试5频谱(Spectral)测试6非重叠字匹配(Non-overlappingTemplateMatching)测试重叠字匹配测试7Maurer通用统计(Maurer’s“UniversalStatistical”)测试8Lempel-Ziv压缩(Lempel-ZivCompression)测试9线性复杂度(LinearComplexity)测试；10系列(Serial)测试11近似熵(ApproximateEntropy)测试12累积和(CumulativeSums)测试13随机游程(RandomExcursions)测试14随机游程变量(RandomExcursionsVariant)测试15自相关测试密码测试与分析符号：设待测序列ε={ε1，ε2，…，εn}，Φ(x)为标准正态分布函数，M表示分组长度(比特数)，「x」表示不超过x的最大整数，N=「n/M」表示分组个数，Γ(x)为Γ函数，Q(a，x)为非完备Γ函数，χ2a(K)表示显著性水平为a、自由度为K的χ2分布对应的门限值。χ2(K，x)表示自由度为K的χ2分布，等价于非完备Γ函数Q(K/2，x/2)。m表示字长(比特数)，一般要求接受水平Pva=0.01。2212()exp()xuxdu10()exp()xxttdtdttexaQaxta1)(1),(密码测试与分析（续）伪随机性是密码算法安全性的重要指标。目前已有几百个统计测试套件，用于评估密码算法的伪随机性，其原理一般是假设检验。接受水平Pv=χ2(k-1，S)。接受水平Pv=2Φ(-S)。?)1()(212knpnpfSakiiii?575829.22111||pnpnpfSnnfS|2|1nnfS3|4|1密码测试与分析——检验水平a=0.01时统计量S的门限值χ2a(N)N123456789χ2a(N)6.6359.21011.34513.27715.08616.81218.47520.09021.666N101112131415161718χ2a(N)23.20924.72526.21727.68829.14130.57832.00033.40934.805N192021222324252627χ2a(N)36.19137.56638.93240.28941.63842.98044.31445.64246.963N282930313233343536χ2a(N)48.27849.58850.89252.19153.48654.77656.06157.34258.619N373839404142434445χ2a(N)59.89261.16262.42863.69164.95066.20667.45968.71069.957N5060708090100120240χ2a(N)76.153988.3794100.425112.329124.116135.807158.95293.89注：6.635=2.5758292，即χ2a(1)与标准正态分布对应。1依赖性(扩散与混乱)测试——完备性与雪崩效应测试定义：1）二进制有限域{0,1}n表示所有n-bit向量x=（x1，…，xn）的集合。2）x(i)表示向量的第i位改变。3）汉明距离w(x)表示x中所有非0元素的个数。4）完备性。对密码算法f:{0,1}n→{0,1}m，如果每一位输出依赖于每一位输入，则称f是完备的。5）雪崩效应。当密码算法f的任意一位输入改变时，如果平均有一半的输出位改变，则称f具有雪崩效应。6）严格雪崩准则.当f的任意一位输入改变时,如果每一位输出改变的概率为0.5,则称f满足严格雪崩准则。1依赖性(扩散与混乱)测试——完备性与雪崩效应测试（续）7）依赖阵A为n×m阶阵，其元素aij表示第i位输入改变时导致第j位输出改变的向量个数。8）距离阵B为n×(m+1)阶阵，其元素bij表示第i位输入改变时导致j位输出改变的向量个数。当然，不可能测试所有的输入情况。假设随机输入样本个数为#X。9）完备度dc10）雪崩效应度da11）严格雪崩准则度dsa如果f具有良好的依赖性，必须满足完备度dc=1，雪崩效应度da≈1，严格雪崩准则度dsa≈1。)/(}0|),{(#1nmajidijc)/(|#/2|111nmmXjbdniijmjasa111|2/#1|/()nmijijdaXnm2频率测试频率测试的目的是检验算法f的输出是否服从均匀分布，分为单比特频率测试、分组频率测试和字频率测试。(1)单比特频率测试方法如下：①计算统计量S，一般要求S2.575829（与接受水平Pv0.01对应）；②计算接受水平Pv=2Φ(-S)。|2()|/Swnn2频率测试(2)分组频率测试分组频率测试步骤如下。①把待测序列ε分成N=「n/M」组：Xi（1≤i≤N），忽略多余的位数；②计算统计量S，一般要求Sχ2a(N)；③计算接受水平Pv=χ2(N，S)。21[2()]/(2)NiiSwXMM2频率测试(3)字频率测试忽略待测序列ε中多余的位数，序列共有2m个不同的字。①统计ε中每种字的个数Vi（0≤i≤2m-1）；②计算每种字的平均个数V=「n/m」/2m；③计算统计量S，一般要求Sχ2a(2m-1)；④计算接受水平Pv=χ2(2m-1，S)。2120()/miiSVVV3动向(Run)测试单比特动向测试是检测算法f的输出在0和1之间摆动的次数，其测试方法如下：①fork=1ton-1{ifεk=εk+1r(k)=0；elser(k)=1；}②计算统计量S，一般要求S2.575829；③计算接受水平Pv=2Φ(-S)。11[1()]2()[()]|1|nknrkwnwSn4二进制矩阵秩(BinaryMatrixRank)测试矩阵秩测试是检验算法f的输出子序列间的线性依赖性，其测试方法如下：①把序列ε分成N=「n/(Q×Q)」个Q×Q（Q设定为32）阶方阵，忽略多余的位数；②统计秩R=Q和R=Q-1的矩阵个数F和G；③计算统计量S，一般要求Sχ2a(2)=9.210；④计算接受水平Pv=χ2(2，S)。222(0.2888)(0.5776)(0.1336)0.28880.57760.1336FNGNNFGNNNNS5频谱(Spectral)测试频谱测试是检测算法f的输出的离散傅立叶变换(DFT)的峰值高度，其测试方法如下：①令序列X=x1，…，xn，其中xi=2εi–1；②对X进行离散傅立叶变换，即F=DFT(X)；③计算F的前一半子序列Z的模值|Z|；④计算95%的峰值高度门限值；⑤计算小于T的期望峰值数N0=0.475n；⑥统计|Z|中小于T的实际峰值数N1；⑦计算统计量S，一般要求S2.575829；⑧计算接受水平Pv=2Φ(-S)。100||/0.05SNNN3Tn6非重叠字匹配(Non-overlappingTemplateMatching)和重叠字匹配测试非重叠字匹配和重叠字匹配测试是检测算法f的输出中预定字出现的次数，两者的区别是非重叠计数和重叠计数。(1)非重叠字匹配测试方法如下。①分组长度M可设定为131072b，把序列ε分成N=「n/M」组，忽略多余的位数。②统计m-bit预定字B在各分组中出现的次数Vj（j=1，…，N）。统计方法为：如果未查找到匹配的字，则移动1-bit再查寻；如果搜索到匹配的字，则移动m-bit再搜寻。推荐字长取m=9b或m=10b。③计算均值μ和方差σ2：μ=(M-m+1)/2m，σ2=M[2-m-(2m-1)/22m]。④计算统计量S，一般要求Sχ2a(N)。⑤计算接受水平Pv=χ2(N，S)。221()/NjjSV6(非)重叠字匹配测试(2)重叠字匹配测试①分组长度M可设定为1032b，把待测序列ε分成N=「n/M」组，忽略多余的位数。②统计m-bit预定字B在各分组中出现的次数Vj（j=1，…，N）。统计方法为：不管是否搜索到匹配的字，都只移动1-bit再搜寻，即重叠计数。推荐字长取m=9b或m=10b。③计算期望概率πi需用到的临时值μ和η：μ=(M-m+1)/2m，η=μ/2。④计算期望概率πi：π0=exp(-η)，π1=ηπ0/2，π2=ηπ0(η+2)/8，π3=ηπ0(η2/6+η+1)/8，π4=ηπ0(η3/24+η2/2+3η/2+1)/16。对于M=1032和m=9有μ=2，η=1；π0=0.367879，π1=0.183940，π2=0.137955，π3=0.099634，π4=0.069935，π5=0.140657。⑤计算统计量S，一般要求Sχ2a(5)=15.086。⑥计算接受水平Pv=χ2(5，S)。520()/()iiiiSVNN7Maurer通用统计(Maurer’s“UniversalStatistical”)测试Maurer通用统计测试是检验算法f的信息压缩损耗是否严重，其测试方法如下。①把待测序列ε分成两段：初始段，由Q个M-bit的分组组成；测试段，由K个M-bit的分组组成。建议取Q=10*2M，K=1000*2M。忽略多余的位数。②对初始段，记录每种M-bit字最后出现的分组编号，如未出现，则该字编号为0，即fori=1toQTj=i，其中j为第i个字的数值。③初始化sum=0。对测试段fori=Q+1toK+Q{sum=sum+log2(i-Tj)；Tj=i；}④fn=sum/K。分组长度M(bits)对应的EV(M)、V(M)、序列长度n(bits)和Q值可参阅相关文献。⑤计算统计量S，一般要求S2.575829。⑥计算接受水平Pv=2Φ(-S)。3/0.83215()|fnEV()|/|0.7(4)|MKKMMVMSM8Lempel-Ziv压缩(Lempel-ZivCompression)测试Lempel-Ziv压缩测试是检测算法f的输出可构成不同单词的个数。统计单词个数的方法为：在序列中取连续的位数构成单词，直到构成一个前面未出现过的新单词为止。①待测序列长度n可设定为106b，要求可构成不同单词的个数W69561（与接受水平Pv0.01对应）。②计算统计量S，一般要求S-2.327；③计算接受水平Pv=Φ(S)。(69586.25)/70.448718SW9线性复杂度(LinearComplexity)测试线性复杂度测试是检测算法f作为线性反馈移位寄存器(LFSR)的长度，其测试方法如下。①把待测序列ε分成N=「n/M」组，忽略多余的位数。②采用Berlekamp-Massey算法确定每个分组的线性复杂度Li（i=1，…，N）。③计算理论平均值。④对每个分组，计算。⑤统