前言

去年就想学密码学，但是被大佬博客上的密密麻麻的数学公式给吓到了，就没搞，转头去学pwn了。现在一年了，去年学的pwn也忘完了，但是对pwn也有了基本概念

在传统ctf中似乎就剩Crypto对于我来说还是一团迷雾，最终还是在好奇心的驱使下开始了这篇文章的编写。当然主要原因还是因为这个月相比前几个月闲了一点

学习目标：比较出名的密码算法的实现原理和对应的密码算法安全性问题

python脚本编写

数学运算脚本的编写总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
print(pow(a, b, n))  # x是a的b次方对n取模的结果

import gmpy2

print(gmpy2.powmod(a, b, n)) # x是a的b次方对n取模的结果
print(gmpy2.invert(a, m))# x是a在模m下的逆元
print(gmpy2.is_prime(n))# x是n是否为素数的判断结果
print(gmpy2.next_prime(n)) # x是大于n的最小素数
print(gmpy2.gcd(a, b)) # x是a和b的最大公约数
print(gmpy2.lcm(a, b)) # x是a和b的最小公倍数
print(gmpy2.fac(n)) # x是n的阶乘


from Crypto.Util.number import *
n = 123456789
print(long_to_bytes(n)) # n转hex后再ascill编码
m = bytes_to_long(b"hello")
print(m) # x是b"hello"的长整数表示
print(inverse(a, m)) # x是a在模m下的逆元
print(isPrime(n)) # x是n是否为素数的判断结果

数学基础

概念名称定义

线性代数

只记录了一些基础的概念，详细的还是要跟着下面这个链接学一下
https://www.bilibili.com/video/BV1ys411472E/?spm_id_from=333.999.0.0&vd_source=ac773e0ddc718f4d685a18d69845e9cd

向量

向量可以看作坐标系中一个从原点出发的箭头，也可以看作一个有序的数列表
如：二维向量 $[2,1]$ 表示 $x$ 轴方向为 2，$y$ 轴方向为 1

线性代数围绕两种基本运算展开
向量加法：两个向量的对应项相加，几何上就是把两个箭头首尾相接
LWjZqSe7BxOwmGF
向量数乘：用一个数（称为标量）缩放整个向量，标量为负时还会反向
LWjZqSe7BxOwmGF1

若 $k_1\alpha_1 + k_2\alpha_2 + \cdots + k_n\alpha_n = 0$ 只在 $k_1 = k_2 = \cdots = k_n = 0$ 时成立，则称 $\alpha_1,\alpha_2,\dots,\alpha_n$ 线性无关，否则称它们线性相关

基和基向量：若向量空间 $V$ 中的一组向量 $\alpha_1,\alpha_2,\dots,\alpha_r$ 线性无关，且 $V$ 中任一向量都能由它们线性表示，则称这组向量为 $V$ 的一个基，其中的向量就叫基向量

若干个数乘向量之后再相加，就叫这些向量的线性组合
如：$\hat i,\hat j$ 就是二维平面的一个基，则$[3,-2] = 3\hat i + (-2)\hat j$
UfVy6N8iATvXuQl

矩阵与线性变换

线性变换：变换可以看成一种函数（输入一个向量，输出一个向量）

线性变换可以用矩阵表示，矩阵与向量相乘，就是对这个向量施加一次线性变换

描述线性变换只要记录基向量变换后的位置：把变换后的 $\hat i,\hat j$ 的坐标按列排成的矩阵，就是这个线性变换的矩阵，它的每一列都是对应基向量变换后的坐标
如：变换后 $\hat i$ 落在 $[1,2]$、$\hat j$ 落在 $[3,1]$，对应的矩阵就是

$$A = \begin{pmatrix} 1 & 3 \cr 2 & 1 \end{pmatrix}$$

lin-transform

矩阵乘法可以看成对向量进行多次线性变化后用一个复合矩阵来描述，因为矩阵乘法就是线性变换的复合，变换的先后顺序会影响结果，所以矩阵乘法满足结合律，但是不满足交换律

7wNHCZEztv1LxGm

矩阵乘法要求左矩阵的列数等于右矩阵的行数，计算规则是「左矩阵第 $i$ 行 与 右矩阵第 $j$ 列 对应相乘再相加」，得到结果中第 $i$ 行第 $j$ 列的元素

$$\begin{pmatrix} a & b \cr c & d \end{pmatrix}\begin{pmatrix} e & f \cr g & h \end{pmatrix} = \begin{pmatrix} ae+bg & af+bh \cr ce+dg & cf+dh \end{pmatrix}$$

如：$[-1,2]$在上述线性变换$A$后就变成了$[5,0]$

$$\begin{pmatrix} 1 & 3 \cr 2 & 1 \end{pmatrix}\begin{pmatrix} -1 \cr 2 \end{pmatrix} = \begin{pmatrix} 1\times (-1)+3\times 2 \cr 2\times (-1)+1\times 2 \end{pmatrix} = \begin{pmatrix} 5 \cr 0 \end{pmatrix}$$

当我们有一个线性方程组的时候，我们可以把它们用矩阵乘以向量的形式表示
cHpoedBJil7ynhg

单位矩阵 $E$：主对角线上的元素都是 1、其余元素都是 0 的 $n$ 阶矩阵（如二阶的 $E = \begin{pmatrix} 1 & 0 \cr 0 & 1 \end{pmatrix}$），它对应的线性变换就是什么都没做，任何矩阵与它相乘都不变，即 $AE = EA = A$

逆矩阵：对于 $n$ 阶矩阵 $A$，若存在 $n$ 阶矩阵 $B$，使得 $AB = BA = E$，则称矩阵 $A$ 是可逆的，$B$ 为 $A$ 的逆矩阵

行列式的计算

行列式（Determinant）本质上是一个数值，记为 $\det(A)$ 或 $|A|$，它表示线性变换把面积（体积）缩放的比例

二阶行列式可以直接计算

$$\begin{vmatrix} a & b \cr c & d \end{vmatrix} = ad - bc$$

降阶要用到代数余子式：$A_{ij} = (-1)^{i+j}M_{ij}$，其中 $M_{ij}$ 是删去 $a_{ij}$ 所在的行与列后得到的子行列式，于是有按行（列）展开定理

$$\det(A) = a_{i1}A_{i1} + a_{i2}A_{i2} + \cdots + a_{in}A_{in}$$

如：三阶行列式按第一行展开，就是把它降成三个二阶行列式

$$\begin{vmatrix} a_{11} & a_{12} & a_{13} \cr a_{21} & a_{22} & a_{23} \cr a_{31} & a_{32} & a_{33} \end{vmatrix} = a_{11}\begin{vmatrix} a_{22} & a_{23} \cr a_{32} & a_{33} \end{vmatrix} - a_{12}\begin{vmatrix} a_{21} & a_{23} \cr a_{31} & a_{33} \end{vmatrix} + a_{13}\begin{vmatrix} a_{21} & a_{22} \cr a_{31} & a_{32} \end{vmatrix}$$

按哪一行（列）展开都可以，选含 0 最多的那一行（列）会快很多

手算更常用化三角形法：用性质里「某一行（列）乘同一个数加到另一行（列）上，行列式不变」这条，把行列式化成上三角，此时行列式就等于主对角元的乘积（注意交换两行要变号、某一行乘 $k$ 要把 $k$ 提到外面，只有倍加不变）

$$\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \cr 0 & a_{22} & \cdots & a_{2n} \cr \vdots & \vdots & \ddots & \vdots \cr 0 & 0 & \cdots & a_{nn} \end{vmatrix} = a_{11}a_{22}\cdots a_{nn}$$

如：把第 2、3 行分别减去第 1 行的 2 倍、3 倍，第 3 行再减去第 2 行的 2 倍

$$\begin{vmatrix} 2 & 1 & 3 \cr 4 & 3 & 8 \cr 6 & 5 & 14 \end{vmatrix} = \begin{vmatrix} 2 & 1 & 3 \cr 0 & 1 & 2 \cr 0 & 2 & 5 \end{vmatrix} = \begin{vmatrix} 2 & 1 & 3 \cr 0 & 1 & 2 \cr 0 & 0 & 1 \end{vmatrix} = 2 \times 1 \times 1 = 2$$

特征值与特征向量

对 $n$ 阶方阵 $A$，若存在非零向量 $x$ 和数 $\lambda$，使得

$$Ax = \lambda x$$

则称 $\lambda$ 是 $A$ 的特征值，$x$ 是 $A$ 对应于 $\lambda$ 的特征向量

几何上，特征向量在变换后仍留在它自己张成的直线上，只被伸缩而不发生旋转，$\lambda$ 就是伸缩的比例，$\lambda < 0$ 表示该特征向量发生了反向

数论基础

群的定义

集合分为有限集合和无限集合
如：无限集合 $S_1 = {\cdots -20,-10,0,10,20,\cdots}$
有限集合 $S_2 = {-10,0,10}$

集合上加上运算规则就是代数结构，为集合 $S_1$ 赋予一个加法运算，组成一个代数结构 $<S_1,+>$

对于$S_1$而言，代数结构$<S_1,+>$中的加法运算满足
封闭性：$\forall a,b \in S_1,~ a+b \in S_1$
结合律：$\forall a,b,c \in S_1,\ (a+b)+c = a+(b+c)$
交换律：$\forall a,b \in S_1,\ a+b = b+a$

并且对于代数结构$<S_1,+>$而言
存在单位元 $e$：$\exists e \in S_1,\ \forall a \in S_1,\ e+a = a$
所有的元素都存在逆元： $\forall a \in S_1,\ \exists b \in S_1,\ a+b = b+a = e$

那么可以根据代数结构满足的条件，对其进行划分
广群 —— 只有封闭性。
半群 —— 封闭性 + 结合律。
幺半群 —— 封闭性 + 结合律 + 单位元。
群 —— 封闭性 + 结合律 + 单位元 + 逆元。
阿贝尔群—— 封闭性 + 结合律 + 单位元 + 逆元 + 交换律。

循环群

设群 $G$ 的运算为 $∗$，存在生成元为 $g$。那么对任意 $y \in G$，一定存在整数 $k \in Z$ 使得：
$y = \underbrace{g * g * \cdots * g}_{k \text{ 次}}$

则群$G$就是循环群

设 $G=\langle g\rangle$ 为循环群。若 $\forall y\in G$，$\exists k\in \mathbb Z$ 使得
$$
y = g^k,
$$
则称 $k$ 为 $y$ 关于底 $g$ 的离散对数，记为 $k=\log_g y$。

设 $m\ge 1$，$(a,m)=1$。使得
$$
a^{d}\equiv 1 \pmod m
$$
成立的最小正整数 $d$，称为 $a$ 对模 $m$ 的阶，记为 $\delta_m(a)$。

若
$$
\delta_m(a)=\varphi(m),
$$
则称 $a$ 是模 $m$ 的原根。

剩余系

对于模数 $m$，定义集合 $S_m$​ 为所有整数除以 $m$ 后可能得到的余数组成的集合：
$$S_m = \lbrace0, 1, 2, \dots, m-1\rbrace$$
这个集合叫作模 $m$ 的完全剩余系。

一组同余的数组成的集合被称为剩余类
例如模 3 下，余数为 2 的剩余类为：
$$ \lbrace\dots, -4, -1, 2, 5, 8, \dots\rbrace = \lbrace2 + 3k \mid k \in \mathbb{Z}\rbrace$$

所以剩余系是有限集合，剩余类是无限集合

上面都是集合，跟前面提到的群还差了一个运算。

以 $⟨S_5,\oplus⟩$ 为例（其中 $a \oplus b = (a + b) \bmod 5$，即$\oplus$是模加 ）：
它同时满足 封闭性 + 结合律 + 单位元 + 逆元 + 交换律，所以其是一个阿贝尔群

从 $ S_m $ 中取出所有与 $ m $ 互素的元素，组成的集合叫作简化剩余系，记作 $ S_m^* $：
$S_m^* = \lbrace a \in S_m \mid \gcd(a, m) = 1\rbrace$

一个元素在模 $m$ 下存在乘法逆元当且仅当它与 $m$ 互素

以$⟨S_{10}^*,\odot⟩$为例，（其中 $a \odot b = (a \times b) \bmod 10$，即$\odot$是模乘，$S_{10}^* = \lbrace1, 3, 7, 9\rbrace$)
它同时满足 封闭性 + 结合律 + 单位元 + 逆元 + 交换律，所以其是一个阿贝尔群

公式定理

数论四大定理

欧拉定理

设 $n,a∈Z$，如果有 $gcd(a,n)=1$，则有$$a^{\varphi(n) } \equiv 1 \pmod n$$（其中 $φ()$ 是欧拉函数，$φ(n)$ 表示模 $n$ 的简化剩余系中元素的个数）

中国剩余定理

设正整数$m_1,m_2…m_k$两两互素，那么对于任意的余数 $a_1,a_2,…,a_k$​,则同余方程组

$$
\begin{align}
\left\lbrace
\begin{array}{ll}
x \equiv a_1 \pmod{m_1} \cr
x \equiv a_2 \pmod{m_2} \cr
\quad \vdots \cr
x \equiv a_k \pmod{m_k}
\end{array}
\right. \notag
\end{align}
$$
有整数解$x$ 。并且在模$M=m_1⋅m_2⋯m_k$下的解是唯一的，解为
$$
x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + \cdots + a_kM_kM_k^{-1}) \mod M
$$
其中$M_i = M / m_i$，$M_i^{-1}M_i \equiv 1 \mod m_i$

威尔逊定理

它给出了一个正整数是素数的充分必要条件。即：一个整数 $p$ 是素数，当且仅当 $(p−1) ! \equiv −1\pmod{p}$。

‌欧几里得算法

也叫辗转相除法，
$\gcd(a, b) = \gcd(b, a \bmod b)$

跟据上述公式，我们可以快速计算两个数的最大公约数

用较大数除以较小数，得到余数 r。
若 r 为 0，则较小数即为最大公约数；若 r 不为 0，则用除数除以余数继续计算。
重复上述过程直到余数为 0，最后的非零余数即为最大公约数

1
2
3
4
def gcd(a,b):
    while b != 0:
        a,b = b, a % b
    return a

欧几里得拓展算法
$$
\exists x,y\in\mathbb{Z},\ \gcd(a,b)=ax+by.
$$
就是根据‌欧几里得算法推导过来的，前面通过余数来回相减得到最大公约数，所以可以得从结论，两个数的最大公约数可以用这两个数的整数倍之后相减得到

BSGS（Baby-Step Gaint Step）算法

已知：$g^x \equiv h \pmod p$

求解$x$

假设 $x=i*n+j$
那么则有：

$$
g^j \equiv h \cdot g^{-in} \pmod p
$$

通过遍历$j$和$i$就能等到x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from math import isqrt

def bsgs(g, h, p):
    n = isqrt(p - 1) + 1

    # Baby Step
    baby = {}
    cur = 1

    for j in range(n):
        if cur not in baby:
            baby[cur] = j #实际上保存： g^j mod p→ j ,j in [0,n)
        cur = cur * g % p
                            # 1 mod p → 0
                            # g mod p → 1
                            # g² mod p → 2
                            # g³ mod p→ 3

    factor = pow(pow(g, n, p), -1, p) # g^(-n) mod p

    # Giant Step
    cur = h

    for i in range(n):
        if cur in baby:
            # 实际上寻找：
            # 即：h(g^(-n))^i ≡ g^j mod p
            return i * n + baby[cur]

        cur = cur * factor % p 
            # h·g^(-n) mod p
            # h·g^(-n)·g^(-n) mod p
            # h·g^(-n)·g^(-n)·g^(-n) mod p

    return None

常见密码算法

大数分解问题—-RSA

设有明文 $m$、公钥 $(e,n)$、私钥 $(d,n)$、密文 $c$、其中$n=p*q$ ， $p,q$ 为两个大素数

RSA 的加密公式为 $c \equiv m^e \pmod n$
RSA 的解密公式为 $m \equiv c^d \pmod n$
其中 $e,d$ 满足 $e \cdot d \equiv 1 \pmod {\varphi(n)}$

因为 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$，所以知道$p,q$就很容易知道 $\varphi (N)$，进而根据公钥设计出私钥，而因为在整个加解密过程中p,q都没有泄露，所以要是想解密就得大数因式分解非常复杂

RSA-CRT

rsa中加解密使用到的幂运算需要大量的时间和算力，所以RSA-CRT算法的作用就是使用CRT将原来的幂运算变成两个指数更小的幂运算，从而提高效率

公钥还是$(e,n)$
私钥改为了 $(d_p,d_q,p,q)$
其中：
$$
d_p\equiv d\pmod{p-1} \equiv e^{-1} \pmod{p-1}, \qquad
d_q\equiv d\pmod{q-1} \equiv e^{-1} \pmod{q-1}, \qquad
q_{\text{Inv}} = q^{-1} \pmod{p}
$$

解密（或签名生成）时，先分别在模 $ p $ 和模 $ q $ 下计算两个中间值：
$$
m_1 = c^{d_p} \bmod p, \qquad m_2 = c^{d_q} \bmod q.
$$
根据CRT
$m \equiv m_1 \pmod{p} \equiv c^{d_p} \pmod{p} \equiv c^d \pmod{p}$
$m \equiv m_2 \pmod{q} \equiv c^{d_q} \pmod{q} \equiv c^d \pmod{q}$

最终计算明文$m$为：
$$
h = q_{\text{Inv}} \cdot (m_1 - m_2) \bmod p,\qquad m = m_2 + h \cdot q
$$

$d_p$泄露

$d_p$和$p$同等重要,一旦泄露就会导致私钥 $(d,n)$被计算出来

已知公钥对$(e,n)$，只需要再加上一个 $d_p$ 或者 $d_q$

由前面可得
$e \cdot d_p \equiv 1 \pmod {\varphi(p)}$
所以有
$e \cdot d_p = 1 + k \varphi(p)=1+k(p-1)$
然后就是遍历$k$就能找到$p$了

1
2
3
4
5
6
7
a = d_p*e-1
for k in range(2,e):
    if a%k == 0:
        p = a//k+1
        if n%p == 0:
            q = n//p
            break

共模攻击

同一明文$m$用的俩不同的公钥加密，但是公钥的$n$一样如
$c_1 \equiv m^{e_1} \pmod n$
$c_2 \equiv m^{e_2} \pmod n$

已知密文$c_1,c_2$，和对应的两条公钥$(e_1,n)和(e_2,n)$，并且$gcd(e_1,e_2)=1$。我们就能通过共模攻击计算出密文$c_1,c_2$对应的明文$m$

通过欧几里得拓展算法可以得出结论

$$
\exists u,v\in\mathbb{Z},\ \gcd(e_1,e_2)=e_1u+e_2v
$$
我们计算出$u,v$,就可以计算出明文
$c_1^u \cdot c_2^v \equiv m^{u\cdot e_1+v\cdot e_2 } \equiv m ^1 \pmod n$

1
2
3
4
u = inverse(e1-e2,e2) # u⋅(e_1−e_2)≡1 (mode e_2)
v = (1-e1*u)//e2
m = pow(c1,u,n)*pow(c2,v,n)%n
print(long_to_bytes(m))

低加密指数广播攻击

假设公钥$e$为3

同一明文有三组不同的公钥加密，但是公钥的e都为3
$c_1 \equiv m^{3} \pmod{n_1}$
$c_2 \equiv m^{3} \pmod{n_2}$
$c_3 \equiv m^{3} \pmod{n_3}$

已知密文$c_1,c_2,c_3$,和对应的公钥$(e,n_1),(e,n_2),(e,n_3)$

根据中国剩余定理可得：
$$
N = n_1 n_2 n_3, \quad N_i = \frac{N}{n_i} \quad (i=1,2,3)
$$

$$ N_i \cdot N_i^{-1} \equiv 1\pmod{n_i} \quad (i=1,2,3)$$

$$
x \equiv m^{3} \mod N \equiv (c_1N_1N_1^{-1} + c_2N_2N_2^{-1} + c_3N_3N_3^{-1}) \mod N
$$

p+q 泄露攻击

已知$p,q$都是512 bit素数，RSA公钥$n$、密文$c$和题目泄露的

$$
hint=(p+q)^2\bmod n
$$

要求出RSA私钥$d$，从而解密得到明文$m$。

由于

$$
(p+q)^2=(p-q)^2+4n
$$

不妨设$p<q<2p$，所以 $q-p<p$

因此

$$
0\leq(p-q)^2<p^2<n
$$

$$
\begin{aligned}
hint
&=(p+q)^2\bmod n\cr
&=((p-q)^2+4n)\bmod n\cr
&=(p-q)^2
\end{aligned}
$$

$$
|p-q|=\sqrt{hint}
$$

$$
p+q=\sqrt{hint+4n}
$$

因此已知$p+q$和$|p-q|$，可以通过两数的和与差求出$p,q$

$$
p=\frac{(p+q)+|p-q|}{2}
$$

$$
q=\frac{(p+q)-|p-q|}{2}
$$

p & q 不当分解 N

这类题型的要点是要能猜测到 $p+q$的大概值

设$a=\frac{p+q}{2}$
$b=\frac{q-p}{2}$

于是
$$
n=pq=(a-b)(a+b)=a^2-b^2
$$

$$
a^2-n=b^2
$$

也就是说，我们只需要找到一个$a$，使得$a^2-n$是一个完全平方数，就可以得到$b$。

  1. 小素数间隔攻击 (Fermat 分解)

RSA公钥$n$、密文$c$，并且已知：
$\qquad p\approx q$ ,即$|p-q|$ 较小

那么就知道a应该在$\lceil\sqrt n\rceil$附近

从$a=\lceil\sqrt n\rceil$ 开始枚举$a$。
代码如下：

1
2
3
4
5
a = isqrt(n) + 1
while not is_square(a*a - n):
    a += 1
b = isqrt(a*a - n)
p, q = a - b, a + b

离散对数问题

Diffie-Hellman 密钥交换算法

现在假设 Alice 想和 Bob 约定一个整数作为密钥，但 他们通信的信道是完全被监听的。

设 $G_p = \langle g \rangle$ 为模 $p$ 的循环群，其中 $p$ 为大素数，$g$ 为生成元。

系统参数：

  • 公共参数：$(p, g)$

密钥生成：

Alice 选取随机数 $a$，计算公钥：

$$
A \equiv g^a \pmod p.
$$

Bob 选取随机数 $b$，计算公钥：

$$
B \equiv g^b \pmod p.
$$

密钥交换：

Alice 将公钥 $A$ 发送给 Bob，Bob 将公钥 $B$ 发送给 Alice。

Alice 收到 Bob 的公钥 $B$ 后，计算共享密钥：

$$
K_A \equiv B^a \pmod p.
$$

Bob 收到 Alice 的公钥 $A$ 后，计算共享密钥：

$$
K_B \equiv A^b \pmod p.
$$

因此：

$$
K_A \equiv K_B \equiv g^{ab} \pmod p.
$$

最终 Alice 和 Bob 得到相同的共享密钥：

$$
\boxed{K = g^{ab} \pmod p}.
$$

安全性：

攻击者可以知道公共参数 $p,g$ 以及双方公钥 $A=g^a\bmod p$、$B=g^b\bmod p$，但在离散对数问题困难的情况下，无法在可行时间内由 $A$ 或 $B$ 求出私钥 $a$ 或 $b$，从而难以计算共享密钥$K$

目前为止，Diffie-Hellman 密钥交换算法是安全的。它被用于 SSL 协议的握手阶段。

ElGamal 加密方案

设 $G_p = \langle g \rangle$ 为循环群。对任意 $y \in G_p$，存在整数 $k \in \mathbb Z$，使得
$$
g^k \equiv y \pmod p.
$$

系统参数：

  • 私钥：$k$
  • 公钥：$(p, g, y)$

加密算法:
加密者选取随机数 $r \in \mathbb Z_{p-1}$，计算密文：
$$
E_k\bigl(m, r, (p, g, y)\bigr) = (y_1, y_2),
$$
其中
$$
\begin{aligned}
y_1 &\equiv g^r \pmod p, \cr
y_2 &\equiv m \cdot y^r \pmod p.
\end{aligned}
$$

解密算法:
接收方使用私钥 $k$ 解密密文 $(y_1, y_2)$：
$$
D_k(y_1, y_2, k) = y_2 \cdot \bigl(y_1^k\bigr)^{-1} \pmod p.
$$

正确性推导：
$$
y_2 \cdot \bigl(y_1^k\bigr)^{-1}
\equiv m \cdot (g^k)^r \cdot (g^{rk})^{-1}
\equiv m \pmod p.
$$

ElGamal 数字签名

密钥与加密方案保持一致

签名算法：
签名者选取随机数 $r \in \mathbb{Z}_{p-1}^*$（即 $1 \le r \le p-2$ 且 $\gcd(r, p-1)=1$），计算消息 $m$ 的签名：
$$
\operatorname{sig}_k(m, r) = (s_1, s_2)
$$
其中：
$$
s_1 \equiv g^r \pmod p
$$
$$
s_2 \equiv (m - k s_1) \cdot r^{-1} \pmod{p-1}
$$

验证算法:
验证者收到消息 $m$ 及其签名 $(s_1, s_2)$ 后，使用公钥 $(p, g, y)$ 进行验证。验证方程为：
$$
y^{s_1} \cdot s_1^{s_2} \equiv g^m \pmod p
$$
若等式成立，则验签成功；否则失败。

正确性证明：
签名生成时满足：
$$
s_2 \equiv (m - k s_1) \cdot r^{-1} \pmod{p-1}
$$
两边乘以 $r$，得：
$$
r s_2 \equiv m - k s_1 \pmod{p-1}
$$
即：
$$
k s_1 + r s_2 \equiv m \pmod{p-1}
$$
根据 费马小定理，可得：
$$
g^{k s_1 + r s_2} \equiv g^{a*(p-1)+m} \equiv g^m \pmod p
$$

椭圆曲线离散对数问题

ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。

椭圆曲线：设 $p$ 为素数，$\mathbb{F}_p$ 上方程
$$y^2 \equiv x^3 + ax + b \pmod p \qquad (4a^3 + 27b^2 \not\equiv 0 \pmod p)$$
的全部解 $(x,y)$，再加上一个无穷远点 $O$，组成的集合记作 $E(\mathbb{F}_p)$
后面的不等式是保证曲线光滑（没有尖点、自交点）的条件

点的加法：几何上就是”过两点的直线与曲线交于第三点，再把第三点关于 $x$ 轴翻折”
image-16
如：设 $P = (x_1,y_1)$、$Q = (x_2,y_2)$，则 $P + Q = (x_3,y_3)$，其中

$$k = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1}, & P \neq \pm Q \cr \dfrac{3x_1^2 + a}{2y_1}, & P = Q \end{cases}, \qquad \begin{aligned} x_3 &= k^2 - x_1 - x_2 \cr y_3 &= k(x_1 - x_3) - y_1 \end{aligned}$$

另外规定 $P + O = O + P = P$、$P + (-P) = O$（其中 $-P = (x_1,-y_1)$）
于是 $E(\mathbb{F}_p)$ 在点的加法下构成阿贝尔群，$O$ 是单位元，和前面的 $⟨S_m^*,\odot⟩$ 一样都是”集合 + 运算 = 群”

标量乘法：$kP$ 表示 $k$ 个 $P$ 相加，用二进制分解（倍点法）只要 $O(\log k)$ 次点加法

椭圆曲线离散对数问题（ECDLP）：已知曲线、基点 $G$ 和点 $Q = kG$，求整数 $k$
目前没有多项式时间的通用算法，$p$ 取 256 位左右就足够安全，ECC 的安全性就建立在这里

ECC 加解密：和前面的离散对数问题完全平行，只是把”模幂”换成”标量乘法”
私钥是随机数 $k$，公钥是点 $Q = kG$
加密（ElGamal 型）：取随机数 $r$，把明文嵌入成曲线上的点 $M$，密文是两个点
$$C = (rG,~ M + rQ)$$
解密时用私钥算 $M = (M + rQ) - k(rG)$，再把点 $M$ 还原成明文

分组密码

DES

DES算法跟前面不同之处在于，他没用到什么数学公式或者一些推导过程，利用到的技术就是分组，置换，异或
总结一下就是不难，但是步骤繁多，复杂
为节约篇幅，就介绍大致流程

加密流程

输入$x$(64 位)。
输出$y$(64 位)。
密钥$K$(64 位)，使用 64 位密钥中的 56 位，剩余的 8 位要么丢弃，要么作为奇偶校验位。
密钥$K$ ⽣成16个48位的轮密钥$K_n$
并且DES内部所用到的置换表都是写死的，即DES内部置换表都为已知

密文$y$生成的流程图如下
canvas

  1. 初始置换 IP

    • 将 64 位明文 $x$ 通过 IP 置换表重新排列，得到 64 位数据。
    • 将其分为左右两部分：$L_0$（左 32 位）和 $R_0$（右 32 位）。

  2. 16 轮 Feistel 迭代
    对 $i = 1, 2, \dots, 16$：

    • $L_i = R_{i-1}$
    • $R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$

    其中 $K_i$ 是第 $i$ 轮子密钥（由密钥调度生成），$F$ 是轮函数。

  3. 轮函数 $F(R, K)$
    输入：32 位 $R$，48 位子密钥 $K$。

    • E 扩展置换：通过扩展表$E$将 32 位 $R$ 扩展为 48 位。
    • 异或：与 48 位子密钥 $K_i$ 逐位异或。
    • S 盒替换：将 48 位分成 8 个 6 位组，分别送入 8 个 S 盒，每个 S 盒输出 4 位，合并为 32 位。
    • P 置换：将 32 位按 P 置换表重新排列，输出 32 位。

  4. 左右交换
    完成 16 轮后，得到 $L_{16}$ 和 $R_{16}$。交换左右，得到预输出：
    $$
    \text{预输出} = R_{16} \parallel L_{16}
    $$

  5. 逆初始置换 IP⁻¹
    将预输出通过 IP⁻¹ 置换表，得到 64 位密文 $y$。

密钥生成流程

canvasmiyao

  1. 64 位初始密钥 $K$ 通过 PC-1 置换，丢弃第8、16、…、64 位，得到 56 位有效密钥。

  2. 将 56 位分为左右两部分 $C_0$ 和 $D_0$，各 28 位。

  3. 对 $i = 1$ 到 $16$ 轮：

    • 根据循环左移表，对 $C_{i-1}$ 和 $D_{i-1}$ 根据循环左移位数序列左移 ，得到 $C_i$ 和 $D_i$。
    • 合并 $C_i \parallel D_i$，得到 56 位。
    • 通过 PC-2 置换，从 56 位中选出 48 位，作为第 $i$ 轮子密钥 $K_i$。

  4. 重复步骤 3 共 16 轮，最终生成 16 个子密钥 $K_1, K_2, \dots, K_{16}$。

分组密码的工作模式

AES

AES 明显用到了线性代数，包括 GF(2⁸) 上的矩阵乘法、仿射变换和有限域运算；DES 则主要是 GF(2) 上的置换和异或，线性代数体现在底层，但没有显式的矩阵乘法或有限域乘法

SM4

流密码

格密码