密码学导论˙第5章 分组密码 8学时 李卫海

本章目录 第一节 数据加密标准DES 第二节 高级加密标准AES 第三节 分组密码工作模式 第四节 其它分组密码标准 Feistel框架；DES结构、原理、安全性 第二节 高级加密标准AES 结构、实现方式 第三节 分组密码工作模式 ECB、CBC、CFB、OFB、CTR；分组填充 第四节 其它分组密码标准 2DES、中间相遇攻击、3DES TDEA、Blowfish、IDEA、RC5、SMS4 第五节 对称密码系统的密钥 对称密码密钥的长度；KDC 密码学导论--中国科学技术大学

第一节 数据加密标准DES 密码学导论--中国科学技术大学

一、Feistel框架 分组密码(Block Cipher) ： 理想分组密码：n比特的明文分组，加密产生n比特的密文分组 通常以大于等于64位的数据块为处理单位 密文仅与算法和密钥有关，与明文数据块的位置无关 例如：DES、AES等 理想分组密码：n比特的明文分组，加密产生n比特的密文分组 2n个不同的明文分组，各自产生2n个唯一的密文分组 本质上是一个巨大的代换表 密码学导论--中国科学技术大学

一、Feistel框架 完美安全的分组映射： 例： n位的分组就有 2n种输入 每种输入需要n位“密钥”控制，共需n×2n位“密钥” 24个明文 24个密文 每个映射需用4比特描述，共24个映射，密钥共需要4×24位 密码学导论--中国科学技术大学

Feistel密码框架 很多分组密码基于Feistel密码结构 通过复杂运算，达到近似的理想 采用了乘积加密器的思想，交替使用代换和置换 代换S-box 置换P-box S-P网络（Substitution-Permutation Network） 密码学导论--中国科学技术大学

Feistel密码框架 加密算法： 解密算法： 将输入等分为两段， 进行若干轮运算，每轮中 与加密算法过程一致 子密钥使用次序相反 对左半段数据进行代换，依据 轮函数F（右半段数据和子密钥） 然后置换：交换左右两段数据 解密算法： 与加密算法过程一致 子密钥使用次序相反 密码学导论--中国科学技术大学

Feistel解密正确性证明 考虑第i轮 加密： 解密：

参数： 特点： 分组长度：长度越大，安全性越高，处理速度也越低 密钥长度：长度越大，安全性越高，可能降低处理速度 迭代轮数：单轮不能提供足够的安全性；轮数越多，安全性越高，处理时间也成倍增加 子密钥产生算法：算法越复杂，密码分析攻击越难，会降低处理速度 轮函数：算法越复杂，安全性越高，处理速度也降低 特点： 快速软件加/解密 分析简单：利于脆弱性的分析与测试 对DES并没有简便的分析方法 密码学导论--中国科学技术大学

讨论 对轮函数F的要求： 同样，对子密钥的生成也应考虑到混淆的效果。 从可解密角度：没有 从安全角度：尽可能复杂 例如 扩散效应局限在两个对应比特上 轮函数F对扩散的效果有影响 同样，对子密钥的生成也应考虑到混淆的效果。 密码学导论--中国科学技术大学

二、数据加密标准DES IBM 设计出Lucifer密码 (1971) Tuchman-Mayer 牵头开发商业密码 由Horst Feistel带领的团队 用128比特密钥加密64比特数据分组 Tuchman-Mayer 牵头开发商业密码 适合于单芯片实现 密钥长度56比特，抗密码分析能力更强 美国国家安全局介入 1973年美国国家标准局征求国家密码标准方案，IBM 将上述方案提交，并被采用，称为数据加密标准（DES） 密码学导论--中国科学技术大学

安全性曾争议颇多 民间研究显示DES安全性很强 曾是应用最广泛的分组密码技术 用56比特密钥加密64比特数据 设计标准列入机密 广泛应用在金融、遗产等领域 虽然差分攻击和线性分析攻击在理论上有效，但实现起来计算量仍很大 曾是应用最广泛的分组密码技术 AES正取而代之 密码学导论--中国科学技术大学

DES的整体结构 64比特明文分组输入 64比特密文分组输出 64比特密钥 Feistel密码框架 实际只使用56位 其它用作奇偶校验等 IP 64比特密文 64比特明文 K1 K16 64比特密钥 第1轮 第2轮 第16轮 32比特置换 IP-1 PC1 分组左移 PC2 64 48 56 64比特明文分组输入 64比特密文分组输出 64比特密钥 实际只使用56位 其它用作奇偶校验等 Feistel密码框架 16轮操作 IP：初始置换 IP-1：逆初始置换 PC1、PC2：压缩置换 密码学导论--中国科学技术大学

初始置换IP与逆初始置换IP-1 置换表中的每个元素表明了输入位在64位输出中的位置 两表互逆 注意：IP-1表很有规律 密码学导论--中国科学技术大学

轮结构 64位数据分为L、R各32位 子密钥K为48位 轮函数： 将32位R通过E扩展为48位 与密钥K异或 由8个S盒子紧缩为32位 置换P Ki Ri-1 Li-1 Ri Li F 32 48 64位数据分为L、R各32位 子密钥K为48位 轮函数： 将32位R通过E扩展为48位 与密钥K异或 由8个S盒子紧缩为32位 由置换P作用后输出 密码学导论--中国科学技术大学

扩展置换E 观察扩展置换E 扩散作用 将32位输入分为8组，每组4位 从相邻两组的邻近位置各取1位 扩展置换E 某一个比特，几轮操作后其影响会扩散到整个分组64位 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 密码学导论--中国科学技术大学

S盒子结构 S盒子为4行16列的矩阵，每行定义一个可逆置换 输入6位，输出4位 S1 S2 S3 S4 S5 S6 S7 S8 48 6 4 32 4 6 密码学导论--中国科学技术大学

S盒子 输入6位，输出4位 例：S1盒子输入011001 注意：S盒子的行、列从0开始计数 输入的第1位和第6位组成一个2位二进制数，选择行 输入的第2位至第5位组成一个4位二进制数，选择列 将选中的数字以二进制数输出 例：S1盒子输入011001 选择行1（01）；选择列12（1100） 将选中的9输出1001。 注意：S盒子的行、列从0开始计数 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

密钥的产生 输入64位密钥，保留56位 置换选择PC1将64位原始密钥置换输出56位 注意：若用大写英文字母作为密钥，常用它们的ASCII码作为二进制密钥。这是危险的，因为它们的ASCII码最高位均为0，而DES舍弃的是最低位！ 密码学导论--中国科学技术大学

56位密钥分为两组，每轮迭代分别循环左移1位或2位，作为下一轮的密钥输入 LS-1 PC2 Ki Ci-1 28 48 Di-1 Ci Di 56位密钥分为两组，每轮迭代分别循环左移1位或2位，作为下一轮的密钥输入 移位产生的值经置换选择2，输出48位作为轮函数子密钥 密码学导论--中国科学技术大学

DES解密 解密是加密的逆过程 对Feistel框架密码，采用相同算法，但是子密钥使用的次序正好相反： IP变换抵消加密的最后一步IP-1； 第一轮使用密钥K16； 第二轮使用密钥K15； …… 第十六轮使用密钥K1； IP-1变换抵消加密的第一步IP； 获得解密明文。 密码学导论--中国科学技术大学

三、DES的安全性 密钥的长度问题 S-box问题 56bits密钥有256 = 72,057,584,037,927,936 ≈ 7.2亿亿之多 蛮力搜索( brute force search ) 似乎很困难，20世纪70年代估计要1000－2000年 技术进步使蛮力搜索成为可能 1997年网络合作破译耗时96天。 1998年在一台专用机上(EFF)只要三天时间即可 1999年在超级计算机上只要22小时! 蛮力搜索需要明文可判决 S-box问题 其设计标准没有公开 迄今没有发现S盒存在致命弱点 密码学导论--中国科学技术大学

至少有4个“弱密钥”：E(k,E(k,m))=m 0101010101010101, 1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1, FEFEFEFEFEFEFEFE 至少有6对“半弱密钥”：E(k,E(k',m))=m 01FE01FE01FE01FE ↔ FE01FE01FE01FE01 1FE01FE00EF10EF1 ↔ E01FE01FF10EF10E 01E001E001F101F1 ↔ E001E001F101F101 1FFE1FFE0EFE0EFE ↔ FE1FFE1FFE0EFE0E 011F011F010E010E ↔ 1F011F010E010E01 E0FEE0FEF1FEF1FE ↔ FEE0FEE0FEF1FEF1 这里每字节的最低位用作奇偶校验位 密码学导论--中国科学技术大学

雪崩效应 Avalanche Effect 雪崩效应： DES密码有良好的雪崩效应 明文或密钥的一比特的变化，引起密文许多比特的改变 加密算法的关键性能之一 希望明文或密钥的1比特变化，会使半数密文比特发生变化；否则，可能存在方法减小待搜索的明文和密钥空间 DES密码有良好的雪崩效应 如果用同样密钥加密只差一比特的两个明文： 0000000000000000......00000000 1000000000000000......00000000 2轮迭代后密文有21个比特不同，16轮迭代后有34个比特不同 如果用只差一比特的两个密钥加密同样明文： 2轮迭代后密文有14个比特不同，16轮迭代后有35个比特不同 密码学导论--中国科学技术大学

计时攻击 能量攻击 依据加密或解密算法对于不同输入所花的时间上的细微差别，进行分析 多用于公开密钥算法 DES能够很好地抵抗计时攻击 通过分析电子设备执行计算过程中的能量消耗来寻找有关密钥的信息 指令执行时（例如在智能卡中）所消耗的能量与其执行的指令和数据的存取有关 密码学导论--中国科学技术大学

通过观测密码算法在执行过程（例如在智能卡中）中任何特定时间所消耗的能量来获得一些有用的信息。 能量攻击可分为简单能量分析攻击SPA（Simple Power Analysis）和差分能量分析攻击DPA（Differential Power Analysis） 通过观测密码算法在执行过程（例如在智能卡中）中任何特定时间所消耗的能量来获得一些有用的信息。 执行乘法比执行加法消耗更多的能量 向存储器中写1比写0消耗更多的能量 某智能卡用DES算法加密时的能量追踪图 密码学导论--中国科学技术大学

DES的密码分析 密码分析攻击问题 主要利用了加密器的一些深层结构 这些攻击本质上是统计分析，包括 DES不能抵御差分分析、线性分析 搜集加密信息 最终设法恢复部分或全部子密钥的位 如果必要的话对其余部分再辅以穷举搜索 这些攻击本质上是统计分析，包括 差分分析、线性分析、相关密钥攻击 DES不能抵御差分分析、线性分析 密码学导论--中国科学技术大学

差分密码分析 Differential Cryptanalysis 历史 1990年，Murphy、Biham和Shamir首次提出用差分密码分析攻击分组密码和散列函数，是第一种可以以少于255的复杂性对DES进行破译的方法 需要247个选择明文及对应密文 1974年IBM的DES研究团队就发现了差分攻击，并在S盒子和置换P的设计中加以考虑 差分密码分析攻击 分析明文对的差异和密文对的差异之间的关系 确定轮运算的子密钥，从而恢复某些密钥比特 密码学导论--中国科学技术大学

差分分析概述 定义：对分组长度为n的r轮迭代密码，将两个n比特串Yi和Yi*的差分定义为 通常取加法运算群，此时差分等价于异或 差分序列： ΔY0, ΔY1, …,ΔYi,…, ΔYr ΔY0是明文对Y0和Y0*的差分 Yi和Yi*即是第i轮的输出，也是第i+1轮的输入 第i轮的子密钥是Ki，轮函数为F，则Yi=F(Yi-1,Ki) 注意，这里不考虑DES中的左右串互换 密码学导论--中国科学技术大学

研究表明：对简单轮函数F，当已知一个或多个三元组(ΔYi-1, Yi, Yi*)的值时，则确定子密钥Ki是容易的。 若密文对已知，且最后一轮的输入对的差分能以某种方式得到，则确定最后一轮的子密钥可行 通过选择具有特定差分值α0的明文对，可以使得最后一轮的输入差分以很高的概率取特定值αr-1 关键在于： 如何找到特定的差分值α0和αr-1 如何确定最后一轮的子密钥 密码学导论--中国科学技术大学

r-轮特征Ω 定义：r-轮特征Ω 是一个差分序列 α0,α1,…,αr，其中 αi-1/αi（1≤i≤r）是第i轮的输入/输出对的差分。 定义：对r-轮特征Ω=α0,α1,…,αr，若Y0和Y0*的差分是α0，第i(1 ≤i ≤r)轮输出的差分为αi，则称明文对为特征Ω的一个正确对，否则称为特征Ω的错误对。 密码学导论--中国科学技术大学

定义：在r-轮特征Ω=α0,α1,…,αr中， piα表示在输入差分为αi-1的条件下，轮函数F的输出差分为αi的概率 轮函数与子密钥有关，此条件概率是对所有可能的子密钥而言的 定理：假设每一轮的子密钥是统计独立且均匀分布的，则r-轮特征Ω=α0,α1,…,αr的概率恰好是差分为α0的明文对是正确对的概率，其值可用p1α p2α … prα来近似代替。 r-轮特征可以看作r个单轮特征的串联 概率相乘时，注意差分序列的前后衔接 实际子密钥由密钥扩展算法从密钥生成，精确值的运算很复杂 密码学导论--中国科学技术大学

r-轮迭代密码的差分密钥攻击算法 第1步：找出一个(r-1)-轮特征Ωr-1=α0,α1,…,αr-1，使得它的概率达到最大或几乎最大。 第2步：均匀随机地选择明文Y0，并计算Y0*，使得输入差分为α0，找出Y0和 Y0*在实际密钥加密下的密文Yr和 Yr*。 第3步：若最后一轮的子密钥Kr有2m个可能值Krj (1≤j≤2m)，设置相应的2m个计数器Λj。用每个Krj解密Yr和 Yr* ，得Yr-1和 Yr-1*，若(Yr-1)=αr-1，则给相应的计数器Λj加1。 第4步：重复第2、3步，直到一个或几个计数器的值明显高于其它计数器的值，输出相应子密钥。 密码学导论--中国科学技术大学

线性密码分析 Linear Cryptanalysis Matsui在1993年提出 攻击16轮DES需243个已知明文 基本原理：寻找密码算法的有效线性近似表达式 令明文分组为P[1],…,P[n],密文分组为C[1],…,C[n],密钥为K[1],…,K[m] 线性密码分析的目标是找到如下有效线性方程： P[α1,α2,…,αa]  C[β1,β2,...,βb] = K[γ1,γ2,…,γc] 其中，1≤a，b≤n，1≤c≤m，α,β和γ表示比特位置 A[i,j,…,k] = A[i]  A[j]  …  A[k] 方程成立的概率p离0.5越远，方程越有效。使|p-0.5|最大的线性表达式称为最佳逼近式，相应的p称为最佳概率 密码学导论--中国科学技术大学

P[α1,α2,…,αa]  C[β1,β2,...,βb] = K[γ1,γ2,…,γc] 最大似然估计： P[α1,α2,…,αa]  C[β1,β2,...,βb] = K[γ1,γ2,…,γc] 假定T是使等式左边等于0的明文个数，p是等式成立的概率，N是明文的个数 若T>N/2，则当p>1/2时，猜测K[γ1,γ2,…,γc]=0 当p<1/2时，猜测K[γ1,γ2,…,γc]=1 若T<N/2，则当p>1/2时，猜测K[γ1,γ2,…,γc]=1 当p<1/2时，猜测K[γ1,γ2,…,γc]=0 密码学导论--中国科学技术大学

S盒子的线性逼近 对于一个给定的S盒子Si，定义 其中1≤i≤8，1≤α≤63，1≤β≤15。 式中的条件等式是某种由α和β决定的线性逼近式 NSi度量了Si盒子的线性逼近式对所有输入x的成立个数，即Si盒子的非线性程度 |NSi(α,β)-32|最大的线性逼近式就是Si盒子的最佳逼近式。由该式出发，可以推出DES的最佳逼近式。 密码学导论--中国科学技术大学

四、DES的设计标准 迭代轮数 密钥扩展算法 函数F的设计准则 迭代次数越多，密码分析的难度就越大。准则是要使已知的密码分析工作量大于简单穷举密钥的工作量。 密钥扩展算法 选择子密钥时要使得推测各子密钥和由此推出主密钥的难度尽可能大，应保证密钥/密文的严格雪崩效应准则和位独立准则。 函数F的设计准则 函数F：非线性、严格雪崩效应SAC、位独立BIC 16轮迭代，差分攻击需要247个选择明文，255.1个已知明文 严格雪崩效应：输入中任意1位发生变化，输出的任意一位发生变化的可能性为1/2 位独立：对任意i,j,k，当输入中第i位发生变化时，输出中第j位和第k位的变化是彼此无关的 密码学导论--中国科学技术大学

S-boxes的设计准则： 混淆性：S盒输入向量的任何变动在输出方都产生看似随机的变动，两种变动的关系是非线性的，并难以用线性函数近似。 输出比特不应太接近输入比特的一个线性函数 每一行应该包括所有16种比特组合 两个输入相差一个比特，输出必须相差两个比特 前两位不同而最后两位相同的两个输入，输出必须不同 具有相同非零差分的32对输入中，至多有8对输出差分相同 密码学导论--中国科学技术大学

置换P的设计准则：增加扩散性 第i轮迭代时每个S盒输出的四个比特被分布开，以便其中两个影响下一循环的中间比特，两个影响两端的比特 每个S盒输出的四个比特影响下一循环的6个不同的S盒，并且任何两个都不会影响同一个S盒 如果Sj的一个输出比特影响下一循环Sk的中间比特，则Sk的一个输出比特就不能影响Sj的一个中间比特 密码学导论--中国科学技术大学

第二节 高级加密标准AES 密码学导论--中国科学技术大学

一、AES的起源 DES不够安全 3DES（或称T-DES）安全，但速度慢 1997年9月，美国国家标准技术协会（NIST）公开征集新的密码方案 1998年6月，15个候选算法通过第一轮评估 1999年8月，5个候选算法通过第二轮评估 2000年10月，Rijndael算法被选中，作为AES算法 2001年11月，发布最终标准FIPS PUB 197 密码学导论--中国科学技术大学

2000年10月，NIST对Rijndael的最终评估 安全性： 实际安全、密文随机性、数学合理性、公众评价 代价 使用许可、计算效率、存储容量 算法及执行特性 适应各种应用、软硬件适应各种环境、简单 2000年10月，NIST对Rijndael的最终评估 整体安全性、软件执行效率、有限存储空间环境、硬件执行效率、抗攻击性、加解密算法比较、密钥灵活、其它多功能行和适应性、指令级并行操作 密码学导论--中国科学技术大学

二、AES密码标准 AES的参数 特性： Rijndael允许分组长度为128位，192位或256位 对所有已知的攻击免疫 在各种平台上，执行速度快且代码紧凑 设计简单 Rijndael允许分组长度为128位，192位或256位 密钥长度（words/bytes/bits) 4/16/128 6/24/192 8/32/256 分组长度（words/bytes/bits) 轮数 10 12 14 每轮的密钥长度（words/bytes/bits) 扩展密钥长度（words/bytes) 44/176 52/208 60/240 密码学导论--中国科学技术大学

1、AES结构 输入分组以正方形矩阵State描述 密钥扩展为矩阵 进行9/11/13轮迭代 最后一个不完整轮 矩阵State转换为输出分组 轮密钥加 逆行移位 逆字节代换 逆列混淆 第1轮 第9轮 第10轮 行移位 字节代换 列混淆 密钥扩展 w[0,3] w[4,7] w[40,43] w[36,39] 密文 明文 密钥 输入分组以正方形矩阵State描述 密钥扩展为矩阵 进行9/11/13轮迭代 字节代换 行移位 列混淆 轮密钥加 最后一个不完整轮 矩阵State转换为输出分组 不是Feistel结构 密码学导论--中国科学技术大学

输入分组描述 输入分组用以字节为单位的正方形矩阵State描述 然后对State进行迭代运算 最后将State转换为输出分组 in0 in4 out0 out4 out8 out12 out1 out5 out9 out13 out2 out6 out10 out14 out3 out7 out11 out15 密码学导论--中国科学技术大学

在算法的开始和结束都有轮密钥加阶段 每轮迭代中 以不需要密钥的运算用于开始和结束不能增加安全性 轮密钥加实质上是一种Vernam密码，本身不难破译 字节代换、行移位、列混淆三个阶段一起提供 了混淆、扩散和非线性功能。这些阶段不涉及 密钥，其本身并不提供安全性 各阶段均可逆 解密算法与加密算法并不一样，各阶段为逆操 作（轮密钥加阶段算法相同） 行移位 字节代换 轮密钥加 列混淆 密码学导论--中国科学技术大学

2、字节代换 正向字节代换 是简单查表操作 S盒是一个16×16字节的矩阵，包含8bits值的256种可能的变换 密码学导论--中国科学技术大学

S盒的构造： 初始化S盒：x行y列的元素值为(xy)16 每个字节映射为GF(28)中的逆，模(x8+x4+x3+x+1) (00)16映射为(00)16 这保证逆操作可行(xy)16 ←→ (x'y')16 每个字节记为(b7,b6,b5,b4,b3,b2,b1,b0)，做如下代换： 密码学导论--中国科学技术大学

S盒 密码学导论--中国科学技术大学

逆向字节代换 使用逆S盒 逆S盒构造:先做如下代换，再求其逆 可以验证此逆代换是构造S盒的代换的逆 密码学导论--中国科学技术大学

逆S盒 密码学导论--中国科学技术大学

评价： S盒被设计成能够防止各种已有的密码分析攻击 输入位和输出位之间几乎没有相关性 输出值不能利用一个简单数学函数变换输入值得到 变换中常数的选择使得S盒中没有不动点〔S盒(a)=a〕，也没有反不动点〔S盒(a)=ā〕。这里ā指a的反。 S盒是可逆的：逆S盒(S盒(a))=a S盒是不自逆的：S盒(a)≠逆S盒(a) 密码学导论--中国科学技术大学

3、行移位 正向行移位变换 逆向行移位变换 评价 State的第一行不变，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移三个字节 逆向行移位变换 将左移改为右移 评价 将某个字节从一列移到另一列中，确保某列中的4字节扩展到了4个不同的列 密码学导论--中国科学技术大学

4、列混淆 正向列混淆变换 对每列独立进行操作 变换中的乘法定义在GF(28)上的，模(11B)16；加法定义为异或 相当于将State每列视为一个系数在GF(28)上的四次多项式，将其乘上a(x)=(03)16x3+(01)16x2+(01)16x+(02)16，再模(x4+1) s3,ix4+s2,ix3+s1,ix2+s0,ix。可用竖式乘法证明 密码学导论--中国科学技术大学

逆向列混淆变换 使用逆矩阵变换 相当于将State每列视为一个系数在GF(28)上的四次多项式，将其乘上b(x)=(0B)16x3+(0D)16x2+(09)16x+(0E)16，再模(x4+1) b(x)=a-1(x) mod (x4+1) 密码学导论--中国科学技术大学

评价： 变换矩阵的系数是基于在码字间有最大距离的线性编码 正向变换的系数(01)16(02)16(03)16考虑到算法执行效率 系数的乘法至多涉及一次移位、一次异或 各项和需要三次异或、无需GF(28)中的模运算 不考虑逆向变换的算法执行效率。加密被视为比解密重要。 在每列的所有字节中有良好的混淆性 列混淆和行移位变换使得经过几轮迭代后，所有输出位均于所有输入位相关 密码学导论--中国科学技术大学

5、轮密钥加 正向轮密钥加与逆向轮密钥加过程相同 + = 以字节为单位，在GF(28)中的加法 s0,0 s0,1 s0,2 s0,3 w0 w1 w2 w3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 s'2,0 s'2,1 s'2,2 s'2,3 s'3,0 s'3,1 s'3,2 s'3,3 + = 密码学导论--中国科学技术大学

AES单轮结构 密码学导论--中国科学技术大学

6、密钥扩展 密钥描述： 密钥用以字节为单位的矩阵描述，再扩展为一个以字为单位的密钥序列数组 … k0 k4 k8 k12 k1 k5 k9 w0 w1 w2 … w42 w43 密码学导论--中国科学技术大学

密钥扩展（对128位密钥） 输入密钥直接复制到扩展密钥数组的前四个字 w[i]的值依赖于w[i-1]和w[i-4] g是一个复杂函数： 字循环：四个字节循环左移一个字节 字节代换：用S盒对每个字节进行代换 与轮常量Rcon[j]异或 密码学导论--中国科学技术大学

轮常量 右边三个字节总为0：Rcon[j]=(RC[j],0,0,0) RC[1]=1 RC[j]=2·RC[j-1]，乘法定义在域GF(28)上，模(11B)16 j 1 2 3 4 5 6 7 8 9 10 RC[j] 01 02 04 08 20 40 80 1B 36 密码学导论--中国科学技术大学

评价： 知道密钥或轮密钥的部分，不能计算出轮密钥的其他位 是一个可逆变换：知道扩展密钥中任何连续的Nk个字能够重建整个扩展密钥，Nk是构成密钥所需的字数 能够在各种处理器上有效地执行 使用轮常量排除对称性 将密钥的差异性扩散到轮密钥中：密钥的每个位能影响到轮密钥的一些位 足够的非线性：轮密钥的差异与密钥的差异关系复杂 易于描述 密码学导论--中国科学技术大学

7、对应的逆算法 解密过程中各变换的顺序与加密中变换的顺序不同 解密的一个等效版本与加密算法有相同的结构，变换顺序相同（但用逆向变换取代正向变换） 密码学导论--中国科学技术大学

轮密钥加 逆行移位 逆字节代换 逆列混淆 第1轮 第9轮 第10轮 行移位 字节代换 列混淆 密钥扩展 w[0,3] w[4,7] 密文 明文 密钥 轮密钥加 逆行移位 逆字节代换 逆列混淆 第1轮 第9轮 第10轮 密钥扩展 w[0,3] w[4,7] w[40,43] w[36,39] 密文 密钥 明文 密码学导论--中国科学技术大学

逆向行移位和逆向字节代换可交换，不影响结果 轮密钥加和逆向列混淆可交换，但要对密钥扩展进行修改 密码学导论--中国科学技术大学

8、算法实现 密码学导论--中国科学技术大学

在8位处理器上 字节代换可用查表实现，需要256字节 行移位是简单的字节移位，轮密钥加是异或操作 列混淆可以用查表取代，需要3张256字节的表 每轮迭代中，每列需要12次查表（若将3张表合并，只需查4次 ）和4次异或操作 这种紧凑、有效的实现方式可能是选择Rijndael作为AES的最重要因素之一 密码学导论--中国科学技术大学

实现方式非常有利于防止能量攻击和计时攻击 在32位处理器上 将操作定义在32位的字上，预先计算4张256字的表 每轮迭代中，每列需要4次查表和4次异或操作 实现方式非常有利于防止能量攻击和计时攻击 这种紧凑、有效的实现方式可能是选择Rijndael作为AES的最重要因素之一 密码学导论--中国科学技术大学

第三节 分组密码工作模式 密码学导论--中国科学技术大学

为将分组密码应用于各种实际场合，NIST在特别公布的800-38A中推荐5种工作模式 描述 典型应用 电码本(ECB) 用相同的密钥分别对明文组加密 单个数据的安全传输 密文分组链接(CBC) 加密算法的输入是上一个密文组和本次明文组的异或 普通目的的面向分组的传输 认证 密文反馈(CFB) 上一块密文作为加密算法的输入，产生j位伪随机数与明文异或 输出反馈(OFB) 与CFB基本相同，只是加密算法的输入是上一次DES的输出 噪声频道上的数据流的传输（如卫星通信） 计数器(CTR) 每个明文分组都与一个加密计数器相异或。对每个后续分组计数器递增 用于高速需求 密码学导论--中国科学技术大学

一、电码本模式(ECB) 消息分组，各组独自加密 就像一个巨大的密码本，对每个分组进行代换 … Count=1 Count=2 Count=N 加密 P1 K C1 P2 C2 PN CN 解密 … 密码学导论--中国科学技术大学

优点： 缺点： 主要用于发送很少明文分组时 可以并行运算 适用于随机存储的数据 传输错误不扩散，只影响所在块的正确解密 当明文分组重复时，密文也重复 格式化数据，将产生大量重复的密文 若明文分组差别很小，对其破译就变为编码本的破译问题 主要用于发送很少明文分组时 例如，用主密钥加密会话密钥 E Pi K D Ci 密码学导论--中国科学技术大学

分组重放 ECB模式最严重的问题是允许对手选取部分分组进行重放攻击 特别是针对按分组格式化的数据 例如： Email中，若发件人和收件人姓名、邮箱各自独占一个或几个分组时，你的情书会发生什么？ 若银行帐号和用户名占用单独一个或几个分组时，你的钱会去到哪里？ 即使在消息中插入时间戳，只要时间戳独占分组，就可以进行交织攻击 必须辅助以消息认证来保证完整性 密码学导论--中国科学技术大学

二、密文分组链接模式(CBC) 上一次密文分组与本次明文分组异或，再加密 IV是一个初始向量 … 加密 Count=1 Count=2 Count=N 加密 P1 K C1 P2 C2 PN CN … IV CN-1 解密 cN-1 密码学导论--中国科学技术大学

关于初始向量IV IV是公开的，等同于前面有一个虚拟分组 若IV是固定的，则对相同的消息，将得到相同的密文 字典只需建立在一个分组之上 原则上要求用同一个密钥加密的消息所使用的IV不重复 攻击者可以通过篡改接收方的IV，来任意改变接收方的第一分组明文，而不被发觉 建议IV用ECB加密传输，或附加其他认证技术 密码学导论--中国科学技术大学

如某密文分组在传输中出错，错误将影响本分组和下一分组解密的明文，之后自同步（自动恢复正确解密） Ci-1 E Pi K D Ci 前面的明文通过链接影响后面所有的密文 扩散，密文分组依赖与它之前的所有明文分组 可用于大量数据加密传输、认证 注意：第一分组密文不受扩散影响 错误扩散：密文错误将导致的明文错误范围 如某密文分组在传输中出错，错误将影响本分组和下一分组解密的明文，之后自同步（自动恢复正确解密） 密码同步不是信号码字同步。信号码字的错位将导致解码或分组划分错误，所有分组都无法正确解密 密码学导论--中国科学技术大学

三、密文反馈模式(CFB) 用加密算法产生伪随机序列，每次加密s位明文 密文反馈s位进入b位移位寄存器值，做为输入 … 加密 … 解密 CM-1 加密 P1 K C1 … IV 选取s位 b位 s位 P2 C2 PM CM 解密 C1 K P1 … IV 选取s位 b位 s位 加密 C2 P2 PM CM CM-1 密码学导论--中国科学技术大学

标准中，反馈位数取1、8、64、128 优缺点： 适用于低误码率网络中流数据加密、认证 Pi K 选s位 b s E Ci-1 Ci 标准中，反馈位数取1、8、64、128 记为CFB-1，CFB-8，CFB-64，CFB-128 优缺点： 不使用解密算法 可以使用计算量不对称的密码算法 适用于数据以比特/字节为单位准备好的场合 数据流需要暂停以等待加密过程完成，速度受限 传输误码将影响本分组及之后的若干分组，直至误码移出移位寄存器，之后自同步 适用于低误码率网络中流数据加密、认证 密码学导论--中国科学技术大学

安全问题 通过一次已知明文攻击，攻击者即可以对加密算法进行已知明文攻击，也可以制作字典以备将来攻击 即使更换IV，若干个分组后，寄存器内容仅由密文决定 攻击者可以篡改某些密文位来影响明文位。当该操作发生在最后一个分组时，甚至不会被发现 CM-1 加密 P1 K C1 … IV 选取s位 b位 s位 P2 C2 PM CM 密码学导论--中国科学技术大学

四、输出反馈模式(OFB) 与CFB类似，但反馈数据是伪随机序列 … 加密 … 解密 OM-1 P1 K C1 IV 选取s位 b位 s位 PM CM 解密 C1 K P1 … IV 选取s位 b位 s位 加密 C2 P2 PM CM OM-1 密码学导论--中国科学技术大学

优缺点： 适用于噪声环境下流数据加密 反馈与明文无关，传输误码仅影响本比 特位，不影响其它比特，不传递 是一种Vernam密码的变形 Pi K 选s位 b s E Ci 优缺点： 反馈与明文无关，传输误码仅影响本比 特位，不影响其它比特，不传递 是一种Vernam密码的变形 同一密钥下，IV不应当重复使用 可以通过修改密文直接篡改明文 收发双方需要同步 研究表明，应当只使用全分组反馈，例如OFB-64/128 当反馈量与分组大小m相同时，产生密钥流平均周期为2m-1 当反馈量n小于分组大小m时，产生密钥流平均周期仅为2m/2 适用于噪声环境下流数据加密 密码学导论--中国科学技术大学

插入攻击 假设攻击者可以在明文中插入一个已知位，并用同一密钥流再次加密 则攻击者可以依次恢复k2, p2, k3, p3, … 甚至无需预先知道插入位的确切位置，只需从密文相异处开始即可 永远不要用同一个密钥流加密两条不同的消息，IV不可重复 密钥流 k1 k2 k3 … 原始明文 p1 p2 p3 密文 c1 c2 c3 插入明文 p1' c2' c3' 密码学导论--中国科学技术大学

五、计数器模式(CTR) 与OFB类似，但无反馈，加密算法的输入是计数器 加密 … 解密 Counter Counter+1 Counter+N-1 加密 P1 K C1 P2 C2 PN CN … 解密 密码学导论--中国科学技术大学

优缺点： 可用于高速网络数据加密 高效 可随机解密任何密文分组 可证明与其他模式同样安全 结构简单，不需要解密算法 可并行进行各加密单元 可预先处理 可应对突发高速链接 可随机解密任何密文分组 无需顺序解密 可证明与其他模式同样安全 结构简单，不需要解密算法 同一密钥下，计数器值不应重复使用 可用于高速网络数据加密 密码学导论--中国科学技术大学

其他分组密码工作模式 分组链接模式BC 扩散密码分组链接模式 带校验和的密码分组链接 带非线性函数的输出反馈 明文分组链接 明文反馈链接 明文与前面所有的密文分组进行异或 扩散密码分组链接模式 明文分组与前一个明文分组及其密文分组相异或 带校验和的密码分组链接 最后一个明文分组与前面的所有明文分组相异或 带非线性函数的输出反馈 每个分组使用一个子密钥，子密钥由原始密钥反复加密得到 明文分组链接 明文反馈链接 等等 密码学导论--中国科学技术大学

交错技术 在多数分组链接模式中，某一分组的加密/解密依赖于前一分组运算的结果，不利于并行处理 交错技术是将明文分组划分为多个交错的序列，分别进行分组链接，从而实现并行处理 例：当加密器包含四个加密芯片时，可以将明文分组划分为p1,p5,p9,…; p2,p6,p10,…; p3, p7, p11,…; p4, p8, p12,…四个序列，使用四个不同的IV进行并行处理，每个芯片负责一个序列的加密 密码学导论--中国科学技术大学

六、明文填充 明文末尾可能有不足一个分组的数据，需要填充 填充随机数据 填充固定格式数字 其他填充方式 需要在消息开头明确消息实际长度 或约定消息结束标志 填充固定格式数字 例如： [ b1 b2 b3 0 0 0 0 5] 表示有3字节有效数据，填充5个字节 这可能导致需要一个新的分组： 当恰好不需要填充时，仍需补充一个完成分组，以避免歧义 其他填充方式 密码学导论--中国科学技术大学

密文挪用模式（以CBC为例） X并不传输 对ECB和CTR模式，最后一个加密明文块为PN‖X 解密 加密 PN K CN-1 PN-1 X CN X CN-2 密码学导论--中国科学技术大学

可变长分组模式（以CBC为例） 加密 解密 PN K CN PN-1 CN-1 选左侧 j位 CN-2 加密 PN K CN PN-1 注意：解密时最后一次仍是加密运算，其它为解密运算 密码学导论--中国科学技术大学

第四节 其它分组密码标准 密码学导论--中国科学技术大学

一、多重加密 DES不够安全 1、双重DES 设计新算法 使用多个密钥，多次加密 算法： 密钥112位 C=E(K2,E(K1,P)) P=D(K1,D(K2,C)) 密钥112位 一般而言，双重DES不会等效为一次DES 双重DES所对应的映射绝大多数不满足： E(K2,E(K1,P))=E(K3,P) E P X K1 K2 C D C X K2 K1 P 密码学导论--中国科学技术大学

中间相遇攻击 寻找：X=E[K1,P]=D[K2,C] 算法：若已知(P, C)，则 攻击双重DES，平均工作量仅为256 对256个可能的K1加密P，结果存入表中，按X值排序 对256个可能的K2解密C，在表中寻找匹配 如果产生匹配，则用另一个明文密文对检测所得两个密钥 如果两密钥产生正确的密文，则接受为正确 攻击双重DES，平均工作量仅为256 密码学导论--中国科学技术大学

中间相遇攻击检测到正确密钥的概率是1-2-16 对任意明文P，双重DES产生的密文有264种可能，密钥有2112可能。 平均来说，对一个给定的明文P和密文C，满足它的112位密钥的个数是2112/264=248，即虚警为248。 用另一个64位已知明文密文对检测，虚警降低到2-16。 密码学导论--中国科学技术大学

加密、解密交替使用，仅仅为了与单次DES兼容 已用于密钥管理标准ANS X9.17和ISO 8732中。 2、3DES（TDEA） 使用两个密钥的算法： C=E(K1,D(K2,E(K1,P))) P=D(K1,E(K2,D(K1,C))) 加密、解密交替使用，仅仅为了与单次DES兼容 已用于密钥管理标准ANS X9.17和ISO 8732中。 没有可行的攻击方法 使用三个密钥的TDEA已应用在基于Internet的应用：PGP和S/MIME E D P A K1 K2 C B D E C B K1 K2 P A 密码学导论--中国科学技术大学

链接工作模式 单循环CBC 三循环CBC Pn An-1 Pn K1 E Cn-1 An Bn-1 K1, K2 EDE K2 D Bn 密码学导论--中国科学技术大学

二、Blowfish密码 Blowfish，1993年由Bruce Schneier提出，特性： 子密钥和S盒的产生 64比特分组 快速：在32位处理器上加密每字节18时钟周期 紧凑：可在少于5K的内存上运行 简单：结构简单、容易实现 可变的安全性：密钥长度可变，从32位到448位 子密钥和S盒的产生 32位到448位可变长密钥，存储在K数组中[Kj]，用来产生 18个32-bit的子密钥，存储在P数组中[Pj] 4个832的32位项的S盒，存储在[Si,j] 密码学导论--中国科学技术大学

产生P数组和S数组的步骤： 用常数π的小数部分初始化P数组和4个S盒 用K数组（循环使用）对P数组逐位异或 对64位全零分组加密，用所得密文替代P1和P2 对第三步的输出加密，用所得密文替代P3和P4 重复这个过程以更新P和S数组的所有元素，每一步都使用不断变化的Blowfish算法的输出 为产生全部子密钥P和S盒，总共执行521次加密算法，所有产生的P和S存储在存储器中 Blowfish对密钥经常变化的应用不合适，也不适合存储空间有限的应用 密码学导论--中国科学技术大学

Blowfish的加密 两个基本操作: 模232的加和逐位异或 数据被分成左右两部分L0 & R0 for i = 1 to 16 do Ri = Li-1 ⊕ Pi; Li = F[Ri] ⊕ Ri-1; R17 = L16 ⊕ P17; L17 = R16 ⊕ P18; 这里： F[a,b,c,d]=((S1,a + S2,b)⊕ S3,c)+S4,d 密码学导论--中国科学技术大学

整体结构 密码学导论--中国科学技术大学

单轮结构 密码学导论--中国科学技术大学

Blowfish的S盒依赖于密钥，子密钥和S盒通过重复使用Blowfish本身产生，使得各比特彻底纠缠在一起，密码分析非常困难 在每一循环中对数据的两部分进行操作，增大了密码强度 通过选择适当的密钥长度(最长448位)，对穷举攻击来说，Blowfish几乎是不可破的 Blowfish的算法执行是很快的 Blowfish可能是最难破译的常规加密算法 密码学导论--中国科学技术大学

三、国际数据加密算法IDEA 国际数据加密算法IDEA (International Data Encryption Algorithm) 1990年由瑞士苏黎世联邦工业大学的Lai Xuejia和James Messey提出，1992年最终完成 设计原理 128位密钥，64位明文分组，目前尚无破译方法 算法本身倾向于软件实现，加密速度快 密码强度 分组长度：64位 密钥长度：128位 扰乱：密文以复杂交错的方式依赖明文和密钥 扩散：每个明文比特都影响每个密文比特 密码学导论--中国科学技术大学

扰乱(IDEA的三种基本操作) 扩散 实现考虑 基本操作是将两个16位的值映射成一个16位的值 逐位异或， 整数模216(65536)加，⊞ 整数模216+1(65537)乘，⊙ 均为无符号16位整数（乘法中，全零表示216） 例如：0000000000000000⊙1000000000000000 = 1000000000000001 因为：216  215 mod (216+1) = 215 + 1 扩散 由乘积/相加(MA)结构的算法基本构件提供 实现考虑 硬件实现速度高，软件灵活低价 密码学导论--中国科学技术大学

整体结构 密码学导论--中国科学技术大学

单轮结构 密码学导论--中国科学技术大学

子密钥产生 密码学导论--中国科学技术大学

输出变换 密码学导论--中国科学技术大学

四、RC5密码 RC5是Ronald Rivest设计的一种对称加密算法，具有如下特点 适于软件和硬件实现 快速：设计成面向字的简单算法，加快运算速度 可用于字长不同的处理器 迭代次数可变 密钥长度可变 简单，易于实现和确定算法强度 对存储量要求低 安全性高 与数据相关的循环 密码学导论--中国科学技术大学

RC5包含一族密码：RC5-w/r/b 常用版本是RC5-32/12/16 每字32比特，分组大小64比特 12轮迭代 16字节（128比特）密钥 密码学导论--中国科学技术大学

密钥扩展 RC5使用2r+2个子密钥字(w-bits)，存储于数组S[i],i=0..t-1 子密钥产生 根据常数e和Φ(黄金分割比)初始化数组S 密钥字节存放（低位在前）于一个c个字的数组L中 通过一个混合运算将L和S合成为最终的S 密码学导论--中国科学技术大学

子密钥产生 密码学导论--中国科学技术大学

子密钥产生 初始化 混合： Pw=Odd[(e-2)2w]; Qw=Odd[(Φ-2)2w]; Odd[x]表示与x最接近的奇数 S[0]=Pw; for i=1 to t-1 do S[i]=S[i-1]+Qw; 混合： i=j=X=Y=0; do 3×max(t,c) times S[i]=(S[i]+X+Y)<<<3; X=S[i]; i=(i+1) mod t; L[j]=(L[j]+X+Y)<<<(X+Y); Y=L[j]; j=(j+1) mod c; 密码学导论--中国科学技术大学

加密算法 每轮迭代类似于两次DES轮迭代 循环移位是非线性的主要来源 轮数不能过少（例如12-16轮） 明文分组分为A、B两部分 L0 = A + S[0]; R0 = B + S[1]; for i = 1 to r do Li = ((Li-1  Ri-1) <<< Ri-1) + S[2 × i]; Ri = ((Ri-1  Li) <<< Li) + S[2 × i + 1]; 这里“<<<”表示循环左移 每轮迭代类似于两次DES轮迭代 循环移位是非线性的主要来源 轮数不能过少（例如12-16轮） 密码学导论--中国科学技术大学

整体结构 密码学导论--中国科学技术大学

五、SMS4密码 无线局域网产品使用 我国第一个公开商用密码标准 分组长度128比特，密钥长度128比特 加密算法与密钥扩展算法都采用32轮非线性迭代结构 解密算法与加密算法结构相同，轮密钥的使用顺序相反 输入明文为4个字(X0,X1,X2,X3) 输出密文为4个字(Y0,Y1,Y2,Y3) 密钥为4个字(MK0,MK1,MK2,MK3) 扩展轮密钥为rki (i=0,…,31)，每个轮密钥为字 FK=(FK0,FK1,FK2,FK3)为系统参数 CK=(CK0,CK1,…,CK31)为固定参数 密码学导论--中国科学技术大学

加密算法 解密算法 Xi+4 = F(Xi,Xi+1,Xi+2,Xi+3,rki) = XiT(Xi+1Xi+2Xi+3rki) (Y0,Y1,Y2,Y3) = (X35,X34,X33,X32) 解密算法 结构与加密算法相同，但密钥使用顺序相反 Xi T rki Xi+1 Xi+2 Xi+3 Xi+4 密码学导论--中国科学技术大学

轮函数F F(X0,X1,X2,X3,rk)=X0  T(X1  X2  X3  rk) T是可逆变换，由非线性变换τ和线性变换L复合而成 T(.)=L(τ(.)) 非线性变换τ由4个S盒构成 设输入为4个字节(a0,a1,a2,a3)，输出为(b0,b1,b2,b3) (b0,b1,b2,b3)=τ((a0,a1,a2,a3))= (S(a0),S(a1),S(a2),S(a3)) 线性变换L 设输入为B，输出为C，均为字 C=B  (B<<<2)  (B<<<10)  (B<<<18)  (B<<<24) “<<<”是循环左移 每轮4次查表，4次循环移位，8次异或 密码学导论--中国科学技术大学

S盒 8位输入，8位输出 输入的前4位选择行，后4位选择列 密码学导论--中国科学技术大学

密钥扩展算法 (K0,K1,K2,K3) = (MK0  FK0, MK1  FK1, MK2  FK2, MK3  FK3) for i=0,1,…,31 rki=Ki+4= Ki  T'(Ki+1  Ki+2  Ki+3  CKi) 说明： 可以事先计算、存储以备用 T'与加密算法轮函数中的T基本相同，但须将线性变换L变为 L'(B)= B  (B<<<13)  (B<<<23) 密码学导论--中国科学技术大学

系统参数 固定参数 FK0=(A3B1BAC6)16，FK1=(56AA3350)16， FK2=(677D9197)16，FK3=(B27022DC)16 固定参数 设CKi=(cki,0,cki,1,cki,2,cki,3)以4个字节表示，则 cki,j=(4i+j)×7 (mod 256) 00070e15 8 1c232a31 16 383f464d 24 545b6269 1 70777e85 9 8c939aa1 17 a8afb6bd 25 c4cbd2d9 2 e0e7eef5 10 fc030a11 18 181f262d 26 343b4249 3 50575e65 11 6c737a81 19 888f969d 27 a4abb2b9 4 c0c7ced5 12 dce3eaf1 20 f8ff060d 28 141b2229 5 30373e45 13 4c535a61 21 686f767d 29 848b9299 6 a0a7aeb5 14 bcc3cad1 22 d8dfe6ed 30 f4fb0209 7 10171e25 15 2c333a41 23 484f565d 31 646b7279 密码学导论--中国科学技术大学

六、小结 几种分组密码在奔腾机上的速度 算法 每轮时钟周期 轮数 每加密一字节所需时钟周期数 Blowfish 9 16 18 RC5 12 23 DES 45 IDEA 50 8 T-DES 48 108 密码学导论--中国科学技术大学

现代分组密码特征： 可变密钥长度/分组大小/迭代轮数 复合运算，数据/密钥相关的循环移位 基于密钥的S盒子产生 更复杂的密钥扩展算法 每轮处理全部分组数据 变化的非线性函数F 密码学导论--中国科学技术大学

第五节 对称密码系统的密钥 密码学导论--中国科学技术大学

一、对称密码密钥长度 密码系统的安全性取决于算法强度和密钥长度 设计密码系统时需要明确系统的安全级别 算法强度更重要，但很难评估 选择那些久经考验的算法 正确的使用这些算法 密钥长度容易描述，给出安全性的上限 设计密码系统时需要明确系统的安全级别 可以抵御何种攻击？ 本节假设密码算法足够好，仅可进行穷举法攻击 穷举攻击所需时间：设密钥长L，则至多需穷举2L次 密码学导论--中国科学技术大学

密钥长度越大越好？ 算法更安全 密钥管理更加困难 密码算法的计算成本增加 选择足够安全的尽量短的密钥 生成密钥的成本增加 密钥分配管理更困难 分配、更新、存储等等 密码算法的计算成本增加 运算量增加 硬件成本增加 消息传输的延迟增加 选择足够安全的尽量短的密钥 密码学导论--中国科学技术大学

专用硬件攻击 硬件攻击的花费 是否进行硬件攻击，取决于消息的价值 需要专用硬件设备和大规模并行运算 摩尔定律：大约每18个月计算机的计算能力就翻一番 推论：每5年同等性能计算机的价格会下降到原来的10% 是否进行硬件攻击，取决于消息的价值 DES的例子 密码学导论--中国科学技术大学

网络协作攻击 大规模网络合作 运气，破译者的天使 结点数量：数百？数万？数百万？ 1997年对DES的攻击，78000个IP地址参与，96天搜索了1/4的密钥空间 运气，破译者的天使 假设一台机器在一天内破译的概率是p，那么M台机器合作在一天内破译的概率是Mp 对DES，假设一台PC每秒尝试100个密钥，一天尝试8.64×106个密钥，破译概率p≈2.4×10-10。中国4.2亿网民合作，一天破译的概率是10% 若各用户独立随机测试密钥，则攻击减慢，一天内 破译的概率降为1-(1-p)M 密码学导论--中国科学技术大学

利用病毒技术进行网络合作 公开邀请网络上计算机参与穷举？多数人会说“不” 网络入侵？耗时且违法 无恶意的病毒：利用机器空余时间进行计算。 计算机空闲时间很多，多核主机更是如此 获得结果后，启动另一病毒，将正确解“传染”到网络中，或显示： 您的机器中存在严重病毒（或恭喜中奖） 请播打1-800-123-4567向工作人员报告下面数字： XXXX-XXXX-XXXX-XXXX 密码学导论--中国科学技术大学

软件攻击 神经网络/遗传技术：作用不大 生物工程技术 它们擅于处理那些解会逐渐变好的问题 密码问题通常没有提供太多“学习”的机会 生物芯片：让单个生物细胞具有穷举和检验密钥的能力 科幻？ 规模仍然很小 恐龙，约1014个细胞——246个 海藻，体积约10-15m3，制备1m3的海藻大约将覆盖深1m、518平方公里的海洋——234个 例如：DNA技术可以用于求解图的连通问题 密码学导论--中国科学技术大学

量子技术 可以同时测试2N个密钥 量子计算机的难点 短期内似乎还不可能得到应用 量子位数的物理控制 量子位的初值设定，与结果的读取 通用量子门电路的设计 量子门的运算速度必须比“退相干”快得多。 量子的“退相干”会使得量子计算机极不稳定 设每个量子门存在很小的错误概率p，整个系统由N个量子门组成，则成功运行一次所需实验次数为(1/(1-p))N 若p=0.01，N=10000，则成功运行一次需要实验1043次 短期内似乎还不可能得到应用 密码学导论--中国科学技术大学

热力学的局限性 热力学第二定律：封闭系统的热力学变化趋势是熵增加 熵增加，即所有粒子状态的随机性更均匀 信息的表达是随机性的减少，需要提供额外的能量 通过改变系统的状态，记录或消除1位信息所需的能量不少于kT T是系统的绝对温度 k是Boltzman常数，k=1.38×10-16 erg/K 密码学导论--中国科学技术大学

可以断言：对256位密钥进行穷举是绝对行不通的 用理想计算机进行穷举 在宇宙环境温度(3.2K)下设置或清除1位将消耗4.4×10-16 erg能量 若工作于更低的环境下，则必须有额外的能量来运行热泵 太阳每年辐射1.21×1041 erg，可改变2.7×1056 位，即穷举187位 若考虑到宇宙中所有的辐射能量，则可以穷举219位 可以断言：对256位密钥进行穷举是绝对行不通的 此结论是针对传统计算机得出的 密码学导论--中国科学技术大学

二、对称密码系统的密钥分配 端到端加密所涉及的问题规模 N个结点需要的密钥数量是[N(N-1)]/2 1000个结点需要多达50万个密钥 密码学导论--中国科学技术大学

密钥分发问题 密钥分发可以采用的多种方法 对称密钥需要通信双方共享密钥 密钥需要经常更换 如何安全地分配密钥是个关键问题 密码系统的安全漏洞往往出在密钥分配方案上 密钥分发可以采用的多种方法 A产生密钥，并由人员送给B 由一个可信第三方产生密钥，并由人员分发给A和B 若A和B之间使用过密钥，并有一段仍安全的密钥，则可利用这个密钥加密新的密钥并完成密钥交换 若A和B都与可信第三方C有一个秘密信道，则可由 C进行中转，或由C分发来完成密钥分配 密码学导论--中国科学技术大学

分散式密钥管理 要求每个端系统能够与所有潜在的伙伴以安全方式为了会话密钥分配的目的进行通信 对于一个有n个端的系统进行配置，可能需要多达[n(n-1)]/2个主密钥 密码学导论--中国科学技术大学

密钥分配中心(KDC) KDC是可信的 KDC负责给需要的用户分发密钥 每个用户与KDC共享一个密钥（主密钥），用于加密密钥（会话密钥） 密钥的层次式使用 主密钥用于用户与KDC之间联络，传递会话密钥 KDC负责完成密钥的中继或分发 用户之间用会话密钥加密需要传输的数据 每次通信都产生一个新的会话密钥，过后作废 主密钥一般利用非对称密码途径分发，采用非密码手段保存 密码学导论--中国科学技术大学

层次化密钥控制 KDC的问题： 层次化密钥控制 KDC的工作量与用户数量有关 KDC可能受到攻击 使得主密钥分配所涉及的工作量减至最小 将出错或受到破坏的KDC的危害限制在它的本地区域 … …… KDC 用户 密码学导论--中国科学技术大学

会话密钥的使用寿命 会话密钥更换越频繁就越安全 对于面向连接的协议 对于无连接的协议 频繁更换密钥会影响网络性能：通信时间，网路容量 每次会话使用新的密钥 若会话时间很长，需要周期性的改变会话密钥 对于无连接的协议 每次交互使用新的密钥 或者每隔固定时间更新会话密钥 或者对于一定数量的交互使用一个会话密钥 密码学导论--中国科学技术大学

一个密钥分配方案 A和B各自拥有与KDC共享的主密钥KA和KB： 存在重放攻击 A向KDC发出请求，要求得到与B通信的会话密钥 KDC用KA加密传送给A如下内容： 一次性会话密钥KS 原始请求报文 用KB加密的要发给B的会话密钥KS和A的标识符IDA A得到会话密钥KS并将有关信息发给B A和B之间进行认证，并正式秘密通信 存在重放攻击 A再次发出请求时，攻击者假冒KDC返回上一次的结果 使用Nonce（临时交互号：时间戳、计数器或随机数） 密码学导论--中国科学技术大学

修改的密钥分配方案 A没有确认对方是不是B。第3步可以改为E(Kb, Ks||IDA||N3) 第4步B返回E(Ks, N2||N3) 密码学导论--中国科学技术大学

一种对用户透明的密钥管理方案 密码学导论--中国科学技术大学