最近需要细节看一下 AES 算法的底层设计，S 盒不能只通过查表来实现了。
随便在中文世界里面搜索了下 S 盒的生成，发现讲得真是非常复杂，大多数也都是用 C/C++ 代码来实现的，直接看代码也无法很快 get 到点。最后发现还是去看维基最为清楚。
$\mathrm{GF}(2^8)$ 有限域
简单回顾一下以前的知识。 AES 中使用的有限域可以有以下几个步骤来生成：
- 首先有 $\mathrm{GF}(p)$ 形成的有限域（$p$ 要求是素数）。
- 有系数为 $\mathrm{GF}(p)$ 中元素的的多项式环 $\mathrm{GF}(p)[X]$ 。
- 有其对于某不可约多项式 $P$ 生成的双边理想的商环 $\mathrm{GF}(p)[X]/P$ 。
- 这个商环又是有限域了。
在这个过程中，选取合适的多项式 $P = x^8 + x^4 + x^3 + x + 1$，使得商环中的元素（也是多项式）最大 order 是 7，$p$ 取 2 （系数就只能是 0 或者 1 了）。
这样，就可以用 8-bit 的字节来进行表示了，即常见表示 $\mathrm{GF}(2^8)$。 此后所有 AES 中操作的最小单位就是这个字节（多项式）了。
各种运算
这样就比较好理解，为什么初学 AES 时，里面的加减乘除操作，有些实现得不可思议地简单，有些又实现得很奇怪。
- 加减操作（ $+/-$），由于继承了 $\mathrm{GF}(2)$ 的特性，实现起来都是按位异或。
- 乘法操作（$\times$），由于涉及到了商环，因此会进行多项式模，所以就会需要在特定条件下异或一个常数。
另外在生成 S 盒的时候，还会有幂次和取逆。
- 幂次（$g^n$），可以简单利用快速幂实现。
- 取乘法逆元（$g^{-1}$），有 $g \times g^{254} = g^{255} = 1$，得到 $g \times g^{254} = 1$。如此一来，乘法逆元也可以用幂次的方法得到。（快速幂的实现也使得在不特别考虑性能的情况下够用了）
S 盒的具体生成
简单来说，S 盒的变换是一个仿射变换和取乘法逆元的叠加。其中仿射变换可以写为元素的多个循环移位的异或。
对于正向的 S 盒，是先求逆，再进行变换。
$$ s=b\oplus (b\lll 1)\oplus (b\lll 2)\oplus (b\lll 3)\oplus (b\lll 4)\oplus 63_{16} $$
对于逆向的 S 盒，是先变换，再求逆。
$$ b=(s\lll 1)\oplus (s\lll 3)\oplus (s\lll 6)\oplus 5_{16} $$
其中，$b = s^{-1}$。
实现
然后就是简单实现了。
|
|