密码学与计算机安全

1、密码学与计算机安全 第六讲 现代密码学 上海交通大学计算机科学与工程系 郑东Zheng-1.现代分组密码- moden-block ciphers目前最广泛使用的加密算法 提供保密与认证服务 2.私钥加密算法private-key encryption也叫单钥或对称算法）通信实体双方使用相同的密钥加密和解密 古典密码是私钥加密算法 现代密码（由乘积密码构成）包括DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) 及其它一些算法 3。分组密码在分组密码中，消息被分成许多块每块都要被加密类似与许多字符被替换-（ 64-bits or more ）许多现代密

2、码具有下列形式：3.分组密码 (cont.)4.理论基础理想的方法是使用尽可能大的替换模块但不实际，因为对每个64bit的模块，将需要264 个实体的替换表因此使用一些小的模块代替使用成绩密码的思想 这种概念由 Shannon and Feistel 提出5. Shannons 保密系统理论保密系统理论 Claude Shannon 对现代密码的重要工作C E Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715 C E Shan

3、non, Prediction and Entropy of printed English, Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64 在上述文章中，提出了下列概念: “熵”的概念语言冗余度破译密码需要多少信息量定义了”计算安全”与”无条件安全” 6. Shannons 保密系统理论保密系统理论 cont 指出 Book cipher 是不安全的即如果通过填加一些英语字母加密英文内容，是不安全的因为英语有80%的冗余度英语密文如果有60%的冗余度，就可以破解7 7. 替换替换-置换密码置换密码 在Shannon 194

4、9 的文章中，介绍了替换-置换网络的思想 (S-P) networks 这种思想形成了现代密码的基础S-P network 替换-置换乘积密码的现代形式S-P networks 是基于下列两种最基本的密码运算（前面介绍过）：替换（ Substitution ）置换（ Permutation ）8. 替换运算替换运算 一个二进制字用其它二进制字替换这种替换函数就构成密钥 可以看作是一个大的查表运算叫做 S-boxes 替换运算（续）替换运算（续）9. 置换运算（变换）置换运算（变换）二进制字次序被打乱 重新排序的方法构成密钥 叫这种变换为 P-boxes 9. Cont.10. Substitu

5、tion-Permutation Network Shannon 把这两种运算组合在一起 一些 S-boxes 由 P-box 连接这种变换叫做混合变换（mixing transformations ）10. 替换替换-置换网络置换网络(cunt.）11. 实际使用的替换实际使用的替换-置换网络置换网络实际中，我们需要加密，也需要解密因此，有两种方法：1。定义每个替换、置换的逆，这样增加了复杂度 or 2。定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密12. Feistel 密码密码 Horst Feistel, （working at IBM Thomas J Wat

6、son Research Labs ）70s初，设计了这样的结构，我们现在叫做feistel cipher 思想是把输入块分成左右两部分 L(i-1) 和R(i-1), 变换是在密码的第I轮只使用R(i-1) 函数 g incorporates one stage of the S-P network的每个阶段有g 工作，由第I 个密钥控制（叫子密钥） 13. Feistel 密码密码变换可以用下列函数表示: L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易 实际中，一些这样的连续变换形成完整密码变换（典型：16轮）14. 基本设计原理基

7、本设计原理Shannons 混合变换形成一种特殊的成绩密码 组成部分一起工作: S-Boxes （S-盒)提供输入bits混合作用 (confusion)P-Boxes 提供扩散作用提供扩散作用(diffusion across S-box inputs) 这种效果进一步解释为”雪崩”与”完全性” (Avalanche and Completeness )by Webster & Tavares On the Design of S-boxes, in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Scien

8、ce, No 218, Springer-Verlag, 1985, pp 523-534 15. 雪崩效应雪崩效应(Avalanche effect )输入改变1bit, 导致近一般的比特发生变化? 16. 完备性效应完备性效应(Completeness effect )每个输出比特是所有输入比特的复杂函数的输出 ?17. 分组密码设计分组密码设计(Block Cipher Design ) 这些设计原理是设计好的分组密码的准则 “雪崩雪崩”保证小的输入变化导致大的输出变保证小的输入变化导致大的输出变化化完全性保证每个输出比特依赖于所有的输出完全性保证每个输出比特依赖于所有的输出比特比特我们

9、可以看到,古典密码没有这些性质 18. Feistel Cipher 设计设计设计密码时,下列参数需要考虑: 分组大小分组大小(block size) 增加分组长度会提高安全性, 但降低了密码运算速度密钥大小密钥大小(key size) 增加密钥长度,可以提高安全性(使得穷搜索困难),同样,降低了密码速度. Feistel Cipher 设计设计(续续)轮数轮数 增加轮数可以提高安全性,但降低速度子密钥生成子密钥生成 子密钥生成越复杂,就越安全,但降低速度(所有问题就是平衡问题)轮函数轮函数 复杂的轮函数能够使的密码分析困难,但降低速度 设计”安全”的密码算法并不难,只要使用足够多的轮数就可以

10、,但降低速度 得到一个快速安全的算法是困难的19. 密码设计密码设计 评价评价 “好的”密码设计具有: 雪崩特性,完备性,不可预料性(avalanche, completeness, unpredictability )差的密码设计缺乏随机性,具有太大的可预料性许多密码都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) 即使密码学专家也会犯这样的错误最好的办法是测试, 通过实际检验证明它的安全性 20. Lucifer 第一个可用的替换-置换密码(by Horst

11、Feistel at IBM labs )Horst Feistel, Cryptography and Computer Privacy, Scientific American, Vol 228(5), May 1973, pp 15-23. 提供了这项工作的框架,但没有Lucifer 的细节 详细的介绍: Arthur Sorkin, Lucifer, A Cryptographic Algorithm, Cryptologia, Vol 8(1), Jan 1984, pp 22-41, with addenda in Vol 8(3) pp260-261 包括算法的详细描述实现21.

12、 Lucifer 浏览浏览 原始描述没有给出细节以下列形式描述: Lu cifer22. Lucifer 密钥编排密钥编排 Lucifer IS Feistel cipher, 分组长度是 128-bit ,密钥长度是128-bit 每轮使用的子密钥是密钥的左半部分密钥每次要向左旋转56-bits, 所以,密钥的每部分都参加运算23. Lucifer 数据计算数据计算 16轮数据计算(使用子密钥) 输出的右半部分作为下轮的输入 RH side as inputs to the round function 交换位置前,与左半异或 S-P function for Lucifer 有下列结构: substitution 使用8个 4-bit S-boxes (S0 & S1) (对)每个对的交替使用方法依赖与密钥(order (S0|S1) or (S1|S0) depending on the key )subkey 替换输出相