数据加密标准论述(ppt 45页).ppt

数据加密标准 DataEncryptionStandard DES 序列密码和分组密码 一次只对明文中的单个位 有时对字节 运算的算法称为序列算法 streamalgorithm 或序列密码 streamcypher 另一类算法是对明文的一组位进行运算 这些位称为分组 block 相应的算法称为分组算法 blockalgorithm 或分组密码 blockcypher 背景 发明人 美国IBM公司W Tuchman和C Meyer1971 1972年研制成功基础 1967年美国HorstFeistel提出的理论产生 美国国家标准局 NBS 1973年5月到1974年8月两次发布通告 公开征求用于电子计算机的加密算法 经评选从一大批算法中采纳了IBM的LUCIFER方案标准化 DES算法1975年3月公开发表 1977年1月15日由美国国家标准局颁布为数据加密标准 DataEncryptionStandard 于1977年7月15日生效 背景 美国国家安全局 NSA NationalSecurityAgency 参与了美国国家标准局制定数据加密标准的过程 NBS接受了NSA的某些建议 对算法做了修改 并将密钥长度从LUCIFER方案中的128位压缩到56位1979年 美国银行协会批准使用DES1980年 DES成为美国标准化协会 ANSI 标准1984年2月 ISO成立的数据加密技术委员会 SC20 在DES基础上制定数据加密的国际标准工作 DES概述 分组加密算法 明文和密文为64位分组长度对称算法 加密和解密除密钥编排不同外 使用同一算法采用混乱和扩散的组合 每个组合先替代后置换 共16轮只使用了标准的算术和逻辑运算 易于实现密钥长度 56位 密钥通常表示位64位 但第8位 16位 第64位都用作奇偶校验 产生16个48位的子密钥 Shannon 乘积密码设有两个子密码系统T1和T2 则先以T1对明文进行加密 然后再以T2对所得结果进行加密 其中 T1的密文空间需作为T2的 明文 空间 乘积密码可表示成T T1T2利用这两种方法可将简单易于实现的密码组合成复杂的更为安全的密码 扩散 diffusion 和混乱 confusion 扩散 就是将明文的统计特性迅速散布到密文中去 实现方式是使得明文的每一位影响密文中多位的值 即密文中每一位受明文中多位影响 将密钥的每位数字尽可能扩散到更多个密文数字中去 以防止对密钥进行逐段破译 根据扩散原则 分组密码应设计成明文的每个比特与密钥的每个比特对密文的每个比特都产生影响 混乱 的目的在于使明文和密文之间的统计关系变得尽可能复杂 使用复杂的非线形代换算法可得预期的混淆效果 Feistel网络 很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构 Feistel提出利用乘积密码可获得简单的代换密码 乘积密码指顺序地执行多个基本密码系统 使得最后结果的密码强度高于每个基本密码系统产生的结果 Feistel网络一层结构 取一个长度为n的分组 n为偶数 然后把它分为长度为n 2的两部分 L和R 定义一个迭代的分组密码算法 其第i轮的输出取决于前一轮的输出 L i R i 1 R i L i 1 f R i 1 K i K i 是i轮的子密钥 f是任意轮函数 容易看出其逆为 R i 1 L i L i 1 R i f R i 1 K i R i f L i K i L i 1 R i 1 Feistel网络 DES工作原理基于Feistel网络 假定信息空间都是由 0 1 组成的字符串 信息被分成64比特的块 密钥是56比特 经过DES加密的密文也是64比特的块 设用m表示信息块 k表示密钥 则 m m1m2 m64mi 0或1k k1k2 k64ki 0或1其中k8 k16 k24 k32 k40 k48 k56 k64是奇偶校验位 真正起作用的仅为56位 加密算法 Ek m IP 1 T16 T15 T1 IP m 其中IP为初始置换 IP 1是IP的逆 Ti是一系列的变换 解密算法 m Ek 1 Ek m IP 1 T1 T2 T16 IP Ek m 输入64比特明文数据 初始置换IP 在密钥控制下16轮迭代 初始逆置换IP 1 输出64比特密文数据 DES加密过程 DES加密过程 令i表示迭代次数 表示逐位模2求和 f为加密函数 DES解密过程 DES算法实现过程 1 初始变换IP 移位操作 仅对64比特明文 8 8 进行操作 列经过偶采样和奇采样置换后再对各行进行逆序得到IP 5758596061626364 IP 5758596061626364 一轮DES DES算法实现过程 2 选择扩展运算 选择运算E 输入32位数据 产生48位输出 设B i b1 i b2 i b64 i 是第i 1次迭代的64个二进制位输入区组 将B i 分为左右两个大小相等的部分 每部分为一个32位二进制的数据块 L i l1 i l2 i l32 i b1 i b2 i b32 i R i r1 i r2 i r32 i b33 i b34 i b64 i 分别表示为8 4 8 6 扩展置换 盒 32位扩展到48位 扩展 DES算法实现过程 3 使用密钥 在第i 1次迭代中 用48位二进制的密钥 由56位密钥生成 K i 1 k1 i 1 k2 i 1 k48 i 1 与E R i 按位相加 逻辑异或 输出仍是48位 8 6 DES算法实现过程 4 选择函数 压缩替代S 盒 48位压缩到32位 S 盒1 S 盒2 S 盒3 S 盒4 S 盒5 S 盒6 S 盒7 S 盒8 S 盒实现 S 盒是算法的关键所在 DES中其它算法都是线性的 而S 盒运算则是非线性的 S 盒不易于分析 它提供了更好的安全性 提供了密码算法所必须的混乱作用 DES算法实现过程 5 选择函数输出的拼接与换位 X i f R i K i 1 p 盒的构造准则 P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化 DES算法实现过程 6 一轮输出 把L i 与X i 按位相加 形成R i 1 且令R i 为L i 1 即得到经第i 1次迭代加密后的输出L i 1 R i R i 1 L i f R i K i 1 i 0 1 2 15 可以看出 DES密码体制的每一次迭代都用替代法和换位法对上一次迭代的输出进行加密变换 用硬件实现DES算法时 实际上用替代盒实现替代函数Sj 1 j 8 用换位盒实现换位函数P 为了使最后输出的密码文与原始输入的明码文没有明显的函数关系 DES算法采用16次迭代 在前15次迭代中 L i 表示左32位 R i 表示右32位 对最后一次迭代 L 16 表示右32位 R 16 表示左32位 即在最后一次迭代时不再左右交换 以保证加密和解密的对称性 DES算法实现过程 7 逆初始变换 用IP 1表示 它和IP互逆 例如 第1位经过初始置换后 处于第58位 而通过逆置换 又将第58位换回到第1位 IP IP 1 DES中的子密钥的生成 密钥置换算法的构造准则 设计目标 子密钥的统计独立性和灵活性实现简单速度不存在简单关系 给定两个有某种关系的种子密钥 能预测它们轮子密钥之间的关系 种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥 DES 三重DES 为了增加密钥的长度 人们建议将一种分组密码进行级联 在不同的密钥作用下 连续多次对一组明文进行加密 通常把这种技术称为多重加密技术 对DES 建议使用3DES增强加密强度 3DES可以用两个密钥对明文进行三次加密 假设两个密钥是K1和K2 1 用密钥K1进行DES加密 2 用K2对步骤1的结果进行DES解密 3 对 2 的结果使用密钥K1进行DES加密 3DES的缺点是加 解密速度比DES慢 三重DESTriple DES 加密 C Ek1 Dk2 Ek1 P 解密 P Dk1 Ek2 Dk1 C DES的安全性 F函数 S Box 设计原理未知密钥长度的争论DES的破译弱密钥与半弱密钥 DES密钥长度 关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击 因为密钥量只有个早在1977年 Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片 每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间 他们估计制造这样的机器大约需要2000万美元 DES密钥长度 在CRYPTO 93上 Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案 这个机器基于并行运算的密钥搜索芯片 所以16次加密能同时完成 花费10万美元 平均用1 5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起 用了96天时间 在Internet上数万名志愿者的协同工作下 成功地找到了DES的密钥 赢得了悬赏的1万美元 DES密钥长度 1998年7月电子前沿基金会 EFF 使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间 电子前