有限域GF(2⁸)上的运算法则

AES中列混淆的矩阵乘法是在有限域GF(2⁸)上进行的

要学会计算它，需要从域开始了解

一、域（Field）

设 F 是一个非空集合，若在 F 上定义了两种二元运算：加法（记作 +）和乘法（记作 × 或省略），且满足以下条件，则称 F 为一个域：

1. 加法结构

  • 封闭性：对任意 a,b∈F，有 a+b∈F。
  • 结合律：对任意 a,b,c∈F，有 (a+b)+c=a+(b+c)。
  • 交换律：对任意 a,b∈F，有 a+b=b+a。
  • 单位元：存在元素 0∈F，使得对任意 a∈F，有 a+0=a。
  • 逆元：对任意 a∈F，存在元素 −a∈F，使得 a+(−a)=0。

2. 乘法结构

  • 封闭性：对任意 a,b∈F，有 a×b∈F。
  • 结合律：对任意 a,b,c∈F，有 (a×b)×c=a×(b×c)。
  • 交换律：对任意 a,b∈F，有 a×b=b×a。
  • 单位元：存在元素 1∈F（1≠0），使得对任意 a∈F，有 a×1=a。
  • 逆元：对任意非零元素 a∈F，存在元素 a⁻¹∈F，使得 a×a⁻¹=1。

值得注意的是，域并没有对乘法结构要求“零因子”，即没有要求存在元素 0∈F，使得对任意 a∈F，有 a×0=0

3. 分配律

  • 对任意 a,b,c∈F，有：a×(b+c)=(a×b)+(a×c)

根据以上对域的描述我们可以发现，所有的实数组成的集合就是一个域，

为实数域ℝ

类似的还有有理数域 ℚ、复数域 ℂ

还有本文的重点有限域GF(q)

二、有限域

有限域（Finite Field） 是指包含有限个元素的域，也称为伽罗瓦域（Galois Field），记为GF(q)，其中q是有限域的阶（即元素的个数）

有限域的阶

有限域的阶q必须满足：q是某个素数p的正整数次幂，即q=pⁿ（p为素数，n为正整数）

  • 当n=1时，GF(p)是最简单的有限域，元素为0,1,2,…,p−1，运算规则为 “模p加法” 和 “模p乘法”（例如GF(2)的元素是0和1，加法为异或，乘法为与）。
  • 当n>1时，有限域GF(pⁿ)的元素需要通过 “多项式运算” 构造。

GF(2³)的元素是次数小于3的二进制多项式

GF(3²)的元素是次数小于2的三进制多项式

多项式表示法

GF(pⁿ) 的每个元素可以表示为一个系数在 GF(p) 中的多项式，且多项式的次数小于 n（多项式的幂次是从x⁰到xⁿ⁻¹）

具体写作：image-20250711210526299

其中系数a∈{0,1,…,p−1}

举例：GF(2³)中，101表示为x²+1

GF(3²)中，21表示为2x+1

多项式的运算法

1.加法

在多项式运算中，加法和减法完全等价，均为异或（加减等价是因为异或的结果相同）

0+0=0

0+1=1

1+1 =0

多项式相加是对应系数模p相加

如

(x²+1) + (x² + x + 1) = (x)

并且注意低幂次系数相加不会向高幂次系数产生进位

2.乘法

多项式进行乘法运算分为两步

第一步是普通多项式相乘

第二步是相乘结果对不可约多项式取模

不可约多项式

在抽象代数中，不可约多项式（Irreducible Polynomial） 是多项式环中的一类特殊多项式，其地位类似于整数中的素数（质数）

设 P(x) 是系数在域 F 上的非零多项式（即 P(x)∈F[x]）。若满足以下条件，则称 P(x) 是不可约多项式：

  1. 次数至少为 1：常数多项式（次数为 0）不是不可约多项式。

  2. 无法分解为更低次多项式的乘积：（可以看出和质数的相似）

    若存在两个次数更低的多项式 A(x) 和 B(x)（次数均 ≥1），使得 P(x)=A(x)×B(x)，则 P(x) 是可约的；否则，P(x) 是不可约的。

而在乘法计算中，不可约多项式的选取不可约多项式 m(x) 的次数必须恰好为 n，以确保生成的有限域包含pⁿ个元素

这个很好理解，选择最高次数为n的不可约多项式，取模时可以消去普通相乘结果中所有次数大于等于n的项，而保留次数0~n-1的项

实际操作演示：

在GF(2⁸)中，计算10000000 × 00000111 = ？

  1. 化为多项式表示，并作普通相乘：x⁷(x²+x+1) = x⁹ + x⁸ + x⁷

  2. 查找GF(2⁸)常用的不可约多项式为：x⁸+x⁴+x³+x+1

  3. 普通相乘结果对不可约多项式取模

    x⁹ mod m(x)= [x⁸ mod m(x) * x mod m(x)] mod m(x)

    又由x⁸ ≡ x⁴+x³+x+1 mod m(x) 由加减等价很容易推导

    最终我们容易得到取模结果为

    x⁷ + x⁵ + x³ + x² + 1

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mod_polynomial(a, m):
    """
    计算多项式 a 模不可约多项式 m 的结果
    输入：a, m 为系数列表，按降幂排列
    输出：余式的系数列表
    """
    while len(a) >= len(m):
        if a[0] == 0:  # 最高次项系数为0
            a = a[1:]  # 去掉前导零
            continue
        factor = a[0]
        shift = len(a) - len(m)
        # 用 m 消去 a 的最高次项
        for i in range(len(m)):
            a[i] ^= (m[i] * factor)  # 系数模2（异或）
        a = a[1:]  # 去掉最高次项
    return a or [0]  # 确保结果不为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gf_multiply(a, b, m):
    """
    在 GF(2^n) 中计算 a * b mod m
    输入：a, b, m 为系数列表
    输出：乘积的系数列表
    """
    # 普通多项式乘法（结果系数为0/1）
    product = [0] * (len(a) + len(b) - 1)
    for i in range(len(a)):
        for j in range(len(b)):
            product[i + j] ^= (a[i] * b[j])  # 系数模2
    # 对 m 取模
    return mod_polynomial(product, m)

有限域的生成元(本原元)

生成元（本原元）：若 g 的幂次能生成 Fₚˣ中所有元素（即每个非零元素都可写成 gⁿ mod p 的形式），则 g 称为 Fₚ的生成元。

  • 若 g 是生成元，则 Fₚˣ中所有元素都可以写成 g 的幂次形式：Fₚˣ = {g¹ mod p, g² mod p, …, g^(p-1) mod p}。（生成方法）
  • 等价地，g 的 “阶”（即满足 gᵏ ≡ 1 mod p 的最小正整数 k）必须等于 p-1（因为群的阶是 p-1，循环群中生成元的阶等于群的阶）。

上面的定义似乎有些我们还没学到的东西，要学习新的定义：

1.乘法群

乘法群 Fₚˣ：Fₚ中所有非零元素构成的集合 {1, 2, …, p-1}，对模 p 乘法封闭，称为 “乘法群”。其元素个数为 p-1（排除 0）。

2.元素的阶

元素的阶：对于 Fₚˣ中的元素 g，满足 gᵏ ≡ 1 mod p 的最小正整数 k，称为 g 的 “阶”，记为 ordₚ(g)

应当明确元素的阶和有限域的阶二者的区别

  • 有限域的阶是 “元素总数”，决定了域的规模；
  • 元素的阶是 “该元素幂次回到 1 的最小次数”，反映了元素在乘法群中的 “生成能力”。

详细解释需要牵涉到群论的内容