# encrypt

**Repository Path**: wufangjie/encrypt

## Basic Information

- **Project Name**: encrypt
- **Description**: 加密知识归档
- **Primary Language**: Rust
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-04-21
- **Last Updated**: 2023-05-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#+AUTHOR: wfj
#+EMAIL: wufangjie1223@126.com
#+OPTIONS: ^:{} \n:t email:t
#+HTML_HEAD_EXTRA: <style type="text/css"> body {padding-left: 26%; background: #e3edcd;} #table-of-contents {position: fixed; width: 25%; height: 100%; top: 0; left: 0; overflow-y: scroll; resize: horizontal;} i {color: #666666;} pre, pre.src:before {color: #ffffff; background: #131926;} </style>
#+HTML_HEAD_EXTRA: <script type="text/javascript"> function adjust_html(){document.getElementsByTagName("body")[0].style.cssText="padding-left: "+(parseInt(document.getElementById("table-of-contents").style.width)+5)+"px; background: #e3edcd;"}; window.onload=function(){document.getElementById("table-of-contents").addEventListener("mouseup",adjust_html,true)}</script>

* 密码学基础
** [定义] 什么是域 F(ield) ?
满足以下八条:
1. 对于加法和乘法运算封闭 (即域内任意两个元素相加或相乘仍在域内)
2. 加法和乘法均满足结合律
3. 加法和乘法均满足交换律
4. 满足分配律
5. 存在零元 0, 使得任意 a + 0 = a
6. 存在幺元 1, 使得任意 a * 1 = a
7. 存在加法逆元 (本文简称负元)
8. 非零元存在乘法逆元 (本文简称逆元)

** [数学描述]
1. \forall a, b \in F, a + b \in F, a * b \in F
2. \forall a, b, c \in F, (a + b) + c = a + (b + c), (a * b) * c = a * (b * c)
3. \forall a, b \in F, a + b = b + a, a * b = b * a
4. \forall a, b, c \in F, a * (b + c) = a * b + a * c
5. \exists 0, s.t. \forall a \in F, a + 0 = a
6. \exists 1 \ne 0, s.t. \forall a \in F, a * 1 = a
7. \forall a, \exists -a \in F, s.t. a + (-a) = 0
8. \forall a \ne 0, \exists a^{-1} \in F, s.t. a * a^{-1} = 1

** [性质]
由以上的定义, 我们可以在域内:
+ 定义减法: 加上一个负元
+ 定义除法: 乘以一个逆元 (要求非零元)
+ 定义数乘: 连续相加
+ 定义乘方: 连续相乘
+ 等式两边同时进行四则运算
+ 定义 0 次幂: 1
+ 定义负整数次幂: 逆元的乘法
+ 消去率

** 阶 (Order)
对于群, 环, 域来说就是其中的元素个数

** 常见的域
根据域的阶, 可分为: 无限域和有限域 (也称为伽罗瓦域, galois)

+ 有理数域
+ 实数域
+ 整数模 p, 记为 F_{p} (若无特殊说明, 本文的 p 均表素数), 是一个有限域
+ 扩展域 GF(p^{m}), 详见后文 (AES 算法会用到 GF(2^{8}))

+ 注1: 整数和多项式都不是域, 因为除法不封闭
+ 注2: F_{p} 是一个伽罗瓦域, 所以通常也记为 GF(p), 其实它就是扩展域的特例 (m = 1)
+ 注3: F_{2} 是最小的域
+ 注4: F_{p} 的阶为 p, GF(p^{m}) 的阶为 p^{m}
+ 注5: 有限域的所有可能的阶就是 p^{m}, TODO: 详见 https://math.stackexchange.com/questions/72856/order-of-finite-fields-is-pn

** 群和环
+ 群 (Group): 集合 + 加法 (只实现了加法的 "域", 称为阿贝尔群, 条件再放宽一点还有其他各种群, 略)
+ 环 (Ring): 集合 + 加法 + 乘法 (这个乘法的要求没域那么高, 比如整数环, 多项式环)

** [证明] 整数模 p 是一个域
+ 定义加法: 普通加法然后模 p
+ 定义乘法: 普通乘法然后模 p

显然满足定义的 1~6 条, 易知第 7 条也满足, 证明第 8 条如下:

对于域内的任意非零元 x, 分别乘以 0 到 p - 1, 然后模 p, 用反证法:

假设域内有两个不同的数 a, b, 使得 x * a \equiv x * b (mod p),

那么就有 x * (a - b) \equiv 0 (mod p),

又因为 p 是素数, 因子只能是 1 和 p, x 在域内不能是 p, a - b 在域内也不能是 p,

矛盾, 所以有这 x * 0~p-1 模 p 的余数各不相同, 所以必存在逆元 x^{-1} 使得余数为 1

例: F_{5}: 1^{-1} = 1, 2^{-1} = 3, 3^{-1} = 2, 4^{-1} = 4

特别地, 根据定义 6, 1 的逆元始终是 1

** 辗转相除法 (求乘法逆元)
求逆元如果每次都需要乘 1~p-1 遍历的话, 那么 p 很大的时候就相当低效了

求两个整数的最大公约数, 通过同余, 可以得到一种快速计算方法: 辗转相除法

非零元 a 和 p 互素, 所以最大公约数为 1, 也就是可以通过辗转相除最终得到 1, 这个 1 就是我们求逆元时想得到的 1,

因此, 我们可以反推辗转相除法的过程, 最终的余数 1 可以用 a 和 p 线性表出, a 前的系数就是我们要找的逆元

+ 注1: 辗转相除法也称为欧几里得算法, 这里用到的是其扩展, 所以称为扩展欧几里得算法
+ 注2: 确切地说, a 的这个系数可以是任意整数 (不一定在 F_{p} 内), 但能通过模 p, 映射到 F_{p} 内, 且不会改变同余关系;
+ 注3: 另一种做法是上述的计算都用 F_{p} 内定义的计算来进行, 由封闭性可得系数也在 F_{p} 内

*** 最大公约数
#+begin_src python
def gcd(a, b): # a >= 0, b >= 0
    def _gcd(a, b):
        return a if b == 0 else _gcd(b, a % b)
    return _gcd(a, b) if a > b else _gcd(b, a)
#+end_src

*** 求逆元
尾递归版本, 注: 本实现返回的数可能不在域内 (负数), 需要再 mod p
#+begin_src python
def inv(a, b): # a >= 0, b >= 0, 且大的那个是素数 p, F_{p}
    def gcd(a, b, k1, k2):
        if b == 1:
            return k2
        k = a // b
        return gcd(b, a - k * b, k2, k1 - k * k2)
    return gcd(a, b, 0, 1) if a > b else gcd(b, a, 0, 1)
#+end_src

*** 实现原理
其实很朴素, 辗转相除有以下等式:
#+begin_src
+ a = k1 * p + p2                  (1)
+ p = k2 * p2 + p3                 (2)
+ ...
+ pn_2 = kn_1 * pn_1 + pn          (n-1)
+ pn_1 = kn * pn + 1               (n)
#+end_src

分析如下:
+ 由式 (1), 我们可以看出: 最终的展开式, 如果有一个 p2 那么就有一个 a, 而有多少个 p 对 a 无影响
+ 现假设有一个函数 f, 能够求出上述的对应关系, 那么我们就有 f(2) = 1, f(1) = 0 (即起始条件)
+ 由式 (n-1), 我们可以得出: f(n) = f(n - 2) - kn_1 * f(n - 1) 的递推关系
+ 由式 (n), 我们可以得出结束条件

NOTE: (其实还有个地方其实还有点绕, 容易忽略) 事实上, 我们是从 p3 开始算的 (也就是 (2) 式), 因为当 a < p 时, 我们有 k1 = 0, p2 = a, 也就是说把 p 和 a 换个顺序就可以了

** 欧拉定理
*** 欧拉函数 \phi(n)
定义: 小于等于 n, 且与 n 互素 (即最大公约数为 1) 的正整数的个数

注: 需要等于的情况, 仅在 n = 1 时, 因为 gcd(n, n) = n

例: \phi(1) = 1, \phi(2) = 1, \phi(3) = 2, \phi(4) = 2, \phi(5) = 4

特别地, n 为素数时, \phi(n) = n - 1, 因为 1~n-1 都与 n 互素

*** 欧拉定理
若正整数 n, a 互素, 即 gcd(n, a) = 1, 则 a^{\phi(n)} \equiv 1 (mod n)

*** 证明
n = 1 时显然成立, 不妨设 n > 1,

记与 n 互素且小于 n 的数为: x_{i}, i = 1..\phi(n),

令 y_{i} = a * x_{i} (mod n), 显然有 y_{i} 与 n 互素,

\forall i \ne j, y_{i} - y_{j} = a * (x_{i} - x_{j}) (mod n) \ne 0

即任意 y_{i} 不同余, 也就是说 y_{i} 是 x_{i} 的一个重排列,

那么, \prod x_{i} \equiv \prod y_{i} \equiv \prod a * x_{i} \equiv a^{\phi(n)} * \prod x_{i} (mod n)

a^{\phi(n)} \equiv 1 (mod n), 证毕

*** 推论: 费马小定理
任意素数 p 和正整数 a, 若 a 不是 p 的倍数, 则 a^{p - 1} \equiv 1 (mod p)

证明: p 为素数, 所以 \phi(p) = p - 1, 又 a 不是 p 的倍数, 所以 a, p 互素, 满足欧拉定理条件, 带入即得 a^{p - 1} \equiv 1 (mod p)

*** 欧拉函数的性质
如果 n 的标准因式分解为 p1^{x1} * ... * pn^{xn}, 那么 \phi(n) = n * (1 - 1/p1) * ... * (1 - 1/pn)

证明: 为了简单起见只给出描述性证明

与 n 互素的情况, 可以用容斥原理表述:
1. 首先假设 n 个元素都互素
2. 然后排除被 pi 整除的情况 (共有 \sum n / pi^{xi} 种)
3. 再加上能被 pi * pj 整除的情况
4. ...

所有这些加起来正好能和 \phi(n) = n * (1 - 1/p1) * ... * (1 - 1/pn) 展开后的每一项匹配 (按分母的次数, 比如第二步对应分母的一次项, 第三步对应分母的二次项)

特别地, n 为素数时, \phi(n) = n - 1; n = p * q 时, \phi(n) = (p - 1) * (q - 1)

** 原根 (primitive roots)
*** 元素的阶 (注意区别于域的阶, 可以理解为由它生成的循环群的阶)
n 为大于 1 的整数, a, n 互素, 使得 a^{x} \equiv 1 (mod n) 成立的最小整数 x 称为 a 模 n 的阶, 符号为 Ord_{n}(a)

存在性: 由欧拉定理, 可知存在 x = \phi(n) \equiv 1 (mod n),

例:
+ Ord_{7}(1) = 1, # 1
+ Ord_{7}(2) = 3, # 2, 4, 1
+ Ord_{7}(3) = 6, # 3, 2, 6, 4, 5, 1
+ Ord_{7}(4) = 3, # 4, 2, 1
+ Ord_{7}(5) = 6, # 5, 4, 6, 2, 3, 1
+ Ord_{7}(6) = 2, # 6, 1

注: 可以看出, 因为有 \phi(n) 保底, 所以 Ord_{n}(x) 都是 \phi(n) 的因子

*** 原根
满足 Ord_{n}(x) = \phi(n) 的 x

+ 注1: 不一定存在, 比如 Ord_{8}, (存在条件: n = 2, 4, p^{k}, 2 * p^{k} (p 为奇素数)), 当然我们最常用的 n 为素数时是存在的 (证明需要同余方程)
+ 注2: 可以存在多个, 比如 Ord_{7} 的 3 和 5
+ 注3: 当 n 为素数时, 原根可以通过自乘 **生成** F_{p} 的所有非零元 (生成元 / 本原元) (generator / primitive element)

** 扩展域 GF(p^{m})
*** 用多项式来表述
a = \sum a_{i} * p^{i}, 其中 a_{i} \in F_{p}, i = 0, 1, ..., m-1

其中每个 a_{i} 都有 p 个取值, 所以总共有 p^{m} 个成员 (阶为 p^{m})

*** 定义加法
多项式加法 (对应项的系数相加) 后求模

注: 显然是满足域对加法的所有要求

*** 定义乘法
多项式乘法 (两两相乘, 同次项相加, 求模)

+ 注1: 这样会导致次数大于 m - 1 (即不在域内), 需要约定不可约多项式求余式 (不能因式分解, 可以认为是广义的素数, prime polynomial)
+ 注2: 特别地, 当 p 等于 2 时, 该域就是有限位数的二进制
+ 注3: 乘法是封闭的, 多项式的除法是会导致余式最高次为 m, 但这里是有限域, 低次项即使不够也能通过求模来补足, 从而消去 m 次项
+ 注4: 显然满足域对乘法的所有要求 (逆元的存在性证明见下一节)

*** 乘法逆元存在性的证明 (模仿 F_{p})
任意确定的 a \in GF(p^{m}), c 是最高次项为 m 的不可约多项式, 那么可以证明: 任意 b_{i} \in GF(p^{m}), a * b_{i} (mod c) 是 b_{i} 的一个重排列

用反证法, 若不是重排列, 则必存在 i, j, 使得 a * (b_{i} - b_{j}) \equiv 0 (mod c), 和 c 的定义矛盾

所以存在 b_{i} 使得 a * b_{i} \equiv 1 (mod c)

注: 不可约多项式可以有多个, 比如对于 GF(2^{8}), 可以是 0b100011011 或 0b100011101, 这些不可约多项式的选择更多是生成元的不同 (详见下一节)

*** 加速
多项式的乘除是比较慢的, 但好在是有限域, 我们可以通过查表来用空间换时间, 那么乘除法各需要 O(N^{2}) 的空间, 有没有可能把空间复杂度降到 O(N)?

假设我们有一个生成元 g, 有限域内的任意非零元 a 都可以用 g^{n} 来表示, 也就是说有 n = log_{g}(a) (不会引起混淆, 所以可以把 log_{g} 简写成 log)

那么我们就可以把复杂的乘除转化成简单的加减法: a * b = g^{log(a)} * g^{log(b)} = g^{log(a) + log(b)}

如果我们对任意元素 (空间复杂度为 N), 都算好了对数和指数表, 那么乘除我们就可以化简为查对数表, 然后加减, 然后查指数表!

GF(2^8) 域, 验证是否为生成元, 建表的代码实现如下:
#+begin_src python
def galois_mul(lhs, rhs, p):
    res = 0
    while lhs != 0:
        if lhs & 1:
            res ^= rhs
        lhs >>= 1
        if rhs & 0x80:
            rhs <<= 1
            rhs ^= p
        else:
            rhs <<= 1
            rhs &= 0xff
    return res


def print_hex_table(table):
    for i in range(16):
        print(" ".join(["{:02x}".format(v)
      		        for v in table[i * 16 : (i + 1) * 16]]))


n = 256
exp_table = [0] * n
log_table = [0] * n
v = 1 # 0 次
for i in range(n):
    exp_table[i] = v
    log_table[v] = i
    v = galois_mul(v, 2, 0b100011101)
    #v = galois_mul(v, 3, 0b100011011)

print(len(set(exp_table)))
print_hex_table(exp_table)
print('-' * 50)
print_hex_table(log_table)
#+end_src

*** 应用
+ AES 列混淆乘法
+ 二维码 EC 冗余

** 三大计算难题 (安全依据)
+ 离散对数难题 (ElGamal, DH)
+ 大整数因式分解难题 (RSA)
+ 椭圆曲线离散对数难题 (其实是数乘的逆运算) (ECC)

** [作用] 为什么是密码学的基础
+ F_{p} 上的四则运算会在密码学频繁用到, 我们知道了 F_{p} 是一个域, 那么我们就可以放心地做各种复杂的运算了
+ 三大计算难题都是建立在 F_{p} 上, (非单调性, 欧拉定理等)

* 基本方法
** ElGamal
1. 生成私钥 x
2. 通过 y \equiv g^{x} (mod p), 生成和计算公钥 (y, g, p)
3. 加密: 发送消息 M 时, 随机生成一个临时私钥 k, 发送 C1 = g^{k} (mod p) 和 C2 = y^{k} * M (mod p)
4. 解密: 那么拥有私钥的一方就可以通过 C2 / (C1^{x}) = y^{k} * M / g^{k*x} = M 来解密

+ 注1: 消息的二进制表示就是那个要来计算的整数 M, 要求 < p
+ 注2: 解密时用的不是实数域的除法, 而是 F_{p} 上的除法, 需要用逆元的定义, 以及交换律和结合律
+ 注3: 安全依据: 离散对数难题 (知道了上述公钥, 不能通过类似求对数的方法快速求出私钥 x)
+ 注4: g 的选择, 根据上一节, 若 g 是本原元, 能最大程度提高安全性
+ 注5: 不在加密的时候用加减法的原因可能是不用引入一种新的计算, 不过这不是 F_{p} 吗, 不理解; 至于不在子群内的其实不是问题, 甚至还能提高安全性
  https://crypto.stackexchange.com/questions/47133/is-it-insecure-using-addition-instead-of-multiplication-in-elgamal-encryption

** DH 算法
+ 约定公共参数: p (大素数, 大于 1024 bits), g (小素数, 2 或 5)
+ 服务器生成随机数 a, 计算得到 Ys = g^{a} (mod p), 发送 Ys 给客户端
+ 客户端生成随机数 b, 计算得到 Yc = g^{b} (mod p), 发送 Yc 给服务器
+ 发送完毕后, 双方可以不用泄露 a, b, 各自计算出商定好的密钥 Z:
  + 服务器: Z = Yc^{a} (mod p)
  + 客户端: Z = Ys^{b} (mod p)

+ 注1: 这个服务器可以是另一个客户端
+ 注2: 商定完密码后, 就可以通过该密码进行对称加密解密了
+ 注3: 一般需要 g 是原根, 以降低被破解的难度
+ 注4: telegram 对 p 还有额外要求, g 可以是 2, 3, 4, 5, 6, 7, 详见 https://core.telegram.org/api/end-to-end#sending-a-request

** 数字签名
+ 签名: signature(hash(M), private_key) -> sig
+ 验证: validate(hash(M), public_key, sig) -> bool

TODO: 为什么不直接用 M, 而是需要 hash(M), 效率? 安全?

+ 注1: 保证在验证时公钥是不可以被篡改, 或者说有能力鉴别公钥的真伪, 这时就需要 CA 和数字证书了
+ 注2: 防止重放攻击 (比如多次付款), 这时就需要在消息内写上消息编号之类的数据

* ECC (椭圆曲线密码学)
** 参考资料
https://zhuanlan.zhihu.com/p/42629724

这篇文章, 背景介绍可以看看, 举的几个例子用来入门很不错

** 椭圆曲线的一般形式
椭圆曲线方程: y^{2} = x^{3} + a * x + b, 其中 a, b 为指定常数 (貌似还有一些特殊限制, 我的知识储备不足以了解这些细节, 不过现在也用不上)

+ 注1: 这个是定义在实数域上的, 一定要注意与下面要讲的密码学中定义在有限域上的椭圆曲线的区别
+ 注2: 这个一般形式, 我们只会在后面证明加法的封闭性的时候用到
+ 注3: 更一般的椭圆还有 x 的二次项, 比如著名的 25519: y^{2} = x^{3} + 486662 * x^{2} + x

** 密码学中的椭圆曲线
椭圆曲线是连续的, 不好用于加密解密, 考虑把椭圆曲线定义到有限域 F_{p} 上 (专业术语叫仿射变换):

y^{2} \equiv x^{3} + a * x + b (mod p), 其中 p 为素数, a, b 为非负整数 (TODO: 待考证), x \in F_{p}, y \in F_{p}

注: ECC 上的点, 我们只实现了加法, 只是一个群 (阿贝尔群); 但是它又分为 x 和 y 坐标, 均为 F_{p} 域内的数, 所以人们通常也会称为有限域内的点

** 常用 ECC
+ (比特币) p = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1, a = 0, b = 7
+ p = 23, a = 1, b = 1
+ p = 11, a = 1, b = 6
+ (ec25519) p = 2^{256} - 19, (这个有二次项 486662, a = 1, b = 0)

注: 一种简单的构造方法, 可以先确定 a 和 一个点 P(x, y), 通过方程求出 b, p 的话可以任意选择 (但不应过小, 域太小没实际意义)

** 为什么 ECC 的零元是无穷远点
通常 ECC 的 b 的取值不为零, 所以代码实现时, 可以用 P(0, 0) 来代替无穷远点

因为 b \ne 0, 所以 P(0, 0) 不在椭圆曲线上, 可以借来使用

猜测: 可能是满足条件的零元不存在, 所以就造了一个出来, 赋予它特殊的计算规则, 反正它不在有限域上, 那就说它在无穷远点吧?

** ECC 的负元
观察椭圆曲线等式, 易知若 P(x, y) 是有限域上满足等式的点, 那么 P(x, -y) 也满足等式, 可以作为负元 (但需要一些调整)

因为 P(x, -y) 不在有限域上, 就像在 F_{5} 域内我们不能说 3 的负元是 -3, 而应该是 5 + (-3) = 2

同理, 根据二项式展开的性质, 知 P(x, p - y) 也满足等式, 且在有限域内, 作为负元再合适不过

*** 注1: 根据负元的定义 P(x, y) + P(x, p - y) = 0 (零元, 即无穷远点) 这一点在定义加法的时候要特别注意

*** 注2: 对于同一个 x = x1, 有限域内最多有两个点, y 坐标通常为一奇一偶 (p 为大素数)
若对于 x = x1 有以下等式成立:
#+begin_src
+ y1^{2} \equiv x1^{3} + a * x1 + b (mod p)
+ y2^{2} \equiv x1^{3} + a * x1 + b (mod p)
#+end_src
由 mod p 的性质知: (y1 - y2) * (y1 + y2) \equiv 0 (mod p), 这里的加减法是域内的加减法, 且 p 为素数, 所以最多有两个点 P(x1, y1), P(x1, p - y1)

其中单个点的情况是 y1 = 0, 这时它的负元就是它自己, x 满足 x^{3} + a * x + b \equiv 0 (mod p)

和为 p, 是奇数, 所以两者必为一奇一偶

*** 注3: 有限域内的点 (除了 y = 0 的点) 关于 y = p / 2 对称
y 和 p - y 关于 y = p / 2 对称

** ECC 的加法
1. 规则一: 若 P2 为 P1 的负元, 规定 P1 + P2 = 0
2. 规则二: 见下面的公式 (为什么这样定义, 详见下一节的封闭性证明)
#+begin_src python
if (x1, y1) != (x1, y2):
    k = (y2 - y1) / (x2 - x1)
else:
    k = (3 * x1 ** 2 + a) / (2 * y1)
x3 = k ** 2 - x1 - x2
y3 = k * (x1 - x3) - y1
#+end_src

+ 注1: 很多资料都是把 k 写成 \lambda 的, 其实就是计算斜率
+ 注2: P1 != P2 时, 还是有可能 x2 = x1 的, 根据上一节的注2, 这时应用规则一
+ 注3: P1 = P2 时, 如果有 y1 = 0, 那么计算 k 时分母为零, 但这是不可能的, y1 = 0, 根据上一节的注2, 此时 P1 的负元就是它自己, 这时应用规则一
+ 注4: 上述规则二, 是为了同时能表示实数域上和有限域上才写成那样的; 实际在有限域上的除法就是用的 F_{p} 的除法, 最后也需要模 p (至于为什么可以这么做, 可能是仿射变换的性质吧)

** 加法的封闭性证明
很多资料多会讲, 椭圆曲线加法, 就是椭圆曲线上两点 (可相同) 确定的直线 (相同点时为切线) 与椭圆曲线的交点, 然后关于 x 轴翻转, 但没给出更进一步的解释

以下采用启发式证明的方式, 也就是我一步步发现的过程
*** 计算 y 坐标
我最先发现的是: y3 的计算可以看成 -(k * (x3 - x1) + y1), 这放在实数域上, 这就是根据斜率求 y 坐标, 然后再关于 x 轴翻转

*** 再看 k 的定义
+ P1 != P2 时就是斜率的计算公式
+ P1 = P2 时, 椭圆曲线一般形式两边对 x 求导得 2 * y * f'(x) = 3 * x^{2} + a, 即 k = f'(x) = (3 * x^{2} + a) / (2 * y)

*** 再来计算 x 坐标
不妨令 z = y^{2},

那么椭圆曲线其实就是 xoz 坐标系上的三次曲线: z = x^{3} + a * x + b,

同样地, 那条直线在 xoz 坐标系上的方程是 z = (k * (x - x1) + x1)^{2},

两者相交就是 (k * (x - x1) + x1)^{2} = x^{3} + a * x + b, (式1)

是关于 x 的三次方程, 最多有三个解, 正好是我们知道的 x1, x2, x3, 可表示成 (x - x1) * (x - x2) * (x - x3) = 0 (式2)

然后比较两者关于 x 的二次项系数, 得出 -(x1 + x2 + x3) = -k^{2}

至此, 我们得到了之前的计算公式 x3 = k^{2} - x1 - x2,

就是说之前定义的加法其实就是求两点确定的直线与椭圆曲线的交点, 然后关于 x 轴翻转

对于任意两点, 相加有以下三种情况:
1. P1 = -P2, 结果是 0, 封闭
2. P1, P2 有一个为零元时, 根据零元的定义, 封闭
3. 其他情况, k 的计算都是有意义的 (除数不为 0), 结果存在并在椭圆曲线上, 封闭
综上所述, 我们证明了加法的封闭性

** 加法的交换律, 结合律
对于负元, 零元的情况, 显然满足交换律和结合律

一般情况, 交换律可根据定义直接得出

结合律看似容易, 其实需要非常复杂的计算 (带入之前的公式, 我是算不过来) 或者一些几何学的知识, 有兴趣可以研究研究: https://www.zhihu.com/question/296821640

** ECC 的阶 (n) 和生成元 (G)
*** 阶
定义: 椭圆曲线上点的个数

性质: 设 ECC 的阶为 n, 那么对于任一 ECC 内的元素 a, 有 n * a = 0 (零元)

推论: 椭圆曲线上所有点的数乘构成循环群 ((n + 1) * a = a)

证明: 对于所有 ECC 内所有的点 a_{i}, 令 b_{i} = a + a_{i},

由消去率知, b_{i} 的任意元素两两不等, 也就是说 b_{i} 是 a_{i} 的一个重排列,

有 \sum a_{i} = \sum b_{i} = n * a + \sum a_{i}, 得 n * a = 0, 证毕

*** 生成元
定义: G 是一个生成元，当且仅当阶 n 是最小的满足 n * G = 0 (零元) 的正整数

例: E_{23}(1, 1) 阶为 28, 有十二个生成元, 如: (3, 10), (0, 1), (19, 5)

性质: 同一个 x 对应的两个元素, 要么都是生成元, 要么都不是 (a + b = 0 推出 k * a + k * b = 0, 即 k 使得 k * a 为零元时, k * b 也为零元)

** 椭圆曲线加密 (EC ElGamal)
1. 生成私钥 k
2. 根据 G = (xg, yg), (椭圆曲线上的约定点), 计算公钥 P = k * G = (xp, yp)
3. 加密: 发送消息 M 时, 随机临时私钥 r, 发送 C1 = r * G, C2 = r * P + M
4. 解密: k * C1 - C2 = k * r * G - r * k * G + M = M

+ 注1: 这个 M 需要在椭圆曲线上, 所以还是有点难用 (需要嵌入什么的)
+ 注2: 另一种加密方法是 ECIES, 据说没有被 NIST 认可

** ECDH (类比之前的 DH)
1. 约定公共参数 p, G
2. 服务器生成私钥 a, 计算得到 Ys = a * G (mod p), 发送给客户端
3. 客户端生成私钥 b, 计算得到 Yc = b * G (mod p), 发送给服务器
4. 发送完毕后, 双方可以不用泄露 a, b, 各自计算出商定好的密钥 Z:
  + 服务器: Z = a * Yc (mod p)
  + 客户端: Z = b * Ys (mod p)

** ECDSA (椭圆曲线数字签名算法)
*** 方法一 (wiki)
设原私钥 k, 原公钥 P(xp, yp) = k * G, 阶为 n

加密:
1. 随机生成新私钥 r, 生成新公钥 R(xr, yr) = r * G 且满足 xr != 0 (mod n)
2. s = r^{-1} * (hash(m) + xr * k) (mod n), 满足 s != 0 (mod n), 否则跳回步骤1

验证: hash(m) * s^{-1} * G + xr * s^{-1} * P 就是 R(xr, yr)

证明: 由交换律结合律得, 原式 = s^{-1} * (hash(m) + xr * k) * G, 由加密步骤2 知, s^{-1} * (hash(m) + xr * k) \equiv r (mod n), 再由阶的性质得, 原式 = R(xr, yr)

+ 注1: 若 xr \equiv 0 (mod n), 则步骤2 的私钥不起作用
+ 注2: s != 0 (mod n) 是为了逆元存在, r 也要有逆元, 最简单的就是 n 为素数 (secp256k1 就是这种情况)
+ 注3: 对 n 求模是由于椭圆曲线的阶的性质
+ 注4: 实际情况只需要验证 xr 相等

随机: 使用相同的 r 是不安全的, s - s' \equiv r^{-1} * (hash(m) - hash(m')) (mod n), 可以求出 r, 从而求出 xr 和 k (私钥), 详见:
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

*** 错误的方法二
加密:
1. 同上
2. s = r - hash(m) * k (mod n)

验证: s * G + hash(m) * P 就是 R(xr, yr)

证明: 原式 = r * G - hash(m) * k * G + hash(m) * P = R(xr, yr)

随机: 使用相同的 r 也是不安全的, s - s' \equiv (hash(m) - hash(m')) * k (mod n), 可以求出 k

证伪: 验证公式和 xr 无关, 很容易伪造, 假设我们要发送假消息 m, hash(m) * P 可以求出, 我们只要随意选 s, 再计算出 R(xr, yr) = s * G + hash(m) * P, 这样根本就不需要密钥就能签名

* RSA
** 加密
+ 任取两个大素数 p, q
+ 计算 n = p * q (公钥1),
+ 计算欧拉函数 \phi(n) = (p - 1) * (q - 1)
+ 任选大整数 e (公钥2), 满足 gcd(e, \phi(n)) = 1,
+ 确定密钥 d: 满足 d * e \equiv 1 (mod \phi(n))
+ 加密: 消息 M, 发送 C = M^{e} (mod n)
+ 解密: M = C^{d} (mod n) (证明略)

证明: M^{e * d} = M^{k * \phi(n) + 1}, 若 M 与 n 互素, 由欧拉定理即可得结论, 不互素情况详见: https://zhuanlan.zhihu.com/p/48994878

+ 注1: 确定密钥过程, 类似求逆元, 但因为 \phi(n) 不是素数, 所以可能不存在, 可以用扩展欧几里得算法求解
+ 注2: 安全依据: 大整数因式分解难题, (其实也有离散对数的, C 和 e 是公开的, 如果没有这个难题, 可以直接求出 M)

** TODO 签名

* TODO AES
详见代码

** 改进混淆矩阵
前面在 GF(2^8) 里讲了用 log 和 exp 来加速的技巧, 在 aes 里可以更进一步, 把混淆矩阵提前求好 log, 然后用同一列 x 求四次 log, 求和, 求 exp, 再异或

** 空间换时间
+ exp 索引, 都是两个数相加之后求, 把长度加长到 512, 就可以避免求模
+ 改变 log_table 的类型为 usize, 可以在索引时避免类型转换
+ #[inline(always)] encode_block 和 decode_block 能省时 1/3, (不用always, 函数多的时候 rust 会选择不优化)

** iv (init vector) 的巧用
对 iv 进行变换而不是 msg_block, 可以减少不必要的 clone

* TODO 25519
** (加密) curve25519
** (交换) x25519
** (签名) ed25519