本文涉及：非对称密码、抽象代数、数论

第一次更新：2021.09.26

第二次更新：2021.10.26

第三次更新：2022.02.26

0.前置知识

0.1.代数结构、模运算、群

大家都知道C语言中的bool值，异或，以及模运算：

0,1 (false,true)

^ (xor)

% (mod)

把异或运算作用在{0,1}上，很明显

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

其实，这是一种模2加法运算

(0 + 0) mod 2 = 0

(0 + 1) mod 2 = 1

(1 + 0) mod 2 = 1

(1 + 1) mod 2 = 0

不难发现，在{0,1}上的异或运算是唯一且封闭的。

像这样，有一个非空集合S = {0,1}以及作用在集合元素上的运算符（异或/模2加），称作一个代数系统（简称代数）

设 G = <S,+>是代数系统 （满足封闭性）

(1)如果+是可结合的，则称V为半群

(2)如果存在e ∈ S ，对于 $\forall a ∈ S$ ，有 ea = ae = a ，则称e是S上的单位元

(3)如果G是半群且拥有单位元，即G = <S,+,e>，若$\forall a \in S$ , 有 $a^{-1} \in S$ ,则称G是群

总结一下，群的性质其实很简单：

一个集合，附带一个运算符

然后拥有封闭性，结合律，单位元，逆元

**P.S.**交换律不是构成一个群的必要条件，满足交换律的群称作交换群/阿贝尔群

0.2.加密与解密

加密就是让明文变成密文，

加密通常需要密码算法和密钥

密码算法就是一系列把明文变成密文的（复杂）步骤（或者说方法/函数）

密钥通常是（伪）随机数

明文和密钥是输入

将其投入到密码算法中

得到输出：密文

解密就是反过来

一些术语：

M: 明文

KeyGen：KeyGenerate，密钥生成，字面意思不解释了

Enc：Encrypt，加密

Dec：Decrypt，解密

pk：public key，非对称密码中的公钥，用来加密

sk：secret key，非对称密码中的私钥，用来解密

$\phi$：欧拉函数，习惯上也使用$\phi(N)$或$phi$表示

P.S. 对欧拉函数不是很了解的可以阅读：欧拉函数一个小的证明 | luo’s Blog

欧拉定理：

设 n 和 a 为正整数，且gcd(a,n) = 1,则：

$a^{\phi(n)} \equiv 1\ (mod\ n)$

其中gcd(a,n) 输出a与n的最大公因子，等于1时a与n互素

0.3.密码学中的一些“反常识”

to be continue

1.RSA

1.1.RSA构造公钥和私钥

KeyGen：

两个大素数p≠q，N = p*q ，$\phi = (p-1)(q-1)$，找到一个与$\phi$互素的元素$e$计算出$d$

使得$d*e \equiv 1\ (mod\ \phi)$

有

pk = (N,e)

sk = d

对于$d*e \equiv 1\ (mod\ \phi)$

我们很容易能想到，e是d关于$Z_\phi^*$的乘法逆元

关于乘法逆元的具体求法，请看luo41:乘法逆元求法总结

至于为什么要构造逆元，在下面的证明中会看到。

$Enc(pk,M) :C \equiv M^e ( mod N )$

输出$C$

$Dec(sk,M) :M' \equiv C^d\ (mod\ N)$

输出$M'$

下面证明$M' \equiv M\ (mod\ N)$

$∵ d*e \equiv 1\ (mod\ \phi)$

$∴ d*e = k\phi + 1$

由欧拉定理得：

$M^\phi \equiv 1\ (mod\ N)$

$∴M' \equiv C^d \equiv M^{ed} \equiv M^{k\phi + 1} \equiv M^{k\phi}*M \equiv M\ (mod\ N)$

当N>M时，M’ = M (这就是要求p和q是两个大素数的原因)

1.2. r-prime RSA

RSA的推广：其中 $r∈Z$且$r≥1$

KeyGen：

r个不等的大素数，$N = r_1*r_2*…*r_n$，$\phi = (r_1-1)*(r_2-1)*…*(r_n-1)$

其余步骤一致

2.ELGamal

2.1.通过Diffie-Hellman密钥交换实现密钥配送问题

Alice和Bob是通信的双方

为了使加解密过程顺利且正确，所以无论用什么密码算法，Alice和Bob总是（至少）要交换密钥K

而在信道中交换K，不免得要考虑窃听的问题

P.S. 虽然这种方法的名字叫“密钥交换”，但实际上双方并没有真正交换密钥，而是通过计算生成出了一个相同的共享密钥。因此，这种方法也成为Diffie-Hellman密钥协商

运用以下方法使得K的交换顺利且窃听者无所获：

Alice或Bob任意一方生成大素数p和生成元g并告诉对方（不需要保密）

Alice拥有自己的随机数a，Bob拥有自己的随机数b (保密)

$a,b ∈ [1,p-2]$

分别计算

$A = g^a\ mod\ p$

$B = g^b\ mod\ p$

Alice和Bob交换A和B

Alice计算 $K \equiv B^a \equiv g^{ba}\ mod\ p$

Bob计算 $K \equiv A^b \equiv g^{ab}\ mod\ p$

显然相等

简单的计算实现了K的交换，而此时窃听者（有可能）得到了什么？

A、B和p、g

知道A和B不能求K，这是CDH（计算性Diffie-Hellman）问题。

知道$g^x\ mod\ p$不能求$x$，这是DLP（离散对数）问题。

P.S. 还有个决策性Diffie-Hellman问题（DDH），Tover说他读研再看，反正我不会

总而言之，窃听者想破解密码是困难的。

2.2. 基于Diffie-Hellman的ELGamal加密

KeyGen :

该步骤由Ailce完成

$1 \leq a \leq p-1$ ; $A \equiv g^a (mod\ p)$

pk = A ; sk = a

$Enc(pk,M):$

该步骤由Bob完成

随机数r;

$C_1 \equiv g^r\ (mod\ p)$

$C_2 \equiv M*A^r\ (mod\ p)$

输出：$C = (C_1,C_2)$

$Dec(sk,C):$

该步骤由Alice完成

$M' \equiv (C_1^a)^{-1} * C_2 (mod\ p)$，其中$C_1^a \equiv A^r \equiv K\ (mod\ p)$

输出：$M'$

下面证明$M' \equiv M\ (mod\ p)$

$M' \equiv (C_1^a)^{-1} * C_2 \equiv (g^{ra})^{-1}*M*A^r \equiv (A^r)^{-1}*M*A^r \equiv M\ (mod\ p)$

当p>M时，M’ = M

2.3. Hash ELGamal

KeyGen:

$1 \leq a \leq p-1$; $A \equiv g^a\ (mod\ p)$

pk = A ; sk = a

$Enc(pk,M):$

随机数r ; $C_1 \equiv g^r\ (mod\ p)$ ; $C_2 \equiv M \oplus H(A^r)(mod\ p)$

输出：$C = (C_1,C_2)$

$Dec(sk,C):$

$M' \equiv H(C_1^a) \oplus C_2\ (mod\ p)$;

输出: $M'$

3.椭圆曲线

3.0.about EC

沿用一下CINTA的定义

椭圆曲线：

设 $\mathbb{F}$ 为域，$a, b ∈ \mathbb{F}$ 为常数，它们使得 $\Delta = 4a^3 + 27b^2 \neq 0$。非奇异椭圆曲线 $E(\mathbb{F})$ 是满足方程 $y^2 = x^3 + ax + b$ 上的解集合 ${(x, y) ∈ \mathbb{F} × \mathbb{F}}$ 加上一个称为无穷远点 (Point at infinity) 的特殊点 O ，并且 $E$ 在加法上形成一个有限交换群。

简单而言，所谓椭圆曲线（EC）就是满足以下方程的解，即序对 (x, y) 形成的集合：

$y^2 = x^3 + ax + b$

其中，要求 $\Delta = 4a^3 + 27b^2 \neq 0$

单位元：无穷远处的点O

逆元：当$Q = P^{-1}$时，P与Q关于x轴对称且PQ连线相交于无穷远处（P + Q = O）

群加法：$R = P + Q$

$P = (x_p,y_p),Q = (x_q,y_q) \in E$ 表示椭圆曲线E上两点

所谓的加法就是作P和Q的连线，该直线与E相交于某个点，把这个点沿X轴翻转就得到了点R

P=Q时，P和Q的连线即为椭圆曲线的切线

P.S. 椭圆曲线不一定是“曲线”，详情请看CINTA

3.1 ECC

ECC: 椭圆曲线加密

KeyGen：

$G \leftarrow E(\mathbb{F_p})$;

选择一个整数n和群G内元素$P(x_p,y_p)$使得Q = n*P

pk = (Q,P)；sk = n

$Enc(pk,M):$

生成随机数r；

$C_1 = r*P$;

$C_2 = M + r * Q$

输出：C = (C_1,C_2)

$Dec(sk,C):$

$M' = C_2 - n*C_1$

输出：M’

显然 M’ = M

3.2 SM2

SM2、SM9是我国颁布的商用密码标准算法中的公钥密码算法，下面介绍SM2

Alice与Bob事先协商好相同的公开参数，包括p,n,E and G

其中p是大素数，E是定义在GF§上的椭圆曲线群，G是E的生成元

3.2.1 SM2数字签名算法

①密钥生成

a) 随机数 $d \in [1,n-2]$

b) 计算 $P = dG$，并将 P 作为公钥公开，d 作为私钥保存

②签名

a) Alice 选取随机数 $k \in [1,n-1]$，计算 $kG = (x_1,y_1)$

b) 计算 $r = (H(M)+x_1)\ mod\ n$，其中 $M = Z_A || m$ ，Z_A 是关于用户的可辨别标识、部分椭圆曲线系统参数和用户的公钥hash值，m是待签名信息，H为国家密码管理局核准的杂凑函数，如SM3；若 $r = 0\ mod\ n$ 或 $r + k = 0\ mod\ n$，则重新选取随机数 $k$

c) 计算 $s = (1+d)^{-1}(k-rd)\ mod\ n$ ; 若 $s \equiv 0$，则重新选取随机数 $k$ ，否则，将 $(r,s)$ 作为签名结果

③验签

a) Bob 收到 $M$ 和 $(r,s)$ 后，先检查 $r,s \in [1,n-1]$ 且 $r + s \neq 0\ mod\ n$ ；然后计算 $(x_1’,y_1’) = sG + (r+s)P$

b) 计算 $r' = (H(M)+x_1')\ mod\ n$ ；判断 r’ 与 r 是否相等，若相等则签名验证通过。

3.2.2 SM2密钥交换协议

	Alice	Bob
pk	$P_A$	$P_B$
sk	$d_A$	$d_B$
唯一标识	$Z_A$	$Z_B$

Alice:

1)选取随机数 $r_A \in [1,n-1]$，计算$R_A = r_AG = (x_2,y_2)$ 并发送给Bob

Bob：

1)选取随机数 $r_B \in [1,n-1]$ ，计算 $R_B = r_BG = (x_3,y_3)$ 并发送给Alice

2)计算 $x_B = 2^w + (x_3 \land (2^w-1))$ 和 $t_B = (d_B + x_Br_B)\ mod\ n$

3)验证接收到的 $R_A$ 是椭圆曲线 $E$ 上的点，验证通过后计算 $x_A = 2^w + (x_2 \land (2^w-1))$

4)计算 $V = t_B(P_A + x_AR_A) = (x_V,y_V)$；若 V 是椭圆曲线 E 上的无穷远点，则重新选取 $r_B$

5)计算 $K_B = KDF(x_V||y_V||Z_A||Z_B,klen)$

Alice:

2)计算 $x_A = 2^w + (x_2 \land (2^w-1))$ 和 $t_A = (d_A+x_Ar_A)\ mod\ n$

3)验证接收到的 $R_B$ 是椭圆曲线上的点，验证通过后计算 $x_B = 2^w + (x_3 \land (2^w-1))$

4)计算 $U = t_A(P_B+x_BR_B) = (x_U,y_U)$ ; 若 U 是椭圆曲线 E 上的无穷远点，则重新选取 $r_A$,重新协商。

5)计算 $K_A = KDF(x_U||y_U||Z_A||Z_B,klen)$

经过以上协商，Alice与Bob共享密钥 $K_A = K_B$

3.2.3 SM2公钥加密算法

M：比特长度为mlen的明文

$Enc$

1）选取随机数 $l \in [1,n-1]$ , 分别计算 $C_1 = lG = (x_4,y_4)\ and\ lP = (x_5,y_5)$

2）计算 $e = KDF(x_5||y_5,mlen)$

3）计算 $C_2 = M \oplus e$ 和 $C_3 = H(x_5||M||y_5)$

4）输出密文 $C = C_1||C_3||C_2$

$Dec$

1）验证 $C_1$ 是否在椭圆曲线上，计算 $d*C_1 = (x_5,y_5)$

2）计算 $e = KDF(x_5||y_5,mlen)$

3）计算 $M = C_2 \oplus e$

4）计算 $C_3' = H(x_5||M||y_5)$ ，并验证 $C_3' = C_3$ 是否成立

输出明文 M

3.-1. 圆锥曲线公钥加密算法

圆锥曲线不是椭圆曲线！详情自行百度。

那为什么这篇blog我要把它归在ec名下呢？

——故意让读者混淆的:)

4.Lattices

4.0 格是什么

一种代数结构。

P.S. 离散数学领域中格的概念不止一种，请注意此格非彼格。

4.1 同余公钥加密系统（NTRU简化版）

KeyGen:

很大的数字q，

数字 f,g 使得 $f < \sqrt{q/2}$ , $\sqrt{q/4} < g < \sqrt{q/2}$ , $gcd(f,q*g) = 1$

$∵gcd(f,q*g) = 1$

$∴gcd(f,g) = 1 = gcd(f,q)$

$∴$在$mod\ g$ 和$mod\ q$ 下 $f$ 都有乘法逆元

令 $h \equiv f^{-1}g\ (mod\ q) , 0 < h < q$

pk = (q,h)

sk = (f,g)

$Enc(pk,M)$

$0 < M < \sqrt{q/4}$

生成随机数$r$ , $ 0 < r < \sqrt{q/2}$

$e \equiv r*h+m\ (mod\ q)$ , $ 0 < e < q$

输出：e

$Dec(sk,e)$

$a \equiv f*e\ (mod\ q)$ , $ 0 < a < q$

$b \equiv f^{-1}*a\ (mod\ g)$ , $ 0 < b < g$

输出：b

下面证明 b = M

$a \equiv f*e \equiv f*(r*h+m) \equiv frf^{-1}g+fm \equiv rg+fm\ (mod\ q)$

$∵ rg + fm < \sqrt{q/2}+\sqrt{q/2} < q$

$∴a = rg+fm$

$∴ b \equiv f^{-1}a \equiv f^{-1}(rg+fm) \equiv f^{-1}fm \equiv m\ (mod\ g)$

$∵ m < \sqrt{q/4} < g$

$∴ b = m$

4.2 背包加密

超递增序列：

$r = \{r_1,r_2,...,r_n\}$ , 使得 $r_{i+1} ≥ 2r_i$

$\therefore r_k > r_{k-1}+...+r_2+r_1$

KeyGen:

大数 A,B , gcd(A,B) = 1 , B > 2r_n

构造新数列M使得：M_i \equiv Ar_i (mod B)

pk = M , sk = r,A

明文：x

$Enc(pk,x)$

$S = X*M = \sum_{i=1}^nx_iM_i$

输出：S

$Dec(sk,S)$

$S' \equiv A^{-1}S \equiv A^{-1} \sum_{i=1}^n x_iM_i \equiv A^{-1} \sum_{i=1}^nx_iAr_i \equiv \sum_{i=1}^nx_ir_i\ (mod\ B)$

$∵ B > 2r_n$

$∴ \sum_{i=1}^nx_ir_i ≤ \sum_{i=1}^nr_i < 2r_n < B$

$∴ S' = \sum{}x_ir_i$

利用下述伪代码

Loop i from n down to 1:

​	If S' ≥ r_i:

​		x_i = 1

​		S' = S' - r_i 

​	Else x_i = 0	

End Loop

从而求出$X = (x_1,x_2,...,x_n)$

4.3 GGH

公共参数生成：

选择一个好基 $V = \{v_1,...,v_n\}$

一个整数矩阵 U 满足 $det(U) = \pm 1$

计算 W = UV , 得到坏基 $W = \{w_1,...w_n\}$ (W的行向量)

加密:

公钥： W

私钥： (U,V)

选择小的明文向量 m

小的随机向量 r

计算 $e = x_1*w_1 + ... + x_n*w_n + r$

发送密文 e

解密：

Babai’s Algorithm 计算 CVP：

与 e 最近的向量 $v \in L$

计算 $vw^{-1}$ 还原 m

4.4. NTRU

公共参数生成：

$(N,p,q,d)$

其中N和p是素数，$q>(6d+1)p\ ,\ gcd(p,q) = gcd(N,p) = 1$

密钥生成：

$\times$ ：模$(x^N - 1)$乘

$f \in T(d+1,d)$ , 且 $f$ 在 $R_p$ 和 $R_q$ 均可逆

$g \in T(d,d)$

$F_q * f \equiv 1\ mod\ R_q$

$F_p * f \equiv 1\ mod\ R_p$

公钥 $h \equiv F_q \times g\ mod\ q$

私钥 $(f,g)$

加密：

明文 $m \in R_p$

随机数 $r \in T(d,d)$

$e \equiv pr \times h + m\ mod\ q$

解密:

$f \times e \equiv pg \times r + f \times m\ mod\ q$

center-lift:

$a = pg \times r + f \times m$

$m \equiv F_q \times a\ mod\ p$

5.Goldwasser-Micali probabilistic public key cryptosystem

怎么对一个比特进行加密？

明文空间太小怎么办？

to be continue……

参考

An Introduction to Mathematical Cryptography

【Crypto培训】公钥密码算法 - 入门to弃坑——Tover