1、第二章第二章 分组密码技术分组密码技术 1 1密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 密码学的历史密码学的历史密码学从形成到发展经历了5个重要阶段手工阶段 机械阶段 电气阶段 计算机阶段 网络化阶段。第二章第二章 分组密码技术分组密码技术 2 2密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 保密系统模型保密系统模型 熵的概念熵的概念 联合熵联合熵 条件熵条件熵 理论保密性理论保密性 “一次一密”的密码系统就是这样的
2、无条件安全的密码系统。实际保密性实际保密性 一个密码系统是计算上安全的是指，利用最好的算法（已知或者是未知的）来破解这个密码系统需要的计算量是O(N)的，N是一个很大的数。的计算量超过了攻击者所能控制的所有计算资源在合理的时间内能够完成的计算量。所以计算上安全也称为实际的保密性。密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 第二章第二章 分组密码技术分组密码技术 3 3什么是分组密码什么是分组密码密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码
3、的工作模式 多重加密 第二章第二章 分组密码技术分组密码技术 4 4分组加密的评价标准分组加密的评价标准评价分组加密算法及其工作模式的一般标准是：预估的安全水平（如破译需要的密文数量等）密钥的有效位长 分组大小 加密映射的复杂性 数据的扩张（Data Expansion）错误的扩散（Diffusion）/传播（Propagation）分分组组加加密密的的一一般般结结构构Feistel Feistel 网络结构网络结构SP SP 网络结构网络结构密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 第二章第二章 分组
4、密码技术分组密码技术 5 5DESDES概述概述分组加密算法：明文和密文为64位分组长度；对称算法：加密和解密除密钥编排不同外，使用同一算法；密钥长度：56位，但每个第8位为奇偶校验位，可忽略；密钥可为任意的56位数，但存在弱密钥，容易避开；采用混乱和扩散的组合，每个组合先替代后置换，共16轮；只使用了标准的算术和逻辑运算，易于实现；DESDES加密算法描述加密算法描述DES加密算法的一般描述加密算法的一般描述初始置换初始置换IPIP和初始逆置换和初始逆置换IPIP11DESDES的一轮叠代的一轮叠代Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄
5、存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1L Li i =R=Ri-1i-1;R Ri i=L=Li-1i-1 F(RF(Ri-1i-1,K,Ki i)扩展置换扩展置换-盒盒3232位扩展到位扩展到4848位位扩展扩展压缩替代压缩替代S-S-盒盒4848位压缩到位压缩到3232位位压缩替代压缩替代S-S-盒盒S-盒1S-盒4S-盒3S-盒2S-盒5S-盒6S-盒7S-盒8S-S-盒的构造盒的构造1 2 3 4 5 61 6262 3 4 5211
6、33 911001110019bbbbbbbbSbbbb行：-盒子 行 列列：值：14=1100S-S-盒的构造要求盒的构造要求S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度；提供了密码算法所必须的混乱作用；如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题；非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门；S-S-盒的构造准则盒的构造准则S盒的每一行应该包括所有16种比特组合；没有一个S盒是它输入变量的线性函数；改变S盒的一个输入位至少要引起两位的输出改变；S盒的两个输入刚好在两个中间比特不同，则输出必须至少两个比特不同；S
7、盒的两个输入在前两位不同，最后两位相同，两个输出必须不同；P-P-盒的构造准则盒的构造准则每个S盒输出的四个比特被分布开，一边其中的两个影响下次循环的中间比特，另外两个影响两端比特；每个S盒输出的四个比特影响下个循环6个不同的S盒；P置换的目的是增强算法的扩散特性，提供雪崩效应（雪崩效应（明文或密钥的一个比特的变动都引起密文许多比特的变化）k1 （56 位）(48 位)ki （56 位）（48 位）64 位 密 钥置 换 选 择 1 C0（28 位）D0（28 位）循 环 左 移循 环 左 移 C1（28 位）D1（28 位）循 环 左 移循 环 左 移 Ci（28 位）Di（28 位）置 换
8、 选 择 2置 换 选 择 2密 钥 表 的 计 算 逻 辑循 环 左 移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1DESDES中的子密钥的生成中的子密钥的生成DESDES的强度分析的强度分析循环次数：循环次数：循环次数越多，密码分析难度越大，循环次数的选择准则是密码分析工作量大于简单的穷举式密钥搜索工作量；函数函数F F：依赖于S盒的使用，非线性程度越大，密码分析难度越大，还应具有良好雪崩性质；密钥调度算法：密钥调度算法：选择子密钥时要使得推测各个子密钥和由此推出主密钥的难度尽可能大；IDEA(Intern
9、ational Data Encryption Algorithm)瑞士联邦理工学院Xuejia Lai和James Massey提出；IDEA是对称、分组密码算法，输入明文为64位，密钥为128位，生成的密文为64位，它的设计目标：（1）密码强度：扰乱通过三种操作实现（逐位异或，整数模相加或乘积）；（2）使用方便性：设计考虑到硬件和软件的实现；IDEA是一种相对较新的算法，虽有坚实理论基础，但仍应谨慎使用(尽管该算法已被证明可对抗差分分析和线性分析)；IDEA是一种专利算法(在欧洲和美国)，专利由Ascom-Tech AG拥有，PGP中已实现了IDEA；IDEAIDEA框图框图IDEAIDE
10、A轮函数轮函数AESAES AES是DES的替代品，希望能有20-30年的使用寿命。在评选过程中，最后的5个候选算法：Mars,RC6,Rijndael,Serpent,和Twofish。2000年10月，Rijndael算法被选中；Rijndael算法的原型是Square算法，其设计策略是宽轨迹策略(Wide Trail Strategy)，以针对差分分析和线性分析；Rijndael是迭代分组密码，其分组长度和密钥长度都是可变的，为了满足AES的要求，分组长度为128bit，密码长度为128/192/256bit，相应的轮数r为10/12/14；2001年11月，美国NIST发布标准FIPS
11、 PUB 197；AESAES框图框图密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 第二章第二章 分组密码技术分组密码技术 6 6对分组密码的攻击对分组密码的攻击 穷举分析 差分分析 线性分析 密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 第二章第二章 分组密码技术分组密码技术 7 7分组密码的工作模式分组密码的工作模式电子密码本 ECB(Electronic Codebook Mode)明文每次处理64 bit，每个明
12、文分组用同一密钥加密；密码分组链接 CBC(Cipher Block Chaining)输入是当前明文和前边明文的异或，每个分组使用相同密码；密码反馈 CFB(Cipher Feedback Mode)分组密码流密码；输出反馈 OFB(Output Feedback Mode)分组密码流密码；电子密码本电子密码本ECBECBiKiiKiC=E(P)P=D(C)ECBECB的特点的特点简单有效，可以并行实现；不能隐藏明文的模式信息，相同明文生成相同密文，同样信息多次出现造成泄漏；对明文的主动攻击是可能的信息块可被替换、重排、删除、重放；误差传递：密文块损坏仅对应明文块损坏；适合于传输短信息；密码
13、分组链接密码分组链接CBCCBCiKii-1iKii-1C =E(PC)P=D(C)CCBCCBC的特点的特点没有已知的并行实现算法；能隐藏明文的模式信息，相同明文生成不同密文，初始化向量IV可以用来改变第一块；对明文的主动攻击是不容易的，信息块不容易被替换、重排、删除、重放；误差传递：密文块损坏两明文块损坏；安全性好于ECB，适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec；密码反馈密码反馈CFBCFB加密加密Ci=Pi(EK(Si)的高j位);Si+1=(Sij)|Ci 密码反馈密码反馈CFBCFB解密解密Pi=Ci(EK(Si)的高j位);Si+
14、1=(Sij)|Ci CFBCFB的特点的特点分组密码流密码;没有已知的并行实现算法;隐藏了明文模式;需要共同的移位寄存器初始值IV;对于不同的消息，IV必须唯一;误差传递：一个单元损坏影响多个单元;输出反馈输出反馈OFBOFB加密加密Ci=Pi(EK(Si)的高j位)；Si+1=(Sij)|(EK(Si)的高j位)输出反馈输出反馈OFBOFB解密解密Pi=Ci(EK(Si)的高j位);Si+1=(Sij)|(EK(Si)的高j位)OFBOFB的特点的特点分组密码流密码；没有已知的并行实现算法；隐藏了明文模式；需要共同的移位寄存器初始值IV,对于不同的消息，IV必须唯一；误差传递：一个单元损坏
15、只影响对应单元；对明文的主动攻击可能，信息块可被替换、重排、删除、重放；安全性较CFB差；密码学的历史 香农安全理论 分组密码的基本概念 分组密码设计原理 典型的分组密码算法 对分组密码的攻击 分组密码的工作模式 多重加密 第二章第二章 分组密码技术分组密码技术 8 8DESDES的密钥长度分析的密钥长度分析关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个 强力攻击：平均255次尝试差分密码分析法：平均247次尝试线性密码分析法：平均243次尝试早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI
16、芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元；1756102DESDES的密钥长度分析的密钥长度分析1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击；在CRYPTO93上，Session和Wiener给出了基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥；美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢
17、得了悬赏的1万美元；DESDES的密钥长度分析的密钥长度分析1998年7月电子前沿基金会（EFF）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES；1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥；两重两重DESDESEK2EK1P=EK3P?中途攻击中途攻击C=EK2EK1PX=EK1P=DK2C三重三重DESDES两个密钥的三重两个密钥的三重DES用于密钥管理标准用于密钥管理标准ANS X9.17 和和 ISO 8732 2中；中；三个密钥的三重三个密钥的三重DES用于用于PGP 和和 S/MIME；进阶阅读和习题进阶阅读和习题
