应用密码学 期末考试 - 文档模板

《应用密码学 期末考试 - 文档模板》由会员分享，可在线阅读，更多相关《应用密码学 期末考试 - 文档模板（15页珍藏版）》请在金锄头文库上搜索。

1、AES 算法分析及实现1 引言引言信息社会的兴起，给全球带来了信息技术飞速发展的契机：信息技术的应用，引起了 人们生产方式、生活方式和思想观念的巨大变化，极大地推动了人类社会的发展和人类文 明的进步。随着人类进入知识经济时代，网络和信息已主见成为人们从事社会活动的基本 工具，但是，由于计算机和网络系统的发放性带来的信息与信息系统的安全问题也拓展到 前所未有的程度。日益增多的对信息系统的非法入侵和破坏活动正在以惊人的速度在全世 界蔓延，给各国信息系统带来巨大的经济损失和安全威胁。 随着信息技术的不断发展，信息安全，网络安全的概念正在与时俱进，逐渐从早期的 通信保密发展到关注信息的保密、完整、可用

2、、可控和不可否认的信息安全。信息与信息 系统，网络与网络系统安全并重，保证信息系统能够安全、可靠、不间断的运行，以提供 必要的服务。近年来，我国在发展知识经济、建设信息基础设施以及中国互联网的建设和 应用方面都有相当大的进步。计算机网络的广泛应用已经对经济、文化、教育、科学的发 展和人类生活质量的提高产生了重要影响，但也带来了一些新的问题。信息系统的的安全 总是面临着日益严重的威胁。一方面是由于互联网的开放性及安全性不足，另一方面是众 多的攻击手段。为了保证信息系统的安全，需要完整的安全保障体系，应具有保护功能、 检测手段、工具的反应以及事故恢复能力。 因而，除了不断完善相应的法律和监督措施，

3、我们更需要自我保护。理论和事实都说 明，密码技术是一种经济、实用而有效的方法，这也是密码技术得到快速发展和广泛应用 的原因。2AES 算法分析算法分析2.1AES 算法产生背景1、AES 是美国国家标准技术研究所NIST旨在取代DES的新一代的加密标准。 NIST 对AES 候选算法的基本要求是:对称分组密码体制;密钥长度支持128 ,192 ,256位;明文分组长度128 位;算法应易于各种硬件和软件实现。 2、1998 年NIST开始AES 第一轮征集、分析、测试,共产生了15 个候选算法。 1999 年3 月完成了第二轮AES 的分析、测试。1999 年8 月NIST 公布了五种算 法(

4、MARS , RC6 ,Rijndael ,Serpent ,Twofish) 成为候选算法。最后, Rijndael ,这个由比利时人设计的算法与其它候选算法在成为高级加密标准 (AES) 的竞争中取得成功,于2000 年10月被NIST宣布成为取代DES 的新一代的 数据加密标准,即AES。 3、Rijndael 作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、 易用和灵活等优点。4、AES 设计有三个密钥长度:128 ,192 ,256 比特2.2AES 算法原理AES 算法是基于置换和代替的。置换是数据的重新排列，而代替是用一个单元数据替换另 一个。AES 使用了几种不同的技术

5、来实现置换和替换。为了阐明这些技术，让我们用 Figure 1 所示的数据讨论一个具体的 AES 加密例子。下面是你要加密的 128 位值以及它 们对应的索引数组：00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 192 位密钥的值是： 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 170 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 2

6、0 21 22 23Figure 2 S-盒（ Sbox ）当 AES 的构造函数（constructor）被调用时，用于加密方法的两个表被初始化。第一个 表是代替盒称为 S-盒。它是一个 1616 的矩阵。S-盒的前五行和前五列如 Figure 2 所 示。在幕后，加密例程获取该密钥数组并用它来生成一个名为 w的密钥调度表，Figure 3 所示。 Figure 3 密钥调度表（Key Sched）w 最初的 Nk (6) 行被作为种子，用原始密钥值（0x00 到 0x17） 。剩余行从种子密钥来 产生。变量 Nk 代表以 32 位字为单位的种子密钥长度。稍后我分析 AES 实现时你将清楚

7、地看到 w 是怎样产生的。 关键是这里现在有许多密钥使用而不只是一个。这些新的密 钥被称为轮密钥（round keys）以将它们与原始种子密钥区别开来。Figure 4 State （态）数组AES 加密例程开始是拷贝 16 字节的输入数组到一个名为 State （态）的 44 字 节矩阵中。 。AES 加密算法 取名为 Cipher，它操作 State，其过程描述的伪代码参见 Figure 5 。在规范中，加密算法实现的一个预备的处理步骤被称为 AddRoundKey（轮密钥加） 。 AddRoundKey 用密钥调度表中的前四行对 State 矩阵实行一个字节一个字节的异或 （XOR）操作

8、，并用轮密钥表 wc,r 异或 输入 Stater,c。举个例子，如果 State 矩阵的第一行保存的字节是 00, 44, 88, cc ，第一列密钥 调度表是 00, 04, 08, 0c ，那么新的 State0,2 值是用 w2,0( 0x08 或 0x80 )异 或 State0,2(0x88)的结果： 1 0 0 0 1 0 0 00 0 0 0 1 0 0 0 XOR1 0 0 0 0 0 0 0 AES 算法的主循环对 State 矩阵执行四个不同的操作，在规范中被称为 SubBytes（字节 替换） 、ShiftRows（行位移变换） 、MixColumns（列混合变换） 和

9、 AddRoundKey。除了每 次循环 AddRoundKey 都被调用并使用密钥调度表的下面四行外，AddRoundKey 与预备处理 步骤中的 AddRoundKey 相同。SubBytes 例程是一个代替操作，它将 State 矩阵中的每个 字节替换成一个由 Sbox 决定的新字节。比如，如果 State0,1的值是 0x40 如果你想找 到它的代替者，你取 State0,1 的值 (0x40) 并让 x 等于左边的数字(4)并让 y 等于右 边的数字(0)。然后你用 x 和 y 作为索引 进到 Sbox 表中寻找代替值，如 Figure 2 所 示。ShiftRows 是一个置换操作

10、，它将 State 矩阵中的字节向左旋转。Figure 6 示范了 ShiftRows 如何操作 State。State 的第 0 行被向左旋转 0 个位置，State 的第 1 行被 向左旋转 1 个位置，State 的第 2 行被向左旋转 2 个位置，而 State 的第 3 行被向左旋转 3 个 位置。Figure 6 对 State 进行 ShiftRows 操作MixColumns 是一个代替操作，它是理解 AES 算法时最具技巧（或者说是最需要动脑筋的 部分）的部分。它用 State 字节列的值进行数学域加和域乘的结果代替每个字节。我将在 下一节中 详细解释专门的域加和域乘细节。假

11、设 State0,1 的值是 0x09，并且列 1 上的其它值分别为 0x60，0xe1 和 0x04， 那么 State0,1的新值计算如下： State0,1 = (State0,1 * 0x01) + (State1,1 * 0x02) +(State2,1 * 0x03) +(State3,1 * 0x01)= (0x09 * 0x01) + (0x60 * 0x02) + (0xe1 * 0x03) +(0x04 * 0x01)= 0x57 此处加法和乘法是专门的数学域操作，而不是平常整数的加法和乘法。SubBytes、ShiftRows、MixColumns 和 AddRoundK

12、ey 四个操作在一个执行 Nr 次的循 环里被调用，Nr 为给定密钥大小的轮数减 1。加密算法使用的轮数要么是 10，12，要么 是 14，这依赖于种子密钥长度是 128 位、192 位还是 256 位。在这个例子中，因为 Nr 等于 12， 则这四个操作被调用 11 次。该迭代完成后，在拷贝 State 矩阵到输出参数前， 加密算法调用 SubBytes、ShiftRows 和 AddRoundKey 后结束。大致说来，AES 加密算法的核心有四个操作。AddRoundKey 使用从种子密钥值中生成 的轮密钥代替 4 组字节。SubBytes 替换用一个代替表 替换单个字节。ShiftRow

13、s 通过旋 转 4 字节行 的 4 组字节进行序列置换。MixColumns 用域加和域乘的组合来替换字节。有限域 GF(28)的加法和乘法正如你所看到的，AES 加密算法使用相当简单明了的技术来代替和置换，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基 于数学（译者注：近世代数）的域论。尤其是 AES 基于有限域 GF(28)。GF(28)由一组从 0x00 到 0xff 的 256 个值组成，加上加法和乘法，因此是(28)。GF 代表伽罗瓦域，以发明这一理论的数学家的名字命名。GF(28) 的一个特性是一个加法或乘 法的操作的结

14、果必须是在0x00 . 0xff这组数中。虽然域论是相当深奥的，但 GF(28) 加法的最终结果却很简单。GF(28) 加法就是异或（XOR）操作。然而，GF(28)的乘法有点繁难。正如你稍后将在 C# 实现中所看到的，AES 的加密和 解密例程需要知道怎样只用七个常量 0x01、0x02、0x03、0x09、0x0b、0x0d 和 0x0e 来 相乘。所以我不全面介绍 GF(28)的乘法，而只是针对这七种特殊情况进行说明。在 GF(28)中用 0x01 的乘法是特殊的；它相当于普通算术中用 1 做乘法并且结果也同 样任何值乘 0x01 等于其自身。现在让我们看看用 0x02 做乘法。和加法的

15、情况相同，理论是深奥的，但最终结果十分 简单。只要被乘的值小于 0x80，这时乘法的结果就是该值左移 1 比特位。如果被乘的值大 于或等于 0x80，这时乘法的结果就是左移 1 比特位再用值 0x1 b 异或。它防止了“域溢出” 并保持乘法的乘积在范围以内。 一旦你在 GF(28)中用 0x02 建立了加法和乘法，你就可以用任何常量去定义乘法。用 0x03 做乘法时，你可以将 0x03 分解为 2 的幂之和。为了用 0x03 乘以任意字节 b， 因为 0x03 = 0x02 + 0x01，因此： b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b *

16、0x01)这是可以行得通的， 因为你知道如何用 0x02 和 0x01 相乘和相加，同哩，用 0x0d 去乘以任意字节 b 可以这样 做： b * 0x0d = b * (0x08 + 0x04 + 0x01) = (b * 0x08) + (b * 0x04) + (b * 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01)在加 解密算法中，AES MixColumns 例程的其它乘法遵循大体相同的模式，如下所示： b * 0x09 = b * (0x08 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x01)b * 0x0b = b * (0x08 + 0x02 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02) +