1 第三章对称密码体制 3 1分组密码原理3 2数据加密标准 DES 3 3高级加密标准 AES 3 4分组密码的工作模式 2 3 1分组密码原理 对称密码体制根据对明文加密方式的不同分为分组密码和流密码 分组密码 按一定长度 如64bit 128bit 对明文进行分组 然后以组为单位采用同样的密钥进行加 解密 流密码 不进行分组 而是按位进行加 解密 无记忆元件 内部记忆元件 k k x1 xm ym y1 y1 x1 分组密码 流密码 3 分组密码对不同的组采用同样的密钥k进行加 解密 设密文组为y y1y2 ym 则对明文组x x1x2 xm用密钥k加密可得到y ek x1 ek x2 ek xm 流密码的基本思想是利用密钥k产生一个密钥流z z0z1 并使用如下规则加密明文串x x0 x1x2 y y0y1y2 ez0 x0 ez1 x1 ez2 x2 密钥流由密钥流发生器f产生 分组密码与流密码的区别就在于记忆性 4 3 1 1分组密码设计原理 分组密码是将明文消息编码表示后的数字 简称明文数字 序列x0 x1 划分成长度为n的组x x0 x1 xn 1 每组分别在密钥k k0 k1 km 1 的控制下变换成等长的输出数字 简称密文数字 序列y y0 y1 yn 1 5 分组密码的算法应满足如下安全性和软 硬件实现的要求 1 分组长度足够大 防止明文被穷举攻击 如n 64bit DES 新的标准n 128bit AES 2 密钥空间足够大 从而防止穷举密钥攻击 同时 密钥又不能太长 以利于密钥管理 DES采用56bit有效密钥 现在不够长 今后采用128bit是足够安全的 3 由密钥确定的算法要足够复杂 充分实现明文与密文的扩散和混淆 没有简单的关系可循 4 软件实现的要求 尽量使用适合编程的子块和简单的运算 5 硬件实现的要求 加密和解密应具有相似性 6 两个基本设计方法Shannon 香浓 现代信息理论的鼻祖 称之为理想密码系统 密文的所有统计特性都与所使用的密钥独立 扩散 Diffusion 明文的统计结构被扩散消失到密文的统计特性中 使得明文和密文之间的统计关系尽量复杂 使得明文的每个比特影响到密文许多比特的取值 即每个密文比特被许多明文比特影响 混乱 confusion 使得密文的统计特性与密钥的取值之间的关系尽量复杂 扩散和混淆的目的都是为了挫败推出密钥的尝试 从而抗统计分析 香农既精通通信又精通数学 将数理知识和工程很好的融合在一起 他把深奥和抽象的数学思想和概括而又很具体的对关键技术问题的理解结合起来 他被认为是最近几十年最伟大的工程师之一 同时也被认为是最伟大的数学家之一 7 3 1 2分组密码的一般结构 分组密码的一般结构可以分为两种 Feistel网络结构和SP网络结构 Feistel网络结构Feistel网络结构如图所示 DES采用的是Feistel网络结构 加密 Li Ri 1 Ri Li 1 F Ri 1 Ki 解密 Ri 1 Li Li 1 Ri F Ri 1 Ki Ri F Li Ki 8 2 SP网络结构是分组密码的另一种重要结构 AES等重要算法采用的是此结构 9 DES DataEncryptionStandard 是迄今为止使用最为广泛的加密算法 DES的产生 i 1973年5月13日 NBS 美国国家标准局 开始公开征集标准加密算法 并公布了它的设计要求 1 算法必须提供高度的安全性 2 算法必须有详细的说明 并易于理解 3 算法的安全性取决于密钥 不依赖于算法 4 算法适用于所有用户 5 算法适用于不同应用场合 6 算法必须高效 经济 7 算法必须能被证实有效 8 算法必须是可出口的 3 2数据加密标准 DES 10 DES的产生 ii 1974年8月27日 NBS开始第二次征集 IBM提交了算法LUCIFER 该算法由IBM的工程师 IBM公司W Tuchman和C Meyer 在1971 1972年研制 1975年3月17日 NBS公开了全部细节 1976年 NBS指派了两个小组进行评价 1976年11月23日 采纳为联邦标准 批准用于非军事场合的各种政府机构 1977年1月15日 被正式批准为美国联邦信息处理标准 即FIPSPUB46 同年7月15日开始生效 美国国家安全局 NSA NationalSecurityAgency 参与了美国国家标准局制定数据加密标准的过程 NBS接受了NSA的某些建议 对算法做了修改 并将密钥长度从LUCIFER方案中的128位压缩到56位 11 DES的应用 1979年 美国银行协会批准使用 1980年 美国国家标准局赞同DES作为私人使用的标准 称之为DEA ANSIX 392 1983年 国际化标准组织ISO赞同DES作为国际标准 称之为DEA 1 该标准规定每五年审查一次 计划十年后采用新标准 最近的一次评估是在1994年1月 已决定1998年12月以后 DES将不再作为联邦加密标准 新的美国联邦加密标准称为高级加密标准AES AdvancedEncryptionStandard 12 3 2 1DES描述 DES是采用将明文按64bit分组 密钥长度为64bit 其中每8位有一位奇偶校验位 实际密钥的有效长度为56bit DES算法是公开的 其安全性依赖于密钥的保密程度 DES结构框图如图 13 14 1 初始置换IP和初始逆置换IP 1 15 2 迭代变换 16 迭代变换是DES算法的核心部分 每轮开始时将输入的64bit数据分成左 右长度相等的两部分 右半部分原封不动地作为本轮输出的64bit数据的左半部分 同时对右半部分进行一系列的变换 即用轮函数F作用右半部分 然后将所得结果与输入数据的左半部分进行逐位异或 最后将所得数据作为本轮输出的64bit数据的右半部分 轮函数F由选择扩展运算E 与子密钥的异或运算 选择压缩运算S和置换P组成 17 18 1 选择扩展运算 将输入的32bit数据扩展为48bit的输出数据 变换表如下 可以看出1 4 5 8 9 12 13 16 17 20 21 24 25 28 29 32这16个位置上的数据被读了两次 19 2 与子密钥的异或运算 与子密钥的异或运算 将选择扩展运算的48bit数据与子密钥Ki 48bit 进行异或运算 后面详述 20 3 选择压缩运算 将输入的48bit数据从左至右分成8组 每组6bit 然后输入8个S盒 每个S盒为一非线性代换 有4bit输出 如图所示 21 22 23 S Box 对每个盒 6比特输入中的第1和第6比特组成的二进制数确定为行 中间4位二进制数用来确定为列 相应行 列位置的十进制数用4位二进制数表示作为输出 例如S2盒输入为101001 则行数和列数的二进制表示分别是11和0100 即表中3行和表中4列 表中3行和表中4列的十进制数为3 用4位二进制数表示为0011 所以输出为0011 24 4 置换P 25 DES中的子密钥的生成 26 27 DES加密算法执行过程 28 3 2 2DES问题讨论1 S盒的安全问题有人认为s盒可能存在陷门 但至今没有迹象表明s盒中存在陷门 2 密钥长度 关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击 因为密钥量只有256 1017个 早在1977年 Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片 每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间 他们估计制造这样的机器大约需要2000万美元 29 在CRYPTO 93上 Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案 这个机器基于并行运算的密钥搜索芯片 16次加密能同时完成 此芯片每秒能测试5000万个密钥 用5760个芯片组成的系统需要花费10万美元 它平均用1 5天左右就可找到DES密钥 1997年1月28日 美国的RSA数据安全公司在RSA安全年会上公布了一项 秘密密钥挑战 竞赛 其中包括悬赏1万美元破译密钥长度为56比特的DES 美国克罗拉多洲的程序员Verser从1997年2月18日起 用了96天时间 在Internet上数万名志愿者的协同工作下 成功地找到了DES的密钥 赢得了悬赏的1万美元 30 1998年7月电子前沿基金会 EFF 使用一台25万美元的电脑在56小时内破译了56比特密钥的DES 1999年1月RSA数据安全会议期间 电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥 31 1 两重DES 3 2 3DES的变形 双重DES密钥长度为112bit 密码强度似乎增强了一倍 但问题并非如此 双重DES易受中途攻击 C EK2 EK1 P P DK1 DK2 C 32 中途攻击 中途攻击算法基于以下观察 如果有C EK2 EK1 P 则X EK1 P DK2 C 给定一个已知明 密文对 P C 攻击方法如下 首先用所有256个可能的密钥加密P 得到256个可能的值 把这些值从小到大存在一个表中 然后再用256个可能的密钥对密文C进行解密 每次做完解密都将所得的值与表中值进行比较 如果发现与表中的一个值相等 则它们对应的密钥可能分别是K1和K2 现在用一个新的明 密文对检测所得到的两个密钥 如果满足X EK1 P DK2 C 则把它们接受为正确的密钥 33 2 三重DES 以被广泛采用 优点 能对付中途攻击 密钥长度为168bit 34 AES背景 i 1997年4月15日 美国 国家标准技术研究所 NIST 发起征集高级加密标准 AdvancedEncryptionStandard AES的活动 活动目的是确定一个非保密的 可以公开技术细节的 全球免费使用的分组密码算法 作为新的数据加密标准 1997年9月12日 美国联邦登记处公布了正式征集AES候选算法的通告 作为进入AES候选过程的一个条件 开发者承诺放弃被选中算法的知识产权 对AES的基本要求是 比三重DES快 至少与三重DES一样安全 数据分组长度为128比特 密钥长度为128 192 256比特 3 3高级加密标准AES 35 AES背景 ii 1998年8月12日 在首届AES会议上指定了15个候选算法 1999年3月22日第二次AES会议上 将候选名单减少为5个 这5个算法是RC6 Rijndael SERPENT Twofish和MARS 2000年4月13日 第三次AES会议上 对这5个候选算法的各种分析结果进行了讨论 2000年10月2日 NIST宣布了获胜者 Rijndael算法 2001年11月出版了最终标准FIPSPUB197 36 Rijndael简介 不属于Feistel结构 加密 解密相似但不对称 支持128 32 Nb数据块大小 支持128 192 256 32 Nk 密钥长度 有较好的数学理论作为基础 结构简单 速度快 37 AES参数 38 SP网络结构在这种密码的每一轮中 轮输入首先被一个由子密钥控制的可逆函数S作用 然后再对所得结果用置换 或可逆线性变换 P作用 S和P分别被称为混乱层和扩散层 主要起混乱和扩散作用 39 AES算法结构 i AES算法的轮变换中没有Feistel结构 轮变换是由三个不同的可逆一致变换组成 称之为层 线性混合层 确保多轮之上的高度扩散 非线性层 具有最优最差 情形非线性性的S 盒的并行应用 密钥加层 轮密钥简单地异或到中间状态上 40 AES算法结构 ii 41 42 电子密码本ECB electroniccodebookmode 密码分组链接CBC cipherblockchaining 密码反馈CFB cipherfeedback 输出反馈OFB outputfeedback 这四种工作模式适用于不同的应用需求 3 4分组密码的工作模式 分组密码在加密时明文的长度是固定的 而实用中待加密消息的数据量是不定的 数据格式也可能是多种多样的 为了能在各种应用场合安全地使用