Chapter1 密码学概述

1.1 安全服务

对称密码机制：（DES,AES,SM4,RC4）

公钥密码机制：（RSA,ECC,SM2,DH）

密钥管理简单的原因：

只需要将公钥分发给需要加密通信的人，而私钥则仅由接收者持有，不需要在通信中共享私钥，可以避免对密钥进行传输和管理

移位密码
仿射密码
- 加密算法：$y=E_{a,b}(x)=(ax+b)%26$
- 解密算法：$x = D_{a,b}(y)=(a^{-1}y-a^{-1}b)%26$
Vignere 密码
- 将明文消息中的每个字母移动 $k_i$ 位， $k_i$ 为密钥，是长度为 $m$ 的序列 $k = (k_0,k_1,…,k_{m-1})$
- $y_i = (x_i+k_{i%m}%26)$，密钥空间为 $26^m$
- 存在周期性弱点。破译方法：重合指数攻击，通过重合指数找到密钥长度，获取移位密码
- OTP 密码原理相似，是一种多表代替算法，密钥空间为 $26^n$

x 和 y 为不同时为 $0$ 的整数，则 x 和 y 的最大公因子 (x,y) 是以 ax+by 表示的最小正整数：

计算 $(100,23)$ 的过程：
$100-4×23=8$
$23-2×8=7$
$8-1×7=1$
$7-7×1=0$

乘法逆元：

$-13×23%100=1$

(*)$23^{-1}%100 = -13 = 87$

$3×100%23=1$

(*)$100^{-1}%23=8^{-1}%23 = 3$

对于正整数 $n$，与其互素的小于等于 $n$ 的正整数的个数表示为 $\varphi(n)$，有以下定理：

若正整数 $m,n$ 满足 $(m,n)=1$，则有 $\varphi(mn) = \varphi(m)\varphi(n)$；特别地，当p为素数时,$\varphi(p)=p-1$
正整数 $n=p_{1}^{e_{1}} p_{2}^{e_{2}} \ldots p_{m}^{e_{m}}$ 的欧拉函数 $\varphi(n)$ 值为 $\varphi(n)=\left(p_{1}-1\right) p_{1}^{e_{1}-1}\left(p_{2}-1\right) p_{2}^{e_{2}-1} \ldots\left(p_{m}-1\right) p_{m}^{e_{m}-1}$
欧拉定理：对 $n>1$，如果 $(x,n)=1$，则有 $x^{\varphi(n)}\equiv 1 (mod;n)$

应用：由于$2^{\varphi(89)}=1,2^{1000};mod;89=(2^{88})^{11}*2^{32};mod;89=2^{32};mod;89$，可以采用快速指数算法计算答案为 $64$.

快速指数算法

计算 $x^e$，设置三元组 $(X,E,Y)$，其初始值为 $(X,E,Y)=(x,e,1)$

若 $E$ 是奇数，则 $Y=X*Y,E=E-1$

若 $E$ 为偶数，则 $X=X*X,E=E/2$

当 $E=0$ 时，$Y$ 的值即为 $x^e$

DES 算法是一种对称密码算法，分组加密，包括三个步骤：

分组长度为 $64$ 位，分 $4$ 子组进行操作，密钥长度为 $128$ 位，使用异或、模 $216$ 加、模 $216+1$ 乘三个混合运算，在 $16$ 位子分组上进行。

128比特的明文分组被分成4×4的字节矩阵

字节替换SubBytes：非线性置换,独立作用于状态中的每一个字节
行移位运算ShiftRows：字节的循环移位运算,第1行至第4行字节分别向左移动0~3列
列混合运算MixColumns：由一个线性变换对状态的每一列进行变换
```
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
```
轮密钥加AddRoundKey：与相应的密钥进行异或.