公钥密码学
公钥密码学基本定义
一个公钥密码学协议由以下的三个部分组成：**生成，加密，解密
1. Gen 秘钥生成算法，根据输入的安全参数，输出为一对公私秘钥对（sk,pk）
2. Enc 加密算法，可以将公钥和明文作为输入，得到密文作为输出，可以直接理解为加密其实本质上是一种算法，同时加密算法应该具备算法的几个基本属性 通用性，确定性，有效性，有穷性，密码学术语中的算法都遵循这些性质。
3. Dec 解密算法，将私钥和密文作为输入，得到明文作为输出。
CPA安全
CPA（Chosen-Plaintext Attacks）选择明文攻击，也称为语义安全，这是最早提出的一种安全定义。其实可以理解为语言上的安全，即看起来的安全，看起来不可区分的安全，给定两个密文不能区分对应加密明文的不可区分安全。简而言之，就是说你无法通过语法、语言、观察判断密文与一个随机数的区别，也就意味着无法通过上述的方式判断密文和明文之间的对应关系。CPA实验形式化的描述如下：
CPA形式化描述如下：
1. 运行秘钥生成算法，得到密码学协议的公钥和私钥。
2. 敌手A 可以获得公钥PK，以及可以在明文空间选择两个不同的明文M0和M1，以及可以访问加密谕言机获得任意明文的密文。
3.随机选择b : 0 - 1 将对应的明文加密得到挑战密文CT。
4.敌手A输出一个比特b`。
5.如果敌手猜测成功，则实验结束。
PS：值得注意的是，这里的加密不是由敌手来实现的，一般来说，我们定义这个给敌手生成挑战密文的角色为挑战者，也可称之为加密谕言机。本质上敌手完全可以自己加密，这是允许的也是现实的，因为CPA假定敌手已经掌握了公钥加密算法，公钥以及明文空间，敌手可以尝试自己加密任何他选择的明文，学习相关的知识。
CPA不可区分安全定义
CPA安全试验已经在上文描述完成，有个这个安全试验，进一步，我们可以定义CPA不可区分性安全定义，如果满足上述的定义10.3 则密码协议在CPA模型下，具有不可区分安全性。其实很简单，就是说一个PPT敌手A能够赢得这个游戏的概率小于等于二分之一 加 可忽略的函数值。这个从定义上看，也是非常好理解的。如果敌手没有任何的计算优势，那么他成功完成CPA实验的概率其实最多只有二分之一，现在要求他赢得这个实验的概率小于等于二分之一，则证明其实本质上敌手是不能完成这个实验的，另外还有一种描述方法，我们称之为优势，敌手赢得这个实验的优势，优势即为完成实验的实际概率减去二分之一，就是敌手完成实验的优势。
Tips:公钥加密无法实现完美保密这个属性，原因是非常简单的，因为存在一个可忽略的函数，即为敌手的优势，所以就无法实现完美保密：
.
Tips:所有的确定性加密均不能满足CPA安全，这是非常容易理解的，如果明文空间比较小，那么完全可以通过穷举的方式，得到任何想要的密文对应的明文。
多次加密协议
在上节中，描述的CPA安全是对两个密文进行加密的描述，那么对于多个明文是否能够保证在窃听敌手下的安全性？
定理10.10 回答了这个问题，如果一个公钥协议在窃听敌手下是不可区分加密的，那么这个协议在多次加密协议下也是不可区分安全的，其实是对上边定理的扩展，为什么？因为在现实中，加密数据的传输往往不是一个一个的密文传输的，很可能是一组一组的密文传送，所以这个定理不但是安全的扩展，还是对现实安全情景的一种更广范围的抽象与提炼。
任意长度加密协议
对于多次加密的描述来看，还是对于每次加密的明文长度都相同的，但是对于每次不同的密文长度又能如何计算呢？
其实比较容易，直接切分成相同长度的部分来使用即可，证明也是类似的，内容如下：
混合加密（Hybrid Encryption）
继续由上可知，公钥加密是安全可用的，但是还存在一个问题，即为公钥加密，密文往往较长，时间消耗比较大，能否存在高效的方案呢？
答案就是混合加密，同时使用对称加密与非对称加密，使用对称加密密文，然后使用公钥加密对称的秘钥。
方案形式化描述如下：
证明在《Introduction to Modern Cryptography》Katz, Lindell P332