[笔记]密码学中的代数基础

发表于 | 分类于

在密码学的世界，代数结构(algebraic structure) 的发展给予了现代密码学很大的推动作用。密码学中用到最多的就是形如 GF(2n)\mathsf{GF}(2^n) 有限域，要聊到有限域，就必须从群开始说起。

1. 群(Group)

群本身可以看成一个满足某种运算(如："⋅\cdot")的集合,对于一个群 G\mathbb{G}来说，需要满足下面的4个基本性质：

  • 封闭性 (Closure): if a,b∈G,c=a⋅ba,b\in \mathbb{G},c=a\cdot b, then c∈Gc\in \mathbb{G}
  • 结合律 (Associativity): (a⋅b)⋅c=a⋅(b⋅c)(a\cdot b)\cdot c = a\cdot (b\cdot c)
  • 存在单位元 (Identity element): ∃e\exists e s.t. a⋅e=aa\cdot e = a
  • 存在逆元 (Inverse element): for a∈Ga\in G, ∃a′\exists a' s.t. a⋅a′=ea\cdot a' = e

如果满足交换性的话， 即 a⋅b=b⋅aa \cdot b = b \cdot a，那么这个群又称为循环群。

1.1 有限群(finite group)

有限群即群里的元素个数有限，对于有限群而言，我们用群的阶(order)来表示群里的元素个数，即 ∣G∣|\mathbb{G}|。

有限群有子群(subgroup)的概念，假如 HH 是 G\mathbb{G} 的子群，那么 HH 需要满足与 G\mathbb{G} 上相同的运算，并且两个群有共同的单位元。

每个群都是它自身的子群

注： 子群与子集的概念是不同的，因为子群还需要考虑到满足的运算要相同。

1.2 循环群(cyclic group)

如果一个群的子群是由某一个元素的幂生成的，这个子群称为循环子群(cyclic group)，产生这个循环子群的元素就被称为生成器(generator)。

Lagrange 定理: 如果 G\mathbb{G} 是一个群，HH 是它的子群，那么有 ∣H∣|H| 整除 ∣G∣|\mathbb{G}|

2. 环(Ring)

与群类似，环是满足一个二元计算的集合，如 R=<{...},⋅,⋄>R=<\{...\},\cdot,\diamond>，第一个运算需要满足交换群的五个性质，第二个运算只需要满足封闭性与结合律。 当然，如果第二个运算还满足交换性的话，就被称为交换环(commutative ring)。

3. 域(Field)

域可以看作是在环的基础上构建的，对于一个域 F=<{...},⋅,⋄>F=<\{...\},\cdot,\diamond>，其本身是一个交换环，并且对于第二个运算满足交换群的5个性质，除了对于第一个运算单位元无逆元之外。

最简单的域就是实数域 R\mathbb{R}，在实数域中，加法和乘法两个运算都满足封闭性，结合律与交换性。加法中的单位元为0,乘法中的单位元为1。对于每个实数 aa，它的加法逆元也就是 −a-a，它的乘法逆元(a≠0a\neq 0)就是 1/a1/a。