AES是现如今最为常用的对称加密算法，它不仅安全，而且性能表现也很出色。稍后，我们也会用它来加密HTTP API返回的数据。不过在使用这种加密算法之前，我们先来了解下这种加密算法是如何实现的。

为了看懂AES的实现，我们得补充一些必要的数学知识。要说一下的是，对这些数学知识的理解视角，是为了看懂AES的实现代码，并非研究数学理论。因此，接下来的有些描述可能不那么科学和严谨，但对于理解代码却足够用了。

群

我们要介绍的第一个概念，叫做群（Group）。数学中的群有下面几个性质：

• 首先，是封闭性。也就是说，对于可以在群里使用的操作（用op表示），如果a和b属于群G，那么a op b的结果也属于G；
• 其次，是群里的操作都支持结合律，也就是(a op b) op c = a op (b op c)；
• 第三，是群中一定存在一个元素e，使得群中的每一个元素a，都有a op e = e op a = a成立。我们管e叫做G的单位元（Identity Element）；
• 最后，群中的每一个元素a，一定可以在群中找到另外一个元素b，使得a ob p = b op a = e。这时，我们管b叫做a的逆元（Inverse Element）；

是不是听着有点儿晕，我们来个具体的例子。假设，在一个由所有整数..., -3, -2, -1, 0, 1, 2, 3, ...构成的集合Z里，我们限制只能在这个集合里做加法，那么显然：

• 两个整数相加的结果肯定还是整数，它满足封闭性；
• 整数加法当然也支持结合律；
• 在这个集合中，整数0满足a + 0 = 0 + a = a；
• 类似的，在这个集合中，整数-a满足a + (-a) = (-a) + a = 0；

因此，这个由所有整数构成的集合Z和整数的加法放在一起，就变成了一个群，这个群的单位元是0，每一个整数a的逆元是-a。

有限群

接下来，我们让刚才的集合Z只包含有限个元素，让Z1等于-3, -2, -1, 0, 1, 2, 3。这时，Z1和加法构成的组合就不能叫做一个群了，因为显然，1+3，2+3都已经超过了Z1表达的范围。至于群剩余的属性，Z1仍旧是满足的。

那如何让Z1也成为一个群呢？

其实很简单，不就是要限定数值的范围么？把结果对3取模就行了。于是，我们只要要求Z1可以进行的操作，是相加后对结果取模，组合上这种操作，Z1就是一个新的群了。通过这个过程，我们可以挖掘出三个新的认知：

• 首先，群操作不一定有交换律，对于Z来说，操作只有加法，因此a + b = b + a。但对于Z1来说，由于相加之后还要取模，这时操作的顺序就很重要了，它并不支持交换律。并且，在数学里，管这种支持交换律的群，叫做可交换群，也叫做阿贝尔群，这是用提出这个概念的挪威数学家尼尔斯·阿贝尔命名的；
• 其次，对于这种元素个数有限的群，也有一个专门的名字，叫做有限群，而元素的数量，叫做有限群的阶，也就是说，Z1是一个6阶有限群；
• 最后，群的计算操作只是一种抽象描述，它并不局限于单一的初等代数中的四则运算，请大家务必要理解这个；

域

了解了群之后，我们来介绍第二个概念，叫做域（Field）。组成一个域的元素有下面这些性质：

• 可以形成一个加法交换群，这个群的单位元为0；
• 除了0之外，可以形成一个乘法交换群，这个群的单位元为1；
• 当混合使用加法和乘法的时候，分配律总是成立的，即：(a + b) * c = (a * c) + (b * c)；

那什么样的集合有这样的性质呢？其中最家常的例子，就是实数集合。因为：

• 实数集合的加法支持交换律，并且任何数加0都是自己；
• 实数集合的乘法也支持交换律，任何数乘1都是自己；
• 实数集合上的乘法和加法当然也支持结合律；

伽罗瓦域（Galois field）

和刚才研究群类似，如果我们限定一下域中的元素又如何呢？由于域要求其中的元素同时可以形式加法交换群和乘法交换群，它一下子就不那么容易直观想象的出来了。不过，好在已经有数学家为我们研究出了一个定理：

如果m等于一个素数p的n次幂（n为正整数），即：m = p^n时，才存在一个m阶的域。

其中：n等于1时叫做素域（Prime Field），n >= 2时，叫做扩展域（Field Extension）。

并且，这种元素个数有限的域还有一个特别的名字，叫做伽罗瓦域（Galois Field），记做GF(m)这是用它的提出者，法国数学家伽罗瓦的名字来命名的。

接下来，我们来看个最简单的2阶伽罗瓦域GF(2)。它只包含两个元素：{0, 1}。但很明显，1+1已经超过了GF(2)能表达的范围，因此，这个域里面，它的加法和乘法同样是特别定制的，而定制的方法，就是对2取模：

(0 + 0) mod 2 = 0
(0 + 1) mod 2 = 1
(1 + 0) mod 2 = 1
(1 + 1) mod 2 = 0

(0 * 0) mod 2 = 0
(0 * 1) mod 2 = 0
(1 * 0) mod 2 = 0
(1 * 1) mod 2 = 1

也就是说，在GF(2)定义的这个世界里，加法操作的规则是：全0或全1相加等于0，否则等于1，它和计算机中二进制中的XOR是一样的。而乘法规则是：全1相乘等于1，否则等于0，它和二进制运算中的AND是一样的。

基于这样运算法则，不难推断，在GF(2)里，1的加法和乘法逆元都是它自己。这有什么用呢？这样，在GF(2)里，就可以支持减法和除法操作了。因为减1就是加上1的逆元，除以1就是乘以1的逆元。再说的直白一些，在GF(2)里，减法就是加法，除法就是乘法。在后面的内容中，我们就会看到，AES加密算法中，对每一个bit的处理，就用了GF(2)中的运算。

接下来，如果我们把bit放大到字节，就不难想到，为了可以用域表示一个字节的所有整数，我们得使用一个扩展域GF(2^8)。

用多项式表达的扩展域

对于GF(2^8)来说，我们并不能直接用0-255这256个数字来表示了，取而代之的方法，是使用多项式。GF(2^8)中的每一个元素，都用形如：

a7x^7 + a6x^6 + a5x^5 + ... + a1x + a0

这样的多项式表达。其中，a0 - a7是多项式的系数，它们只能从GF(2)中取值。这样，a0 - a7就代表了一个字节中的对应bit。并且，这些系数的运算法则，也使用刚才GF(2)中提到的加法和乘法法则。来看个例子：下面这两个，都是GF(2^8)中的元素：

A(x) = x^7 + x^5 + x^3 + 1
B(x) = x^2 + 1

多项式加法

按照之前的约定，它们分别表示二进制数的10101001和00000101。接下来，为了在GF(2^8)中计算A(x) + B(x)，我们只要按位依次执行GF(2)中的加法就好了，也就是说它等于：

  1 0 1 0 1 0 0 1
+ 0 0 0 0 0 1 0 1
------------------
  1 0 1 0 1 1 0 0

把这个结果对应到多项式，就是x^7 + x^5 + x^3 + x^2，而这个多项式对应的字节，是0xab。

多项式乘法

但GF(2^8)多项式的乘法，就麻烦一些了。为了计算A(x)B(x)，我们先按照普通代数的计算方法展开多项式：

A(x)B(x) = (x^7 + x^5 + x^3 + 1)(x^2 + 1)
  = x^9 + x^7 + x^5 + x^2 + x^7 + x^5 + x^3 + 1
  = x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1

然后，把这个多项式的系数对2取模：

    x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1
mod 2
--------------------------------------
    x^9                 x^3 + x^2 + 1

这样，就可以得到x^9 + x^3 + x^2 + 1。但问题是x^9已经超过了GF(2^8)可以表达的范围，它也对应不到计算机的一个字节中的bit。显然这个结果是不对的，怎么办呢？

其实，思路和刚才在处理GF(2)加法结果的时候是类似的。既然我们要把结果限定在x^8以内，那就把多项式对x^8取模不就行了。道理是这么个道理，不过这个取模的多项式，可不是随便选的。AES的设计者Vincent Rijmen 使用了一个经典的不可约多项式：P(x) = x^8 + x^4 + x^3 + x + 1。什么是不可约呢？就是说，P(x)不能表示为GF(2^8)域中两个多项式的乘积。这和自然数中的素数是类似的，因此，P(x)也叫素多项式。

由于P(x)的最高次幂是8，因此对P(x)取模，结果就一定会落在GF(2^8)里了，我们来算一下。先算xP(x)让P(x)升到9次幂：

xP(x) = x^9 + x^5 + x^4 + x^2 + x

其次，用x^9 + x^3 + x^2 + 1 - x(Px)：

  x^9 +             x^3 + x^2     + 1
- x^9 + x^5 + x^4 +       x^2 + x
--------------------------------------
        x^5 + x^4 + x^3       + x + 1

这样，得到的结果就落在GF(2^8)里了，它表示的二进制数是00111011，这就是GF(2^8)中A(x)B(x)的运算结果。下一节就会看到，AES正是使用这种方法对字节进行了处理。

求多项式的逆元

了解了多项式乘法之后，我们就能计算GF(2^8)中任意一个多项式A(x)的逆元了，AES加密算法需要这个值。要说明的是，选取的素多项式不同，GF(2^8)中元素的逆元也不同。这里，我们就用刚才说到的P(x)举例了。

对于给定的一个GF(2^8)中的多项式A(x)，如果A(x)B(x)的结果对P(x)取模等于1，那么B(x)就是A(x)的逆元了。那该怎么计算这个B(x)呢？

第一种方法，当然就是暴力穷举。用GF(2^8)中的每一个元素分别和A(x)计算；

第二种方法，来自于一个有趣的现象。GF(2^8)中的每一个非0多项式，都可以表示成(x+1)的n次幂，这里0<=n<=254，例如：

(x+1)^0 = 1
(x+1)^1 = x+1
(x+1)^2 = x^2+1
...
(x+1)^254 = x^7+x^6+x^5+x^4+x^3+x^2+x

注意这里我们执行的是GF(2)中的加法和乘法。并且，当n从255开始，就又会用和之前同样的顺序遍历GF(2^8)中的多项式。

(x+1)^255 = 1
(x+1)^256 = x+1
...

正是由于这种特性，(x+1)有了一个形象的名字，叫做生成元。有了生成元之后，我们可以把GF(2^8)中的每一个多项式和它对应的生成元的幂保存成一个映射表。接下来，对于给定的A(x)，如果B(x)是A(x)的逆元，则一定有下面的关系成立：

A(x)B(x) = (x+1)^a (x+1)^b = (x+1)^(a+b) = 1 (mod P(x))

于是，我们只要根据之前创建的映射表，查到A(x)对应的幂a，然后用255-a计算出b，再从表中查出b对应的多项式，就是A(x)的逆元了。

当然，除了这两种方法之外，还有很多数学上的手段来计算逆元，不过就像一开始说的，我们的重点并不是研究数学，也不会手动去计算逆元值。通过这些计算过程，大家理解和伽罗瓦域、单位元以及逆元这些概念的含义就行了。

What's next?

至此，为了实现AES加密算需要铺垫的数学知识，就说完了。下一节，我们就可以来看AES究竟是如何实现加密解密的了。

Discuss It

参与视频讨论