《对称密钥密码课件》由会员分享，可在线阅读，更多相关《对称密钥密码课件（45页珍藏版）》请在金锄头文库上搜索。
1、2 对称密钥密码1对称密钥密码对称密钥密码对称密钥密码u流密码流密码(Stream Ciphers) 根据根据一次一密一次一密获获得得密钥相对较短密钥相对较短密钥被扩展为更长的密钥流密钥被扩展为更长的密钥流(keystream)Keystream被用做一次一密的密钥被用做一次一密的密钥只用到了混淆只用到了混淆u分组密码分组密码(Block cipher) 根据根据电码本密码电码本密码获得获得分组密码密钥决定电码本分组密码密钥决定电码本每个密钥生成一个不同的电码本每个密钥生成一个不同的电码本混淆和扩散都得到利用混淆和扩散都得到利用2对称密钥密码对称密钥密码流密码流密码 Stream Cipher
2、s3对称密钥密码对称密钥密码流密码流密码u现在已不如分组密码流行现在已不如分组密码流行u本节讨论一种流密码本节讨论一种流密码uA5/1基于线性移位寄存器（硬件实现）基于线性移位寄存器（硬件实现）用于用于GSM移动通信系统移动通信系统4对称密钥密码对称密钥密码流密码原理流密码原理u流密码使用流密码使用n比特长的密钥比特长的密钥K，并将其扩展为更长的密钥流。，并将其扩展为更长的密钥流。u将密钥流与明文做异或运算，将密钥流与明文做异或运算， 得到密文得到密文C。u密钥流的使用方法与一次一密中的密钥相同。密钥流的使用方法与一次一密中的密钥相同。u解密时将密文与密钥做异或运算得到明文。解密时将密文与密钥
3、做异或运算得到明文。u函数可表示为函数可表示为StreamCipher(K)=SK是密钥，是密钥， S是和一次一密中对等的密钥流是和一次一密中对等的密钥流5对称密钥密码对称密钥密码A5/1 原理原理1uA5/1 使用使用3个线性移位寄存器个线性移位寄存器(LFSR)寄存器寄存器X: 19 bits (x0,x1,x2, ,x18)寄存器寄存器Y: 22 bits (y0,y1,y2, ,y21)寄存器寄存器Z: 23 bits (z0,z1,z2, ,z22)三个寄存器共有三个寄存器共有64 bits密钥密钥K采用采用64 bits。 初始时密钥初始时密钥K被载入被载入3个寄存器个寄存器6对称
4、密钥密码对称密钥密码A5/1 原理原理2u对每一步做对每一步做: m = major(x8, y10, z10) Major（多数）（多数）函数定义函数定义: major(0,1,0) = 0 and major(1,1,0) = 1 u如果如果 x8 = m 那么那么 X寄存器寄存器 进行移位运算进行移位运算 t = x13 x16 x17 x18xi = xi 1 for i = 18,17,1 and x0 = tu如果如果 y10 = m 那么那么 Y寄存器寄存器进行移位运算进行移位运算t = y20 y21yi = yi 1 for i = 21,20,1 and y0 = tu如果
5、如果 z10 = m 那么那么 Z寄存器寄存器进行移位运算进行移位运算t = z7 z20 z21 z22zi = zi 1 for i = 22,21,1 and z0 = tu密钥流比特最后由密钥流比特最后由 x18 y21 z22 产生产生7对称密钥密码对称密钥密码A5/1原理原理3u每次运算获得一个比特每次运算获得一个比特u密钥用于初始化三个寄存器密钥用于初始化三个寄存器u每个寄存器是否进行移位操作由每个寄存器是否进行移位操作由M(x8, y10, z10)决定决定u密钥流比特由三个最右端比特进行密钥流比特由三个最右端比特进行XOR运算获得运算获得y0y1y2y3y4y5y6y7y8y
6、9y10y11y12y13y14y15y16y17y18y19y20y21z0z1z2z3z4z5z6z7z8 z9 z10 z11 z12z13z14z15z16z17z18z19z20z21z22XYZx0x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x188对称密钥密码对称密钥密码A5/1实例实例u在这种情况下在这种情况下, m = maj(x8, y10, z10) = maj(1,0,1) = 1 u寄存器寄存器 X 进行移位进行移位, Y不进行移位不进行移位, Z进行移位进行移位u密钥流比特由最右端比特进行密钥流比特由最右端比特进行XOR操作而
7、得操作而得u此例此例, 密钥流比特是密钥流比特是 0 1 0 = 1u最后用密钥流和明文做最后用密钥流和明文做XOR运算进行加密和解密运算进行加密和解密1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 11 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1XYZ101010101010 10101019对称密钥密码对称密钥密码流密码总结流密码总结u密钥流的产生看似很复杂，但用硬件实现很简密钥流的产生看似很复杂，但用硬件实现很简单单产生速度与计算机时钟速度相当（可与语音同步）产生速度与计算机时钟速度相当（可与语音同步）从一个
8、从一个64位密钥可产生无穷多密钥流位密钥可产生无穷多密钥流最终会产生密钥流循环！最终会产生密钥流循环！10对称密钥密码对称密钥密码流密码总结流密码总结u因为过去基于软件的密码系统不能产生高速比因为过去基于软件的密码系统不能产生高速比特流，流密码曾十分辉煌，当今，基于软件的特流，流密码曾十分辉煌，当今，基于软件的密码系统的出现，使分组密码成为主流密码系统的出现，使分组密码成为主流u密码流的未来密码流的未来?密码学家密码学家Shamir: “密码流已步入死亡密码流已步入死亡-the death of stream ciphers”-2004或许太夸张或许太夸张但分组密码是现今主流但分组密码是现今主
9、流11对称密钥密码对称密钥密码分组密码分组密码 Block Ciphers12对称密钥密码对称密钥密码(Iterated) 分组密码（迭代）分组密码（迭代）u密文和明文均是固定长度的分组密文和明文均是固定长度的分组(block)u通过若干轮使用轮函数通过若干轮使用轮函数(round function)迭代产生密迭代产生密文文u轮函数的输入由前一轮的输出和密钥组成轮函数的输入由前一轮的输出和密钥组成u分别设计一个安全的分组密码或者一个高速的算法分别设计一个安全的分组密码或者一个高速的算法不难，但既安全又高效的算法则非常困难不难，但既安全又高效的算法则非常困难u通常用软件实现通常用软件实现13对称
10、密钥密码对称密钥密码Feistel 密码密码(Cipher)uFeistel Feistel 密码密码 是分组密码的一种是分组密码的一种(分组分组)原则，不是原则，不是一种特殊的密码一种特殊的密码u将明文分解成右半部分和左半部分将明文分解成右半部分和左半部分: 明文明文 = (L0, R0)u对于每一轮对于每一轮 i=1, 2,.,n, 计算：计算：Li= Ri 1 Ri= Li 1 F(Ri 1,Ki)此处此处 F 是是 轮函数轮函数, Ki是第是第i轮的轮的 子密钥子密钥(subkey)u密文密文 = (Ln, Rn)14对称密钥密码对称密钥密码Feistel 密码解密密码解密u解密解密:
11、 密文密文 = (Ln, Rn)u对每轮对每轮 i=n,n 1,1, 计算计算Ri 1 = LiLi 1 = Ri F(Ri 1,Ki)此处此处 F 是是 轮函数轮函数, Ki是第是第i轮的轮的 子密钥子密钥 subkey u明文明文 = (L0,R0)u此算法对所有函数此算法对所有函数F都适用都适用u但只对特定函数来说是安全的但只对特定函数来说是安全的u优点在于所有安全性问题可以转化为轮函数优点在于所有安全性问题可以转化为轮函数F的问题的问题15对称密钥密码对称密钥密码DES密码密码u20世纪世纪70年代提出年代提出DES(Data Encryption Standard)u根据根据IBM公
12、司提出公司提出Feistel密码之一的密码之一的Lucifer密码设计密码设计 u当时，密码技术除被政府和军方所研究及掌握，民间及当时，密码技术除被政府和军方所研究及掌握，民间及商业对此尚无研究商业对此尚无研究u但计算机的发展，数据加密对商业至关重要但计算机的发展，数据加密对商业至关重要u美国标准局美国标准局(NBS)提出了对密码算法的征集提出了对密码算法的征集u获胜者将成为美国政府及实际上的产业界标准获胜者将成为美国政府及实际上的产业界标准u因参与者不多，最终由唯一因参与者不多，最终由唯一IBM提出的提出的Lucifer算法获得算法获得16对称密钥密码对称密钥密码DES密码密码u由于技术力量
13、不足，由于技术力量不足，NBS求助于政府密码机构求助于政府密码机构NSA (National Security Agency)u由于由于NSA专门负责政府及军方高级敏感信息加密研究，专门负责政府及军方高级敏感信息加密研究，开始不愿参与民间密码开发开始不愿参与民间密码开发 u后被怀疑在后被怀疑在DES中植入中植入后门后门，使，使NSA很容易破解很容易破解DESuLucifer算法经过修改成为算法经过修改成为DESu主要修改为将密钥长度由主要修改为将密钥长度由128位减为位减为64位，并且位，并且64位中有位中有8位势用来校验奇偶性的，实际密钥长度由为位势用来校验奇偶性的，实际密钥长度由为56。破
14、译难。破译难度降低了度降低了272倍，难怪被指动过手脚倍，难怪被指动过手脚17对称密钥密码对称密钥密码DES密码归纳密码归纳uDES是是16轮的轮的Feistel结构密码结构密码uDES的分组长度是的分组长度是64位位 uDES使用使用56位密钥位密钥uDES每一轮使用每一轮使用48位的子密钥，每个子密钥是由位的子密钥，每个子密钥是由56位的密钥的子集构成的位的密钥的子集构成的uDES竟是住了时间的考验，其遭受攻击只是因为竟是住了时间的考验，其遭受攻击只是因为密钥过短，而不是存在比穷举更为有效的攻击方密钥过短，而不是存在比穷举更为有效的攻击方法法18对称密钥密码对称密钥密码DES的分析的分析u
15、DES是一种是一种Feistel原理的密码系统（将明文分为两部分，原理的密码系统（将明文分为两部分，然后迭代）然后迭代）64位为一个分段位为一个分段56位长的密钥位长的密钥经过经过16论迭代论迭代每步迭代采用每步迭代采用48位长的子密钥位长的子密钥(?)u每步迭代很简单每步迭代很简单u安全性主要取决于安全性主要取决于“S盒盒”每个每个S盒将盒将6位映射为位映射为4位位19对称密钥密码对称密钥密码LR扩展移位移位密钥密钥S盒压缩LR28282828282848324832323232DES的一轮4832KiP置换20对称密钥密码对称密钥密码DES的扩展组合的扩展组合u输入输入32位位(图中图中L
16、、R) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151616 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3116u输出输出48位位(经过扩展）经过扩展）31 0 1 2 3 4 3 4 5 6 7 812 7 8 9 10 11 12 11 12 13 14 15 161215 16 17 18 19 20 19 20 21 22 23 241223 24 25 26 27 28 27 28 29 30 31 01221对称密钥密码对称密钥密码DES的的S盒盒u8个个S盒盒u每个每个S盒将盒将6位输入映射到位输入映射到4位
17、输出位输出u下图为下图为1号号S盒盒输入输入bits (0,5)确定列数确定列数 输入输入bits (1,2,3,4)确定行数确定行数 | 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111-00 | 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 011101 | 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1
18、001 0101 0011 100010 | 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 000011 | 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101矩阵中的四位输出是矩阵中的四位输出是0，1, 2,F的某种置换排列。的某种置换排列。22对称密钥密码对称密钥密码DES的的P置换置换u输入输入32位位 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151
19、6 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31u输出输出32位位15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9 1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24P置换并非出于安全性考虑，至今仍被认为是一个历史谜团，置换并非出于安全性考虑，至今仍被认为是一个历史谜团， 一个可能的解释是使算法难以用软件实现一个可能的解释是使算法难以用软件实现(当初使用的是特当初使用的是特殊硬件殊硬件)。23对称密钥密码对称密钥密码DES 的子密钥的子密钥u56位的位的DES密钥密钥, 序号序号0
20、,1,2,55u左半部分密钥比特左半部分密钥比特, LK(28bit)49 42 35 28 21 14 7 0 50 43 36 29 22 15 8 1 51 44 37 30 2316 9 2 52 45 38 31u右半部分密钥比特右半部分密钥比特, RK(28bit) 55 48 41 34 27 20 13 6 54 47 40 33 26 1912 5 53 46 39 32 2518 11 4 24 17 10 324对称密钥密码对称密钥密码DES 的子密钥的子密钥 子密钥的产生式一个循环过程，该过程是安全性的关子密钥的产生式一个循环过程，该过程是安全性的关键。最终结果是选择键
21、。最终结果是选择56位中的位中的48位成为子密钥。位成为子密钥。u对于对于 i=1,2,.,16 轮轮赋值赋值 LK = (LK 循环左移位循环左移位ri位位)赋值赋值 RK = (RK 循环左移位循环左移位ri位位)左半部分的子密钥左半部分的子密钥Ki 是是LK13 16 10 23 0 4 2 27 14 5 20 912位位22 18 11 3 25 7 15 6 26 19 12 112位位右半部分的子密钥右半部分的子密钥Ki 是是RK12 23 2 8 18 26 1 11 22 16 4 1912位位15 20 10 27 5 24 17 13 21 7 0 312位位25对称密钥
22、密码对称密钥密码DES 的子密钥的子密钥u对于对于1, 2, 9和和16轮，轮，ri = 1, 其他轮其他轮 ri = 2uLK的的8,17,21,24位在每轮被忽略位在每轮被忽略uRK的的6,9,14,25位在每轮被忽略位在每轮被忽略u压缩过程后 从从56位原始密钥产生位原始密钥产生48 位子密钥位子密钥Kiu密钥生成机制 产生子密钥产生子密钥26对称密钥密码对称密钥密码DES 结束语结束语(Almost)u对原文对原文P在第一轮前进行初始置换在第一轮前进行初始置换u在最后一轮结束后再进行一次置换在最后一轮结束后再进行一次置换u在加密时，将左右两部分互换产生密文在加密时，将左右两部分互换产生
23、密文(R16,L16)u以上的这些设计在设计时并不是以安全作为考以上的这些设计在设计时并不是以安全作为考量的量的27对称密钥密码对称密钥密码DES的安全性的安全性u安全的主要依据是依赖于安全的主要依据是依赖于S盒盒其他部件均为线性部件其他部件均为线性部件u三十年的使用并未发现有所谓的三十年的使用并未发现有所谓的 “后门后门”u直到今天，攻击者仍然只能依靠穷举密钥搜索来解决直到今天，攻击者仍然只能依靠穷举密钥搜索来解决密钥问题密钥问题u由此得到的唯一结论 DES的设计者当初知道他们在做什么的设计者当初知道他们在做什么DES的设计者具有超前思维的设计者具有超前思维28对称密钥密码对称密钥密码分组密
24、码工作模式分组密码工作模式29对称密钥密码对称密钥密码多块分组多块分组u如何加密多块分组呢如何加密多块分组呢?u是否对每个分组采用一个密钥是否对每个分组采用一个密钥?和一次一密同样困难，甚至更难和一次一密同样困难，甚至更难!u对每一组进行独立加密对每一组进行独立加密?u根据前一个组的信息加密，例如将信息组串联成根据前一个组的信息加密，例如将信息组串联成串串?u怎样处理部分或是不完全的分组怎样处理部分或是不完全的分组?30对称密钥密码对称密钥密码操作的模式操作的模式u在众多模式中，本节讨论两种在众多模式中，本节讨论两种u电码本模式电码本模式 (ECB) 显而易见的方法显而易见的方法每个分组分别加
25、密每个分组分别加密有严重的安全隐患有严重的安全隐患u密文链接模式密文链接模式(CBC)将分组板块串在一起将分组板块串在一起比比ECB安全安全, 基本上无附加工作基本上无附加工作31对称密钥密码对称密钥密码电码本模式电码本模式 ECB Modeu符号含义符号含义: C=E(P,K)u给定明文给定明文 P0,P1,Pm,u显然的使用分块加密方法是显然的使用分块加密方法是加密加密 解密解密C0 = E(P0, K), P0 = D(C0, K), C1 = E(P1, K),P1 = D(C1, K),C2 = E(P2, K),P2 = D(C2, K),u对于一个固定的密钥对于一个固定的密钥K,
26、 有一个版本的电码本有一个版本的电码本u对于每个密钥，产生一个新电码本对于每个密钥，产生一个新电码本32对称密钥密码对称密钥密码ECB 的弱点的弱点u假设假设 Pi = Pju那么那么 Ci = Cj 而且而且 Trudy 已知已知 Pi = Pju在这种情况下即便在这种情况下即便Trudy不知道明文不知道明文Pi 或或 Pj，也也将给将给Trudy一些关于明文的信息一些关于明文的信息u这是否是一个严重的问题呢这是否是一个严重的问题呢?33对称密钥密码对称密钥密码Alice hate ECB ModeuAlice的未压缩加密图片的未压缩加密图片, Alice经经ECB加密后的图片加密后的图片什
27、么原因导致模糊?同样的明文段 同样的密文段!34对称密钥密码对称密钥密码密文链接模式密文链接模式 CBC Modeu字段被字段被 “链接链接” 在一起在一起u用一个随机初始化的向量用一个随机初始化的向量IV来初始化来初始化 CBC modeuIV是随机的并不一定是保密的是随机的并不一定是保密的加密加密 解密解密C0 = E(IV P0, K),P0 = IV D(C0, K),C1 = E(C0 P1, K),P1 = C0 D(C1, K),C2 = E(C1 P2, K),P2 = C1 D(C2, K),35对称密钥密码对称密钥密码CBC 模式模式u相同的明文段会产生不同的密文段相同的明
28、文段会产生不同的密文段u剪切剪切-粘贴依然可能，但更复杂粘贴依然可能，但更复杂(会产生模糊会产生模糊)u如果如果C1 变的模糊像变的模糊像G，那么那么P1 C0 D(G, K), P2 G D(C2, K)u但但 P3 = C2 D(C3, K), P4 = C3 D(C4, K),u自动从错误中恢复过来了自动从错误中恢复过来了!36对称密钥密码对称密钥密码Alice 喜欢喜欢CBC ModeuAlice未加密压缩图像未加密压缩图像, Alice经过经过CBC加密后的图像加密后的图像为何效果如此?同样的明文生成不同的密文!37对称密钥密码对称密钥密码分组密码引发的剪切分组密码引发的剪切-粘贴攻
29、击粘贴攻击u假定明文是假定明文是 Alice digs Bob. Trudy digs Tom.u假设用假设用 64-bit 分组，分组，8-bit ASCII字符字符:P0 = “Alice di”, P1 = “gs Bob. ”,P2 = “Trudy di”, P3 = “gs Tom. ”u加密后密文加密后密文: C0,C1,C2,C3uTrudy 剪切并粘贴剪切并粘贴: C0,C3,C2,C1u解密后明文为解密后明文为Alice digs Tom. Trudy digs Bob.（部分明文泄露）部分明文泄露）38对称密钥密码对称密钥密码完整性完整性(Integrity)39对称密钥
30、密码对称密钥密码数据完整性数据完整性u完整性 防止防止(至少探测到至少探测到)未经授权修改数据未经授权修改数据u实例实例: 银行内部资金转账银行内部资金转账保密性很好保密性很好, 完整性是关键完整性是关键u加密提供保密性加密提供保密性 (防止未经授权地修改信息防止未经授权地修改信息)u单靠加密单靠加密不能不能保证完整性保证完整性(一次一密和电码本一次一密和电码本)40对称密钥密码对称密钥密码消息认证码消息认证码 MACuMessage Authentication Code (MAC)用来确保数据完整性用来确保数据完整性 完整性完整性不 同于保密性同于保密性uMAC通过计算通过计算CBC的最后
31、一个分组的最后一个分组计算计算CBC加密加密, 保留最后一个密文段保留最后一个密文段41对称密钥密码对称密钥密码MAC 算法算法uMAC 算法算法(假设假设N个分段个分段)C0 = E(IV P0, K),C1 = E(C0 P1, K),C2 = E(C1 P2, K),CN 1 = E(CN 2 PN 1, K) = MACuMAC必须和明文一起发送必须和明文一起发送u接收方使用同一算法计算然后将所得结接收方使用同一算法计算然后将所得结果与果与MAC比较看是否一致比较看是否一致u接收方必须知道密钥接收方必须知道密钥K42对称密钥密码对称密钥密码MAC算法为何可行算法为何可行?u假设假设Al
32、ice有有4块明文要加密块明文要加密uAlice计算计算C0 = E(IV P0,K), C1 = E(C0 P1,K),C2 = E(C1 P2,K), C3 = E(C2 P3,K) = MACuAlice将将 IV,P0,P1,P2,P3及及MAC发给发给Bob u假设假设Trudy将将P1 换为换为 X uBob的到错误的信息然后计算的到错误的信息然后计算C0 = E(IV P0,K), C1 = E(C0 X,K),C2 = E(C1 P2,K), C3 = E(C2 P3,K) = MAC MACu错误将错误将传递(propagates)到到MAC (和和CBC解码不同解码不同)u
33、Trudy在没有密钥在没有密钥K的情况下无法将的情况下无法将MAC换成换成MAC43对称密钥密码对称密钥密码保密性和完整性保密性和完整性u用一个密钥加密用一个密钥加密, 用另一个密钥计算用另一个密钥计算MAC u为何不用同一密钥为何不用同一密钥?将最后一个加密的版块将最后一个加密的版块(MAC)发送两次发送两次twice? 对安全性无帮助对安全性无帮助!u使用不同的密钥加密和计算使用不同的密钥加密和计算MAC是可行的是可行的,即即使密钥是相对有联系的使密钥是相对有联系的但需要两倍的付出（相对于加密）但需要两倍的付出（相对于加密）u能否找到一种加密方法能同时保护保密性与完能否找到一种加密方法能同时保护保密性与完整？整？ 当前正在研究中当前正在研究中44对称密钥密码对称密钥密码对称密钥密码的应用对称密钥密码的应用u保密性保密性在不安全通道上传播数据在不安全通道上传播数据在不安全媒介上安全存储在不安全媒介上安全存储u完整性完整性(MAC)u认证协议认证协议45对称密钥密码对称密钥密码
