第二章信息加密技术(4) 网络安全 NETWORK SECURITY ·本节学习目标： ·掌握常用密码分析相关知识 >对称密码分析：DES >非对称密码分析：RSA 2
2 第二章 信息加密技术（4） • 本节学习目标： ▪ 掌握常用密码分析相关知识 ➢对称密码分析：DES ➢非对称密码分析：RSA
基本概念 网络安全 NETWORK SECURITY Kerckhoff假设 ·通常假定密码分析者或敌手知道所使用的密码系统 ·攻击类型（攻击强度递增） ·唯密文攻击：密码分析者有一个或多个密文 ·已知明文攻击：密码分析者有一些明文以及相应的密文 ·选择明文攻击：密码分析者有机会使用密码机，因此可选择 一些明文，并产生密文 ·选择密文攻击：密码分析者有机会使用密码机，因此可选择 一些密文，并产生明文 3
3 基本概念 • Kerckhoff假设 ▪ 通常假定密码分析者或敌手知道所使用的密码系统 • 攻击类型（攻击强度递增） ▪ 唯密文攻击：密码分析者有一个或多个密文 ▪ 已知明文攻击：密码分析者有一些明文以及相应的密文 ▪ 选择明文攻击：密码分析者有机会使用密码机，因此可选择 一些明文，并产生密文 ▪ 选择密文攻击：密码分析者有机会使用密码机，因此可选择 一些密文，并产生明文
分组密码的分析方法 网络安全 NETWORK SECURITY 。典型的攻击方法 ·强力攻击方法 ·差分密码分析 ·线性密码分析 ·差分-线性密码分析 4
4 分组密码的分析方法 • 典型的攻击方法 ▪ 强力攻击方法 ▪ 差分密码分析 ▪ 线性密码分析 ▪ 差分-线性密码分析
强力攻击 网络安全 NETWORK SECURITY 强力攻击可用于任何分组密码，攻击复杂度只依赖于分组 长度和密码长度 ·穷尽密钥搜索攻击： ·攻击者试用密钥空间中的所有密钥解密一个或多个密文，直 至得到一个或多个有意义的明文。 ·字典攻击： ·攻击者搜集明密文对，编排成字典，遇到密文时查找字典获 得明文 5
5 强力攻击 强力攻击可用于任何分组密码，攻击复杂度只依赖于分组 长度和密码长度 • 穷尽密钥搜索攻击： ▪ 攻击者试用密钥空间中的所有密钥解密一个或多个密文，直 至得到一个或多个有意义的明文。 • 字典攻击： ▪ 攻击者搜集明密文对，编排成字典，遇到密文时查找字典获 得明文
强力攻击 网络安全 NETWORK SECURITY ·查表攻击： ·采用选择明文攻击，对给定明文，用所有可能的密钥，计算 密文，并建立密钥和密文的表，通过密文查表获得密钥 ·时间-存储权衡攻击： ·是一种选择明文攻击，由穷尽密钥搜索攻击和查表攻击两种 方法混合而成，在选择明文攻击中以时间换空间，比穷尽密 钥搜索攻击时间复杂度小，比查表攻击空间复杂度小 6
6 强力攻击 • 查表攻击： ▪ 采用选择明文攻击，对给定明文，用所有可能的密钥，计算 密文，并建立密钥和密文的表，通过密文查表获得密钥 • 时间-存储权衡攻击： ▪ 是一种选择明文攻击，由穷尽密钥搜索攻击和查表攻击两种 方法混合而成，在选择明文攻击中以时间换空间，比穷尽密 钥搜索攻击时间复杂度小，比查表攻击空间复杂度小
差分密码分析 网络安全 NETWORK SECURITY 1.差分密码分析基本原理 差分密码分析是已知的攻击跌代密码（所谓跌代 密码就是以跌代一个简单的轮函数为基础的密码， 即通过选择某个较简单的密码变换，在密钥控制 下以跌代方式多次利用它进行加密变换)最有效 的方法之一，其基本思想是：通过分析明文对的 差值对密文对的差值的影响来恢复某些密钥比特
7 差分密码分析 1. 差分密码分析基本原理 差分密码分析是已知的攻击跌代密码（所谓跌代 密码就是以跌代一个简单的轮函数为基础的密码， 即通过选择某个较简单的密码变换，在密钥控制 下以跌代方式多次利用它进行加密变换）最有效 的方法之一，其基本思想是：通过分析明文对的 差值对密文对的差值的影响来恢复某些密钥比特
差分密码分析 网络安全 NETWORK SECURITY 对分组长度为n的轮跌代密码，设Yo和Y,*是明文对，Y:和Y*(1≤isr)是 第轮的输出，第i+1轮的输入，第轮的子密钥为K,轮函数为F,即 Yi=F(Yi-1,Ki) ● 定义1差分：△Y=Y⑧Y*-1,其中⑧表示n比特串集上的一个特定群运算， Y*-1表示Y*在此群中的逆元 研究结果表明，对于Y=F(Y-1K)和Y*=F(Y-1*,K),若三元组(AY-1 Y,Y*)的一个或多个值是已知的，则确定子密钥K是容易的。从而，若 密文对已知，并且最后一轮的输入对的差分能够得到，则一般来说，确 定最后一轮的子密钥或其一部分是可行的。在差分密码分析中，通过选 择具有特定差分值ao的明文对(Yo,Yo),使得最后一轮的输入差分△Y1 以很高的概率取特定值a1来达到这一点 8
8 差分密码分析 对分组长度为n的r轮跌代密码，设Y0和Y0 *是明文对，Yi和Yi *(1ir)是 第i轮的输出，第i+1轮的输入，第i轮的子密钥为Ki，轮函数为F，即 Yi=F(Yi-1,Ki) • 定义1 差分：Yi=YiYi *-1，其中表示n比特串集上的一个特定群运算， Yi *-1表示Yi *在此群中的逆元 • 研究结果表明，对于Yi=F(Yi-1,Ki)和Yi *=F(Yi-1 *,Ki)，若三元组(Yi-1, Yi , Yi *)的一个或多个值是已知的，则确定子密钥Ki是容易的。从而，若 密文对已知，并且最后一轮的输入对的差分能够得到，则一般来说，确 定最后一轮的子密钥或其一部分是可行的。在差分密码分析中，通过选 择具有特定差分值a0的明文对(Y0, Y0 *)，使得最后一轮的输入差分Yr-1 以很高的概率取特定值ar-1来达到这一点
差分密码分析 网络安全 NETWORK SECURITY 定义2r-轮特征2是一个差分序列aoa1vyar,其中a是Y:和 Y*(0≤isr)的差分。r-轮特征2=aova1vva的概率是指在明文 Y,和子密钥Kv,K独立、均匀随机时，明文对Y和Y,*的差分 为ao的条件下，Y:和Y**(0sisr)的差分为a的概率 定义3如果r-轮特征2=aoa1a满足条件：Yo和Yo*的差分 为ao.第i轮输出Y和Y*的差分为a(I≤isr),则称明文对Y,和 Y,*为特征2的一个正确对，否则称为特征2的错误对 定义421=aova1.vam和22=bob1,b分别是m轮和l轮特征， 如果am=bo,则21和22可以串联为一个m+1的轮特征 23=a0a1 ...amr borb1b1923称为21和22的串联
9 差分密码分析 • 定义2 r-轮特征是一个差分序列a0 ,a1 ,…,ar，其中ai是Yi和 Yi *(0ir)的差分。 r-轮特征=a0 ,a1 ,…,ar的概率是指在明文 Y0和子密钥K1 ,…,Kr独立、均匀随机时，明文对Y0和Y0 *的差分 为a0的条件下，Yi和Yi * *(0ir)的差分为ai的概率 • 定义3 如果 r-轮特征=a0 ,a1 ,…,ar满足条件： Y0和Y0 *的差分 为a0，第i轮输出Yi和Yi *的差分为ai(1ir)，则称明文对Y0和 Y0 *为特征的一个正确对，否则称为特征的错误对 • 定义4 1=a0 ,a1 ,…,am和2=b0 ,b1 ,…,bl分别是m轮和l轮特征， 如果am=b0，则1和2可以串联为一个m+l的轮特征 3=a0 ,a1 ,…,am, b0 ,b1 ,…,bl。3称为1和2的串联
差分密码分析 网络安全 NETWORK SECURITY 。定义5在r-轮特征2=aova1v.,a中，定义pP=P(△F(Y)=a;| △Y=a-1),即pP表示在输入差分为a1的条件下，轮函数F的输 出差分为a的概率 注意：由于轮函数F与子密钥有关，所以P是对所有可能的子 密钥而言的。对某些密码体制，选取合适的群运算⑧能保证对 所有可能的子密钥值，此概率是常值。 实际中，r-轮特征2=aova1a的概率可用IpP来近似替代， 因此r-轮特征可以看作个单轮特征的串联，它的概率是r个单 轮特征概率的乘积。 10
10 差分密码分析 • 定义5 在r-轮特征=a0 ,a1 ,…,ar中，定义pi =P(F(Y)=ai | Y=ai-1)，即pi 表示在输入差分为ai-1的条件下，轮函数F的输 出差分为ai的概率 • 注意：由于轮函数F与子密钥有关，所以pi 是对所有可能的子 密钥而言的。对某些密码体制，选取合适的群运算能保证对 所有可能的子密钥值，此概率是常值。 • 实际中，r-轮特征=a0 ,a1 ,…,ar的概率可用pi 来近似替代， 因此r-轮特征可以看作r个单轮特征的串联，它的概率是r个单 轮特征概率的乘积
差分密码分析 网络安全 NETWORK SECURITY R轮迭代密码的差分攻击算法 第1步：找出一个(r-1)轮特征2=aoa1va-1,使得它的概率达到最大 或几乎最大 第2步：均匀随机地选择明文Y并计算Y,*,使得Y和Y,*的差分为ao, 找出Yo和Y,*在实际密钥加密下所得的密文Y和Y*。若最后一轮的子密 钥K(或K的部分比特)有2m个可能值K,(1≤j≤2m),设置相应的2m个计 数器△(1js2m)；用每个K解密密文Y和Y*,得到Y-1和Yr-1*,如果 Y-1和Y-1*的差分是ar-1,则给相应的计数器A加1。 第3步：重复第2步，直到一个或几个计数器的值明显高于其他计数器的 值，输出它们所对应的子密钥（或部分比特） 11
11 差分密码分析 • R轮迭代密码的差分攻击算法 • 第1步：找出一个(r-1)轮特征=a0 ,a1 ,…,ar-1，使得它的概率达到最大 或几乎最大 • 第2步：均匀随机地选择明文Y0并计算Y0 *，使得Y0和Y0 *的差分为a0， 找出Y0和Y0 *在实际密钥加密下所得的密文Yr和Yr *。若最后一轮的子密 钥Kr(或Kr的部分比特)有2m个可能值Kr j(1j2m)，设置相应的2m个计 数器j(1j2m)；用每个Kr j解密密文Yr和Yr *，得到Yr-1和Yr-1 *，如果 Yr-1和Yr-1 *的差分是ar-1，则给相应的计数器j加1。 • 第3步：重复第2步，直到一个或几个计数器的值明显高于其他计数器的 值，输出它们所对应的子密钥（或部分比特）