高级加密标准AES外文翻译.doc

《高级加密标准AES外文翻译.doc》由会员分享，可在线阅读，更多相关《高级加密标准AES外文翻译.doc（33页珍藏版）》请在三一办公上搜索。

1、加密它：用新的高级加密标准（AES）保持你的数据安全James McCaffrey 摘要 AES（The Advanced Encryption Standard）是美国国家标准与技术研究所用于加密电子数据的规范。它被预期能成为人们公认的加密包括金融、电信和政府数字信息的方法。本文展示了AES的概貌并解析了它使用的算法。包括一个完整的C#实现和加密.NET数据的举例。在读完本文后你将能用AES加密、测试 基于AES的软件并能在你的系统中使用AES加密。美国国家标准与技术研究所(NIST)在2002年5月26日建立了新的高级数据加密标准(AES)规范。本文中我将提供一个用C#编写的的能运行的 A

2、ES 实现，并详细解释到底什么是 AES 以及编码是如何工作的。我将向您展示如何用 AES 加密数据并扩展本文给出的代码来开发一个商业级质量的 AES 类。我 还将解释怎样把 AES 结合到你的软件系统中去和为什么要这么做，以及如何测试基于 AES 的软件。AES 是一个新的可以用于保护电子数据的加密算法。明确地说，AES 是一个迭代的、对称密钥分组的密码，它可以使用128、192 和 256 位密钥，并且用 128 位（16字节）分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据 的位数与输入数据相同。迭代加密使用一个循环结

3、构，在该循环中重复置换（permutations ）和替换(substitutions）输入数据。Figure 1 显示了 AES 用192位密钥对一个16位字节数据块进行加密和解密的情形。AES算法概述 AES 算法是基于置换和代替的。置换是数据的重新排列，而代替是用一个单元数据替换另一个。AES 使用了几种不同的技术来实现置换和替换。为了阐明这些技术，让我们用 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

4、 7 8 9 10 11 12 13 14 15192位密钥的值是：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 20 21 22 23Figure 2 S-盒（ Sbox ）当 AES 的构造函数（constructor）被调用时，用于加密方法的两个表被初始化。第一个表是代替盒称为S-盒。它是一个1616的矩阵。S-盒的前五行和前五列如 Figure 2 所示。在幕后，加密例程获取该密钥数组并用它来生

5、成一个名为w的密钥调度表，Figure 3 所示。Figure 3 密钥调度表（Key Sched）w 最初的 Nk (6) 行被作为种子，用原始密钥值（0x00 到0x17）。剩余行从种子密钥来产生。变量 Nk 代表以 32 位字为单位的种子密钥长度。稍后我分析 AES 实现时你将清楚地看到 w 是怎样产生的。 关键是这里现在有许多密钥使用而不只是一个。这些新的密钥被称为轮密钥（round keys）以将它们与原始种子密钥区别开来。Figure 4 State （态）数组AES 加密例程开始是拷贝 16 字节的输入数组到一个名为 State （态）的 44 字节矩阵中。（参见 Figure

6、4）。AES 加密算法 取名为 Cipher，它操作 State，其过程描述的伪代码参见 Figure 5 。在规范中，加密算法实现的一个预备的处理步骤被称为 AddRoundKey（轮密钥加）。AddRoundKey 用密钥调度表中的前四行对 State 矩阵实行一个字节一个字节的异或（XOR）操作，并用轮密钥表 wc,r 异或 输入 Stater,c。举个例子，如果 State 矩阵的第一行保存的字节是 00, 44, 88, cc ，第一列密钥调度表是 00, 04, 08, 0c ，那么新的 State0,2 值是用 w2,0( 0x08 或 0x80 )异或 State0,2(0x8

7、8)的结果：1 0 0 0 1 0 0 00 0 0 0 1 0 0 0 XOR1 0 0 0 0 0 0 0AES 算法的主循环对 State 矩阵执行四个不同的操作，在规范中被称为 SubBytes（字节替换）、ShiftRows（行位移变换）、MixColumns（列混合变换） 和 AddRoundKey。除了每次循环 AddRoundKey 都被调用并使用密钥调度表的下面四行外，AddRoundKey 与预备处理步骤中的 AddRoundKey 相同。SubBytes 例程是一个代替操作，它将 State 矩阵中的每个字节替换成一个由 Sbox 决定的新字节。比如，如果 State0,

8、1的值是 0x40 如果你想找到它的代替者，你取 State0,1 的值 (0x40) 并让 x 等于左边的数字(4)并让 y 等于右边的数字(0)。然后你用 x 和 y 作为索引 进到 Sbox 表中寻找代替值，如 Figure 2 所示。ShiftRows 是一个置换操作，它将 State 矩阵中的字节向左旋转。Figure 6 示范了 ShiftRows 如何操作 State。State 的第0行被向左旋转0个位置，State 的第1行被向左旋转1个位置，State 的第2行被向左旋转2个位置，而 State 的第3行被向左旋转3个 位置。Figure 6 对 State 进行 Shif

9、tRows 操作MixColumns 是一个代替操作，它是理解 AES 算法时最具技巧（或者说是最需要动脑筋的部分）的部分。它用 State 字节列的值进行数学域加和域乘的结果代替每个字节。我将在下一节中 详细解释专门的域加和域乘细节。假设 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 * 0x

10、02) + (0xe1 * 0x03) +(0x04 * 0x01)= 0x57此处加法和乘法是专门的数学域操作，而不是平常整数的加法和乘法。SubBytes、ShiftRows、MixColumns 和 AddRoundKey 四个操作在一个执行 Nr 次的循环里被调用，Nr 为给定密钥大小的轮数减 1。加密算法使用的轮数要么是10，12，要么是14，这依赖于种子密钥长度是128位、192 位还是 256 位。在这个例子中，因为 Nr 等于12， 则这四个操作被调用11次。该迭代完成后，在拷贝 State 矩阵到输出参数前，加密算法调用 SubBytes、ShiftRows 和 AddRou

11、ndKey 后结束。大致说来，AES 加密算法的核心有四个操作。AddRoundKey 使用从种子密钥值中生成的轮密钥代替 4 组字节。SubBytes 替换用一个代替表 替换单个字节。ShiftRows 通过旋转 4字节行 的 4 组字节进行序列置换。MixColumns 用域加和域乘的组合来替换字节。有限域GF(28)的加法和乘法正如你所看到的，AES 加密算法使用相当简单明了的技术来代替和置换，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于数学（译者注：近世代数）的域论。尤其是 AES 基于有限域GF(28)。GF(28)由

12、一组从 0x00 到 0xff 的256个值组成，加上加法和乘法，因此是(28)。GF代表伽罗瓦域，以发明这一理论的数学家的名字命名。GF(28) 的一个特性是一个加法或乘法的操作的结果必须是在0x00 . 0xff这组数中。虽然域论是相当深奥的，但GF(28)加法的最终结果却很简单。GF(28) 加法就是异或（XOR）操作。然而，GF(28)的乘法有点繁难。正如你稍后将在 C# 实现中所看到的，AES的加密和解密例程需要知道怎样只用七个常量 0x01、0x02、0x03、0x09、0x0b、0x0d 和 0x0e 来相乘。所以我不全面介绍GF(28)的乘法，而只是针对这七种特殊情况进行说明。

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

14、1，因此：b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b * 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

15、* 0x09 = b * (0x08 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x01)b * 0x0b = b * (0x08 + 0x02 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02) + (b * 0x01)b * 0x0e = b * (0x08 + 0x04 + 0x02) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x02)总之，在GF(28)中，加法是异或操作。其乘法将分解成加法和用0x02做的乘法，而用0x02做的乘法是

16、一个有条件的左移1比特位。AES规范中包括大量 有关GF(28)操作的附加信息。密钥扩展AES加密和解密算法使用了一个由种子密钥字节数组生成的密钥调度表。AES规范中称之为密钥扩展例程（KeyExpansion）。从本质上讲，从一个原始密钥中生成多重密钥以代替使用单个密钥大大增加了比特位的扩散。虽然不是无法抵御的困难，但理解 KeyExpansion 仍是 AES 算法中的一个难点。KeyExpansion 例程高级伪代码如下所示： KeyExpansion(byte key, byte4 w) copy the seed key into the first rows of w for ea

17、ch remaining row of w use two of the previous rows to create a new row “用前面两行来产生一个新行”（“use two of the previous rows to create a new row”）的例程用到了两个子 例程，RotWord 和 SubWord 以及一个名为“Rcon”的常数表（作为“轮常数”）。让我们先来逐个看一下这三东西，然后再回到整个 KeyExpansion 的讨论中来。RotWord 例程很简单。它接受一个4个字节的数组并将它们向左旋转一个位置。因为轮调度表 w 有四列，RotWord 将 w的

18、1行左旋。注意 KeyExpansion 使用的这个 RotWord 函数与加密算法使用的 ShiftRows （行位移变换）例程非常相似，只是它 处理的是单行密钥调度 w，而不是整个加密状态表 State。SubWord 例程使用替换表 Sbox 对一给定的一行密钥调度表 w 进行逐字节替换。KeyExpansion 操作中的替换实际上就像在加密算法中的 替换一样。被代替的输入字节被分成 (x,y) 对，它被当作进入替换表 Sbox 的索引。举例来说，0x27的代替结果是 x2 和 y7，并且 Sbox2,7 返回 0xcc。KeyExpansion 例程使用一个被称为轮常数表的数组 Rco

19、n。这些常数都是4个字节，每一个与密钥调度表的某一行相匹配。AES 的 KeyExpansion 例程需要11个轮常数。你可以在 Figure 7 中看到这些常数清单。每个轮常数的最左边的字节是GF(28)域中2的幂次方。它的另一个表示方法是其每个值是前一个值乘上0x02，正如前一部分讨论 GF(28) 乘法 时所描述的那样。注意 0x80 0x02 = 0x1b 是 0x80 左移1个比特位后紧接着与 0x1b 进行异或，如前所述。现在让我们更进一步看看 KeyExpansion 内幕中的循环。这里所用的伪码比以前更为详细，这个循环是：for (row = Nk; row 操作符右移 4 位

20、将得到 x 索引，并且与 0000 1111 进行逻辑与得到 y 值。虽然有些长，但比实际代码更可读，我可以象下面这样：int x = word0 4;int y = word0 & 0x0f;byte substitute = this.Sboxx,y;result0 = substitute;代替我原来用的代码：result0 = this.Sbox word0 4, word0 & 0x0f ;总的来说，AES 构造函数接受一个密钥的长度为128，192 或 256 位和一个字节数组种子密钥值。构造函数为输入块长度，种子密钥长度 以及加密算法的轮数赋值，并将种子密钥拷贝到一个名为 key

21、 的数据成员中。构造函数还创建了四个表：两个由加密和解密方法使用的替换表，一个轮常数表，和一个轮密钥的密钥调度表。用C#编写的 AES Cipher 方法Cipher方法如 Figure 11 所示。它真的非常简单，因为它分出了大部分的工作给私有方法AddRoundKey, SubBytes, ShiftRows 和 MixColumns。Cipher 方法以拷贝明文输入数组到状态矩阵 State 为开始。最初调用 AddRoundKey 之后，Cipher 方法比总轮数少迭代一次。在最后一轮时，正如规范中所说的那样，MixColumns 调用被省略了。AddRoundKey 和 SubByt

22、es 私有方法的代码如 Figure 12 所示。AddRoundKey 方法需要知道它处在那一轮，以便它正确引用4行密钥调度数组 w。请注意 Stater,c 是用 wc,r 来异或并不是wr,c。SubBytes 方法从输入字节中提取索引，与 KeyExpansion 方法中所用的右移4位和 0x0f 屏蔽技术相同。ShiftRows 方法的代码如 Figure 13 所示。回想一下，ShiftRows（可能叫做 RotateRows 更好）将 row0 向左旋转 0 个位置，将 row1 向左旋转 1 位置等等。把 State 拷贝到 temp 矩阵之后，然后用下面的这行代码实现转换：t

23、his.Stater, (c + r) % Nb = tempr,c;这里利用%操作符的优点抱合一行。MixColumns 方法(Figure 14)用GF(28)加和乘，以字节列中所有其它值的线性组合对每一个字节进行替换。乘法所用的常量系数基于域论的，并且是0x01, 0x02或 0x03中的任意一个值。给定某一列 c ，其替代式如下：State0,c = 0x02 * State0,c +0x03 * State1,c +0x01 * State2,c +0x01 * State3,c State1,c = 0x01 * State0,c +0x02 * State1,c+0x03 * S

24、tate2,c+ 0x01 * State3,cState2,c = 0x01 * State0,c + 0x01 * State1,c +0x02 * State2,c +0x03 * State3,cState3,c = 0x03*State0,c+0x01 * State1,c+0x01*State2,c+0x02 * State3,c这些表达式稍微有些长，因此我决定编写返回 GF(28)与 0x01,0x02 和 0x03 之乘积的私有辅助函数。这些辅助函数非常短。例如，一个字节 b 被 0x03 域乘的代码如下： return (byte) ( (int)gfmultby02(b)

25、(int)b );正如我前面讨论的，被 0x02 乘是所有 GF(28) 乘法的基本操作。我调用了我的 gfmultby02 方法，我改变了使用与规范相同的方法命名惯例，规范上称此例程为 xtime。Cipher 方法其输入反复应用四个操作来产生加密的输出。AddRoundKey 用源于单个原始种子密钥的多重轮密钥来替代字节。SubBytes 用某个替换表中的值替代字节。ShiftRows 用移动字节行置换字节，而 MixColumns 用某一列的域加和乘法值来替代字节。用C#编写 AES InvCipher 方法AES 解密算法背后的基本原则很简单：解密一个加密块，也就是以反向顺序还原（Un

26、do）每个操作。尽管这是基本概念，但仍有几个细节要处理。AES规范称解密例程为 InvCipher，而不是 Decipher 或 Decrypt 中的一个。这是 AES 背后的数学基础的反映，它基于可逆的数学操作。如果你将这个代码和 Cipher 代码比较的话，你会看到它比你预期的漂亮很多，但是有两点例外。首先，在 InvCipher 方法中逆方法调用（如 InvSubBytes）顺序并不完全与在 Cipher 方法中相应调用（如 SubBytes）的逆向顺序正好相同。其次，InvCipher 调用的是一个 AddRoundKey 方法而不是 InvAddRoundKey 方法。值得注意的是

27、InvCipher 算法用密钥调度表并不是从较高编号的索引处开始向下处理至第0行。InvSubBytes，InvShiftRows 和 InvMixColumns 方法的代码和与之有关的 SubBytes，ShiftRows和 MixColumns 方法的代码非常接近。InvSubBytes 方法几乎就是 SubBytes 方法，只是它用逆替换表 iSbox 而不是 Sbox 表。正如你可能猜测到的，iSbox 就是还原任何被 Sbox 处理的对应操作。比如，如果你有字节 b 等于 0x20，并在 Sbox 中找到其代替值，你得到 0xb7。如果你在 iSbox 中找到 0xb7的替代值，你便

28、可得到 0x20。相似地，InvShiftRows 方法还原 ShiftRows 方法 row0 被右移了 0 个位置，row1 被右移了 1个位置，row2 被右移了 2 个位置，而 row3 被右移了 3个位置。InvMixColumns 方法还原 MixColumns 的工作，但没有用显而易见的方法。回想一下，MixColumns 用原始字节列中的字节线性组合替换状态矩阵中的每个字节，并且系数是 0x01，0x02，和 0x03，域论再一次得到应用。它证明逆运算是相似的，只是被 0x09，0x0b，0x0d 和 0x0e 乘，如下所示： State0,c = 0x0e * State0,

29、c +0x0b * State1,c + 0x0d * State2,c + 0x09 * State3,cState1,c = 0x09 * State0,c +0x0e * State1,c +0x0b * State2,c +0x0d * State3,cState2,c = 0x0d * State0,c +0x09 * State1,c +0x0e * State2,c +0x0b * State3,cState3,c = 0x0b * State0,c +0x0d * State1,c +0x09 * State2,c +0x0e * State3,c 对于 MixColumns

30、方法，我决定专门写一个辅助函数，而不是内联展开已经较长的表达式或写一个普通的乘法辅助函数。让我向你展示一下我示如何编写这个任何字节 b 被常数 0x0e (在10进制中的14)乘的函数，像任何数字一样，数字 14 可以被表示成 2 的幂的和，因此，14 等于 2 + 4 + 8。并且 4 等于 2 的平方，8 等于 2 的立方，你可以将14表示为 2 + 22 + 23。记住加法就是 GF(28)中上的异或()，既然我已经有了 gfmultby02 函数，我可以用它得到我的结果： return (byte)( (int)gfmultby02(gfmultby02(gfmultby02(b) /

31、* 23 + */ (int)gfmultby02(gfmultby02(b) /* 22 + */ (int)gfmultby02(b) ); /* 2 */用于 AES 加密算法的所有的操作都是可逆的，因此解密算法本质上是加密的所有操作的倒转。使用 AES 类用C#实现 AES 的特色之一就简单。看看 Figure 15，它是我用来生成输出 Figure 1 的代码。声明了 16 字节 明文输入硬代码值和 24 字节(192位)的种子密钥后，一个 AES 对象被初始化，加密 Cipher 方法 将明文加密成为密文，然后再用 InvCipher 将密文解密。非常清楚和简单。因为 AES 对象

32、针对字节数组进行处理，你可以轻松地用它处理.NET的其它数据类型。我创建了一个基于 Windows 的小Demo程序，它接受一个 单纯的字符串有 8 个字符 (16-byte) ，对它进行加密和解密处理。运行画面如 Figure 16。Figure 16 加密 Demo 程序因为加密和解密例程都需要知道用户定义的密钥长度，我把它当作一个类范围的变量来声明，像这样： private Aes.KeySize keysize;注意种子密钥并不是由用户定义的。这个 demo 程序用一个“空密钥”（null key）作为种子密钥，通过为构造函数提供一个哑参数 new byte16 使得它全部由零字节组成

33、。哑参数的长度是不相关的，因为种子密钥还是要被初始化为零。空密钥加密和解密是一个容易和有效的办法来阻止外界对数据偶然的检查。在 System.Text 中的 Encoding.Unicode.GetBytes和Encoding.Unicode.GetString 方法使得将一个.NET 字符串转换成一个字节数组变得非常容易，反之亦然。实现选择现在让我们看看本文 AES 实现中出现的一些重要的变量，本文提供的代码可能出现的扩展，以及针对 AES 的密码分析学攻击。和我曾经处理的任何代码一样，AES 算法也可以用其它可选的途径来实现。为什么这很重要呢？AES 被试图广泛应用于各种系统，从只有很少内

34、存容量的智能卡（smart cards）到大型的多处理器主机系统。在许多情况下，性能是关键因素，并且有时内存或处理器资源是有限的。事实上，AES 的每个例程都能针对非常昂贵的内存资源进行性能优化，反之亦然。比如，为替换表Sbox 分配 256 个值看起来好像很简单直白。但是，这些值是基于 GF(28) 理论的，它们都可以用编程方式来生成。逆向替换表和轮常数表也是如此。可选实现另外一个有趣的可能性是 Cipher 和 InvCipher 方法所用的 GF(28) 乘法。我的实现代码是一个被 0x02 乘的基本函数，而后是六个调用 gfmultby02 的附加函数。另一个可能性应该是写一个一般的乘法函数