应用密码学
这是一门网安专属的专业课，也是一门高校之外很难学到的必修课。
Week1：Introduction
这门课虽然偏重应用的密码学，但笔记中会加入更多的数学背景和分析密码学知识，以帮助更好地理解。
有多少种不同的简单替换密码？可以通过枚举每个明文字母的可能密文字母来计算。
将26个明文字母分配给26个密文字母的总方式（每个密文字母只使用一次）是
26 × 25 × 24 × … × 4 × 3 × 2 × 1 = 26! = 403291461126605635584000000
因此，有超过10^26种不同的简单替换密码。每个相关的加密表称为一个密钥。
假设Eve截获了Bob的一条消息，并尝试通过尝试每个可能的简单替换密码来解密它。在不知道底层密钥的情况下解密消息的过程称为密码分析。
如果Eve（或她的计算机）每秒可以检查一百万种密码字母表，她仍然需要超过10^13 年才能尝试所有可能的密钥。但宇宙的年龄估计在10^10年左右。因此，Eve几乎没有机会解密Bob的消息
但事实并非如此：
在密码学的实际应用中，一个重要的教训：
你的对手总是使用她最好的策略来击败你，而不是你希望她使用的策略。因此，加密系统的安全性取决于已知的最佳方法来破解它。随着新的和改进的方法的发展，安全级别只能变得更差，而不会更好。
对单体换密码的密码分析：
Eve可以轻松破解简单替换密码的原因是，英语中的字母（或其他人类语言中的字母）并不是随机的。
如果Eve统计Bob加密消息中的字母并制作一个频率表，最频繁的字母很可能代表 e，而 t、a、o 和 n 将出现在接下来最频繁的字母中。通过这种方式，Eve可以尝试各种可能性，并在一定量的试错后解密Bob的消息。
(a) 表1.4中密文中出现的最常见的英文二元组（每1000个单词的频率）
(b) 表1.4中密文中出现的最常见的二元组
在之前信息安全数学的学习中，我们的同学知道欧几里得除法：
a = m*q + r
这表示 a = r (mod m)
为了更好地研究模数m的剩余类，有了这个定义：
Z/mZ = {0,1,2,……,m-1}
同时我们也知道它是一个商环。
这个性质让我在其中研究加法，减法，乘法非常方便。
但除此之外还想做除法，
于是根据裴蜀定理我们定义了逆元。
为了让这个研究范围内的每个数都有逆元
有了这个符号：
Z/pZ ，这个解释了我们之后所学的阶原根等等都围绕素数展开。
但是为了让每个元素都有除法，需要去除0
得到：
(Z/pZ*)，或者表示成F*_p，这定义了有限域
通过对以往学习到的数学知识的综述，我们可以认识到有限域：
“有限域在整个密码学中具有极大的重要性，并且贯穿了所有的数学部分”
之前的课程学到了这两种算法，但我们只知道它们数学上的用处。
扩展到密码学上：
在RSA和Diffie-Hellman密码系统中，Alice和Bob需要计算模N下大的幂，就可以用到快速幂算法。
在面对已知明文攻击时：
gcd(c1,c2,……) = gcd(km1,km2,km3……) = kgcd(m1,m2,……)
这里如果有欧几里得算法的时间复杂度证明，这会为后续密码学系统的安全性分析打下坚实的基础。
在学习了我们所知道的那些数学知识，介绍到凯撒密码时，还可以结合对称密码系统五的元组进行举例，
可以帮助同学们练习对问题进行抽象的符号化数学建模的能力，也让同学们理解原来所学的模算数的用处：
(Ciphertext Letter) == (Plaintext Letter) + (Secret Key) (mod 26) =>加密过程 c = p+k(mod 26)
(Plaintext Letter) == (Ciphertext Letter) - (Secret Key) (mod 26) =>解密过程 p = c-k(mod 26)
另一个例子：
加密函数：
$e: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{C} $解密函数：
$d: \mathcal{K} \times \mathcal{C} \rightarrow \mathcal{M}$解密函数“撤销”加密函数的结果：
$d(k, e(k, m)) = m \quad \text{for all } k \in \mathcal{K} \text{ and all } m \in \mathcal{M}$每个密钥 ( k ) 的函数对：
$e_k: \mathcal{M} \rightarrow \mathcal{C} \quad \text{and} \quad d_k: \mathcal{C} \rightarrow \mathcal{M}$解密性质：
$ d_k(e_k(m)) = m \quad \text{for all } m \in \mathcal{M} $
单射：
$ m = d_k(e_k(m)) = d_k(e_k(m’)) = m’ $
之前在古代，密钥可能只是一串数字或符号。现在我们可能还不知道现代密码学系统中的密钥张什么样子，
我们的PPT美中不足就是好像没有介绍编码，
密钥空间 $ \mathcal{K} $：
$ \mathcal{K} = { k \in \mathbb{Z} : 0 \leq k < 2^{B_k} } $明文空间 ( \mathcal{M} )：
$ \mathcal{M} = { m \in \mathbb{Z} : 0 \leq m < 2^{B_m} } $密文空间 ( \mathcal{C} )：
$ \mathcal{C} = { c \in \mathbb{Z} : 0 \leq c < 2^{B_c} } $将明文 (m) 表示为二进制形式：
$ m_{B-1}m_{B-2}\ldots m_2m_1m_0 \longleftrightarrow m_{B-1} \cdot 2^{B-1} + \ldots + m_2 \cdot 2^2 + m_1 \cdot 2 + m_0 $
其中 (m_0, m_1, \ldots, m_{B-1}) 为 (m) 的二进制位，每个位的值均为 0 或 1。
于是我们就能对密钥有一个实际的感受，并且对穷举搜索攻击的穷举对象有个了解，以及密钥长度应该大于多少有个了解。
我们的课上介绍了OTP，说它时理论上完美的密码，但是同学们可能还是对OTP陌生，或许可以将这里异或运算的公式拿来：
随机比特序列可能我们的课上还没有见到，通过加一些这样的内容。或许可以让同学们在学到密码算法的分类基础上更近一步，为什么要这样分类，
由此对各种密码学算法的优劣有一个大致的分析，让同学们产生一个全局的认识，激起学习热情。
同学们通过课上的示图直观地感受到了这种非对称，但是这种非对称的建立基础？以及这里为什么还要有密钥协商协议，它们来做什么用的？
这里取到了上学期《信息安全数学》里的图：
一些原理性的解释可能会让同学们注意力更集中，更兴奋地了解到算法背后的机制。