[笔记]什么是密码学

1. 第一节笔记

The syntax of encryption. A private-key encryption scheme, or cipher, is comprised of three algorithms: the first is a procedure for generating keys, the second a procedure for encrypting, and the third a procedure for decrypting.

在密码学里面，我们需要定义三个算法，即生成密钥算法 $\mathsf{Gen}$，加密算法 $\mathsf{Enc}$ 和解密算法 $\mathsf{Dec}$，一般定义密钥空间 $\mathcal{K}$，明文空间 $\mathcal{M}$，密文空间 $\mathcal{C}$，对于每一个由算法 $\mathsf{Gen}$ 生成的密钥 $k$，在针对某个明文 $m\in\mathcal{M}$ 时，有

$Dec_k(Enc_k(m))=m$

Kerckhoffs’ principle:
The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.

柯克霍夫原则(Kerckhoffs’ principle)，即认为密码学的安全性应该建立在对密钥的保护上，而不是建立在算法上。即使对手知道加密算法，如果他不知道密钥的话，整个密码系统应该也是安全的。

Stated differently, Kerckhoffs’ principle demands that security rely solely on the secrecy of the key.

书中给出了两个支撑柯克霍夫原则的论点：

1. 密钥比算法要容易保存和分享
2. 即使密钥丢失了，去生成一个新的密钥比去设计一个新的算法更容易

常见攻击方法(Attack scenarios)：

1. 唯密文攻击(Ciphertext-only attack)：passive，只知道密文
2. 已知明文攻击(Known-plaintext attack)：passive，知道一些明文/密文对
3. 选择明文攻击(Chosen-plaintext attack)：active，能加密，Sec.3.5
4. 选择密文攻击(Chosen-ciphertext attack)：active，能解密，Sec.3.7

古典密码：

1. 凯撒密码(Casar’s cipher):将每个字母用它后三位的来代替
   由凯撒密码而衍生出了移位密码(shift cipher)，凯撒密码中没有密钥，而移位密码则将密钥设置为移动的长度，范围为0～25，密钥空间太小，很容易用穷举法攻破
2. 单字母表替换(Mono-alphabetic substitution):因为是替换整个字母表，所以密钥长度为26!，由于单个字母出现的概率没变，所以很容易用概率统计的方法攻破
3. 维吉尼亚密码(Vigenere cipher)

现代密码学所遵循的原则：

1. Formal Definitions
2. Precise Assumptions
3. Proofs of Security