密码编码学软件学院信息安全课程

1 信息安全密码编码学 2 对称密码 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4对称密码的密钥分配 3 对称密码 对称密码机制提供一个双向信道 A和B共享一个秘密密钥 双方既能加密信息发送给对方 也可以解密从对方得到的密文信息 流密码 streamcipher 分组密码 blockcipher 4 对称密码 DES 1973年5月15日 NBS公开征集标准加密算法 并公布了它的设计要求 算法必须提供高度的安全性算法必须有详细的说明 并易于理解算法的安全性取决于密钥 不依赖于算法算法适用于所有用户算法适用于不同应用场合算法必须高效 经济算法必须能被证实有效算法必须是可出口的 5 对称密码 DES 1974年8月27日 IBM提交了算法LUCIFER 该算法由IBM的工程师在1971 1972年研制1976年11月23日 采纳为联邦标准 批准用于非军事场合的各种政府机构1977年1月15日 数据加密标准 FIPSPUB46发布 FIPSPUB81 DES的工作方式 在1980年公布FIPSPUB74 实现和使用DES的指南 于1981年公布FIPSPUB112规定了DES用作口令加密的标准FIPSPUB113规定了DES如何用作计算机数据鉴别 6 对称密码 DES DES的应用1979年 美国银行协会批准使用1980年 美国国家标准局 ANSI 赞同DES作为私人使用的标准 称之为DEA ANSIX 392 1983年 国际化标准组织ISO赞同DES作为国际标准 称之为DEA 1 7 对称密码 DES DES加密64位明文输入56位密钥输入64位密文输出 初始置换 第1轮 第2轮 第16轮 32位互换 逆初始置换 置换选择2 置换选择2 置换选择2 置换选择1 循环左移 循环左移 循环左移 64位明文 64位密文 K1 K2 K16 图3 4DES加密算法的一般描述 密钥 9 DES明文的处理 从图3 4中左半部分 可见明文的处理经过了三个阶段 首先 64位的明文经过初始置换IP而被重新排列 然后进行16轮相同函数的作用 每轮作用都有置换和代换 最后一轮迭代的输出有64位 它是输入明文和密钥的函数 其左半部分和右半部分互换产生预输出 最后预输出再被与初始置换IP互逆的置换IP 1作用产生64位的密文 初始置换IP 逆初始置换IP 1 11 DES的一轮迭代 图3 5给出了一轮变换的内部结构 64位中间数据的左右两部分作为独立的32位数据 分别记为L和R 在任何古典Feistel密码中 每轮变换的整个过程可以写为下面公式 Li Ri 1Ri Li 1 F Ri 1 Ki 12 DES的一轮迭代 子密钥Ki长48位 R是32位 首先将R用一个表定义的置换 扩充置换E 扩展为48位 其中有16位是重复的 见表3 2c 这48位与Ki异或 再用一个代换函数 S盒 作用产生32位的输出 再用表3 2d定义的置换P进行作用后输出 Li 1 32位 Ri 1 32位 扩充置换 E 代换运算 S盒 置换运算 P Li 32位 Ri 32位 48b 子密钥Ki 48b 32b 32b 48b 图3 5DES的一轮迭代 扩充置换E 置换运算P 代换运算 S盒 对每个盒 6比特输入中的第1和第6比特组成的二进制数确定的行 中间4位二进制数用来确定的列 相应行 列位置的十进制数的4位二进制数表示作为输出 DES的S Box DES的S Box 18 例如 在S1中 若输入为011001 则行是1 01 列是12 1100 该处的值是9 所以输出为1001 19 DES密钥的使用 图3 4的右半部分给出了使用密钥的过程 密钥经过初始置换 置换选择1 后 经过循环左移和置换 置换选择2 分别得到子密钥Ki用作每一轮的迭代 每轮的置换函数都一样 但是由于密钥的循环移位使得子秘密钥互不相同 C0 28位 D0 28位 密钥 64位 置换选择1 循环左移 循环左移 C1 28位 D1 28位 循环左移 循环左移 C16 28位 D16 28位 置换选择2 置换选择2 K1 48b K16 48b 子密钥的产生 21 DES子密钥的产生 表3 4 a 输入密钥 DES输入64比特的密钥 密钥各比特分别标记为1到64 如表3 4a中没有阴影的部分 也就是每行第8个位被忽略 22 DES子密钥的产生 用标记为置换选择1的表 表3 4b 作用 所得56位密钥分为两个28位数据C0和D0 每轮迭代中 Ci 1和Di 1分别循环左移 或旋转 一位或两位 见表3 4d 移位后的值作为下一轮的输入 它们同时也作为置换选择2 表3 4c 的输入 将产生一个48位的输出作为函数f Ri 1 Ki 的输入 23 b 置换选择1 PC 1 c 置换选择2 PC 2 d 左移方案 24 3 8这个问题给出了用一轮DES加密的具体数字的例子 我们假设明文和密钥有相同的位模式 即 用十六进制表示 0123456789ABCDEF用二进制表示 0000000100100011010001010110011110001001101010111100110111101111推导第一轮的子密钥K1 推导L0 R0 扩展R0求E R0 计算A E R0 K1 把 d 的48位结果分成6位 数据 的集合并求对应S 盒代换的值 利用 e 的结论来求32位的结果B 应用置换求P B 计算R1 P B L0 写出密文 练习 25 a 64位初始密钥经过置换选择1 PC 1 变成56位密钥 1 1 26 经PC 1所得的56位密钥分为前后两个28位数据C0和D0 分别循环左移一位 C0 D0 27 循环左移后的密钥再经过置换选择2 PC 2 得到48位密钥K1 0 0 K1 000010110000001001100111100110110100100110100101 28 b 对64位明文进行初始置换 IP 然后前32位作为L0 后32位作为R0 1 1 L0 11001100000000001100110011111111R0 11110000101010101111000010101010 29 c 利用扩展置换E将R0扩展成48位 E R0 011110100001010101010101011110100001010101010101 30 d 计算A E R0 K1 E R0 011110100001010101010101011110100001010101010101 K1 000010110000001001100111100110110100100110100101 A 011100010001011100110010111000010101110011110000 31 e 把A分为6位一组进行S盒代换 例如 第一组为011100 即行号为00 列号1110 所以查S1的0行14列 对应的值为0 十进制 即0000 二进制 同理第二组查S2 第三组查S3 32 f 将e的结果合并写出得到B 32位 B 00001100001000010110110101010000 33 g 利用置换P求P B P B 10010010000111000010000010011100 34 h 计算R1 P B L0 L0 11001100000000001100110011111111 P B 10010010000111000010000010011100 R1 01011110000111001110110001100011 35 i 连接L1和R1得到密文 L1 R0 11110000101010101111000010101010 R1 01011110000111001110110001100011 密文 1111000010101010111100001010101001011110000111001110110001100011十六进制表示为 F0AAF0AA5E1CEC63 36 DES的特点 DES算法只使用了标准的算术与逻辑运算解密算法与加密算法相同 只是子密钥的使用次序相反适合软硬件的实现 37 DES的特点 DES具有很强的雪崩效应雪崩效应明文或密钥的微小变换可以对密文产生很大的影响 加密算法所期望的一个好的性质 38 DES的破译 1990年 以色列密码学家EliBiham和AdiShamir提出了差分密码分析法 可对DES进行选择明文攻击 线性密码分析 1993 比差分密码分析更有效强力攻击 平均255次尝试差分密码分析法 使用247对明密文的选择明文攻击线性密码分析法 使用247对明密文的已知明文攻击 39 DES的破译 1997年 克罗拉多州的程序员Verser在Internet上数万名志愿者的协作下用96天的时间找到了密钥长度为40位和48位的DES密钥1998年电子边境基金会 EFF 使用一台价值25万美元的计算机在56小时之内破译了56位的DES1999年 电子边境基金会 EFF 通过互联网上的10万台计算机合作 仅用22小时15分破译了56位的DES 40 对称密码 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4对称密码的密钥分配 41 多重DES DES由于安全问题 美国政府于1998年12月宣布DES不再作为联邦加密标准新的美国联邦加密标准是高级加密标准 AES 在新的加密标准实施之前 为了使已有的DES算法投资不浪费 NIST在1999年发布了一个新版本的DES标准 FIPSPUB46 3 该标准指出DES仅能用于遗留的系统 同时将三重DES 简写为3DES 取代DES成为新的标准 42 多重DES 双重DES 用DES加密两次 每次使用不同的密钥 E K1 C M 加密 解密 E K2 X D D K2 K1 M C X 43 但是双重DES不安全 双重DES存在中间相遇攻击 使它的强度跟一个56位DES强度差不多若已知明文密文对 M C 攻击方法如下 先用256个可能的K1加密M 得到256个可能的值 将这些值从小到大存入一个表中再对256个可能的K2解密C 每次做完解密 将所得的值与表中的值比较 如果产生匹配 则它们对应的密钥可能是K1和K2用一个新的明文密文对检测所得两个密钥 如果两密钥产生正确的密文 则它们是正确的密钥 44 为防止中间相遇攻击 可以采用三次加密方式 如下图所示 这是使用两个密钥的三重EDS 采用加密 解密 加密 E D E 方案注意的是 加密与解密在安全性上来说是等价的 这种加密方案穷举攻击代价是2112 45 目前还没有针对两个密钥的三重DES实际的攻击方法但是感觉它不大可靠 如果采用三把密钥的三重DES则比较放心三把密钥的三重DES的密钥长度是168位 采用加密 解密 加密 E D E 方案 46 3DES已经被一些网络应用采用 如PGP和S MIME 3DES存在几个优点 首先它的密钥长度是168位 足以抵抗穷举攻击 其次 3DES的底层加密算法与DES的加密算法相同 该加密算法比任何其它加密算法受到分析的时间要长得多 也没有发现有比穷举攻击更有效的密码分析攻击方法缺点 加解密速度慢 分组长度只有64位 47 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4对称密码的密钥分配 对称密码 48 AES产生的背景 1997年4月15日 NIST发起征集高级加密标准 AdvancedEncryptionStandard AES的活动 活动目的是确定一个非保密的 可以公开技术细节的 全球免费使用的分组密码算法 作为新的数据加密标准 对AES的基本要求是 比三重DES快 至少与三重DES一样安全 无类别的 可公开的 无特权的 数据分组长度为128比特 密钥长度为128 192 256比特 49 AES产生的背景 1998年6月NIST共收到21个提交的算法 在同年的8月首届AES会议上指定了15个候选算法 1999年3月22日第二次AES会议上 将候选名单减少为5个 这5个算法是MARS RC6 Rijndael SERPENT 和Twofish 50 AES产生的背景 MARS 由IBM公司研究部门的一个庞大团队发布 对它的评价是算法复杂 速度快 安全性高 RC6 由RSA实验室发布 对它的评价是极简单 速度极快 安全性低 Rijndael 由JoanDaemen和VincentRijmen两位比利时密码专家发布 对它的评价是算法简洁 速度快 安全性好 Serpent 由RossAnderson EliBiham和LarsKnudsen发布 对它的评价是算法简洁 速度慢 安全性极高 Twofish 由Counterpane公司一个庞大的团队发布 对它的评价是算法复杂 速度极快 安全性高 51 AES产生的背景 从全方位考虑 Rijndael汇聚了安全 性能 效率 易用和灵活等优点 使它成为AES最合适的选择2000年10月NIST宣布Rijndael算法被选为高级加密标准2001年11月发布为联邦信息处理标准 FederalInformationProcessingStandard FIPS 用于美国政府组织保护敏感信息的一种特殊的加密算法 即FIPSPUB197标准 52 AES的特点 使用的数学背景 近似代数不属于Feistel结构加密 解密相似但不对称支持128 192 256b数据块大小支持128 192 256b密钥长度结构简单 速度快 53 DES和AES的比较 54 AES算法简介 算法有多轮相同的运算 每一轮包括4个步骤 字节代换 S 盒 行移位 ShiftRows 列混淆 MixColums 轮密钥加 AddRoundKey 每一轮的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域GF 28 上进行的 55 AES算法简介 AES算法的轮数和明文分组长度及密钥长度的关系为 除最后一轮不做列混淆变换外 每一轮都经过4步相同的操作 Round State RoundKey ByteSub State S 盒ShiftRow State 行循环左移MixColumn State 列混淆变换AddRoundKey State RoundKey 与扩展密钥相异或 56 AES算法简介 AES算法中进行运算的单位包括 1个字节1列1行用字节数组表示的整个加密块加密块数组中 n可以是3 5 7 所代表的加密块分别表示128bit 192bit和256bit ai j 57 AES算法简介 AES加密过程演示 58 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4对称密码的密钥分配 对称密码 59 分组密码的工作模式 分组密码算法是提供数据安全的一个基本构件分组密码是针对固定大小的分组进行加密的 例如 DES是对64比特的明文分组进行加密 AES是对128位分组操作需要保密传输的消息不一定刚好是一个分组大小为了在实际中应用分组密码 定义了五种工作模式 任何一种对称分组密码算法都可以以这些方式进行应用 60 分组密码的工作模式 分组密码的5种工作模式电码本 ECB 密文分组连接 CBC 密文反馈 CFB 输出反馈 OFB 计数器 CTR 61 电码本 ECB 电码本 ElectronicCodeBook ECB 模式是分组密码的基本工作方式它将明文分割成独立大小的分组b 最后一组在必要时需要填充 一次处理b比特的明文 每次使用相同的密钥加密每一个分组依次独立加密 产生独立的密文组 62 电码本 ECB 加密 p1 c1 k 解密 c1 p1 k 加密 pn cn k 加密 cn pn k a 加密 b 解密 63 电码本 ECB 特点优点 并行处理来加速加 解密运算 一分组发生错误不会影响到其他分组 缺点 相同的明文组将产生相同的密文组 这样会泄露明文的数据模式 ECB模式特别适合短数据 如加密密钥 64 密文分组链接 CBC 密文分组链接 CiphertextBlockChaining 将明文分成b位的一串分组 最后一组不足b位要进行填充CBC将这些分组链接在一起进行加密操作加密输入是当前明文分组和前一密文分组的异或 它们形成一条链每次加密使用相同的密钥 加密 p1 c1 k 加密 cn k IV 加密 c2 k p2 pn cn 1 解密 p1 c1 k 解密 cn k IV 解密 c2 k p2 pn cn 1 a 加密 b 解密 66 密文分组链接 CBC 特点能隐藏明文的模式信息 相同明文得到的密文不同使用了初始化向量IV IV为收发双方共享 需要加以保护信息块不容易被替换 重排 删除 重放误差传递 密文块损坏导致两明文块损坏安全性高于ECB适合于传输长度大于64位的报文 可以进行用户鉴别 是大多系统的标准如SSL IPSec 67 密文反馈模式 CFB 密文反馈模式 CiphertextFeedbackBlock 将加密的明文必须按照一个字节或者一位进行处理 即将分组密码转换为流密码假设它的输出是s位 s位的大小可以是1位 8位 64位或者其他大小 表示为CFB 1 CFB 8 CFB 64等特点 具有流密码的优点 也拥有CBC模式的优点和缺点 误差传递 一个单元损坏影响多个单元 选择丢弃s位 64 s位 加密 C1 s位 K P1 移位寄存器IV 64位 64位 加密 C2 s位 K 移位寄存器64 s位 s位 64位 64位 选择丢弃s位 64 s位 a 加密 s位 s位 s位 P2 s位 s位 参加下一分组加密计算 s位 选择丢弃s位 64 s位 加密 P1 s位 K 移位寄存器IV 64位 64位 加密 K C1 s位 移位寄存器64 s位 s位 64位 64位 选择丢弃s位 64 s位 b 解密 s位 s位 P2 s位 C2 s位 同时参加下一分组解密计算 70 密文反馈模式 CFB 以DES为例 用CFB 8工作模式说明加密过程 加密 加密函数的输入是一个64位的移位寄存器 产生初始向量IV 对移位寄存器64位的数据用密钥进行加密 然后取加密数据最左边的8位跟输入的明文最初的8位进行异或操作 得到的值作为8位密文单元 这8比特密文被移至位寄存器的最右端 而其它位则向左移动8位 最左端8比特丢弃 继续加密 与第2段明文输入异或 如此重复直到所有明文单元都完成加密 71 输出反馈模式 OFB 输出反馈模式 OutputFeedbackBlock 类似于密文反馈模式不同的地方是输出反馈模式是将加密算法的输出反馈到移位寄存器 而密码反馈模式是将密文单元反馈到移位寄存器特点 OFB模式的优点是传输过程中的位错误不会被传播 但是这种模式数据之间相关性小 这种加密模式是比较不安全的 选择丢弃s位 64 s位 加密 C1 s位 K P1 移位寄存器IV 64位 64位 加密 C2 s位 K 移位寄存器64 s位 s位 64位 64位 选择丢弃s位 64 s位 a 加密 s位 s位 P2 s位 s位 选择丢弃s位 64 s位 加密 P1 s位 K 移位寄存器IV 64位 64位 IV 加密 K C1 s位 移位寄存器64 s位 s位 64位 64位 选择丢弃s位 64 s位 b 解密 s位 s位 P2 s位 C2 s位 74 计数器模式 CTR 计数器 Counter CTR 采用与明文分组相同的长度加密不同的明文组 计数器对应的值不同计数器首先被初试化为一个值 然后随着消息块的增加 计数器的值依次递增1计数器加1后与明文分组异或得到密文分组解密是使用相同的计数器值序列 用加密后的计数器的值与密文分组异或来恢复明文特点 简单 安全 可以并行处理 效率高 加密 计数器 C1 k P1 加密 计数器 N 1 Cn k Pn 加密 计数器 P1 k C1 加密 计数器 N 1 Pn k Cn a 加密 b 解密 加密 计数器 1 C2 k P2 加密 计数器 1 P2 k C2 分组密码的工作模式 77 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4 对称密码的密钥分配 对称密码 78 数据加密标准DES多重DES高级加密标准AES分组密码的工作模式流密码和RC4对称密码的密钥分配 对称密码 79 对称密码的密钥分配 对称密码体制要求双方共享一个共同的密钥 为防止攻击者得到密钥 还必须时常更新密钥 密钥分配方法是指将密钥发给需要交换数据的双方而不让别人知道的方法 80 对称密码的密钥分配 对于参与者A和B 密钥分配的方法有以下几种 1 密钥由A选取 并通过物理手段交给B 2 密钥由第三方选取 并由第三方通过物理手段交给A和B 3 如果A B事先已有一密钥 则其中一方选取新密钥后 用已有的密钥加密新密钥并发送给另一方 4 如果A和B与可信的第三方C分别有一保密通道 则C为A B选取密钥后 分别在两个保密信道上发送给A B 81 前两种方法称为人工发送 不可取对于第3种方法 攻击者一旦获得一个密钥就可获取以后所有的密钥 而且用这种方法对所有用户分配初始密钥时 代价仍然很大