密码学基础
古典加密算法
Vigenere算法：
首先我们有一组密钥：K，对明文M进行加密，得到密文C。
在密钥当中，a表示凯撒前移0位，b表示1位。。。z表示25位。然后对M的对应字符加密。加密完，K用下一个字母，对M的下一个字母加密。可以表示为：
$$
C_i=M_i+K_{i\ mod\ L} \ mod\ 26
$$
$$
M_i=C_i-K_{i\ mod\ L}\ mod\ 26
$$
Playfair加密算法：
选取一个密钥，将其去重。如cryptography -> cryptogah。然后从左到右、从上到下填入5x5的矩阵（注意，i/j视为同一个字母）。剩下的部分则a-z顺序填写。得到密钥矩阵。
接下来把明文两两一组切分。如love -> lo ve。如果有相邻且相同的字符，中间插入x。如killers -> ki lx le rs。如果最后还有落单的字符，配上x。如tom -> to mx。
最后进行加密：对于一组内的两个字符：
- 如果在矩阵的同一行，各自变成各自右边字符
- 如果在同一列，各自变成下面的字符
- 否则，变成对角线的字符。x a | b y -> (x, y) -> (a, b)
解密则是把右下变成左上。
现代加密算法
DES算法：
$$
L_i=R_{i-1},\
R_i=L_{i-1}\oplus F(R_{i-1},k_i)
$$
总共有16轮加密。CBC加密算法：
$$
C_N=E_K(C_{N-1}\oplus P_N), C_0=IV,\
P_N=D_K(C_N)\oplus C_{N-1},C_0=IV
$$
流密码加密：
把密钥流与明文数据异或。
线性反馈移位寄存器LFSR：
对于一个特征多项式，$f(x)=1+c_1x+c_2x^2+c_3x^3+…$ 其中, x^n表示离结果寄存器距离为n的寄存器，c_n表示是否参与异或操作。如 $f(x)=1+x^2+x^4$
递归关系为：$a_n=a_{n-2}\oplus a_{n-4}$，表示a_n受到距离为2，4两个寄存器a_{n-2}, a_{n-4}的影响。
Diffie-Hellman算法
Alice和Bob各自保有a, b。双方都已知p, g
Alice生成 $A=g^a\ mod\ p$，将A, p, g发给Bob
Bob生成 $B=g^b\ mod\ p$，同时计算得到 $K=A^b=g^{ab}\ mod\ p$。将B发回给Alice
Alice计算 $K=B^a=g^{ab}\ mod\ p$
这样，双方共有p, g, K。各自保有a, b。
数学原理
- 扩展的欧式算法，求乘法逆元。
- 普通欧式算法：求最大公约数
$$
\gcd(a,b) = \gcd(b, a\ mod\ b)
$$
- 中国剩余定理：解同余方程。
对于
$$
x\equiv b_i\ mod\ m_i
$$
求取$ m=\Pi m_i, M_i=m/m_i, M’_i=M^{-1}_i\ mod\ m_i, sum = \sum M_iM’_ib_i$
则$x=sum\ mod\ m.$
- 费马小定理
$a^{p-1}=1\ mod \ p$
- 欧拉定理
欧拉函数：$\varphi(n)$是从[1, n)与n互质的数的数量。显然 $\varphi(p) = p-1.$
定理内容：$a^{\varphi(n)} = 1\ mod\ n$.
可以看到，费马小定理是欧拉定理的一种特殊的情况。
上面两个定理结合模运算的性质，可以解决一些数论问题。
- 本原根
例如2是29的一个本原根，这意味着 $2^1, 2^2, …, 2^{28}$可以取遍1~28的所有数。也意味着所有数y都可以写成 $y=2^x$。
离散对数： $x=dlog_{2,29}y$