上海交大密码学课件--第六讲 现代密码学

1、1 第六讲 现代密码学21.现代分组密码- moden-block ciphers目前最广泛使用的加密算法 提供保密与认证服务 32.私钥加密算法private-key encryption是一种单钥或对称算法通信实体双方使用相同的密钥加密和解密 现代密码（由乘积密码构成）包括DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) 及其它一些算法 43。分组密码在分组密码中，消息被分成许多块每块都要被加密类似于许多字符被替换-（ 64-bits or more ）许多现代分组密码具有下列形式：53.分组密码 (cont.)64.理论基础理想的方法是使用尽可

2、能大的替换模块但不实际，因为对每个64bit的模块，将需要264 个实体的替换表因此使用一些小的模块代替使用乘积密码的思想 这种概念由 Shannon and Feistel 提出75. Shannons 保密系统理论保密系统理论 Claude Shannon 对现代密码的重要工作C E Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715 C E Shannon, Prediction and Entropy of printe

3、d English, Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64 在上述文章中，提出了下列概念: “熵”的概念语言冗余度破译密码需要多少信息量定义了”计算安全”与”无条件安全” 86. Shannons 保密系统理论保密系统理论 cont 即如果通过填加一些英语字母加密英文内容，是不安全的因为英语有80%的冗余度英语密文如果有60%的冗余度，就可以破解 97. 替换替换-置换密码置换密码 在Shannon 1949 的文章中，介绍了替换-置换网络的思想 (S-P) networks 这种思想形成了现代密码的基础S-P ne

4、twork 替换-置换乘积密码的现代形式S-P networks 是基于下列两种最基本的密码运算（前面介绍过）：替换（ Substitution ）置换（ Permutation ）108. 替换运算替换运算 一个二进制字用其它二进制字替换这种替换函数就构成密钥 可以看作是一个大的查表运算叫做 S-boxes 11替换运算（续）替换运算（续）129. 置换运算（变换）置换运算（变换）二进制字次序被打乱 重新排序的方法构成密钥 叫这种变换为 P-boxes 139. Cont.1410. Substitution-Permutation Network Shannon 把这两种运算组合在一起 一

5、些 S-boxes 由 P-box 连接这种变换叫做混合变换（mixing transformations ）1510. 替换替换-置换网络置换网络(cunt.)1611. 实际使用的替换实际使用的替换-置换网络置换网络实际中，我们需要加密，也需要解密因此，有两种方法：1.定义每个替换、置换的逆，这样增加了复杂度2. 定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密1712. Feistel 密码密码 Horst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，设计了这样的结构，我们现在叫做feis

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

7、种特殊的乘积密码 组成部分一起工作: S-Boxes （S-盒)提供输入bits混合作用 (confusion) 其目的在于使作用于明文的密钥和密文之间的关系复杂化，其目的在于使作用于明文的密钥和密文之间的关系复杂化，使明文和密文之间、密文和密钥之间的统计相关特性极小化，使明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。通常的方法是从而使统计分析攻击不能奏效。通常的方法是“替换替换（Substitution)”（回忆恺撒密（回忆恺撒密 码）。码）。 21P-Boxes提供扩散作用提供扩散作用(diffusion) 将明文及密钥的影响尽可能迅速地散布到较多个输出的

8、密文中将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中（将明文冗余度分散到密文中）。产生扩散的最简单方法是通（将明文冗余度分散到密文中）。产生扩散的最简单方法是通过过“换位换位(Permutation)”（比如：重新排列字符）（比如：重新排列字符）这种效果进一步解释为”雪崩”与”完全性” (Avalanche and Completeness )by Webster & Tavares On the Design of S-boxes, in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science

9、, No 218, Springer-Verlag, 1985, pp 523-5342215. 雪崩效应雪崩效应(Avalanche effect )输入改变1bit, 导致近一般的比特发生变化一个函数F具有好的雪崩特性是指: 对2m个明文 向量, 分为2m-1个向量对xi和xi,每对向量只有一个bit不同, 定义Vi = f(X) XOR f(Xi) ,则近一半的Vi为1.2316. 完备性效应完备性效应(Completeness effect )每个输出比特是所有输入比特的复杂函数的输出 F具有好的完备性是指: 对密文输出向量的每一比特j, 0jm, 至少存在一个明文对(xi,xi),

10、此明文对只在第i比特不同,且F(xi)与F(xi)的第j比特不同.2417. 分组密码设计分组密码设计(Block Cipher Design ) 这些设计原理是设计好的分组密码的准则 “雪崩雪崩”保证小的输入变化导致大的输出变保证小的输入变化导致大的输出变化化完全性保证每个输出比特依赖于所有的输入完全性保证每个输出比特依赖于所有的输入比特比特我们可以看到,古典密码没有这些性质 2518. Feistel Cipher 设计设计设计密码时,下列参数需要考虑: 分组大小分组大小(block size) 增加分组长度会提高安全性, 但降低了密码运算速度密钥大小密钥大小(key size) 增加密钥

11、长度,可以提高安全性(使得穷搜索困难),同样,降低了密码速度. 26Feistel Cipher 设计设计(续续)轮数轮数 增加轮数可以提高安全性,但降低速度子密钥生成子密钥生成 子密钥生成越复杂,就越安全,但降低速度轮函数轮函数 复杂的轮函数能够使的密码分析困难,但降低速度 (所有问题就是平衡问题)设计”安全”的密码算法并不难,只要使用足够多的轮数就可以,但降低速度 得到一个快速安全的算法是困难的2719. 密码设计密码设计 评价评价 “好的”密码设计具有: 雪崩特性,完备性,不可预料性(avalanche, completeness, unpredictability )差的密码设计缺乏随

12、机性,具有太大的可预料性许多密码都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) 即使密码学专家也会犯这样的错误最好的办法是测试, 通过实际检验证明它的安全性 2820. Lucifer 第一个可用的替换-置换密码(by Horst Feistel at IBM labs )Horst Feistel, Cryptography and Computer Privacy, Scientific American, Vol 228(5), May 1973, pp

13、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 包括算法的详细描述实现2921. Lucifer 浏览浏览 原始描述没有给出细节以下列形式描述: 30Lu cifer3122. Lucifer 密钥编排密钥编排 Lucifer IS Feistel cipher, 分组长度是 128-bit ,密钥长度是12

14、8-bit 每轮使用的子密钥是密钥的左半部分密钥每次要向左旋转56-bits, 所以,密钥的每部分都参加运算3223. 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 ke

15、y )subkey 替换输出相加(modulo 2)在通过几个8bit 置换组成128的简单置换33Lucifer Function f3424. Lucifer Security Lucifer 没有经过很强的分析 现在认为是理论可破的(通过差分分析) 现在不被使用 是 DES的前生 3525. 小结小结 讨论了:分组密码的概念及理论基础feistel ciphers 的概念, 雪崩与完备性概念Lucifer 的主要结构 36END37Exercises A Shannon style Substitution Box (S-box) grows in size as the number of input bits increases. For inputs of 4, 6, 8, 10, and 12 bits, list how many entries would be required. How large would each of these entries be, and why? What are the implications fo