【安全课件】第78讲--分组密码.ppt

第四章分组密码 王滨2005年3月14日 2 明文处理方式分组密码 blockcipher 将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出也是固定长度的密文 流密码 streamcipher 又称序列密码 序列密码每次加密一位或一字节的明文 3 4 1分组密码的基本原理 定义1分组密码就是将明文数据按固定长度进行分组 然后在同一密钥控制下逐组进行加密 从而将各个明文分组变换成一个等长的密文分组的密码 其中二进制明文分组的长度称为该分组密码的分组规模 m1 m2 m3 mn 4 实现原则 1 必须实现起来比较简单 知道密钥时加密和脱密都十分容易 适合硬件和 或 软件实现 2 加脱密速度和所消耗的资源和成本较低 能满足具体应用范围的需要 例 对高速通信数据的加密 硬件实现 嵌入到系统软件的加密程序 软件实现 智能卡内数据的加密 低成本实现 5 安全性设计原则 1 混乱原则 又称混淆原则 Confusion 混乱原则就是将密文 明文 密钥三者之间的统计关系和代数关系变得尽可能复杂 使得敌手即使获得了密文和明文 也无法求出密钥的任何信息 即使获得了密文和明文的统计规律 也无法求出明文的新的信息 可进一步理解为 1 明文不能由已知的明文 密文及少许密钥比特代数地或统计地表示出来 2 密钥不能由已知的明文 密文及少许密钥比特代数地或统计地表示出来 6 2 扩散原则 Diffusion 扩散原则就是应将明文的统计规律和结构规律散射到相当长的一段统计中去 Shannon的原话 也就是说让明文中的每一位影响密文中的尽可能多的位 或者说让密文中的每一位都受到明文中的尽可能多位的影响 如果当明文变化一个比特时 密文有某些比特不可能发生变化 则这个明文就与那些密文无关 因而在攻击这个明文比比特时就可不利用那些密文比特 7 分组密码的设计方法 采用乘积密码 即通过将一个弱的密码函数迭代若干次 产生一个强的密码函数 使明文和密钥得到必要的混乱和扩散 在设计迭代函数时 充分利用代替密码和移位密码各自的优点 抵消各自的缺点 从而通过多次迭代 形成一个强的分组密码算法 8 4 2DES分组密码算法 DateEncipherStandard 一 背景简介该算法是在美国NSA 国家安全局 资助下由IBM公司开发的密码算法 其初衷是为政府非机密的敏感信息提供较强的加密保护 它是美国政府担保的第一种加密算法 并在1977年被正式作为美国联邦信息处理标准 DES主要提供非军事性质的联邦政府机构和私营部门使用 并迅速成为名声最大 使用最广的商用密码算法 9 背景 发明人 美国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日生效 10 背景 美国国家安全局 NSA NationalSecurityAgency 参与了美国国家标准局制定数据加密标准的过程 NBS接受了NSA的某些建议 对算法做了修改 并将密钥长度从LUCIFER方案中的128位压缩到56位1979年 美国银行协会批准使用DES1980年 DES成为美国标准化协会 ANSI 标准1984年2月 ISO成立的数据加密技术委员会 SC20 在DES基础上制定数据加密的国际标准工作 11 DES首次被批准使用五年 并规定每隔五年由美国国家保密局作出评估 并重新批准它是否继续作为联邦加密标准 最近的一次评估是在1994年1月 美国已决定1998年12月以后将不再使用DES 因为按照现有的技术水平 采用不到几十万美元的设备 就可破开DES密码体制 目前的新标准是AES 它是由比利时的密码学家JoanDaemen和VincentRijmen设计的分组密码 Rijndael 荣代尔 12 1DES分组密码算法 二 算法概述 一 基本参数 分组加密算法 明文和密文为64位分组长度对称算法 加密和解密除密钥编排不同外 使用同一算法密钥长度 有效密钥56位 但每个第8位为奇偶校验位 可忽略密钥可为任意的56位数 但存在弱密钥 容易避开采用混乱和扩散的组合 每个组合先替代后置换 共16轮只使用了标准的算术和逻辑运算 易于实现 13 输入64比特明文数据 初始置换IP 在密钥控制下16轮迭代 初始逆置换IP 1 输出64比特密文数据 DES加密过程 14 加密框图 15 置换 定义4 1 设S是一个有限集合 是从S到S的一个映射 如果对任意的u v 当u v时 u v 则称 是S上的一个置换 16 初始置换与逆初始置换输入和输出比特的序号从左向右编排为1 2 3 64 含义 输出的第1比特是输入的第58比特 该表示方法实现方便 17 IP和IP 1 IP IP 1 18 二 加密算法 DES的第i圈加密结构图 19 DES加密算的圈函数 属于Feistel模型 DES的圈函数的结构 它等价于两个对合变换 20 注意 无论f函数如何选取 DES的圈函数是一个对合变换 21 DES的F函数 22 E盒扩展扩展变换的作用是将输入的32比特数据扩展为48比特数据 扩展 23 E盒扩展 扩展方式 1 将输入的32比特每4比特为一组分为8块 2 分别将第m 1块的最右比特和第m 1块的最左比特添到第m块的左边和右边 形成输出的第k个6比特块 主要原因 硬件实现简单 24 DES的F函数 25 压缩替代S 盒 48位压缩到32位 123456 434445464748 1234 29303132 26 S盒 行和列的序号从0起算 27 S 盒的构造 28 S 盒的构造要求 S 盒是算法的唯一非线性部件 因此 它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用非线性度 差分均匀性 严格雪崩准则 可逆性 没有陷门 29 DES的F函数 30 P盒置换 将S 盒变换后的32比特数据再进行P盒置换 置换后得到的32比特即为f函数的输出 含义 P盒输出的第1个元是输入的第16个元 基本特点 1 P盒的各输出块的4个比特都来自不同的输入块 2 P盒的各输入块的4个比特都分配到不同的输出块之中 3 P盒的第t输出块的4个比特都不来自第t输入块 31 例 利用DES算法和全0密钥对输入1000000119600000进行1圈加密的结果 1 输入的右半部分是19600000 00011001011000000000000000000000 2 经E盒扩展后变为000011110011101100000000000000000000000000 3 与全0子密钥模2加后变为000011110010101100000000000000000000000000 4 查S盒后的32比特输出为f8372c4d11111000001101110010110001001101 5 经P盒后得F函数的32比特输出 9cd89aa7 10011100110110001001101010100111 6 将F函数的输入放到左边 将F函数的输出与圈函数的左半输入模2加后放到右边 的圈函数的64比特输出为196000008cd89aa6 32 DES中的子密钥的生成 33 置换选择1 从64比特密钥中取出56个有效比特 置换选择2 从56个密钥比特中取出48个作为子密钥 34 移位次数 意想不到的效果 子密钥寄存器的内容经16次迭代后又回到原来的设置 35 三 脱密算法 脱密结构与加密结构完全相同 只不过是所使用的子密钥的顺序正好相反 加密子密钥 脱密子密钥 36 DES的加密和脱密变换 加密 y IP 1 fek16 D D fek2 D fek1 IP x 脱密x IP 1 fdk16 D D fdk2 D fdk1 IP y 注意 1 加密密钥eki和脱密密钥dki的关系 dki ek 16 i 2 最后一圈若添加交换则无法正常脱密 y IP D fek16 D D fek2 D fek1 IP x x IP fdk16 D D fdk2 D fdk1 D IP y 37 DES分组密码算法小结 3 基本参数 分组长度 64比特 密钥长度 64比特 有效密钥长度 56比特 迭代圈数 16圈 每圈子密钥长度 48比特 4 编码环节 6进4出的S盒变换 逐位模2加变换 比特移位变换P盒 1 密码模型 Feistel模型 2 F函数模型 S P网络 实现性能 软件实现慢 硬件实现块 可全部用布尔电路实现 比特扩展变换E盒 比特抽取变换PC1 PC2和IP 38 穷举攻击分析穷举攻击就是对所有可能的密钥逐个进行脱密测试 直到找到正确密钥为止的一种攻击方法 穷举攻击判断正确密钥的方法 将利用试验密钥脱密得到的可能明文与已掌握的明文的信息相比较 并将最吻合的那个试验密钥作为算法输出的正确密钥 穷举攻击又称为穷尽攻击 强力攻击 蛮干攻击等 只要明文不是随机的 就可实施穷举攻击 39 穷举攻击的算法已知条件 已知密文c及对应的明文m Step1对每个可能密钥k 计算c D k m 并判断c c是否成立 不成立时返回Step1检验下一个可能密钥 成立时将k作为候选密钥 并执行Step2 Step2利用其它条件对作k进一步确认 确认通过时输出 算法终止 否则返回Step1检验下一个可能密钥 40 穷举攻击算法的计算复杂性定理设密钥在密钥空间K中服从均匀分布 且没有等效密钥 则穷举攻击平均需要检验完个密钥后才找到正确密钥 结论 对DES算法的穷举攻击平均计算复杂性为255 41 DES的安全性 F函数 S Box 设计原理未知密钥长度的争论DES的破译弱密钥与半弱密钥 42 DES密钥长度 关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击 因为密钥量只有个早在1977年 Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片 每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间 他们估计制造这样的机器大约需要2000万美元 43 DES密钥长度 在CRYPTO 93上 Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案 这个机器基于并行运算的密钥搜索芯片 所以16次加密能同时完成 花费10万美元 平均用1 5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起 用了96天时间 在Internet上数万名志愿者的协同工作下 成功地找到了DES的密钥 赢得了悬赏的1万美元 44 DES密钥长度 1998年7月电子前沿基金会 EFF 使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间 电子前沿基金会用22小时