现代密码学理论与实践 第5章高级数据加密标准AES Fourth Edition by William Stallings Slides by 杨寿保 syang@ustc.edu.cn http://staff.ustc.edu.cn/~syang 2012年9月 2018/11/16 现代密码学理论与实践05
高级加密标准AES要点 AES是一种分组密码，用以取代DES的商业应用。其分组长度为128位，密钥长度为128位、192位或256位。 AES没有使用Feistel结构，每轮由四个独立的运算组成：字节代换、置换、有限域上的算术运算，以及与密钥的异或运算。 2018/11/16 现代密码学理论与实践05
AES的评估准则 AES的起源 因为DES的不安全，建议用3DES，密钥168位，抵御密码分析攻击。但是3DES用软件实现速度较慢，分组短，仅64位。 美国国家标准技术协会NIST在1997年征集新标准，要求分组128位，密钥128、192或256位。 15种候选算法在1998年6月通过了第一轮评估，仅有5个候选算法在1999年8月通过了第二轮评估。 2000年10月，NIST选择Rijndael作为AES算法， Rijndael的作者是比利时的密码学家Joan Daemen博士和Vincent Rijmen博士。 2001年11月，NIST完成评估并发布了最终标准 FIPS PUB 197。 2018/11/16 现代密码学理论与实践05
AES的评估 AES评估准则的三大类别 安全性：指密码分析方法分析一个算法所需的代价 算法和执行特征：算法灵活性、适合于多种硬件和软件方式的实现、简洁性，便于分析安全性 2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
AES评估准则 一般安全性 软件实现 受限空间环境 硬件实现 对执行的攻击 加密与解密 密钥灵活性 其他的多功能性和灵活性 依赖于密码学界的公共安全分析 软件实现 软件执行速度，跨平台执行能力及密钥长度改变时速度变化 受限空间环境 在诸如智能卡中的应用 硬件实现 硬件执行提高执行速度或缩短代码长度 对执行的攻击 抵御密码分析攻击 加密与解密 密钥灵活性 快速改变密钥长度的能力 其他的多功能性和灵活性 指令级并行执行的潜力 2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
NIST对AES的要求 对称密钥分组密码 128位分组，密钥长度可以分别是128/192/256位 要求比Triple-DES更安全和更快 至少能够安全工作20-30年 提供完整的规范说明和设计细节 能够用C或Java实现 NIST公布了所有提交的算法和不保密的分析资料，最终通过评估，选择了Rijndael 2018/11/16 现代密码学理论与实践05
AES密码 AES的分组长度为128位，密钥长度可以是 128/192/256的任意一种 未采用Feistel密码结构而是用迭代方式 数据分成4组，每组4字节 每一轮对整个分组进行操作 Rijndael具有如下特性 对所有已知的攻击具有免疫性 在各种CPU平台上其执行速度快且代码紧凑 设计简单 Rijndael is an academic submission, based on the earlier Square cipher, from Belgium academics Dr Joan Daemen and Dr Vincent Rijmen. It is an iterative cipher (operates on entire data block in every round) rather than feistel (operate on halves at a time). cf IDEA cipher 2018/11/16 现代密码学理论与实践05
AES的参数 2018/11/16 现代密码学理论与实践05
AES的加密与解密 2018/11/16 现代密码学理论与实践05
AES的数据结构 2018/11/16 现代密码学理论与实践05
AES的结构 非Feistel结构 密钥被扩展成由44个32位字组成的数组w[i] 一个混淆和三个代换 算法结构非常简单 行移位：一个简单的置换 列混淆：利用在域GF(28)上的算术特性的代换 轮密钥加：利用当前分组和扩展密钥的一部分进行按位XOR 算法结构非常简单 仅在轮密钥加密阶段中使用密钥 轮密钥加配合其他三个混淆的交替使用提供了安全性 每个阶段均可逆 解密按逆序方式使用扩展密钥，但是算法加密不一样 一旦将四个阶段求逆，可以证明解密函数可以恢复明文 加密和解密过程的最后一轮均只包括三个阶段 2018/11/16 现代密码学理论与实践05
Rijndael密码 128位数据分成4组，每组4字节(state) 每个state执行9/11/13轮操作: 行移位变换(在组和列之间变换) 列混淆变换(使用组的矩阵乘) 轮密钥加(用密钥异或state) 所有运算均可通过异或和查表来完成，因此非常快而且效率高。 Data is written into the state matrix by columns; this matrix is manipulated at stage of the en/decryption process, and is then finally copied to the output. The key is expanded into 44/52/60 lots of 32-bit words (see later), with 4 used in each round. The data computation then consists of an “add round key” step, then 9/11/13 rounds with all 4 steps, and a final 10th/12th/14th step of byte subs + mix cols + add round key. All steps are easily reversed. Note only the “add round key” step makes use of the key and obscures the result, hence MUST be used at start and end of each round, since otherwise could undo effect of other steps. But the other steps provide confusion/diffusion/non-linearity. ie can look at cipher as a series of XOR with key then scramble/permute block repeated. This is efficient and highly secure it is believed. 2018/11/16 现代密码学理论与实践05
AES的一轮加密过程 2018/11/16 现代密码学理论与实践05
字节代替变换 对每个字节做一简单的替换 使用一个16x16字节的表，其中包含了所有256种8位的置换值 每个字节的左4位选择行，右4位选择列来查表替换 比如字节{95}由第9行第5列所在字节替换 也就是字节{2A} S盒使用GF(28)中定义的所有转换值来构建 能够抵御所有已知攻击 There is a single 8-bit wide S-box used on every byte. This S-box is a permutation of all 256 8-bit values, constructed using a transformation which treats the values as polynomials in GF(28) – however it is fixed, so really only need to know the table when implementing. Decryption requires the inverse of the table. 2018/11/16 现代密码学理论与实践05
AES的字节层操作 字节代替变换和轮密钥加变换 2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
行移位变换 正向行移位变换 逆向行移位变换进行相反的移位以实现解密 因为State是按列处理的，行移位变换就把字节在列之间进行了置换 This step provides “permutation” of the data, whereas the other steps involve substitutions. 2018/11/16 现代密码学理论与实践05
2018/11/16 现代密码学理论与实践05
列混淆变换 正向列混淆变换对每列独立进行操作 每列中的每个字节被映射为一个新值，由该列中的4个字节通过函数变换得到 这个变换由以下基于State的矩阵乘法表示，使用素多项式m(x) =x8+x4+x3+x+1, GF(28) 逆向列混淆变换也由矩阵乘法定义 This step is also a substitution, but one involving ALL values in a column. Designed as a matrix multiplication where each byte is treated as a polynomial in GF(28). The inverse used for decryption involves a different set of constants. The constants used are based on a linear code with maximal distance between code words – this gives good mixing of the bytes within each column. Combined with the “shift rows” step provides good avalanche, so that within a few rounds, all output bits depend on all input bits. 2018/11/16 现代密码学理论与实践05
轮密钥加变换 正向轮密钥加变换中128位的State按位与128位的秘密钥异或(XOR) 都是基于State列的操作，即把State的一列中的4个字节与轮密钥的1个字进行异或 逆向轮密钥加变换与正向轮密钥加变换相同，因为异或操作是其本身的逆 轮密钥加变换非常简单，却能影响State中的每一位 2018/11/16 现代密码学理论与实践05
AES的密钥扩展 AES密钥扩展算法的输入是4字(16字节)，输出是44字(或者52字, 或60字)，每字32位 输入密钥直接被复制到扩展密钥数组的前4个字 然后每次用4个字填充扩展密钥数组余下的部分 这样的设计能够抵御已知攻击 Key expansion is designed to be simple to implement, but by using round constants break symmetries, and make it much harder to deduce other key bits if just some are known (but once have as many consecutive bits as are in key, can then easily recreate the full expansion). 2018/11/16 现代密码学理论与实践05
对应的逆算法 AES的解密算法和加密算法不同，主要是解密中变换的顺序与加密中变换的顺序不同 但是可以定义一个等价的逆密码算法，采用与加密算法一样的步骤 每一步都是逆向进行的 密钥的安排不同于加密 By constructing an equivalent inverse cipher with steps in same order as for encryption, can derive a more efficient implementation. Clearly swapping the byte substitutions and shift rows has no effect, since work just on bytes. Swapping the mix columns and add round key steps requires the inverse mix columns step be applied to the round keys first – this makes the decryption schedule a little more complex with this construction. 2018/11/16 现代密码学理论与实践05
AES的实现 可以在8位处理器上非常有效地实现 可以在32位处理器上非常有效地实现 字节代换是在字节级别上进行操作的，只要求一个256字节的表 行移位是简单的移字节操作 轮密钥加是按位异或操作 列混淆变换要求在域GF(28)上的乘法，所有的操作都是基于字节的，只要简单地查表即可 可以在32位处理器上非常有效地实现 将操作定义在32位的字上 事先准备好4张256字的表 在每一轮中通过查表并加上4次异或即可计算每一列的值 需要16Kb空间来存储这4张表 2018/11/16 现代密码学理论与实践05
Summary We have considered: the AES selection process the details of Rijndael – the AES cipher looked at the steps in each round the key expansion implementation aspects 2018/11/16 现代密码学理论与实践05