密码学中的一些数学基础

2023-05-05

上下标丢了，图裂了，先这样

=表示赋值, ==表示等于, ===表示同余

群 Group

由一个集合 G 和一个二元运算 * 构成，满足以下性质：

  • 封闭性：对于 G 中的任意元素 a 和 b，a * b 也在 G 中
  • 结合律：对于 G 中的任意元素 a, b 和 c，(a * b) * c = a * (b * c)
  • 单位元：存在 G 中的一个元素 e，对于 G 中的任意元素 a，满足 a * e = e * a = a
  • 逆元：对于 G 中的任意元素 a，存在 G 中的元素 a\，使得 a * a\ = a\ * a = e

群可能是有限的，也可能是无限的。如果群中的运算满足交换律，即对于 G 中的任意元素 a 和 b，a * b = b * a，则称该群为阿贝尔群（Abelian group）或交换群。

环

在群的基础上增加第二种运算

  1. 封闭性
  2. 加法结合律和交换律
  3. 乘法结合律和分配律
  4. 存在加法和乘法单位元
  5. 存在加法逆元

交换环则满足乘法交换律，不含0则为整环

环的乘法逆元不一定存在也就是说环不一定支持除法

域 Field

在群的基础上增加第二种运算，通常表示为加法+和乘法 ·，有以下性质

  1. 封闭性，对于F中任意a和b，a · b也在F中
  2. 结合律与交换律，即a · b == b · a，a · (b · c) == (a · b) · c
  3. 存在加法单位元0和乘法单位元1(不等于0), 是的a + 0 == a, a * 1 == a
  4. 存在加法逆元和乘法逆元，使得a + -a = 0，a * a^{-1} = 1

有限域(伽罗瓦域GF)

拥有有限元素的域是伽罗瓦域，表示为GF(n), 其中n成为有限域的阶(Cardinality)

素域及其扩展域

定理：只有当m是素数幂时(m=pn, p为素数，n为自然数)，阶为m的有限域才存在，这个素数称为该域的特征

p为素数则GF(p)为素域GF(pn)称为扩展域，其性质为

  1. GF(pn)中元素可表示为GF(p)上次数严格小于n的多项式(n-1维向量空间)
  2. 存在一个不可约多项式P作为该域中的模(也是加法逆元)
  3. GF(pn)中的加法是多项式系数相加模p加法，p==2则为XOR
  4. GF(pn)中的乘法是多项式乘法模p
举例

GF(28)的阶为8，其中次数(度)最大为7，其中元素为A(x) = a7x7 + ... + a1x1 + a0，不可约多项式可以为P = x4 + x + 1, 即

加法: b(10110011) + b(01100110) = b(11010101)

乘法: b(10110011) * b(01100110) = (x7 + x5 + x4 + x + 1) * (x6 + x5 + x2 + x) = (x13 + x11 + x10 + x7 + x6) + x12 + x10 + x9 + x6 + x5 + (x9 + x7 + x6 + x3 + x2) + x8 + x6 + x5 + x2 + x

= x13 + x12 + x11 + 2 * x10 + 2 * x9 + x8 + 2 * x7 + 4 * x6 + 2 * x5 + x3 + 2 * x2 + x

= (x13 + x12 + x11 + x8 + x3 + x) mod (x4 + x + 1)

= (x13 + x12 + x11 + x8 + x3 + x - x9 * (x4 + x + 1)) mod (x4 + x + 1)

= (x12 + x11 + x8 + x3 + x + x10 + x9) mod (x4 + x + 1)

= x7 + x3 + x

除法: 使用EEA求解线性同余方程A(X) * A-1(X) === 1 (mod P), 即A-1(X) * A(X) + y * P == 1

任意多项式的逆元为A-1(X) * A(X) = 1 mod P，A(X)和A-1(X)是非线性操作，构成了AES的S盒

一些简单算术/数论知识

  1. 欧几里得算法 gcd(a, b) = gcd (b, a % b)

```cpp int gcd(int m, int n) { int t = 1; while (t != 0) { t = m % n; m = n; n = t; } return m; }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } ```

  1. 扩展欧几里得算法EEA 裴蜀定理: ax + by = gcd(a, b)即如果a和b为整数则一定存在整数x和y使得ax+by=gcd(a, b)
  2. ax + by = m是否有解，任一组解，通解，最小整数解 x0 * a + y0 * b = m == gcd(a, b) == gcd(b, a % b) -> x1 * b + y1 * (a % b) = m -> x1 * b + y1 * (a - (a // b) * b) = m -> y1 * a + (x1 - (a // b) * y1) * b = m x0 = y1, y0 = x1 - (a // b) * y1
  3. 求解线性同余方程ax === b (mod n) 对于ax === b (mod n), 该方程等价于a * x + n * y == b == gcd(a, n)，求x
  4. 求逆元 即线性同余方程中的b为1时，ax === 1 (mod n) 使用EEA计算a * x + n * y == b则求得x与a在mod n中互为逆元

cpp int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int m = exgcd(b, a % b, x, y); int k = y; y = x - (a / b) * y; x = k; return m; }

  1. 欧拉函数 整数环Zm中与m互质的整数的个数为p，则欧拉函数为φ(m) = p 假设 m = p1e1 * p2e2 * ... * pnen 则φ(m) = (连乘1\~n)(piei - piei-1) 其中p为素数e为正整数 (分解质因数) 特别的，当m = p * q (p, q为质数), 则φ(m) = (p - p0) * (q - q0) = (p - 1) * (q - 1) 对于当前计算能力，当m为大整数时，可通过p和q得出φ(m)，而无法通过m直接得到φ(m)，这个过程为RSA的基础
  2. 费马小定理 a为整数，p为素数时，ap === a (mod p)，或ap-1 === 1 (mod p)或ap-2 === a-1 (mod p) 所有素数都符合费马小定理，(符合费马小定理不一定为素数，虽然很少)
  3. 欧拉定理 费马小定理的推广 假设a和m为互素的两个整数(gcd(a, m) == 1)则aφ(m) === 1 (mod m)

有限群

一个群(G, o)仅包含有限的n个元素则G为有限群，元素的个数为阶或基，表示为|G|

例子:

  • (Zn, +) |Zn| = n
  • (Zn*, · )由小于n且与n互素的正整数组成，即阶|Zn|为φ(n), 如Z9* = {1, 2, 3, 5, 7, 8}

循环群

群(G, o)内元素a的阶ord(a)为ak = a o a ... k次 ... o a == 1(G的单位元) 最小的k即为ord(a)

计算元素的阶最简单的方式就是疯狂计算直到得到单位元，这时会发现元素a的幂值在一个集合内循环, 如Z11* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }中元素3的幂值为{3, 9, 5, 4, 1}

定义: 如果群G包含ord(α) = |G|的元素α则G为循环群，α为本原元/生成元/原根

G中包含的所有元素都可以表示为生成元的幂值即Zn* 中的所有元素都可以表示为αk mod n，这个生成过程构成了离散对数问题的单向函数

如Z11* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }中的元素2，则210 == 1 mod 11即2是本原元，即2的0-10次方可以生成Z11*中的所有元素，2的指数i与元素a之间存在一种伪随机关系

定理: 对每个素数p，(Zp*, · ) 都是阿贝尔有限循环群

定理: 如G为有限群，则对G中所有元素α都有α |G| == 1且ord(α) | |G| (ord(α) mod |G| == 0)

尤其重要的就是有限群内所有元素的阶都是元素个数的约数

定理: 对有限循环群G，G中本原元的个数为φ(|G|), 如|G|为素数则所有不为中性元1的元素都是生成元

以G = Z11* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }为例，|G| = 10,

\"image\"

生成元为α== 2, 6, 7, 8 有四个，φ(10) = (2 - 1) * (5 - 1) = 4

子群

定理: 假设(G, o)为循环群，则G内每个满足ord(α) = s的元素α都是有s个元素的循环子群的本原元

Z11* 为例，ord(3) = 5, 则α == 3是一个有5个元素的循环群的生成元

该循环群H为{1, 3, 4, 5, 9}, |H| = 5生成如下, 注意循环子群的模是原循环群的模

30 mod 11 == 1, 31 mod 11 == 3, 32 mod 11 == 4, 33 mod 11 == 5, 34 mod 11 == 5, 35 mod 11 == 9

拉格朗日定理: 如H为G的子群，则|H|可以整除|G|

对G = Z11* ，|G| == 10 == 1 * 2 * 5则子群的阶位1， 2， 5

定理: 对生成元为α, 阶为n的有限循环群G, 对整除n的每个整数k, G都存在一个唯一的阶为k的循环子群H，该子群的生成元是αn/k，H由G中满足αk == 1的元素组成

根据这个定理，对于有限群G == Zm* ，其阶为n == |G| == φ(m)，找到αk == 1 mod m可以找到生成元α，计算αn/k就能得到拥有k个元素的子群生成元

衷心感慨，数学家真是太厉害了，如此抽象又合理的规则，无时无刻都在直接或间接地影响现实生活。