Introduction

概念

传统的密码学被称为 Codes 或是 Ciphers，如凯撒密码等构造方式；而现代密码学提供的与之对应的概念被称为 Encryption Scheme，并有严格的安全证明，两者存在巨大差别。

密钥假设

之后的讨论中，默认为对称密钥加密。

在刚学密码学的时候，我们简单的假设密钥能够安全共享，避开对安全传递密钥过程的讨论（因为目前的知识无法对其进行讨论）。 另外，实际的安全方案里，妥善保存密钥是十分麻烦的，因此在刚开始学的时候，我们默认密钥能够安全保存。

基本记号

$$\begin{split} K:& key\quad space\\ M:& plaintext\quad space\\ C:& ciphertext\quad space \end{split}$$

类似于取值空间（概率论）的概念。 $M$在传统密码学中可能是一些字母（编码）表，但现代密码学将其设定为二进制字符串，对应现实中传递的信息。 加密方案（Encryption scheme）由以下部分组成：

1. 密钥生成算法: $Gen->K(probabilistic)$
2. 加密算法: $Enc:K\times M\rightarrow C$
3. 解密算法: $Dec:K\times C\rightarrow M$

加密算法必须保证正确性：$\forall k \in K,m \in M:Dec_k(Enc_k(m))=m$

现代密码学和传统密码学的一个重要区别是Kerckhoffs principle：

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.

加密的方法必不能被要求是秘密的，并且这种加密的方法必定能够被敌手获取。

现代密码学放弃了对加密方案的保密性，因此你可以在网络上找到加密库的源代码，例如OpenSSL。密码学认为，唯一应该保密的是密钥本身，而加密方案应当公开。(同时，这个原则也隐含了一点：不要用自己实现的加密方案)

WHY?

1. 对加密方案保密是不切实际的，诸如逆向工程、渗透攻破等方式便可以得到加密方案。即，你无法预计敌手会采取什么方式获取到你的加密方案；也因此，不能够认为对加密方案进行保密措施便能够确保更好的安全性。
2. 相比而言，相较加密方案而言，更小的密钥更易保存，更改密钥也比更改方案更加容易。
3. 能够更好的在公开场合下讨论加密方案的安全性，从而促进加密方案的标准化。

传统加密

这里就简略了。

传统密码学更多意义上可以看作一种“艺术”，是一种智力上的比拼；但其也可以通过诸如暴力破解、频次分析、词法分析等方式破解，暴力破解的原因就是因为密钥空间不够大，如凯撒密码只要暴力枚举26次就能解。因此，你可以看到如今的加密方案密钥空间越来越大，DES为$2^{56}$，比特币采用$2^{90}$大小的密钥空间加密方案，AES的密钥空间已经扩展到了$2^{128},2^{256}$及以上.

然而DES因为密钥空间太小的原因，也已经变得不够安全。现在用DES基本都要用3DES方案。

现代密码学

现代密码学有以下原则，来保证可证明性安全（归约安全）：

1. 提供形式化的安全定义。
2. 精确的给定假设。
3. 在假设的基础上，提供一个构造的加密方案的安全性证明，安全性基于安全定义。

安全定义

安全定义又分为两部分：

1. 安全目标
2. 威胁模型

只有明白了这两个才能进一步构造安全方案。

安全目标

形式化定义，也就是形式化以上的安全加密方案。

作用：

1. 避免糊里糊涂的方案定义，能够提供一种方法去评估、证明安全性与否。
2. 提供了方案比较的有效性。方案的安全性取决于具体的上下文环境，弱定义的安全方案可能比强定义更加有效。->模块化的可行性。

安全目标

不管攻击者有了多少信息。密文都不能泄露给敌手任何额外的关于明文的信息。

实际上，这种定义比想象中的要强。该加密方案不会泄露密钥、不会泄露明文信息，加密者也无法获取除了明文外的别的信息。因此，理论上，这种强定义便可阻绝一切可能的攻击。

这里并没有定义信息的“meaningful”，而是直接定义没有任何信息被泄露，因此该定义可以应对其他潜在的威胁。关于“不泄露任何关于明文的信息”，以及有关攻击手可能有的先验知识相关，在之后的第二、三章中便有涉及。

威胁模型

可以看看这里的威胁模型。

密码学中认为有四种威胁模型，这些威胁模型代表了敌手的能力（但你无从得知敌手的能力，这里的四种能力更多是学术上的分类）。

1. Ciphertext-only attack,获取密文攻击，敌手仅能获取到传递的密文。
2. Known-plaintext attack,获取明文攻击，敌手可以得到明文、密文对，他的攻击目标是攻破用相同密钥加密的密文。
3. Chosen-plaintext attack(CPA)，选择明文攻击，敌手任意选择明文，能够得到明文/密文对。CPA安全性是很重要的（后面的章节有讨论）
4. Chosen-ciphertext attack(CCA)，选择密文攻击，敌手能够得到任何密文的解密结果。

可以发现，由上到下的威胁模型，敌手越来越强。另外需要说明的一点是，这里的attack便已经为之后的预言机模型打下某些基础。预言机的概念暂且不表。

相关假设

除了安全性证明需要精确的假设，其还可以让我们能够进行方案间的比较。基于更弱的安全性假设，能够有更高的自由度去构建加密方案，因此相较而言，弱安全性假设下的安全性证明更受到人们的青睐。

同时，精确假设也提供了：若组成加密方案的block被攻破后，假设仍然成立下的衡量原加密方案安全性的方式。

这里解释了一堆为什么采用建立在假设上的安全方案，而不是直接认为安全方案是安全的原因，这里略了（书P19）。

Turing Machine

图灵机模型在计算机科学中占有极为重要的地位，以其为基础建立的图灵机模型成为可计算性理论、计算复杂度理论中重要的一环。 在之后的学习中，将会学习到以下定理：

Strong Church-Turing Thesis

Every physically realisable computation can be simulated on a Turing Machine with at most polynomial slowdown. Probably only true if we exclude quantum computers.

也就是：任何多项式算法，无论在现实中采用什么物理模型，都可以归约到图灵机模型，并且时间复杂度也同样是多项式。（当然还没有出来的量子计算机不在讨论范围内）

然而这是第三章的内容.

NP

有了图灵机模型，才能够讨论$NP$问题。实际上，密码学大部分的原语(大约是基本组成部分的意思)都建立在$NP\neq P$的基础上，这样才能讨论计算复杂性安全（后面的博客来讲）

公钥密码学（非以上讨论的对称密码）中的很多结构，例如因式分解的难解性就基于$NP$问题。

实际上，密码学也是一个自底而上的不断构建的过程，构建复杂加密方案的时候需要之前验证过的简单的密码学部分。这样，即使部分出现问题，换一个component就行了；若加密方案出现问题，则认为是加密方案组织的问题，不是component的问题。

安全性

之前讨论的是可证明安全性，加密方案建立在安全目标和威胁模型的假设基础上证明其安全性。自然是和实际中的安全性是不一样的。

可证明安全性建立在安全目标、威胁模型的基础上，现实世界不会提供这么理想的模型的。同时，即使现实世界满足了可证明安全性的条件，也不能一定确保安全性，但这种方式自然是极难找到的。在密码学中不进行讨论。

若要构建加密方案，必须要建立在精确假设上的安全性证明上，这比启发式，或者没有假设的证明好。

关于启发式的证明：即使证明了对于一大批攻击下你的方案的安全性，也不能保证你的方案一定安全。