密码算法安全测试方法.ppt

安全程序设计方法 密码算法安全测试方法,黄玉划 A12-118,目的,了解常用密码算法及其性能，会“使用”密码算法。 会“选用”密码算法进行网络安全设计。,密码管理办法,需要使用密码技术手段加密保护信息安全的单位和部门，必须按照国家密码管理规定，使用国家密码管理委员会指定单位研制生产的密码，不得使用自行研制的密码，也不得使用从国外引进的密码。 我国发展和管理密码实行“统一领导、集中管理、定点研制、专控经营、满足使用”的20 字方针。 选用算法时，最好选用公开算法。公开算法已受到很多公开的研究分析和攻击验证，其强度和可靠性通常更优。 选用公钥密码完成密钥加密分配和各种密码协议的工作；选用对称密码加密数据。,密码算法的选用依据 密码测试与分析,1 依赖性(扩散与混乱)测试； 2 频率测试； 3 动向(Run)测试； 4 二进制矩阵秩测试 5 频谱(Spectral)测试 6 非重叠字匹配(Non-overlapping Template Matching)测试 重叠字匹配测试 7 Maurer通用统计(Maurers “Universal Statistical”)测试 8 Lempel-Ziv压缩(Lempel-Ziv Compression)测试 9 线性复杂度(Linear Complexity)测试；10 系列(Serial)测试 11 近似熵(Approximate Entropy)测试 12 累积和(Cumulative Sums)测试 13 随机游程(Random Excursions)测试 14 随机游程变量(Random Excursions Variant)测试 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表示字长(比特数)，一般要求接受水平Pv a = 0.01。,密码测试与分析（续）,伪随机性是密码算法安全性的重要指标。 目前已有几百个统计测试套件，用于评估密码算法的伪随机性，其原理一般是假设检验。 接受水平Pv =2(k -1，S )。 接受水平Pv = 2(-S )。,密码测试与分析 检验水平a=0.01时统计量S的门限值2a(N ),注：6.635 = 2.575829 2，即2a(1)与标准正态分布对应。,1 依赖性(扩散与混乱)测试 完备性与雪崩效应测试,定义：1）二进制有限域0, 1n表示所有n-bit向量x =（x1，xn）的集合。2）x(i)表示向量的第i位改变。 3）汉明距离w(x)表示x中所有非0元素的个数。 4）完备性。对密码算法f: 0, 1n 0, 1m，如果每一位输出依赖于每一位输入，则称f是完备的。 5）雪崩效应。当密码算法f 的任意一位输入改变时，如果平均有一半的输出位改变，则称f具有雪崩效应。 6）严格雪崩准则.当f 的任意一位输入改变时,如果每一位输出改变的概率为0.5,则称f 满足严格雪崩准则。,1 依赖性(扩散与混乱)测试 完备性与雪崩效应测试（续）,7）依赖阵A为nm阶阵，其元素aij表示第i位输入改变时导致第j位输出改变的向量个数。 8）距离阵B为n(m+1)阶阵，其元素bij表示第i位输入改变时导致j位输出改变的向量个数。 当然，不可能测试所有的输入情况。假设随机输入样本个数为#X。 9）完备度dc 10）雪崩效应度da 11）严格雪崩准则度dsa 如果f具有良好的依赖性，必须满足完备度dc = 1，雪崩效应度da1，严格雪崩准则度dsa1。,2 频率测试,频率测试的目的是检验算法f 的输出是否服从均匀分布，分为单比特频率测试、分组频率测试和字频率测试。 (1) 单比特频率测试方法如下： 计算统计量S，一般要求S0.01对应）； 计算接受水平Pv = 2(-S )。,2 频率测试 (2)分组频率测试,分组频率测试步骤如下。 把待测序列分成N =n / M组：X i（1iN），忽略多余的位数； 计算统计量S，一般要求S 2a(N )； 计算接受水平Pv =2 (N，S )。,2 频率测试 (3) 字频率测试,忽略待测序列中多余的位数，序列共有2m个不同的字。 统计中每种字的个数V i（0i2m-1）； 计算每种字的平均个数V =n/m/ 2m； 计算统计量S，一般要求S 2a(2 m -1 )； 计算接受水平Pv =2(2m-1，S )。,3 动向(Run)测试,单比特动向测试是检测算法f的输出在0和1之间摆动的次数，其测试方法如下： for k=1 to n-1 ifk =k+1 r(k)=0； else r(k)=1； 计算统计量S，一般要求S 2.575829； 计算接受水平Pv = 2(-S )。,二进制矩阵秩 (Binary Matrix Rank)测试,矩阵秩测试是检验算法f的输出子序列间的线性依赖性，其测试方法如下： 把序列分成N =n / (QQ)个QQ（Q设定为32）阶方阵，忽略多余的位数； 统计秩R = Q和R = Q -1的矩阵个数F和G； 计算统计量S，一般要求S 2a(2)=9.210； 计算接受水平Pv =2 (2，S )。,5 频谱(Spectral)测试,频谱测试是检测算法f的输出的离散傅立叶变换(DFT)的峰值高度，其测试方法如下： 令序列X = x1，xn，其中x i = 2i 1； 对X进行离散傅立叶变换，即F=DFT(X)； 计算F的前一半子序列Z的模值|Z|； 计算95%的峰值高度门限值 ； 计算小于T的期望峰值数N0 = 0.475 n； 统计|Z|中小于T的实际峰值数N1； 计算统计量S，一般要求S 2.575829； 计算接受水平Pv = 2(-S )。,6 非重叠字匹配(Non-overlapping Template Matching)和重叠字匹配测试,非重叠字匹配和重叠字匹配测试是检测算法f的输出中预定字出现的次数，两者的区别是非重叠计数和重叠计数。 (1) 非重叠字匹配测试方法如下。 分组长度M可设定为131072 b，把序列分成N =n / M组，忽略多余的位数。 统计m-bit预定字B在各分组中出现的次数Vj（j = 1，N）。统计方法为：如果未查找到匹配的字，则移动1-bit再查寻；如果搜索到匹配的字，则移动m-bit再搜寻。 推荐字长取m = 9 b或m = 10 b。 计算均值和方差2：= (M-m+1)/2m， 2 = M 2 - m -(2m-1)/2 2 m 。 计算统计量S，一般要求S 2a(N )。 计算接受水平Pv =2 (N，S )。,6(非)重叠字匹配测试 (2) 重叠字匹配测试,分组长度M可设定为1032 b，把待测序列分成N =n / M组，忽略多余的位数。统计m-bit预定字B在各分组中出现的次数Vj（j = 1，N）。统计方法为：不管是否搜索到匹配的字，都只移动1-bit再搜寻，即重叠计数。推荐字长取m = 9 b或m = 10 b。计算期望概率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 )。,7 Maurer通用统计(Maurers “Universal Statistical”)测试,Maurer通用统计测试是检验算法f的信息压缩损耗是否严重，其测试方法如下。 把待测序列分成两段：初始段，由Q个M-bit的分组组成；测试段，由K个M-bit的分组组成。建议取Q =10*2M，K=1000*2M。忽略多余的位数。 对初始段，记录每种M-bit字最后出现的分组编号，如未出现，则该字编号为0，即 for i=1 to Q T j = i，其中j为第i个字的数值。 初始化sum=0。对测试段for i=Q+1 to K+Q sum=sum+log2(i -T j )；T j = i； fn = sum / K。分组长度M (bits)对应的EV(M)、V(M)、序列长度n (bits)和Q值可参阅相关文献。 计算统计量S，一般要求S2.575829。 计算接受水平Pv = 2(-S )。,8 Lempel-Ziv压缩(Lempel-Ziv Compression)测试,Lempel-Ziv压缩测试是检测算法f的输出可构成不同单词的个数。统计单词个数的方法为：在序列中取连续的位数构成单词，直到构成一个前面未出现过的新单词为止。 待测序列长度n 可设定为106 b，要求可构成不同单词的个数W 69561（与接受水平Pv 0.01对应）。 计算统计量S，一般要求S -2.327； 计算接受水平Pv =(S )。,9 线性复杂度(Linear Complexity)测试,线性复杂度测试是检测算法f作为线性反馈移位寄存器(LFSR)的长度，其测试方法如下。 把待测序列分成N =n / M组，忽略多余的位数。 采用Berlekamp-Massey算法确定每个分组的线性复杂度Li（i = 1，N）。 计算理论平均值 。 对每个分组，计算 。 统计Ti的分布个数Vj：V0 = VTi -2.5， V1 = V-2.52.5。 计算统计量S，其中0 = 1/96，1 = 0.03125， 2 =0.125，3 = 0.5，4 = 0.25，5 = 0.0625， 6 = 1/48。一般要求S 2a(6 ) = 16.812。 计算接受水平Pv =2 (6，S )。,10 系列(Serial)测试,系列测试是同时检测算法f的输出中3种长度(m，m-1，m-2)的重叠字出现的频率，相当于重叠字频率测试，有两个统计量S和S*，其测试方法如下。 把前m-1比特追加到待测序列后面。 统计每种m-bit字的个数Vim（i = 0，2m-1），每种m-1比特字的个数V i，m-1（i = 0，2m-1-1），每种m-2比特字的个数V i，m-2（i = 0，2 m 2 -1）。统计方法为：各计数n次，每次移动1-bit进行计数，即重叠计数。 计算 计算统计量S =m-m-1，S*=m-2m-1+m-2，要求S 2a(2 m - 1)，S*2a(2 m 2)。 计算接受水平Pv =2 (2 m - 1 ，S )，计算接受水平P2 =2 (2 m 2 ，S*)。,11 近似熵(Approximate Entropy)测试,近似熵测试是比较算法f的输出中两个相邻长度(m，m+1)的重叠字出现的频率，其测试方法如下。 把前m-bit追加到待测序列后面。 统计每种m-bit字的个数Vim（i = 0，2m-1），每种m+1比特字的个数V i，m+1（i = 0，2m+1-1）。统计方法为：各计数n次，每次移动1-bit进行计数，即重叠计数。 对每种字，计算im = Vim / n次， i，m+1 = V i，m+1 / n。 计算 计算统计量S = 2n(ln2 -m+m+1) ， 一般要求S 2a (2 m )。 计算接受水平Pv =2 (2m，S )。,12 累积和(Cumulative Sums)测试,累积和测试是检测算法f的输出中累积和随机步的最大游程，需要计算模式0(正向)和模式1(反向)的累积和，其测试方法如下： 令序列X = x1，xn，其中x i = 2i 1； 计算各个连续子序列的累积和 （正向）， （反向）； 计算两个统计量S = maxk ，其中1kn；计算K =(n/S-1)/4； 计算两个接受水平,13随机游程(Random Excursions)测试,随机游程测试是检测算法f的累积和随机步中特定状态在各轮中出现的次数，其测试方法如下。 令序列X = x1，xn，其中x i = 2i 1 。 计算各个连续子序列的累积和 其中1kn；令0 =n+1 = 0。 统计k（1kn+1）中0的个数J，以k = 0（1kn）为分界点把k 分为J轮。 对8种非0状态x=14,统计它们在各轮中出现的次数。 对8种状态，统计它们在各轮中出现次数为k的个数Vkx，其中k5的个数归入V5x中。 对8种状态，分别计算统计量 要求S 2a(5) = 15.086。其中0x = 1-1/|2x|；kx = (1-1/|2x|)k 1/(4x2 )，1k4；5x = (1-1/|2x|)4 /|2x|。 计算接受水平Pv =2 (5，S )。,14 随机游程变量(Random Excursions Variant)测试,随机游程变量测试是检测算法f的累积和随机步中特定状态出现的次数，其测试方法如下。 令序列X = x1，xn，其中x i = 2i 1 。 计算各个连续子序列的累积和 其中1kn；令0 =n+1 = 0。 统计k （1kn+1）中0的个数J0。 对18种非0状态x = 19，统计它们在J0轮中出现的总次数Jx。 对18种状态,分别计算统计量 一般要求S 2.575829。 对18种状态，分别计算接受水平Pv = 2(-S )。,15 自相关测试,自相关测试的目的是考察非循环移位之后的序列与原序列之间的相关性。d为一个固定的正整数，它满足1dn/2。长度为n的二进制序列X = x0 , x1 , x2 , , xn 1，其中的一个二进制位表示为xi，与它相距d位的二进制位表示为xi+d，自相关函数 统计量 如果n d10，S近似服从标准正态分布。,作业,大作业：综合运用所学知识，设计、开发和实现一个文件加密软件系统。 上机作业：常用密码算法编程实现，并测试其速度及部分伪随机性指标。 1 分组密码算法：AES、SHACAL2、MISTY1、Camellia、RC6。工作模式采用CBC+PXOR(或CRC-32)、ECB(或CTR或OFB)+CBC-MAC 3 流密码算法和PRNG(与CBC-MAC结合)：RC4、SEAL 4 CRC-32 5 单向Hash函数：SHA1、SHA256、Whirlpool、RIPEMD160、SHA384、SHA512,习题,1、网络系统安全机制的简单模型一般可分为两步： (1) (身份)认证与密钥交换和(2)保密通信。 2、身份认证可分为两类：(1)对称认证（即常用的口令认证）；(2)非对称认证（基于数字签名算法）。 、(1)流密码算法、分组密码算法和公钥密码算法用于加解密(保密)；(2) 分组密码算法的认证模式、单向Hash函数和数