《1.总述：密码的分析学.pdf》由会员分享，可在线阅读，更多相关《1.总述：密码的分析学.pdf（11页珍藏版）》请在金锄头文库上搜索。
1、1 密码分析学密码分析学 教教师师： 袁袁 征征教教师师： 袁袁 征征 主要内容主要内容 一、对敌手攻击能力的基本假设 二、密码分析方法的分类 三、穷举攻击 四、中间相遇攻击 一、对敌手攻击能力的基本假设 二、密码分析方法的分类 三、穷举攻击 四、中间相遇攻击 五五线性密码分析线性密码分析五五、线性密码分析线性密码分析 六、差分分析 七、不可能差分分析 八、代数分析 九、相关密钥攻击 十、旁道攻击 六、差分分析 七、不可能差分分析 八、代数分析 九、相关密钥攻击 十、旁道攻击 对敌手攻击能力的基本假设对敌手攻击能力的基本假设一、一、对敌手攻击能力的基本假设对敌手攻击能力的基本假设 一、对敌手攻
2、击能力的基本假设一、对敌手攻击能力的基本假设 KerckhoffsKerckhoffs假设:假设: 假设敌手知道假设敌手知道除密钥之外除密钥之外的所有知识的所有知识 -思想：思想：假设敌手具有最强的攻击能力！假设敌手具有最强的攻击能力！ -假设敌手知道假设敌手知道除密钥之外除密钥之外的所有知识的所有知识! -即要求密码算法应当使得： ! -即要求密码算法应当使得： 一切的秘密蕴于密钥之中!一切的秘密蕴于密钥之中! 假设敌手知道假设敌手知道: (1) 所使用的加密算法所使用的加密算法; 1. 对敌手攻击能力的Kerckhoffs假设：对敌手攻击能力的Kerckhoffs假设： (2) 知道明文的
3、概率分布规律知道明文的概率分布规律 ; (3) 知道密钥的概率分布规律知道密钥的概率分布规律 ; (4) 知道所有可能的破译方法知道所有可能的破译方法 ! 假设条件如此强的原因假设条件如此强的原因: (4) 知道所有可能的破译方法知道所有可能的破译方法 ! (1) 我们不能保证敌手得不到这些信息我们不能保证敌手得不到这些信息!- 绝对不能赌绝对不能赌! (2) 如果在这么优越的条件下仍不可破译，说明密码 算法在实际中将会更加安全 如果在这么优越的条件下仍不可破译，说明密码 算法在实际中将会更加安全! (3) 对于实现性能相同的两个密码，我们一定选择强 度高的。 对于实现性能相同的两个密码，我们
4、一定选择强 度高的。 还可假设：还可假设： 敌手可以拿到我们的加密装置，可以敌手可以拿到我们的加密装置，可以 测试加密过程的各种能量消耗测试加密过程的各种能量消耗、时间延迟时间延迟、测试加密过程的各种能量消耗测试加密过程的各种能量消耗、时间延迟时间延迟、 信号辐射等，甚至可以主动设置故障、弱 化加密算法等。 信号辐射等，甚至可以主动设置故障、弱 化加密算法等。 -以便实施旁道攻击。以便实施旁道攻击。 2 敌手攻击的目标：敌手攻击的目标： 对于加密算法：对于加密算法： （1）求出密文对应的明文；）求出密文对应的明文； （2）求出密钥或等效密钥求出密钥或等效密钥，进而求出密进而求出密（2）求出密钥
5、或等效密钥求出密钥或等效密钥，进而求出密进而求出密 文对应的明文。文对应的明文。 对于认证算法：对于认证算法： （1）伪造一个明文的认证码； （ ）伪造一个明文的认证码； （2）求出认证密钥，进而伪造明文的认 证码。 ）求出认证密钥，进而伪造明文的认 证码。 二二密码分析方法的分类密码分析方法的分类二二、密码分析方法的分类密码分析方法的分类 分组密码的分析方法分为两类： （ 分组密码的分析方法分为两类： （1）基于数学理论的分析方法）基于数学理论的分析方法 差分分析差分分析、线性分析线性分析、积分分析积分分析、插值攻插值攻差分分析差分分析、线性分析线性分析、积分分析积分分析、插值攻插值攻 击、
6、代数攻击 （ 击、代数攻击 （2）基于物理实现的分析方法 计时攻击、能量攻击、电磁攻击、故障攻 击、缓存攻击 ）基于物理实现的分析方法 计时攻击、能量攻击、电磁攻击、故障攻 击、缓存攻击 二、密码分析方法的分类二、密码分析方法的分类 （1）唯密文攻击唯密文攻击： 敌手除加密算法、明文和密钥的概率分布外，还 知道很多由同一个密钥加密的密文。 敌手除加密算法、明文和密钥的概率分布外，还 知道很多由同一个密钥加密的密文。 （2）已知明文攻击已知明文攻击： 分类方法：分类方法：按敌手可利用按敌手可利用知识的类别知识的类别分类分类 （3）选择明文选择明文(密文密文)攻击攻击： 敌手除具备已知明文攻击的条
7、件外，还可任意选 择对他有利的明文 敌手除具备已知明文攻击的条件外，还可任意选 择对他有利的明文(密文密文) ,并能得到相应的密文并能得到相应的密文 (明文明文) （2）已知明文攻击已知明文攻击： 敌手除具备唯密文攻击的条件外，还知道许多密 文对应的明文。 敌手除具备唯密文攻击的条件外，还知道许多密 文对应的明文。 二、密码分析方法的分类二、密码分析方法的分类 （4）相关密钥攻击相关密钥攻击： 敌手可以针对若干个有一定关联的密钥，任意选 择对他有利的明文 敌手可以针对若干个有一定关联的密钥，任意选 择对他有利的明文(密文密文) ,并能得到相应的密文并能得到相应的密文 (明文明文) 例如：例如：
8、 可以假设： 我们知道用密钥 可以假设： 我们知道用密钥kIV1, kIV2,., kIVr加密任意 明文的加密结果。这里 加密任意 明文的加密结果。这里IV1, IV2,., IVr都是已知的、甚 至攻击者可以自主选择。 都是已知的、甚 至攻击者可以自主选择。 按攻击方法分类按攻击方法分类 穷举攻击穷举攻击 中间相遇攻击中间相遇攻击 线性密码分析线性密码分析 差分分析差分分析 不可能差分分析不可能差分分析 代数分析代数分析-代数方程求解代数方程求解 相关密钥攻击相关密钥攻击 旁道攻击旁道攻击 3 密钥求解的原理密钥求解的原理 -真假密钥呈现不同的规律真假密钥呈现不同的规律- 正确密钥正确密钥
9、错误密钥错误密钥 区分器区分器 规律规律1 区分器区分器 规律规律2 规律不一样规律不一样 三三穷举攻击穷举攻击三三、穷举攻击穷举攻击 三、穷举攻击三、穷举攻击 密钥的变化量太少会怎样? -如果对每个可能的密钥都逐个测试，则 一定可以碰到正确的密钥，利用它就可脱密! 这就是穷举攻击方法！ 穷举攻击就是逐一利用每个可能的密钥对密 密钥的变化量太少会怎样? -如果对每个可能的密钥都逐个测试，则 一定可以碰到正确的密钥，利用它就可脱密! 这就是穷举攻击方法！ 穷举攻击就是逐一利用每个可能的密钥对密 文进行文进行脱密测试脱密测试， 何为最合理？ 与攻击者掌握的明文的信息最吻合！ ， 何为最合理？ 与攻
10、击者掌握的明文的信息最吻合！ 如何区分真假密钥？ 并将脱密结果并将脱密结果最合理最合理的那个密钥判 断为正确密钥。 的那个密钥判 断为正确密钥。 三、穷举攻击三、穷举攻击 穷举攻击是最基本的攻击方法穷举攻击是最基本的攻击方法。穷举攻击是最基本的攻击方法穷举攻击是最基本的攻击方法。 许多攻击方法本质上都有穷举攻击的影 子。 许多攻击方法本质上都有穷举攻击的影 子。 三、穷举攻击三、穷举攻击 例:例: 假设明文每个16位字的最高比特都是0， 并假设加密算法采用的是AES-192，如何在获得足够 长的密文的条件下，求出对应的明文？ 假设明文每个16位字的最高比特都是0， 并假设加密算法采用的是AES
11、-192，如何在获得足够 长的密文的条件下，求出对应的明文？ 密钥长度是192比特 三、穷举攻击三、穷举攻击 攻击方案攻击方案: for key=0 to key=2192-1, do for i=1 to i=N do (1) 脱密第脱密第i个密文分组个密文分组,得到明文分组得到明文分组m； (2) 检查检查的的8个个16位字的最高位是否全是位字的最高位是否全是0 穷举所有可能的密钥 利用所有可能的明文 (2) 检查检查m的的8个个16位字的最高位是否全是位字的最高位是否全是0. 若不全是若不全是0，则，则goto L; 输出输出key; break; L: ; 只要有一个明密文对不上，就
12、判断实验密钥不是正确密钥 只输出一个密钥(单候选密钥方案）。 若需输出所有候选密钥，则去掉该步骤. 4 三、穷举攻击三、穷举攻击 攻击方案攻击方案: for key=0 to key=2192-1, do for i=1 to i=N do (1) 脱密第脱密第i个密文分组个密文分组,得到明文分组得到明文分组P； (2) 检查检查P的的8个个16位字的最高位是否全是位字的最高位是否全是0(2) 检查检查P的的8个个16位字的最高位是否全是位字的最高位是否全是0. 若不全是若不全是0，则，则goto L; 输出输出key; break; L: ; 时间复杂性：时间复杂性：假设第假设第i个被测密钥
13、是正 确密钥的概率是 个被测密钥是正 确密钥的概率是pi，则平均测试，则平均测试e个密 钥才能找到正确密钥。这里 个密 钥才能找到正确密钥。这里 192 2 1 ( ) i i eE iip = = 三、穷举攻击三、穷举攻击 攻击方案攻击方案: for key=0 to key=2192-1, do for i=1 to i=N do (1) 脱密第脱密第i个密文分组个密文分组,得到明文分组得到明文分组P； (2) 检查检查P的的8个个16位字的最高位是否全是位字的最高位是否全是0(2) 检查检查P的的8个个16位字的最高位是否全是位字的最高位是否全是0. 若不全是若不全是0，则，则goto
14、L; 数据复杂性：数据复杂性：一个错误密钥能通过一个错误密钥能通过N个 明文分组检测的概率是 个 明文分组检测的概率是2-8N，故，故2192-1 个错误密钥能通过个错误密钥能通过N个明文分组检测的 个数平均为 个明文分组检测的 个数平均为(2192-1)2-8N 2192-8N 192/8=24N 输出输出key; break; L: ; 三、穷举攻击三、穷举攻击 攻击方案攻击方案: for key=0 to key=2192-1, do for i=1 to i=N do (1) 脱密第脱密第i个密文分组个密文分组,得到明文分组得到明文分组P； (2) 检查检查P的的8个个16位字的最高位
15、是否全是位字的最高位是否全是0(2) 检查检查P的的8个个16位字的最高位是否全是位字的最高位是否全是0. 若不全是若不全是0，则，则goto L; 输出输出key; break; L: ; 成功率：成功率：（1）单候选密钥方案 （ ）单候选密钥方案 （2）多候选密钥方案）多候选密钥方案 p=1,候选密钥量为候选密钥量为 192 8 192 8 1 12 12 N N p = + 192 8 12 N + 可能密钥总数的安全界限：可能密钥总数的安全界限： 要想能抵抗穷举攻击，一个加密算法的可能密 钥总数不能太少 要想能抵抗穷举攻击，一个加密算法的可能密 钥总数不能太少! 目前，目前，可能密钥的
16、总数可能密钥的总数少于少于264的密码算法不能 对抗穷举攻击，因而是不安全的 的密码算法不能 对抗穷举攻击，因而是不安全的! 可能密钥的总数可能密钥的总数为为2128的密码算法能够对抗穷举的密码算法能够对抗穷举 64个二进制数能够 表示的数的总数 个二进制数能够 表示的数的总数 可能密钥的总数可能密钥的总数为为2的密码算法能够对抗穷举的密码算法能够对抗穷举 攻击攻击! 为什么为什么? 假设假设可能可能密钥的总数密钥的总数为为2128. 1年可检测年可检测3.15107230= 255个密钥个密钥 264 = 25529 现考查该加密算法抗现考查该加密算法抗穷举攻击穷举攻击的能力。的能力。 假设一台计算机每秒能检测假设一台计算机
