AES对称加密算法原理

======中文翻译（后面有英文原版）=========================

原著：James McCaffrey

翻译：
http://blog.csdn.net/guo2777/archive/2007/09/19/1791399.aspx

原文出处：

本文的代码下载： (143KB)

本文假设你熟悉 C# 和 位（bit）操作。

摘要

　 　AES（The Advanced Encryption Standard）是美国国家标准与技术研究所用于加密电子数据的规范。它被预期能成为人们公认的加密包括金融、电信和政府数字信息的方法。本文展示了 AES的概貌并解析了它使用的算法。包括一个完整的C#实现和加密.NET数据的举例。在读完本文后你将能用AES加密、测试 基于AES的软件并能在你的系统中使用AES加密。
　

---

　　美国国 家标准与技术研究所(NIST)在2002年5月26日建立了新的高级数据加密标准(AES)规范。本文中我将提供一个用C#编写的的能运行的 AES 实现，并详细解释到底什么是 AES 以及编码是如何工作的。我将向您展示如何用 AES 加密数据并扩展本文给出的代码来开发一个商业级质量的 AES 类。我 还将解释怎样把 AES 结合到你的软件系统中去和为什么要这么做，以及如何测试基于 AES 的软件。
　　注意本文提供的代码和基于本文的任何其它的实现都在联邦加密模块出口控制的适用范围之内（详情请参看 Commercial Encryption Export Controls ）。
　 　AES 是一个新的可以用于保护电子数据的加密算法。明确地说，AES 是一个迭代的、对称密钥分组的密码，它可以使用128、192 和 256 位密钥，并且用 128 位（16字节）分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据 的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换（permutations ）和替换(substitutions）输入数据。Figure 1 显示了 AES 用192位密钥对一个16位字节数据块进行加密和解密的情形。


Figure 1 部分数据

AES算法概述

　 　AES 算法是基于置换和代替的。置换是数据的重新排列，而代替是用一个单元数据替换另一个。AES 使用了几种不同的技术来实现置换和替换。为了阐明这些技术，让我们用 Figure 1 所示的数据讨论一个具体的 AES 加密例子。下面是你要加密的128位值以及它们对应的索引数组：

00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
0 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 17
0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23

Figure 2 S-盒（ Sbox ）

当 AES 的构造函数（constructor）被调用时，用于加密方法的两个表被初始化。第一个表是代替盒称为S-盒。它是一个16×16的矩阵。S-盒的前五行 和前五列如 Figure 2 所示。在幕后，加密例程获取该密钥数组并用它来生成一个名为w[]的密钥调度表，Figure 3 所示。


Figure 3 密钥调度表（Key Sched）

w[] 最初的 Nk (6) 行被作为种子，用原始密钥值（0x00 到0x17）。剩余行从种子密钥来产生。变量 Nk 代表以 32 位字为单位的种子密钥长度。稍后我分析 AES 实现时你将清楚地看到 w[] 是怎样产生的。 关键是这里现在有许多密钥使用而不只是一个。这些新的密钥被称为轮密钥（round keys）以将它们与原始种子密钥区别开来。


Figure 4 State （态）数组

　　AES 加密例程开始是拷贝 16 字节的输入数组到一个名为  State （态）的 4×4 字节矩阵中。（参见 Figure 4）。AES 加密算法 取名为 Cipher，它操作 State[]，其过程描述的伪代码参见 Figure 5 。
　 　在规范中，加密算法实现的一个预备的处理步骤被称为 AddRoundKey（轮密钥加）。AddRoundKey 用密钥调度表中的前四行对 State 矩阵实行一个字节一个字节的异或（XOR）操作，并用轮密钥表 w[c,r] 异或 输入 State[r,c]。
　　举个例子，如 果 State 矩阵的第一行保存的字节是{ 00, 44, 88, cc }，第一列密钥调度表是{ 00, 04, 08, 0c }，那么新的 State[0,2] 值是用 w[2,0]( 0x08 或 0x80 )异或 State[0,2](0x88)的结果：

1 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 XOR

1 0 0 0 0 0 0 0

AES 算法的主循环对 State 矩阵执行四个不同的操作，在规范中被称为 SubBytes（字节替换）、ShiftRows（行位移变换）、MixColumns（列混合变换） 和 AddRoundKey。除了每次循环 AddRoundKey 都被调用并使用密钥调度表的下面四行外，AddRoundKey 与预备处理步骤中的 AddRoundKey 相同。SubBytes 例程是一个代替操作，它将 State 矩阵中的每个字节替换成一个由 Sbox 决定的新字节。比如，如果 State[0,1]的值是 0x40 如果你想找到它的代替者，你取 State[0,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 进行 ShiftRows 操作

MixColumns 是一个代替操作，它是理解 AES 算法时最具技巧（或者说是最需要动脑筋的部分）的部分。它用 State 字节列的值进行数学域加和域乘的结果代替每个字节。我将在下一节中 详细解释专门的域加和域乘细节。
　　假设 State[0,1] 的值是0x09，并且列1上的其它值分别为 0x60，0xe1 和 0x04，那么State[0,1]的新值计算如下：

State[0,1] = (State[0,1] * 0x01) + (State[1,1] * 0x02) +(State[2,1] * 0x03) +(State[3,1] * 0x01)
= (0x09 * 0x01) + (0x60 * 0x02) + (0xe1 * 0x03) +(0x04 * 0x01)
= 0x57

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

有限域GF(28)的加法和乘法

　　正如你所看到的，AES 加密算法使用相当简单明了的技术来代替和置换，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于数学（译者注：近世代数）的域论。尤其是 AES 基于有限域GF(28)。
　 　GF(28)由一组从 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)的乘法，而只是针对这七种特殊情况进行说明。
　　在GF(28)中用0x01的乘法是特殊的；它相当于普通算术中用1做乘法并且结果也同样—任何值乘0x01等于其自身。
　 　现在让我们看看用0x02做乘法。和加法的情况相同，理论是深奥的，但最终结果十分简单。只要被乘的值小于0x80，这时乘法的结果就是该值左移1比特 位。如果被乘的值大于或等于0x80，这时乘法的结果就是左移1比特位再用值0x1b异或。它防止了“域溢出”并保持乘法的乘积在范围以内。
一旦你在GF(28)中用0x02建立了加法和乘法，你就可以用任何常量去定义乘法。用0x03做乘法时，你可以将 0x03 分解为2的幂之和。为了用 0x03 乘以任意字节b， 因为 0x03 = 0x02 + 0x01，因此：

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 * 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做的乘法是一个有条件的左移1比特位。AES规范中包括大量 有关GF(28)操作的附加信息。

密钥扩展

　 　AES加密和解密算法使用了一个由种子密钥字节数组生成的密钥调度表。AES规范中称之为密钥扩展例程（KeyExpansion）。从本质上讲，从一 个原始密钥中生成多重密钥以代替使用单个密钥大大增加了比特位的扩散。虽然不是无法抵御的困难，但理解 KeyExpansion 仍是 AES 算法中的一个难点。KeyExpansion 例程高级伪代码如下所示：

KeyExpansion(byte[] key, byte[][4] w)
{
  copy the seed key into the first rows of w

  for each 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[]的1行左旋。注意 KeyExpansion 使用的这个 RotWord 函数与加密算法使用的  ShiftRows （行位移变换）例程非常相似，只是它 处理的是单行密钥调度 w[]，而不是整个加密状态表 State[]。
　　SubWord 例程使用替换表 Sbox 对一给定的一行密钥调度表 w[] 进行逐字节替换。KeyExpansion 操作中的替换实际上就像在加密算法中的 替换一样。被代替的输入字节被分成 (x,y) 对，它被当作进入替换表 Sbox 的索引。举例来说，0x27的代替结果是 x＝2 和 y＝7，并且 Sbox[2,7] 返回 0xcc。
　　KeyExpansion 例程使用一个被称为轮常数表的数组 Rcon[]。这些常数都是4个字节，每一个与密钥调度表的某一行相匹配。AES 的 KeyExpansion 例程需要11个轮常数。你可以在 Figure 7 中看到这些常数清单。
　 　每个轮常数的最左边的字节是GF(28)域中2的幂次方。它的另一个表示方法是其每个值是前一个值乘上0x02，正如前一部分讨论 GF(28) 乘法 时所描述的那样。注意 0x80 × 0x02 = 0x1b 是 0x80 左移1个比特位后紧接着与 0x1b 进行异或，如前所述。
　　现在让我们更进一步看看 KeyExpansion 内幕中的循环。这里所用的伪码比以前更为详细，这个循环是：

for (row = Nk; row < (4 * Nr+1); ++row)
{
  temp = w[row-1]

  if (row % Nk == 0) 
    temp = SubWord(RotWord(temp)) xor Rcon[row/Nk]
  else if (Nk == 8 and row % Nk == 4)
    temp = SubWord(temp)

  w[row] = w[row-Nk] xor temp
}

先不要去看if子句，你将看到密钥调度表 w[] 的每一行都是前面一行与行 Nk 异或的结果（4, 6, 或 8 取决于密钥的长度）。if条件的第一部分用 SubWord、RotWord 以及与轮常数的异或修改密钥调度表的每个第4、第6或第8行，取决于是否密钥的长度是128、192或256位。这个条件的第二部分将修改行 12、20 和 28 等等——对于256位密钥而言——每 一个第8行都将添加密钥调度额外的可变性。
　　让我们用本文开头所举的例子来考察 KeyExpansion 是如何开始的。种子密钥是192-bit / 6-word 值：

      00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17      

　　密钥调度字节表 w[] 的维数是 4 列并且 Nb × (Nr + 1) 等于 4 × (12 + 1)，或 52 行。KeyExpansion 将种子密钥的值拷贝到密钥调度字节表 w[] 的第一行。因为我的种子密钥是 192 位（24字节），并且 w[] 表总是 4 列，在这种情况下KeyExapansion 将种子密钥拷贝到 w[] 的前面 6 行。现在让我们看看 KeyExapansion 例程是如何填充密钥调度表其余部分的。在我的例子里，第一个被计算的行是第 6 行 ，因为第0-5行已被种子密钥的值填上了：

      temp = w[row-1] = 14 15 16 17

条件 (row % Nk == 0)为真，因此首先 RotWord 子程序被应用：

      temp = 15 16 17 14

这时 SubWord 被应用：

      temp = 59 47 f0 fa

用 Rcon[row / Nk] = Rcon[6 / 6] = 01 00 00 00 进行异或：

      temp = 58 47 f0 fa

这时用 w[row-Nk] = w[6-6] = 00 01 02 03 异或，产生了下面结果：

      w[6] = 58 46 f2 f9

密钥调度表 w[] 中其余所有行来重复这个过程本身。
　　总而言之，AES 加密和解密的一个重要部分就是从最初的种子密钥中生成多重轮密钥。这个 KeyExapansion 算法生成一个密钥调度并 以某种方式进行替代和置换，在这种方式中，加密和解密算法极其相似。

用 C# 编写 AES 类构造函数

　 　现在我已研究了构成 AES 加密算法的各个成分，我将用 C# 来实现它。官方的 AES 算法规范包含在联邦信息处理标准出版物197 （Federal Information Processing Standards Publication 197）中。我决定尽可能贴切地以它作为我的实现的基础，但是我很快发现这个规范更是一个理论文献而非一个实现的向导。为了将这个官方规范作为资源来使 用，我使用 的变量名与标准出版物中所用的相同。（即便它们是那么晦涩，如“Nr”和“W”）。

我的设计使用9个数据成员和一个枚举类型，如下所示：

public enum KeySize { Bits128, Bits192, Bits256 };
private int Nb; 
private int Nk; 
private int Nr; 
private byte[] key; 
private byte[,] Sbox; 
private byte[,] iSbox; 
private byte[,] w; 
private byte[,] Rcon; 
private byte[,] State; 

因为密钥长度只能是128位、192位或256位比特，它是非常适于用枚举类型：

public enum KeySize { Bits128, Bits192, Bits256 };

　 　该规范文档一般用字节作为基本储存单元而不是用4字节的字作为两个重要数据成员的长度。这两个成员 Nb 和 Nk 代表 以字为单位的块长以及以字为单位的密钥长度。Nr代表轮数。块长度总是16字节（或这说是 128 位，即为 AES 的 4个字），因此它可以被声明为一个常量。密钥长度 依照枚举参数 KeySize 的值被赋值为 4、6 或 8。AES 算法强调通过大量轮数来增加加密数据的复杂性。轮数是10、12或14中的任意一个并且是基于密码分析学理论的。它直接取决于密钥长度。
　　当设计一个类接口时，我喜欢向后来做。我设想从应用程序中调用构造函数和方法。使用这个办法，我决定象下面这样来实例化一个 AES 对象：

Aes a = new Aes(the key size, the seed key)

我调用的加密和解密例程如下：

a.Cipher(plainText, cipherText);
a.InvCipher(cipherText, decipheredText);

我选择少许笨拙的方法来命名 Cipher 和 InvCipher，因为它们是用在 AES 规范文档中的。这里是 AES 类构造函数的代码为：

public Aes(KeySize keySize, byte[] keyBytes)
{
  SetNbNkNr(keySize);

  this.key = new byte[this.Nk * 4];  
  keyBytes.CopyTo(this.key, 0);

  BuildSbox();
  BuildInvSbox();
  BuildRcon();
  KeyExpansion();  
} 

　　该构造函数首先调用一个辅助方法　SetNbNkNr 给 Nb、Nk 和 Nr 赋值，如 Figure 8 所示。如果考虑到效率，你可能将这些代码直接放入构造函数 以避免方法调用的开销。
　　接下来，你必须将传入构造函数的字节拷贝到类域变量中。密钥用其它的类域声明，并且用如下方法获得它的值：

this.key = new byte[this.Nk * 4]; 
keyBytes.CopyTo(this.key, 0);

　 　我决定在构造函数中调用私有辅助方法 BuildSbox 和 BuildInvSbox 来初始化替换表 Sbox[] 和 iSbox[] 。现在密钥扩展例程 、Cipher 方法和 InvCipher 方法各自都需要 Sbox[] 和 iSbox[]，因此我本来可以在 Cipher 和 InvCipher 两个方法中初始化 Sbox[] 并调用 KeyExpansion 方法，但是将它们放入构造函数会代码结构更加清晰。在 Figure 9 中 sBox[] 被填充。填充 iSbox[] 代码 类似。为了可读性对代码进行了结构化处理。正如后面你将看到的，还有另外一个可供选择的令人惊讶的方法为 Sbox 和 iSbox 表提供值。
　　在构造函数中声明密钥调度表 w[]、轮常数表 Rcon[] 和状态矩阵 State[]，并用私有辅助方法来给 Rcon[] 和 w[] 赋值在我看来似乎是组织它们的最好办法，但那主要还是个风格问题。置换轮常数表 Rcon 的赋值代码参见 Figure 7。
回想一下，GF(28)中，Rcon[] 每一行左边的字节都 2 的幂，因此这个表可用下面的方法建立：

newVal = prevVal * 0x02;

　　AES 构造函数在建立完密钥调度表 w[] 后结束，而 w[] 是在 KeyExpansion 方法中完成的（参见 Figure 10）。 其代码相当简单。规范文档使用一个假设的 4-字节的字数据类型。因为 C# 没有那样的类型，但可以用一个4个字节的数组来模拟。在用 new 操作符为密钥调度 表 w[] 分配空间后，w[] 最初的 Nk(4, 6, 或 8) 行从被传递到构造函数的种子密钥 key[] 数组中获值。

this.w[row,0] = this.key[4*row];
this.w[row,1] = this.key[4*row+1];
this.w[row,2] = this.key[4*row+2];
this.w[row,3] = this.key[4*row+3];

　　两个字节相互的异或操作在这个代码中频频发生。它需要一些从 byte 到 int 的强制类型转换并转回到 byte，因为异或操作“^”是不能定义在 C# 的 byte 类型上，例如：

temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );

用来替代：

temp[0] = temp[0] ^ this.Rcon[row/Nk,0];

　 　KeyExpansion 方法有条件地调用私有方法 SubWord 和 RotWord 以保持同规范命名的一致性。此外，因为在C#中没有 word类型，我用 4字节数组实现了一个字。SubWord 和 RotWord 的代码是相当简单，参见本文附带的 AesLib 源代码，它应该很容易理解。
　　稍微具备有些技巧的部分是在 SubWord 中查找替代值。回想一下，为了寻找代替值，你将输入字节分成最左边的4位比特和最右边的4位比特。对于一个给定字节，用 >> 操作符右移 4 位将得到 x 索引，并且与 0000 1111 进行逻辑与得到 y 值。虽然有些长，但比实际代码更可读，我可以象下面这样：

int x = word[0] >> 4;
int y = word[0] & 0x0f;
byte substitute = this.Sbox[x,y];
result[0] = substitute;

代替我原来用的代码：

result[0] = this.Sbox[ word[0] >> 4, word[0] & 0x0f ];

　 　总的来说，AES 构造函数接受一个密钥的长度为128，192 或 256 位和一个字节数组种子密钥值。构造函数为输入块长度，种子密钥长度 以及加密算法的轮数赋值，并将种子密钥拷贝到一个名为 key 的数据成员中。构造函数还创建了四个表：两个由加密和解密方法使用的替换表，一个轮常数表，和一个轮密钥的密钥调度表。

用C#编写的 AES Cipher 方法

　　Cipher方法如 Figure 11 所示。它真的非常简单，因为它分出了大部分的工作给私有方法AddRoundKey, SubBytes, ShiftRows 和 MixColumns。
　　Cipher 方法以拷贝明文输入数组到状态矩阵 State[] 为开始。最初调用 AddRoundKey 之后，Cipher 方法比总轮数少迭代一次。在最后一轮时，正如规范中所说的那样，MixColumns 调用被省略了。
　　AddRoundKey 和 SubBytes 私有方法的代码如 Figure 12 所示。AddRoundKey 方法需要知道它处在那一轮，以便它正确引用4行密钥调度数组 w[]。请注意 State[r,c] 是用 w[c,r] 来异或并不是w[r,c]。SubBytes 方法从输入字节中提取索引，与 KeyExpansion 方法中所用的右移4位和 0x0f 屏蔽技术相同。
　　ShiftRows 方法的代码如 Figure 13 所示。回想一下，ShiftRows（可能叫做 RotateRows 更好）将 row[0] 向左旋转 0 个位置，将 row[1] 向左旋转 1 位置等等。
把 State[] 拷贝到 temp[] 矩阵之后，然后用下面的这行代码实现转换：

this.State[r, (c + r) % Nb ] = temp[r,c];

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

        State[0,c] = 0x02 * State[0,c] + 
        	            0x03 * State[1,c] + 
                     0x01 * State[2,c] + 
                     0x01 * State[3,c]
                     
        State[1,c] = 0x01 * State[0,c] + 
        	            0x02 * State[1,c] + 
        	            0x03 * State[2,c] + 
        	            0x01 * State[3,c]
        	     
        State[2,c] = 0x01 * State[0,c] + 
                     0x01 * State[1,c] + 
                     0x02 * State[2,c] +  
                     0x03 * State[3,c]
                     
        State[3,c] = 0x03 * State[0,c] + 
                     0x01 * State[1,c] + 
                     0x01 * State[2,c] +  
                     0x02 * State[3,c]

　　这些表达式稍微有些长，因此我决定编写返回 GF(28)与 0x01,0x02 和 0x03 之乘积的私有辅助函数。这些辅助函数非常短。例如，一个字节 b 被 0x03 域乘的代码如下：

return (byte) ( (int)gfmultby02(b) ^ (int)b ); 

　　正如我前面讨论的，被 0x02 乘是所有 GF(28) 乘法的基本操作。我调用了我的 gfmultby02 方法，我改变了使用与规范相同的方法命名惯例，规范上称此例程为 xtime。
　 　Cipher 方法其输入反复应用四个操作来产生加密的输出。AddRoundKey 用源于单个原始种子密钥的多重轮密钥来替代字节。SubBytes 用某个替换表中的值替代字节。ShiftRows 用移动字节行置换字节，而 MixColumns 用某一列的域加和乘法值来替代字节。

用C#编写 AES InvCipher 方法

　　AES 解密算法背后的基本原则很简单：解密一个加密块，也就是以反向顺序还原（Undo）每个操作。尽管这是基本概念，但仍有几个细节要处理。
　　AES规范称解密例程为 InvCipher，而不是 Decipher 或 Decrypt 中的一个。这是 AES 背后的数学基础的反映，它基于可逆的数学操作。
　 　如果你将这个代码和 Cipher 代码比较的话，你会看到它比你预期的漂亮很多，但是有两点例外。首先，在 InvCipher 方法中逆方法调用（如 InvSubBytes）顺序并不完全与在 Cipher 方法中相应调用（如 SubBytes）的逆向顺序正好相同。其次，InvCipher 调用的是一个 AddRoundKey 方法而不是 InvAddRoundKey 方法。值得注意的是 InvCipher 算法用密钥调度表并不是从较高编号的索引处开始向下处理至第0行。
　　 InvSubBytes，InvShiftRows 和 InvMixColumns 方法的代码和与之有关的 SubBytes，ShiftRows和 MixColumns 方法的代码非常接近。InvSubBytes 方法几乎就是 SubBytes 方法，只是它用逆替换表 iSbox[] 而不是 Sbox[] 表。
　　正如你可能猜测到的，iSbox[] 就是还原任何被 Sbox[] 处理的对应操作。比如，如果你有字节 b 等于 0x20，并在 Sbox[] 中找到其代替值，你得到 0xb7。如果你在 iSbox[] 中找到 0xb7的替代值，你便可得到 0x20。
　　相似地，InvShiftRows 方法还原 ShiftRows 方法—— row[0] 被右移了 0 个位置，row[1] 被右移了 1个位置，row[2] 被右移了 2 个位置，而 row[3] 被右移了 3个位置。
　 　InvMixColumns 方法还原 MixColumns 的工作，但没有用显而易见的方法。回想一下，MixColumns 用原始字节列中的字节线性组合替换状态矩阵中的每个字节，并且系数是 0x01，0x02，和 0x03，域论再一次得到应用。它证明逆运算是相似的，只是被 0x09，0x0b，0x0d 和 0x0e 乘，如下所示：

      
State[0,c] = 0x0e * State[0,c] + 
	    0x0b * State[1,c] + 
	    0x0d * State[2,c] + 
             0x09 * State[3,c]

State[1,c] = 0x09 * State[0,c] + 
             0x0e * State[1,c] + 
             0x0b * State[2,c] + 
             0x0d * State[3,c]

State[2,c] = 0x0d * State[0,c] + 
             0x09 * State[1,c] + 
             0x0e * State[2,c] + 
             0x0b * State[3,c]

State[3,c] = 0x0b * State[0,c] + 
             0x0d * State[1,c] + 
             0x09 * State[2,c] + 
             0x0e * State[3,c] 

　　对于 MixColumns 方法，我决定专门写一个辅助函数，而不是内联展开已经较长的表达式或写一个普通的乘法辅助函数。让我向你展示一下我示如何编写这个任何字节 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))) ^ /* 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 对象针对字节数组进行处理，你可以轻松地用它处理.NET的其它数据类型。我创建了一个基于 Windows 的小Demo程序，它接受一个 单纯的字符串——有 8 个字符 (16-byte) ，对它进行加密和解密处理。运行画面如 Figure 16。


Figure 16 加密 Demo 程序

因为加密和解密例程都需要知道用户定义的密钥长度，我把它当作一个类范围的变量来声明，像这样：

private Aes.KeySize keysize; 

　 　注意种子密钥并不是由用户定义的。这个 demo 程序用一个“空密钥”（null key）作为种子密钥，通过为构造函数提供一个哑参数 new byte[16] 使得它全部由零字节组成。哑参数的长度是不相关的，因为种子密钥还是要被初始化为零。空密钥加密和解密是一个容易和有效的办法来阻止外界对数据偶然的检 查。在 System.Text 中的 Encoding.Unicode.GetBytes和Encoding.Unicode.GetString 方法使得将一个.NET 字符串转换成一个字节数组变得非常容易，反之亦然。


 实现选择

　　现在让我们看看本文 AES 实现中出现的一些重要的变量，本文提供的代码可能出现的扩展，以及针对 AES 的密码分析学攻击。
　 　和我曾经处理的任何代码一样，AES 算法也可以用其它可选的途径来实现。为什么这很重要呢？AES 被试图广泛应用于各种系统，从只有很少内存容量的智能卡（smart cards）到大型的多处理器主机系统。在许多情况下，性能是关键因素，并且有时内存或处理器资源是有限的。事实上，AES 的每个例程都能针对非常昂贵的内存资源进行性能优化，反之亦然。比如，为替换表Sbox[] 分配 256 个值看起来好像很简单直白。但是，这些值是基于 GF(28) 理论的，它们都可以用编程方式来生成。逆向替换表和轮常数表也是如此。
　　可选实 现另外一个有趣的可能性是 Cipher 和 InvCipher 方法所用的 GF(28) 乘法。我的实现代码是一个被 0x02 乘的基本函数，而后是六个调用 gfmultby02 的附加函数。另一个可能性应该是写一个一般的乘法函数，并用它代替我目前实现的七个单独函数。另一个极端是你可以用被 0x01, 0x02, 0x03, 0x09, 0x0b, 0x0d 和 0x0e 乘好的所有 256 个可能的字节值构成的一个完整乘积表。此外，实现 GF(28) 乘法另一途径是通过在两个 256 个字节的数组里查找，通常称为 alog[] 和 log[]，因为它们在 GF(28)中基于某些类似对数的方法。
　 　虽然这里给出的 AES 类完全能用于加密任何形式的.NET数据，你可能考虑想用各种方法扩展它。首先，因为本文的重点在于清楚地解释 AES，所有 错误检查被剥离掉，以我的经验，为某个象 AES 这样的类添加合理数量的错误检查将会产生三倍的代码量膨胀。因为 AES 使用了这么多的数组，需要做很多索引 边界检查。例如，所给出的构造函数甚至都不检查种子密钥参数的长度。
　　你可能还考虑通过添加更多的特性来扩展 AES 类。最明显的一个地方是添加加密和解密.NET基本数据类型的方法，比如：System.String 和 System.Int32。更加雄心勃勃的扩展可能会是实现一个 流数据加密类。
　 　AES 的安全性怎样呢？这是一个很难回答的问题，但是一般多数人的意见是：它是目前可获得的最安全的加密算法。AES 已被列为比任何现今其它加密算法更 安全的一种算法。在理论和实践基础上，AES 被认为是“安全的”，因为要破解它的话，唯一有效的方法是强行（brute-force）生成所有可能的密钥。 如果密钥长度为 256 位，还没有已知的攻击可以在一个可接受的时间内破解 AES（即便在当今最快的系统上，它也要花费数年时间）。
　　注意针对 AES 密码最可能成功的攻击来自一个允许时间选择攻击的弱实现。攻击者用不同的密钥并精确地测量出加密例程所需的时间。如果加密例程被粗心编码 ，因此执行时间便依赖于密钥值，它就有可能推导出有关密钥的信息。在 AES 中，这种事情最可能发生在 MixColumns 例程中，因为有域乘。 针对这种攻击的两个安全措施是加入虚指令，以便所以所有乘法都需要相同数量的指令，或者将域乘实现为一个查询表，就象我前面描述的那样。
　　AES 有许多种可能的实现，尤其是是使用查询表而不是计算。本文提供的 AES 基本类可以被用于加解密任何形式的.NET数据或 被扩展成一个具有更多功能的类。

 结束语

　　新的 AES 将无疑成为加密所有形式电子信息的事实上的标准，取代 DES。AES 加密的数据在某种意义上是牢不可破的，因为没有已知的密码分析攻击可以解密 AES 密文，除非强行遍历搜索所有可能的 256 位密钥。
　 　我发现在 Microsoft .NET Framework 上实现 AES 类的主要的障碍是官方文档是以一个数学家的观点，而不是以一个软件开发者的观点来写的。尤其是该规范假定读者十分熟悉 GF(28) 域，并省略了几个正确实现 AES 所必需的关于 GF(28) 乘法的关键事实。我在本文中试图努力去掉 AES 的神秘面纱，特别是围绕在 GF(28) 域乘法部分的。
　　以 .NET Framework 库的形式从 Microsoft 以及第三方供应商处获得对 AES 的广泛支持只是一个时间问题。然而，处于种种理由，让本文代码作为你的技能储备仍然是有价值的。这个实现尤其简单，并且是低资源开销。另外，阅读并理解源 代码将使你能定制 AES 类且更有效地使用它的任何实现。
　　在任何软件设计过程中安全已不再是后顾之忧。AES 是一个重大进步，使用并理解它将大大增加软件系统的可靠性和安全性。

Cipher Algorithm Pseudocode

Cipher(byte[] input, byte[] output)
{
  byte[4,4] State;
  copy input[] into State[]
  AddRoundKey
  for (round = 1; round < Nr-1; ++round)
  {
    SubBytes
    ShiftRows
    MixColumns
    AddRoundKey
  }
  SubBytes
  ShiftRows
  AddRoundKey
  copy State[] to output[]
}

---

Initializing Rcon

private void BuildRcon()
{
  this.Rcon = new byte[11,4] { {0x00, 0x00, 0x00, 0x00},  
                               {0x01, 0x00, 0x00, 0x00},
                               {0x02, 0x00, 0x00, 0x00},
                               {0x04, 0x00, 0x00, 0x00},
                               {0x08, 0x00, 0x00, 0x00},
                               {0x10, 0x00, 0x00, 0x00},
                               {0x20, 0x00, 0x00, 0x00},
                               {0x40, 0x00, 0x00, 0x00},
                               {0x80, 0x00, 0x00, 0x00},
                               {0x1b, 0x00, 0x00, 0x00},
                               {0x36, 0x00, 0x00, 0x00} };
}  // BuildRcon()

---

SetNbNkNr Method

private void SetNbNkNr(KeySize keySize)
{
  this.Nb = 4;     

  if (keySize == KeySize.Bits128)
  {
    this.Nk = 4;   
    this.Nr = 10;  
  }
  else if (keySize == KeySize.Bits192)
  {
    this.Nk = 6;   
    this.Nr = 12;
  }
  else if (keySize == KeySize.Bits256)
  {
    this.Nk = 8;   
    this.Nr = 14;
  }
}  // SetNbNkNr()

---

Sbox Initialization

private void BuildSbox()
{
  this.Sbox = new byte[16,16] {  // populate the Sbox matrix
/*        0     1     2     3     4     5     6     7     8     9     a     b     c     d     e     f */
/*0*/  {0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76},
/*1*/  {0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0},
/*2*/  {0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15},
/*3*/  {0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75},
/*4*/  {0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84},
/*5*/  {0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf},
/*6*/  {0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8},
/*7*/  {0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2},
/*8*/  {0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73},
/*9*/  {0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb},
/*a*/  {0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79},
/*b*/  {0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08},
/*c*/  {0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a},
/*d*/  {0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e},
/*e*/  {0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf},
/*f*/  {0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16} };

}  // BuildSbox()

---

KeyExpansion Method

private void KeyExpansion()
{
  this.w = new byte[Nb * (Nr+1), 4];  
  
  for (int row = 0; row < Nk; ++row)
  {
    this.w[row,0] = this.key[4*row];
    this.w[row,1] = this.key[4*row+1];
    this.w[row,2] = this.key[4*row+2];
    this.w[row,3] = this.key[4*row+3];
  }
  
  byte[] temp = new byte[4];
  
  for (int row = Nk; row < Nb * (Nr+1); ++row)
  {
    temp[0] = this.w[row-1,0]; temp[1] = this.w[row-1,1];
    temp[2] = this.w[row-1,2]; temp[3] = this.w[row-1,3];
  
    if (row % Nk == 0)  
    {
      temp = SubWord(RotWord(temp));
  
      temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );
      temp[1] = (byte)( (int)temp[1] ^ (int)this.Rcon[row/Nk,1] );
      temp[2] = (byte)( (int)temp[2] ^ (int)this.Rcon[row/Nk,2] );
      temp[3] = (byte)( (int)temp[3] ^ (int)this.Rcon[row/Nk,3] );
    }
    else if ( Nk > 6 && (row % Nk == 4) )  
    {
      temp = SubWord(temp);
    }
  
    // w[row] = w[row-Nk] xor temp
    this.w[row,0] = (byte) ( (int)this.w[row-Nk,0] ^ (int)temp[0] );
    this.w[row,1] = (byte) ( (int)this.w[row-Nk,1] ^ (int)temp[1] );
    this.w[row,2] = (byte) ( (int)this.w[row-Nk,2] ^ (int)temp[2] );
    this.w[row,3] = (byte) ( (int)this.w[row-Nk,3] ^ (int)temp[3] );
  
  }  // for loop
}  // KeyExpansion()

---

The Cipher Method

public void Cipher(byte[] input, byte[] output)  
{
  // state = input
  this.State = new byte[4,Nb];  
  for (int i = 0; i < (4 * Nb); ++i)
  {
    this.State[i % 4, i / 4] = input[i];
  }

  AddRoundKey(0);
        
  for (int round = 1; round <= (Nr - 1); ++round)  
  {
    SubBytes(); 
    ShiftRows();  
    MixColumns(); 
    AddRoundKey(round);
  }  

  SubBytes();
  ShiftRows();
  AddRoundKey(Nr);
          
  // output = state
  for (int i = 0; i < (4 * Nb); ++i)
  {
    output[i] = this.State[i % 4, i / 4];
  }

}  // Cipher()

---

AddRoundKey and SubBytes Methods

private void AddRoundKey(int round)
{
  for (int r = 0; r < 4; ++r)
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = (byte) ( (int)this.State[r,c] ^
                                 (int)w[(round*4)+c,r] );
    }
  }
}  // AddRoundKey()

private void SubBytes()
{
  for (int r = 0; r < 4; ++r)
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = this.Sbox[ (this.State[r,c] >> 4),
                                   (this.State[r,c] & 0x0f) ];
    }
  }
}  // SubBytes

---

ShiftRows Method

private void ShiftRows()
{
  byte[,] temp = new byte[4,4];
  for (int r = 0; r < 4; ++r)  
  {
    for (int c = 0; c < 4; ++c)
    {
      temp[r,c] = this.State[r,c];
    }
  }

  for (int r = 1; r < 4; ++r)  // 
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = temp[ r, (c + r) % Nb ];
    }
  }
}  // ShiftRows()

---

MixColumns Method

private void MixColumns()
{
  byte[,] temp = new byte[4,4];
  for (int r = 0; r < 4; ++r)  
  {
    for (int c = 0; c < 4; ++c)
    {
      temp[r,c] = this.State[r,c];
    }
  }
      
  for (int c = 0; c < 4; ++c)
  {
    this.State[0,c] = (byte) ( (int)gfmultby02(temp[0,c]) ^
                               (int)gfmultby03(temp[1,c]) ^
                               (int)gfmultby01(temp[2,c]) ^
                               (int)gfmultby01(temp[3,c]) );

    this.State[1,c] = (byte) ( (int)gfmultby01(temp[0,c]) ^
                               (int)gfmultby02(temp[1,c]) ^
                               (int)gfmultby03(temp[2,c]) ^
                               (int)gfmultby01(temp[3,c]) );

    this.State[2,c] = (byte) ( (int)gfmultby01(temp[0,c]) ^
                               (int)gfmultby01(temp[1,c]) ^
                               (int)gfmultby02(temp[2,c]) ^
                               (int)gfmultby03(temp[3,c]) );

    this.State[3,c] = (byte) ( (int)gfmultby03(temp[0,c]) ^
                               (int)gfmultby01(temp[1,c]) ^
                               (int)gfmultby01(temp[2,c]) ^
                               (int)gfmultby02(temp[3,c]) );
    }
  }  // MixColumns

---

Using AES

static void Main(string[] args)
{
  byte[] plainText = new byte[] {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 
      0x66, 0x77,0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff};
    
  byte[] cipherText = new byte[16];
  byte[] decipheredText = new byte[16];
    
  byte[] keyBytes = new byte[] {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 
      0x07,0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,0x10, 0x11, 
      0x12, 0x13, 0x14, 0x15, 0x16, 0x17};
  
  Aes a = new Aes(Aes.KeySize.Bits192, keyBytes);

  Console.WriteLine("\nAdvanced Encryption System Demo in .NET");
  Console.WriteLine("\nThe plaintext is: ");
  DisplayAsBytes(plainText);

  Console.WriteLine("\nUsing a " + Aes.KeySize.Bits192.ToString() + 
      "-key of: ");
  DisplayAsBytes(keyBytes);
   
  a.Cipher(plainText, cipherText);

  Console.WriteLine("\nThe resulting ciphertext is: ");
  DisplayAsBytes(cipherText);

  a.InvCipher(cipherText, decipheredText);

  Console.WriteLine("\nAfter deciphering the ciphertext, the result 
      is: ");
  DisplayAsBytes(decipheredText);

  Console.WriteLine("\nDone");
  Console.ReadLine();
}  // Main()

static void DisplayAsBytes(byte[] bytes)
{
  for (int i = 0; i < bytes.Length; ++i)
  {
    Console.Write(bytes[i].ToString("x2") + " " );
    if (i > 0 && i % 16 == 0) Console.Write("\n");
  }
  Console.WriteLine("");

}  // DisplayAsBytes()

 相关文章

• Security: Protect Private Data with the Cryptography Namespaces of the .NET Framework
  
• Exploring Kerberos, the Protocol for Distributed Security in Windows 2000
  

 背景信息

　　The Design of Rijndael: AES - The Advanced Encryption Standard by Joan Daemen and Vincent Rijmen. (Springer-Verlag, 2002)
　　

 作者简介
　 　James McCaffrey 在Volt Information Sciences Inc公司工作，在那里他管理为 Microsoft 的软件工程师技术培训。他作为一些 Microsoft 产品的承包人工作包括 Internet Explorer 和 MSN Search。可通过 [e-mail] 或
[e-mail]与他联系。
　 本文出自 的 期刊，可通过当地报摊获得，或者最好是




======英文原版=========================
Encrypt It

Keep Your Data Secure with the New Advanced Encryption Standard

James McCaffrey

Code download available at: (143 KB)

This article assumes you're familiar with C# and bit manipulation

Level of Difficulty 1 2 3

SUMMARY

The Advanced Encryption Standard (AES) is a National Institute of Standards and Technology specification for the encryption of electronic data. It is expected to become the accepted means of encrypting digital information, including financial, telecommunications, and government data. This article presents an overview of AES and explains the algorithms it uses. Included is a complete C# implementation and examples of encrypting .NET data. After reading this article you will be able to encrypt data using AES, test AES-based software, and use AES encryption in your systems.

 Contents

The National Institute of Standards and Technology (NIST) established the new Advanced Encryption Standard (AES) specification on May 26, 2002. In this article I will provide a working implementation of AES written in C#, and a complete explanation of exactly what AES is and how the code works. I'll show you how to encrypt data using AES and extend the code given here to develop a commercial-quality AES class. I'll also explain how and why to incorporate AES encryption into your software systems, and how to test AES-based software.

Note that the code presented in this article and any other implementation based on this article is subject to applicable Federal cryptographic module export controls (see for the exact regulations).

AES is a new cryptographic algorithm that can be used to protect electronic data. Specifically, AES is an iterative, symmetric-key block cipher that can use keys of 128, 192, and 256 bits, and encrypts and decrypts data in blocks of 128 bits (16 bytes). Unlike public-key ciphers, which use a pair of keys, symmetric-key ciphers use the same key to encrypt and decrypt data. Encrypted data returned by block ciphers have the same number of bits that the input data had. Iterative ciphers use a loop structure that repeatedly performs permutations and substitutions of the input data. Figure 1 shows AES in action encrypting and then decrypting a 16-byte block of data using a 192-bit key.

Figure 1 Some Data 

AES is the successor to the older Data Encryption Standard (DES). DES was approved as a Federal standard in 1977 and remained viable until 1998 when a combination of advances in hardware, software, and cryptanalysis theory allowed a DES-encrypted message to be decrypted in 56 hours. Since that time numerous other successful attacks on DES-encrypted data have been made and DES is now considered past its useful lifetime.

In late 1999, the Rijndael (pronounced "rain doll") algorithm, created by researchers Joan Daemen and Vincent Rijmen, was selected by the NIST as the proposal that best met the design criteria of security, implementation efficiency, versatility, and simplicity. Although the terms AES and Rijndael are sometimes used interchangeably, they are distinct. AES is widely expected to become the de facto standard for encrypting all forms of electronic data including data used in commercial applications such as banking and financial transactions, telecommunications, and private and Federal information.

Overview of the AES Algorithm

The AES algorithm is based on permutations and substitutions. Permutations are rearrangements of data, and substitutions replace one unit of data with another. AES performs permutations and substitutions using several different techniques. To illustrate these techniques, let's walk through a concrete example of AES encryption using the data shown in Figure 1.

The following is the 128-bit value that you will encrypt with the indexes array:

00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15

The 192-bit key value is:

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23

Figure 2 Sbox 

When the AES constructor is called, two tables that will be used by the encryption method are initialized. The first table is a substitution box named Sbox. It is a 16 × 16 matrix. The first five rows and columns of Sbox are shown in Figure 2. Behind the scenes, the encryption routine takes the key array and uses it to generate a "key schedule" table named w[], shown in Figure 3.

Figure 3 Key Sched. 

The first Nk (6) rows of w[] are seeded with the original key value (0x00 through 0x17) and the remaining rows are generated from the seed key. The variable Nk represents the size of the seed key in 32-bit words. You'll see exactly how w[] is generated later when I examine the AES implementation. The point is that there are now many keys to use instead of just one. These new keys are called the round keys to distinguish them from the original seed key.

Figure 4 State 

The AES encryption routine begins by copying the 16-byte input array into a 4×4 byte matrix named State (see Figure 4). The AES encryption algorithm is named Cipher and operates on State[] and can be described in pseudocode (see Figure 5).

 Figure 5 Cipher Algorithm Pseudocode

Cipher(byte[] input, byte[] output)
{
  byte[4,4] State;
  copy input[] into State[]
  AddRoundKey
  for (round = 1; round < Nr-1; ++round)
  {
    SubBytes
    ShiftRows
    MixColumns
    AddRoundKey
  }
  SubBytes
  ShiftRows
  AddRoundKey
  copy State[] to output[]
}

The encryption algorithm performs a preliminary processing step that's called AddRoundKey in the specification. AddRoundKey performs a byte-by-byte XOR operation on the State matrix using the first four rows of the key schedule, and XORs input State[r,c] with round keys table w[c,r].

For example, if the first row of the State matrix holds the bytes { 00, 44, 88, cc }, and the first column of the key schedule is { 00, 04, 08, 0c }, then the new value of State[0,2] is the result of XORing State[0,2] (0x88) with w[2,0] (0x08), or 0x80:

1 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0  XOR

1 0 0 0 0 0 0 0

The main loop of the AES encryption algorithm performs four different operations on the State matrix, called SubBytes, ShiftRows, MixColumns, and AddRoundKey in the specification. The AddRoundKey operation is the same as the preliminary AddRoundKey except that each time AddRoundKey is called, the next four rows of the key schedule are used. The SubBytes routine is a substitution operation that takes each byte in the State matrix and substitutes a new byte determined by the Sbox table. For example, if the value of State[0,1] is 0x40 and you want to find its substitute, you take the value at State[0,1] (0x40) and let x equal the left digit (4) and y equal the right digit (0). Then you use x and y as indexes into the Sbox table to find the substitution value, as shown in Figure 2.

ShiftRows is a permutation operation that rotates bytes in the State matrix to the left. Figure 6 shows how ShiftRows works on State[]. Row 0 of State is rotated 0 positions to the left, row 1 is rotated 1 position left, row 2 is rotated 2 positions left, and row 3 is rotated 3 positions left.

Figure 6 Running ShiftRows on State 

The MixColumns operation is a substitution operation that is the trickiest part of the AES algorithm to understand. It replaces each byte with the result of mathematical field additions and multiplications of values in the byte's column. I will explain the details of special field addition and multiplication in the next section.

Suppose the value at State[0,1] is 0x09, and the other values in column 1 are 0x60, 0xe1, and 0x04; then the new value for State[0,1] is shown in the following:

State[0,1] = (State[0,1] * 0x01) + 
             (State[1,1] * 0x02) +
             (State[2,1] * 0x03) +
             (State[3,1] * 0x01)

           = (0x09 * 0x01) + (0x60 * 0x02) + (0xe1 * 0x03) +
             (0x04 * 0x01)

           = 0x57

The addition and multiplication are special mathematical field operations, not the usual addition and multiplication on integers.

The four operations SubBytes, ShiftRows, MixColumns, and AddRoundKey are called inside a loop that executes Nr times—the number of rounds for a given key size, less 1. The number of rounds that the encryption algorithm uses is either 10, 12, or 14 and depends on whether the seed key size is 128, 192, or 256 bits. In this example, because Nr equals 12, the four operations are called 11 times. After this iteration completes, the encryption algorithm finishes by calling SubBytes, ShiftRows, and AddRoundKey before copying the State matrix to the output parameter.

In summary, there are four operations that are at the heart of the AES encryption algorithm. AddRoundKey substitutes groups of 4 bytes using round keys generated from the seed key value. SubBytes substitutes individual bytes using a substitution table. ShiftRows permutes groups of 4 bytes by rotating 4-byte rows. MixColumns substitutes bytes using a combination of both field addition and multiplication.

Field Addition and Multiplication in GF(28)

As you've seen, the AES encryption algorithm uses fairly straightforward techniques for substitution and permutation, except for the MixColumns routine. The MixColumns routine uses special addition and multiplication. The addition and multiplication used by AES are based on mathematical field theory. In particular, AES is based on a field called GF(28).

The GF(28) field consists of a set of 256 values from 0x00 to 0xff, plus addition and multiplication, hence the (28). GF stands for Galois Field, named after the mathematician who founded field theory. One of the characteristics of GF(28) is that the result of an addition or multiplication operation must be in the set {0x00 ... 0xff}. Although the theory of fields is rather deep, the net result for GF(28) addition is simple: GF(28) addition is just the XOR operation.

Multiplication in GF(28) is trickier, however. As you'll see later in the C# implementation, the AES encryption and decryption routines need to know how to multiply by only the seven constants 0x01, 0x02, 0x03, 0x09, 0x0b, 0x0d, and 0x0e. So instead of explaining GF(28) multiplication theory in general, I will explain it just for these seven specific cases.

Multiplication by 0x01 in GF(28) is special; it corresponds to multiplication by 1 in normal arithmetic and works the same way—any value times 0x01 equals itself.

Now let's look at multiplication by 0x02. As in the case of addition, the theory is deep, but the net result is fairly simple. If the value being multiplied is less than 0x80, then the result of multiplication is just the value left-shifted 1 bit position. If the value being multiplied is greater than or equal to 0x80, then the result of multiplication is the value left-shifted 1 bit position XORed with the value 0x1b. This prevents "field overflow" and keeps the product of the multiplication in range.

Once you've established addition and multiplication by 0x02 in GF(28), you can use them to define multiplication by any constant. To multiply by 0x03 in GF(28), you can decompose 0x03 as powers of 2 and additions. To multiply an arbitrary byte b by 0x03, observe that 0x03 = 0x02 + 0x01. Thus:

b * 0x03 = b * (0x02 + 0x01)
         = (b * 0x02) + (b * 0x01)

This can be done because you know how to multiply by 0x02 and 0x01 and how to perform addition. Similarly, to multiply an arbitrary byte b by 0x0d, you do this:

b * 0x0d = b * (0x08 + 0x04 + 0x01)
         = (b * 0x08) + (b * 0x04) + (b * 0x01)
         = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01)

The other multiplications needed for the AES MixColumns routine in the encryption and decryption algorithm follow the same general pattern, as shown here:

b * 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)

To summarize, addition in GF(28) is the XOR operation. Multiplication in GF(28) reduces to additions and multiplications by 0x02, where multiplication by 0x02 is a conditional 1-bit left shift. The AES specification contains a lot of additional information about operations in GF(28).

Key Expansion

The AES encryption and decryption algorithms use a key schedule generated from the seed key array of bytes. The AES specification refers to this as the KeyExpansion routine. Generating, in essence, multiple keys from an initial key instead of using a single key greatly increases the diffusion of bits. Although not overwhelmingly difficult, understanding KeyExpansion is one of the trickier parts of the AES algorithm. In high-level pseudocode, the KeyExpansion routine looks like the following:

KeyExpansion(byte[] key, byte[][4] w)
{
  copy the seed key into the first rows of w

  for each remaining row of w
  {
    use two of the previous rows to create a new row
  }
}

The "use two of the previous rows to create a new row" routine makes use of two subroutines, RotWord and SubWord, and a table of constants named Rcon (for "round constants"). Let's look at each of these three items and then come back to the KeyExpansion routine as a whole.

The RotWord routine is simple. It accepts an array of 4 bytes and rotates them 1 position left. Because the round schedule table w[] has four columns, RotWord rotates a row of w[] to the left. Notice that the RotWord function used by KeyExpansion is very similar to the ShiftRows routine used by the encryption algorithm except that it works on a single row of the key schedule w[] instead of the entire encryption state table State[].

The SubWord routine performs a byte-by-byte substitution on a given row of the key schedule table w[] using the substitution table Sbox. The substitutions in KeyExpansion operate exactly like those in the encryption algorithm. The input byte to be substituted is separated into an (x,y) pair which are used as indexes into the substitution table Sbox. For example, substitution for 0x27 results in x = 2 and y = 7, and Sbox[2,7] returns 0xcc.

The KeyExpansion routine uses an array Rcon[], called the round constant table. These constants are 4 bytes each to match with a row of the key schedule table. The AES KeyExpansion routine requires 11 round constants. You can see these constants listed in Figure 7.

 Figure 7 Initializing Rcon

private void BuildRcon()
{
  this.Rcon = new byte[11,4] { {0x00, 0x00, 0x00, 0x00},  
                               {0x01, 0x00, 0x00, 0x00},
                               {0x02, 0x00, 0x00, 0x00},
                               {0x04, 0x00, 0x00, 0x00},
                               {0x08, 0x00, 0x00, 0x00},
                               {0x10, 0x00, 0x00, 0x00},
                               {0x20, 0x00, 0x00, 0x00},
                               {0x40, 0x00, 0x00, 0x00},
                               {0x80, 0x00, 0x00, 0x00},
                               {0x1b, 0x00, 0x00, 0x00},
                               {0x36, 0x00, 0x00, 0x00} };
}  // BuildRcon()

The leftmost byte of each round constant is a power of 2 in the GF(28) field. Another way of looking at it is to observe that each value is the previous value times 0x02, as described in the previous section discussing multiplication in GF(28). Notice that 0x80 × 0x02 = 0x1b is 0x80 left-shifted 1 bit followed by an XOR with 0x1b, as described earlier.

Now let's take a closer look at the loop inside KeyExpansion. In more detailed pseudocode than before, the loop is:

for (row = Nk; row < (4 * Nr+1); ++row)
{
  temp = w[row-1]

  if (row % Nk == 0) 
    temp = SubWord(RotWord(temp)) xor Rcon[row/Nk]
  else if (Nk == 8 and row % Nk == 4)
    temp = SubWord(temp)

  w[row] = w[row-Nk] xor temp
}

Ignoring the if clause for a moment, you'll see that each row of the key schedule table w[] is the result of XORing the previous row with the row Nk (4, 6, or 8 depending on the key size) rows before. The first part of the if conditional modifies every fourth, sixth, or eighth row of the key schedule with SubWord, RotWord, and XORing with a round constant, depending on whether the key size is 128, 192, or 256 bits. The second part of the conditional will modify rows 12, 20, 28 and so on—every eighth row—for a 256-bit key to add additional variability to the key schedule.

Let's see how KeyExpansion gets started with the example presented at the beginning of this article. The seed key is the 192-bit / 6-word value:

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17

The key schedule byte table w[] has the dimensions 4 columns and Nb × (Nr + 1) equals 4 × (12 + 1), or 52 rows. The KeyExpansion routine copies the values in the seed key into the first rows of the key schedule byte table w[]. Because my seed key is 192 bits (24 bytes), and the w[] table always has 4 columns, in this case KeyExapansion copies the seed key into the first 6 rows of w[]. Now let's see how the KeyExpansion routine fills the rest of the key schedule table. In my example, the first calculated row is row 6 because rows 0 to 5 were filled with the seed key values:

temp = w[row-1] = 14 15 16 17

The condition (row % Nk == 0) is true, so first the RotWord subroutine is applied:

temp = 15 16 17 14

Then SubWord is applied:

temp = 59 47 f0 fa

Then XORed with Rcon[row / Nk] = Rcon[6 / 6] = 01 00 00 00:

temp = 58 47 f0 fa

This is then XORed with w[row-Nk] = w[6-6] = 00 01 02 03, yielding the following result:

w[6] = 58 46 f2 f9

The process repeats itself for all of the remaining rows in key schedule table w[].

To summarize, an important part of AES encryption and decryption is the generation of multiple round keys from the initial seed key. This KeyExpansion algorithm generates a key schedule and uses substitution and permutation in a way that is similar in most respects to the encryption and decryption algorithms.

The AES Class Constructor in C#

Now that I've examined all the components of the AES encryption algorithm, I'll implement it in C#. The official specification of the AES algorithm is contained in Federal Information Processing Standards Publication 197. I decided to base my implementation on it as closely as possible, but I quickly discovered that the specification was more of a theory document than an implementation guide. To exploit the official specification as a resource, I have used the same variable names as those used in the standards publication (even when they are rather cryptic like "Nr" and "w").

My design uses the nine data members and one enumeration type as shown here:

public enum KeySize { Bits128, Bits192, 
                      Bits256 };  

private int Nb;         
private int Nk;         
private int Nr;         

private byte[] key;     
private byte[,] Sbox;   
private byte[,] iSbox;  
private byte[,] w;       
private byte[,] Rcon;   
private byte[,] State;  

Because the key size can only be 128, 192, or 256 bits, it is a great candidate for an enumerated type:

public enum KeySize { Bits128, Bits192, Bits256 };

The specification document generally uses bytes as its basic storage unit but uses 4-byte words as the size for two important data members. The two members Nb and Nk represent the block size in words and key size in words, respectively. Nr represents the number of rounds. The block size is always 16 bytes (or 128 bits, which is 4 words for AES), so it could have been declared as a constant. The key size is assigned a value of 4, 6, or 8 according to the value of the enumeration parameter KeySize. The AES algorithm iterates through a number of rounds to increase the complexity of the encrypted data. The number of rounds is either 10, 12, or 14 and is based on cryptanalysis theory. It depends directly on the key size.

When designing a class interface, I like to work backwards. I imagine calling the constructor and methods from an application. Using this approach, I decided that I wanted to instantiate an AES object like the following:

Aes a = new Aes(the key size, the seed key)

I called the encryption and decryption routines as follows:

a.Cipher(plainText, cipherText);
a.InvCipher(cipherText, decipheredText);

I chose the slightly awkward method names Cipher and InvCipher because they are used in the AES specification document. Here is the code for the AES class constructor:

public Aes(KeySize keySize, byte[] keyBytes)
{
  SetNbNkNr(keySize);

  this.key = new byte[this.Nk * 4];  
  keyBytes.CopyTo(this.key, 0);

  BuildSbox();
  BuildInvSbox();
  BuildRcon();
  KeyExpansion();  

} 

The constructor first set the values of Nb, Nk, and Nr by calling a helper method SetNbNkNr, which is shown in Figure 8. If efficiency is a concern, you could put this code directly in the constructor to avoid the overhead of a method call.

 Figure 8 SetNbNkNr Method

private void SetNbNkNr(KeySize keySize)
{
  this.Nb = 4;     

  if (keySize == KeySize.Bits128)
  {
    this.Nk = 4;   
    this.Nr = 10;  
  }
  else if (keySize == KeySize.Bits192)
  {
    this.Nk = 6;   
    this.Nr = 12;
  }
  else if (keySize == KeySize.Bits256)
  {
    this.Nk = 8;   
    this.Nr = 14;
  }
}  // SetNbNkNr()

Next, you have to copy the bytes that are passed into the constructor into the class field variable. The key is declared with the other class fields and it gets its value by doing this:

this.key = new byte[this.Nk * 4];  
keyBytes.CopyTo(this.key, 0);

I decided to call the initialization of the substitution tables Sbox[] and iSbox[] using the private helper methods BuildSbox and BuildInvSbox in the constructor. Now Sbox[] and iSbox[] are required by the key expansion routine and the Cipher and InvCipher methods, respectively, so I could have put initialization of Sbox[] and invocation of the KeyExpansion method in both the Cipher and the InvCipher methods, but putting them in the constructor results in a cleaner code structure. sBox[] gets populated in Figure 9. The code that populates iSbox[] is similar. The code is structured for readability. As you'll see later, there is a surprising alternative to this way of supplying values for the Sbox and iSbox tables.

 Figure 9 Sbox Initialization

private void BuildSbox()
{
  this.Sbox = new byte[16,16] {  // populate the Sbox matrix
/*        0     1     2     3     4     5     6     7     8     9     a     b     c     d     e     f */
/*0*/  {0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76},
/*1*/  {0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0},
/*2*/  {0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15},
/*3*/  {0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75},
/*4*/  {0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84},
/*5*/  {0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf},
/*6*/  {0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8},
/*7*/  {0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2},
/*8*/  {0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73},
/*9*/  {0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb},
/*a*/  {0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79},
/*b*/  {0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08},
/*c*/  {0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a},
/*d*/  {0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e},
/*e*/  {0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf},
/*f*/  {0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16} };

}  // BuildSbox()

Declaring the key schedule table w[], the round constants table Rcon[] and the state matrix State[] in the constructor, and assigning values to Rcon[] and w[] with private helper methods seems to me to be the best way to organize them, but that is mostly a matter of style. The code that populates the round constant table Rcon is shown in Figure 7.

Recall that the left byte of each row of Rcon[] is a power of 2 in GF(28) so this table could be built computationally using something like the following:

newVal = prevVal * 0x02;

The AES constructor finishes by building the key schedule table w[] which is done in the KeyExpansion method (see Figure 10). The code is fairly straightforward. The specification document uses a hypothetical 4-byte word data type. Since C# has no such type, it is simulated with an array of 4 bytes. After the key schedule w[] is allocated space using the operator new, the first Nk (4, 6, or 8) rows of w[] get values from the seed key[] array that was passed into the constructor:

this.w[row,0] = this.key[4*row];
this.w[row,1] = this.key[4*row+1];
this.w[row,2] = this.key[4*row+2];
this.w[row,3] = this.key[4*row+3];

 Figure 10 KeyExpansion Method

private void KeyExpansion()
{
  this.w = new byte[Nb * (Nr+1), 4];  
  
  for (int row = 0; row < Nk; ++row)
  {
    this.w[row,0] = this.key[4*row];
    this.w[row,1] = this.key[4*row+1];
    this.w[row,2] = this.key[4*row+2];
    this.w[row,3] = this.key[4*row+3];
  }
  
  byte[] temp = new byte[4];
  
  for (int row = Nk; row < Nb * (Nr+1); ++row)
  {
    temp[0] = this.w[row-1,0]; temp[1] = this.w[row-1,1];
    temp[2] = this.w[row-1,2]; temp[3] = this.w[row-1,3];
  
    if (row % Nk == 0)  
    {
      temp = SubWord(RotWord(temp));
  
      temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );
      temp[1] = (byte)( (int)temp[1] ^ (int)this.Rcon[row/Nk,1] );
      temp[2] = (byte)( (int)temp[2] ^ (int)this.Rcon[row/Nk,2] );
      temp[3] = (byte)( (int)temp[3] ^ (int)this.Rcon[row/Nk,3] );
    }
    else if ( Nk > 6 && (row % Nk == 4) )  
    {
      temp = SubWord(temp);
    }
  
    // w[row] = w[row-Nk] xor temp
    this.w[row,0] = (byte) ( (int)this.w[row-Nk,0] ^ (int)temp[0] );
    this.w[row,1] = (byte) ( (int)this.w[row-Nk,1] ^ (int)temp[1] );
    this.w[row,2] = (byte) ( (int)this.w[row-Nk,2] ^ (int)temp[2] );
    this.w[row,3] = (byte) ( (int)this.w[row-Nk,3] ^ (int)temp[3] );
  
  }  // for loop
}  // KeyExpansion()

The operation of XORing 2 bytes together happens a lot in this code. It requires some casting from byte to int and back to byte because the XOR operator ^ is not defined on the C# byte type. For example

temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );

is used instead of:

temp[0] = temp[0] ^ this.Rcon[row/Nk,0];

The KeyExpansion method conditionally calls the private methods SubWord and RotWord to maintain naming consistency with the specification. Again, because there is no word type in C#, I implemented one using an array of 4 bytes. The code for SubWord and RotWord is fairly simple and you should be able to understand it easily by examining it in the AesLib source code that accompanies this article.

The slightly tricky part is looking up the substitution values in SubWord. Recall that to find the substitute value, you separate the input byte into its leftmost 4 bits and its rightmost 4 bits. For a given byte, right-shifting 4 bits with the >> operator will yield the x index, and logical ANDing with 0000 1111 will yield the y value. In slightly longer, but more readable form than the actual code, I could have done something like the following

int x = word[0] >> 4;
int y = word[0] & 0x0f;
byte substitute = this.Sbox[x,y];
result[0] = substitute;

instead of the code I used:

result[0] = this.Sbox[ word[0] >> 4, word[0] & 0x0f ];

To summarize, the AES constructor accepts a key size of 128, 192, or 256 bits and a byte array seed key value. The constructor assigns values for the input block size, the seed key size, and the number of rounds for the encryption algorithm and copies the seed key to a data member named key. The constructor also builds four tables: two substitution tables used by the encryption and decryption methods, a table of round constants, and a key schedule of round keys.

The AES Cipher Method in C#

The code for the Cipher method is shown in Figure 11. It is really very simple because it mostly farms out the work to the private methods AddRoundKey, SubBytes, ShiftRows, and MixColumns.

 Figure 11 The Cipher Method

public void Cipher(byte[] input, byte[] output)  
{
  // state = input
  this.State = new byte[4,Nb];  
  for (int i = 0; i < (4 * Nb); ++i)
  {
    this.State[i % 4, i / 4] = input[i];
  }

  AddRoundKey(0);
        
  for (int round = 1; round <= (Nr - 1); ++round)  
  {
    SubBytes(); 
    ShiftRows();  
    MixColumns(); 
    AddRoundKey(round);
  }  

  SubBytes();
  ShiftRows();
  AddRoundKey(Nr);
          
  // output = state
  for (int i = 0; i < (4 * Nb); ++i)
  {
    output[i] = this.State[i % 4, i / 4];
  }

}  // Cipher()

The Cipher method starts by copying the plaintext input array to the state matrix State[]. After an initial call to AddRoundKey, the Cipher method iterates one time fewer than the total number of rounds. On the last round, the call to MixColumns is omitted as described in the specification.

The code for the AddRoundKey and SubBytes private methods is shown in Figure 12. The AddRoundKey method needs to know what round it is at so that it can reference the correct four rows of the key schedule array w[]. Notice that State[r,c] is XORed with w[c,r] and not w[r,c]. The SubBytes method extracts indexes from the input byte using the same right-shift-4-bits and mask-with-0x0f technique used in the KeyExpansion method.

 Figure 12 AddRoundKey and SubBytes Methods

private void AddRoundKey(int round)
{
  for (int r = 0; r < 4; ++r)
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = (byte) ( (int)this.State[r,c] ^
                                 (int)w[(round*4)+c,r] );
    }
  }
}  // AddRoundKey()

private void SubBytes()
{
  for (int r = 0; r < 4; ++r)
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = this.Sbox[ (this.State[r,c] >> 4),
                                   (this.State[r,c] & 0x0f) ];
    }
  }
}  // SubBytes

The code for the ShiftRows method is shown in Figure 13. Recall that ShiftRows (which might have been better named RotateRows) rotates row[0] 0 positions to the left, row[1] 1 position to the left, and so forth.

 Figure 13 ShiftRows Method

private void ShiftRows()
{
  byte[,] temp = new byte[4,4];
  for (int r = 0; r < 4; ++r)  
  {
    for (int c = 0; c < 4; ++c)
    {
      temp[r,c] = this.State[r,c];
    }
  }

  for (int r = 1; r < 4; ++r)  // 
  {
    for (int c = 0; c < 4; ++c)
    {
      this.State[r,c] = temp[ r, (c + r) % Nb ];
    }
  }
}  // ShiftRows()

After copying State[] into a temp[] matrix, the shifts are then performed with:

this.State[r, (c + r) % Nb ] = temp[r,c];

This takes advantage of the % operator to wrap around a row.

The MixColumns method (see Figure 14) takes every byte and substitutes it with a linear combination of all the other values in the byte's column using GF(28) addition and multiplication. The constant coefficients used for multiplication are based on field theory and are either 0x01, 0x02, or 0x03. The substitution for a given column c is:

State[0,c] = 0x02 * State[0,c] + 0x03 * State[1,c] + 0x01 * State[2,c] +
    0x01 * State[3,c]
State[1,c] = 0x01 * State[0,c] + 0x02 * State[1,c] + 0x03 * State[2,c] +
    0x01 * State[3,c]
State[2,c] = 0x01 * State[0,c] + 0x01 * State[1,c] + 0x02 * State[2,c] +
    0x03 * State[3,c]
State[3,c] = 0x03 * State[0,c] + 0x01 * State[1,c] + 0x01 * State[2,c] +
    0x02 * State[3,c]

 Figure 14 MixColumns Method

private void MixColumns()
{
  byte[,] temp = new byte[4,4];
  for (int r = 0; r < 4; ++r)  
  {
    for (int c = 0; c < 4; ++c)
    {
      temp[r,c] = this.State[r,c];
    }
  }
      
  for (int c = 0; c < 4; ++c)
  {
    this.State[0,c] = (byte) ( (int)gfmultby02(temp[0,c]) ^
                               (int)gfmultby03(temp[1,c]) ^
                               (int)gfmultby01(temp[2,c]) ^
                               (int)gfmultby01(temp[3,c]) );

    this.State[1,c] = (byte) ( (int)gfmultby01(temp[0,c]) ^
                               (int)gfmultby02(temp[1,c]) ^
                               (int)gfmultby03(temp[2,c]) ^
                               (int)gfmultby01(temp[3,c]) );

    this.State[2,c] = (byte) ( (int)gfmultby01(temp[0,c]) ^
                               (int)gfmultby01(temp[1,c]) ^
                               (int)gfmultby02(temp[2,c]) ^
                               (int)gfmultby03(temp[3,c]) );

    this.State[3,c] = (byte) ( (int)gfmultby03(temp[0,c]) ^
                               (int)gfmultby01(temp[1,c]) ^
                               (int)gfmultby01(temp[2,c]) ^
                               (int)gfmultby02(temp[3,c]) );
    }
  }  // MixColumns

These expressions are a bit long already so I decided to write private helper functions that return the product of GF(28) multiplication by 0x01, 0x02, and 0x03. The helper functions are very short. For example, the code that's used to field-multiply a byte b by 0x03 is as follows:

return (byte) ( (int)gfmultby02(b) ^ (int)b ); 

As I discussed earlier, multiplication by 0x02 is the essential operation for all GF(28) multiplication. I called my gfmultby02 method, bending my convention of using the same method names that have been used in the specification; the specification calls this routine xtime.

The Cipher method iteratively applies four operations on its input to produce encrypted output. AddRoundKey substitutes bytes using multiple round keys derived from the single original seed key. SubBytes substitutes bytes using values in a substitution table. ShiftRows permutes bytes by shifting rows of bytes, and MixColumns substitutes bytes using field addition and multiplication of values in a column.

The AES InvCipher Method in C#

The basic premise behind the AES decipher algorithm is simple: to decrypt an encrypted block, just undo every operation in the reverse order. Although this is the basic concept, there are a few details to handle.

The AES specification names the decipher routine InvCipher rather than alternatives Decipher or Decrypt. This is a reflection of the mathematics behind AES, which are based in terms of inverse mathematical operations.

If you compare this code with the Cipher code, you will see that it is pretty much what you might expect, but with two exceptions. First, the order of the inverse method calls (like InvSubBytes) in the InvCipher method is not exactly the reverse of the corresponding calls (like SubBytes) in the Cipher method, and second, InvCipher calls the AddRoundKey method instead of an InvAddRoundKey method. Notice that the InvCipher algorithm uses the key schedule table but starts at the higher-numbered indexes and works its way down to row 0.

The code for the InvSubBytes, InvShiftRows, and InvMixColumns methods closely mirrors the code for the related SubBytes, ShiftRows, and MixColumns methods. The InvSubBytes method is just like the SubBytes method except that it uses the inverse substitution table iSbox[] instead of the Sbox[] table.

As you might guess, iSbox[] just undoes any mapping performed by Sbox[]. For example, if you have byte b that equals 0x20 and find its substitution value in Sbox[], you get 0xb7. If you look up the substitution value for 0xb7 in iSbox[], you get 0x20.

Similarly the InvShiftRows method undoes the ShiftRows method—row[0] is shifted 0 positions to the right, row[1] is shifted 1 position right, row[2] is shifted 2 positions right, and row[3] is shifted 3 positions right.

The InvMixColumns method undoes the work of MixColumns, but not in an obvious way. Recall that MixColumns replaces each byte in the state matrix with a linear combination of bytes in the original byte's column and that the coefficients were 0x01, 0x02, and 0x03. Once again, field theory comes into play. It turns out that the inverse operation is similar but uses multiplication by 0x09, 0x0b, 0x0d, and 0x0e like this:

State[0,c] = 0x0e * State[0,c] + 0x0b * State[1,c] + 0x0d * State[2,c] +
    0x09 * State[3,c]
State[1,c] = 0x09 * State[0,c] + 0x0e * State[1,c] + 0x0b * State[2,c] +
    0x0d * State[3,c]
State[2,c] = 0x0d * State[0,c] + 0x09 * State[1,c] + 0x0e * State[2,c] +
    0x0b * State[3,c]
State[3,c] = 0x0b * State[0,c] + 0x0d * State[1,c] + 0x09 * State[2,c] +
    0x0e * State[3,c] 

As with the MixColumns method, I decided to write dedicated helper functions rather than expand the already long expressions inline or write a general multiplication helper function. Let me show you how I wrote the function that multiplies any byte, b, by the constant 0x0e (14 in base 10). The number 14, like any number, can be expressed as the sum of powers of 2. In this case, 14 equals 2 + 4 + 8. And since 4 equals 2 squared and 8 equals 2 cubed, you can express 14 as 2 + 22 + 23. Remember that addition is just XOR (^) in GF(28) and since I already have the gfmultby02 function, I can use it to get my result:

return (byte)( (int)gfmultby02(gfmultby02(gfmultby02(b))) ^  /* 23 + */
                    (int)gfmultby02(gfmultby02(b)) ^         /* 22 + */
                    (int)gfmultby02(b) );                    /* 2    */

All of the operations used by the AES encryption algorithm are invertible, so the decryption algorithm essentially reverses all the operations performed by encryption.

Using the AES Class

One of the features of AES as implemented in C# is its simplicity. Consider the code in Figure 15 that I used to generate the output shown in Figure 1. After declaring hardcoded values for the 16-byte plaintext input and the 24-byte (192-bit) seed key, an AES object is initialized, the encrypting Cipher method encrypts the plaintext to cipher text, and then the cipher text is decrypted back using InvCipher. Very clean and simple.

 Figure 15 Using AES

static void Main(string[] args)
{
  byte[] plainText = new byte[] {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 
      0x66, 0x77,0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff};
    
  byte[] cipherText = new byte[16];
  byte[] decipheredText = new byte[16];
    
  byte[] keyBytes = new byte[] {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 
      0x07,0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,0x10, 0x11, 
      0x12, 0x13, 0x14, 0x15, 0x16, 0x17};
  
  Aes a = new Aes(Aes.KeySize.Bits192, keyBytes);

  Console.WriteLine("\nAdvanced Encryption System Demo in .NET");
  Console.WriteLine("\nThe plaintext is: ");
  DisplayAsBytes(plainText);

  Console.WriteLine("\nUsing a " + Aes.KeySize.Bits192.ToString() + 
      "-key of: ");
  DisplayAsBytes(keyBytes);
   
  a.Cipher(plainText, cipherText);

  Console.WriteLine("\nThe resulting ciphertext is: ");
  DisplayAsBytes(cipherText);

  a.InvCipher(cipherText, decipheredText);

  Console.WriteLine("\nAfter deciphering the ciphertext, the result 
      is: ");
  DisplayAsBytes(decipheredText);

  Console.WriteLine("\nDone");
  Console.ReadLine();
}  // Main()

static void DisplayAsBytes(byte[] bytes)
{
  for (int i = 0; i < bytes.Length; ++i)
  {
    Console.Write(bytes[i].ToString("x2") + " " );
    if (i > 0 && i % 16 == 0) Console.Write("\n");
  }
  Console.WriteLine("");
}  // DisplayAsBytes()

Because an AES object works on byte arrays, you can easily adapt it to work on other .NET data types. I constructed a little Windows®-based demo app that accepts a single 8-character (16-byte) string and then encrypts and decrypts it. A sample run is shown in Figure 16.

Figure 16 Encryption Demo 

Because both the encryption and decryption routines need to know what key size the user has specified, I declared it as a class-scope variable, like this:

private Aes.KeySize keysize;  

Notice that the seed key is not specified by the user. The demo uses a "null key" which consists of all zero bytes by supplying a dummy new byte[16] to the constructor. The size of the dummy argument is irrelevant because the seed key will also be initialized to all zeros. Null key encryption and decryption is an easy and effective way to deter casual external examination of your data. The Encoding.Unicode.GetBytes and Encoding.Unicode.GetString methods in System.Text make it very easy to convert a .NET string to a byte array, and vice versa.

Implementation Alternatives

Now let's look at some important variations of the AES implementation presented in this article, possible extensions of the code presented here, and cryptanalysis attacks against AES.

As much as any code that I've ever worked on, the AES algorithm has significant alternative approaches to implementation. Why is this important? AES is intended to be applicable to a wide range of systems, from smart cards with tiny memory capacities to large multiprocessor mainframe systems. In many scenarios, performance is critical and sometimes memory or processing resources are limited. Virtually every routine in AES can be modified to optimize performance at the expense of memory, or vice versa. For example, assigning the 256 values to the substitution table Sbox[] seems straightforward enough. However, these values are based on GF(28) theory and it turns out that these values can be generated programmatically. The same is true for the inverse substitution table and the round constants table.

Another interesting possibility for alternate implementation is the GF(28) multiplication used by the Cipher and InvCipher methods. My implementation codes a basic function that multiplies by 0x02 and then six additional functions which call gfmultby02. Another possibility would be to write a general multiplication function and use it instead of implementing seven separate functions like I did. At another extreme you could use a complete table of the product of all 256 possible byte values multiplied by 0x01, 0x02, 0x03, 0x09, 0x0b, 0x0d, and 0x0e. Yet another way to approach GF(28) multiplication is to implement it as a lookup into two 256-byte arrays, usually called alog[] and log[] because they are based on certain logarithm-like properties of GF(28).

Although the AES class presented here is fully capable of encrypting any form of .NET data, you might want to consider extending it in a number of ways. First, because the emphasis of this article is on presenting a clear explanation of AES, all error checking was stripped away. In my experience, adding a reasonable amount of error checking to a class similar to this AES class would triple the size of the source code. Because AES uses so many arrays, there is a lot of index bounds checking that should be done. For example, the constructor presented does not even check the size of the seed key parameter.

You might also consider extending this AES class by adding more features. The most obvious place to start would be to add methods that encrypt and decrypt fundamental .NET data types such as System.String and System.Int32. A more ambitious extension would be to implement an encrypted stream class.

How secure is AES? This is a hard question to answer, but the general consensus is that it is the most secure encryption algorithm available. AES has been subjected to more scrutiny than any other encryption algorithm to date. On both a theoretical and practical basis, AES is considered "secure" in the sense that the only effective way to crack it is through a brute-force generation of all possible keys. With a key size of 256 bits, no known brute-force attack can break AES in a reasonable amount of time (it would take years even on the fastest systems available).

Note that the most likely successful attack on an AES cipher results from a weak implementation that allows what is called a timing attack. The attacker uses different keys and precisely measures the time the encryption routine requires. If the encryption routine is carelessly coded so that execution time depends on the key value, it is possible to deduce information about the key. In AES, this is most likely to occur in the MixColumns routine because of field multiplication. Two safeguards against this attack are to insert dummy instructions so that all multiplications require the same number of instructions, or to implement field multiplication as a lookup table, as I've described.

There are many possible implementations of AES, especially using lookup tables rather than computation. The basic AES class presented in this article can be used to encrypt and decrypt any form of .NET data or can be extended into a class with added functionality.

Conclusion

The new AES will certainly become the de facto standard for encrypting all forms of electronic information, replacing DES. AES-encrypted data is unbreakable in the sense that no known cryptanalysis attack can decrypt the AES cipher text without using a brute-force search through all possible 256-bit keys.

The major obstacle I found when implementing an AES class in the Microsoft® .NET Framework was that the official specification document was written from a mathematician's point of view rather than from a software developer's point of view. In particular, the specification assumes that the reader is fairly familiar with the GF(28) field and it leaves out a few key facts regarding GF(28) multiplication that are necessary to correctly implement AES. I've tried here to remove the mystery from AES, especially surrounding GF(28) field multiplication.

It is only a question of time before AES encryption becomes widely available from Microsoft and third-party vendors in the form of .NET Framework libraries. However, having this code in your skill set will remain valuable for a number of reasons. This implementation is particularly simple and will have low resource overhead. In addition, access to and an understanding of the source code will enable you to customize the AES class and use any implementation of it more effectively.

Security is no longer an afterthought in anyone's software design and development process. AES is an important advance and using and understanding it will greatly increase the reliability and safety of your software systems.

For related articles see:
Security: Protect Private Data with the Cryptography Namespaces of the .NET Framework
Exploring Kerberos, the Protocol for Distributed Security in Windows 2000

For background information see:
The Design of Rijndael: AES - The Advanced Encryption Standard by Joan Daemen and Vincent Rijmen. (Springer-Verlag, 2002)

James McCaffrey works for Volt Information Sciences Inc. where he manages technical training for software engineers at Microsoft. He has worked as a contractor on several Microsoft products including Internet Explorer and MSN Search. Reach him at or .