密码编码学 网络安全 第03章 对称密码体制课件.ppt

第三章 对称密码体制,本章内容,Feistel密码 简化的数据加密标准S-DES 数据加密标准DES 差分分析和线性分析 分组密码的设计原理,1. Feistel密码,当前使用的大部分对称加密算法都基于被称为Feistel分组密码的结构 数据映射设计 扩散和扰乱(混淆) 加密算法结构 解密算法,1.0 流密码与分组密码,流密码 每次加密数据流的一位或一个字节 例子：古典密码中的Vigenre密码和Vernam密码 分组密码 将一个明文组作为整体加密且通常得到的是与之等长的密文组 典型分组大小是64位或128位1.1 数据映射设计,,1.1 数据映射设计,,n=4时的一个n比特到n比特的分组密码,1.1 数据映射设计,示例：4bit明文 一般替代 线性映射 y1k11x1k12x2k13x3k14x4 y2k21x1k22x2k23x3k24x4 y3k31x1k32x2k33x3k34x4 y4k41x1k42x2k43x3k44x4,替代密码的加密与解密表,,,1.1 数据映射设计,可逆映射和不可逆映射 n bit的可逆映射的不同变换个数为2n！ 分组长度较小时等同于古典的替代密码 n bit的一般替代分组密码，密钥的大小是 n x 2n n bit线性映射的密钥的大小是n2,,1.2 扩散和混淆（扰乱）,现代分组密码设计的基础是为统计分析制造障碍 扩散 将明文的统计特征消散到密文中，让明文的每个数字影响许多密文数字的取值，亦即每个密文数字被许多明文数字影响。

混淆（扰乱） 明文分组到密文分组的变换依赖于密钥，使得密文的统计特性与加密密钥的取值之间的关系尽量复杂 ，使得即使攻击者掌握了密文的某些统计特性，由于密钥产生密文的方式是如此复杂以至于攻击者难于从中推测出密钥 1.2 扩散和混淆（扰乱）,扩散 采用平均操作进行加密 重复使用对数据的某种置换，并对置换结果再应用某个函数 扰乱 采用复杂的替代算法（非线性函数）1.3 Feistel加密算法结构,明文分组被分为两个部分L0和R0，数据的这两个部分经过n轮的处理后组合起来产生密文分组 每一轮i以从前一轮得到的Li-1和Ri-1为输入，另外的输入还有从总的密钥K生成的子密钥Ki 子密钥Ki不同于K，它们彼此之间也不相同 每一轮的结构都一样对数据的左边一半进行替代操作，替代的方法是对数据右边一半应用round函数F，然后用这个函数的输出和数据的左边一半做异或 round函数在每一轮中有着相同的结构，但是以各轮的子密钥Ki为参数形成区分 在这个替代之后，算法做一个置换操作把数据的两个部分进行互换1.3 Feistel加密算法结构,分组大小：分组越大意味着安全性越高（如果其他条件相同），但加密/解密速度也越慢。

密钥大小：密钥长度越长则安全性越高，但加密/解密速度也越慢 循环次数：一个循环不能保证足够的安全性，而循环越多 则安全性越高 子密钥产生算法 ：算法越复杂则密码分析就应该越困难 Round函数：复杂性越高则抗击密码分析的能力就越强Feistel具体实现依赖的参数和设计特点,1.3 Feistel加密算法结构,Feistel具体实现应考虑的其它因素 快速的软件加密/解密：在很多情况下，加密过程被以某种方式嵌入在应用程序或工具函数中以至于没法用硬件实现，因此，算法的执行速度就成为一个重要的考虑因素 便于分析：如果算法能够简洁地解释清楚，那么就很容易通过分析算法而找到密码分析上的弱点，也就能够对其牢固程度有更大信心1.4 Feistel解密算法,,1.4 Feistel解密算法,Feistel密码的解密过程与其加密过程实质是相同的 以密文作为算法的输入，但是以相反的次序使用子密钥Ki这就是说在第一轮用Kn，在第二轮用kn-1，如此等等，直到在最后一轮使用K11.4 Feistel解密算法,证明： 设：LEi和REi表示加密过程中各个阶段的数据 LDi和RDi表示解密过程中各个阶段的数据 则：LE16RE15 RE16=LE15 F(RE15，K16) LD1=RD0=LE16=RE15 RD1=LD0F(RD0，K16) =RE16F(RE15，K16) LE15F(RE15，K16)F(RE15，K16) 由于：ABC = ABC DD = 0 E0 = E 故： RD1=LE15 通式： 由于：LEi = REi-1 REi = LEi-1F(REi-1，Ki) 因此：REi-1 = LEi LEi-1 = REiF(REi-1，Ki) = REiF(LEi，Ki),2. 简化的数据加密标准S-DES,DES-Data Encryption Standard (1977年元月15日-美国联邦标准） 1998年被破解。

Simplified DES方案，简称S-DES方案 1. 加密算法涉及算法涉及五个函数： (1)初始置换IP(initial permutation) (2)复杂函数fk1，它是依赖于密钥K，具有置换和替换的运算 (3)置换函数SW (4)复杂函数fk2 (5)初始置换IP的逆置换IP-1,2. 简化的数据加密标准S-DES,,2. 简化的数据加密标准S-DES,,2.加密算法的数学表示： IP-1*fk2*SW*fk1*IP 也可写为 密文=IP-1（fk2(SW(fk1(IP(明文))))) 其中 K1=P8(移位(P10(密钥K))) K2=P8(移位(移位(P10(密钥K)))) 解密算法的数学表示： 明文=IP-1（fk1(SW(fk2(IP(密文))))),（1） S-DES的密钥生成：,2. 简化的数据加密标准S-DES,,（1） S-DES的密钥生成： 设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7, k8,k9,k10) 置换P10是这样定义的 P10(k1,k2,,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 相当于 P10= LS-1为循环左移，在这里实现左移1位; LS-2为循环左移，在这里实现左移2位; P8= 按照上述条件,若K选为(1010000010), 产生的两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1),2. 简化的数据加密标准S-DES,(2)S-DES的加密运算: 初始置换用IP函数: 末端算法的置换为IP的逆置换: 易见IP-1(IP(X))=X,2. 简化的数据加密标准S-DES,,,(3)S-DES加密图,,2. 简化的数据加密标准S-DES,函数fk，是加密方案中的最重要部分，它可表示为： fk(L,R)=(LF(R,SK),R)其中L，R为8位输入, 左右各为4位, F为从4位集到4位集的一个映射, 并不要求是一一映射的。

SK为子密钥 对映射F来说： 首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算： 事实上，它的直观表现形式为：,,2. 简化的数据加密标准S-DES,,,8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得： 把它们重记为8位： 上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出两个S盒按如下定义：,,2. 简化的数据加密标准S-DES,,,,S盒按下述规则运算： 将第1和第4的输入比特做为2- bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列如此确定为S盒矩阵的（i,j）数 例如：（P0,0, P0,3）=(00),并且(P0,1,P0,2)=(1 0) 确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出 由S0, S1输出4-bit经置换 它的输出就是F函数的输出2. 简化的数据加密标准S-DES,,(4)S-DES的安全性分析 无法抗强力攻击 具有一定的抗密码分析能力 置换和加法操作都是线性映射 非线性来自于S盒子 设： S盒子 输入为(p0,0，p0,1，p0,2，p0,3) = (a，b，c，d) 和(p1,0，p1,1，p1,2，p1,3) = (w，x，y，z) S盒子输出为(q，r，s，t) 则：q = abcd + ab + ac + b + d （模2加） r = abcd + abd + ab + ac + ad + a + c +1 （模2加） 线性映射和非线性映射交替使用将产生复杂的密文比特多项式，其复杂性可用8个包含10个未知数的非线性方程表示，每一个方程大约有29个项 （含有10个二进制未知数的一个多项式方程可以有210个可能的项 ）。

2. 简化的数据加密标准S-DES,背景,发明人：美国IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制成功 基础：1967年美国Horst Feistel提出的理论 产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告， 公开征求用于电子计算机的加密算法经评选从一大批算法中采纳了IBM的LUCIFER方案 标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效,3. 数据加密标准DES,背景,美国国家安全局（NSA, National Security Agency)参与了美国国家标准局制定数据加密标准的过程NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位 1979年，美国银行协会批准使用DES 1980年，DES成为美国标准化协会(ANSI)标准 1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作,DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文 该算法分三个阶段实现：1. 给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。

X0=IP（X）=L0R0其中L0由X0前32位组成，R0由X0的后32位组成2.计算函数F的16次迭代, 根据下述规则来计算LiRi(1<=i<=16） Li=Ri-1, Ri=Li-1 F(Ri-1, Ki)其中Ki是长为48位的子密钥子密钥K1，K2，，K16是作为密钥K（56位）的函数而计算出的 3.对比特串R16L16使用逆置换IP-1得到密文YY=IP-1（R16L16）,3. 数据加密标准DES,3. 数据加密标准DES,DES加密流程图,,3. 数据加密标准DES,初始置换及逆初始置换,,IP和IP-1,,DES,的一 轮迭 代,37,选择压缩运算,41,3. 数据加密标准DES,一轮加密通。