公钥加密相关基础知识

主要记录一下主流体系以及可证明安全方法

1. 传统公钥基础设施（PKI）体系

这是最常见的方式，比如用在HTTPS网站上。

• 核心角色：证书颁发机构（CA）
• 怎么工作：
  1. 你生成一对公钥和私钥。
  2. 你把公钥和你的身份信息，交给一个绝对可信的第三方——CA。
  3. CA核实你的身份后，用它的私钥对你的公钥和身份信息进行数字签名，生成一个“数字证书”。
  4. 别人想和你通信时，需要先拿到你的证书，然后用CA的公开的公钥去验证这个证书的签名。验证通过了，才相信这个公钥确实是你的。
• 缺点：
  • 成本高，管理复杂： 你需要向CA购买和维护证书。
  • 单点故障： 整个系统的信任都依赖于CA。如果CA被攻破或者它的私钥泄露了，整个信任体系就崩塌了。

简单比喻： CA就像一个公安局户政科。你要证明“你是你”，需要去那里办一张带公章和防伪的身份证（数字证书）。别人通过检查身份证上的公章真伪（验证CA签名）来相信你的身份。

2. 身份基密码（IBE）体系

为了解决PKI的证书管理问题，有人提出了IBE。

• 核心思想： 你的公钥就是你的身份标识！比如你的邮箱地址 your_name@company.com 或者手机号，直接就可以作为公钥。
• 怎么工作：
  1. 有一个叫私钥生成器（PKG） 的中心机构，它掌握着一个主私钥。
  2. 你想获取你的私钥？把你的身份信息（邮箱）给PKG，PKG用主私钥为你计算生成对应的私钥。
  3. 别人想用你的公钥（也就是你的邮箱）加密信息时，也需要从PKG获取一些公开的系统参数。
• 缺点：
  • 密钥托管问题： 这是最致命的缺陷。PKG知道所有用户的私钥！ 这意味着PKG可以冒充任何用户，也可以解密所有密文。你完全信任PKG不会作恶。

简单比喻： PKG就像一个配钥匙的总管家。你的名字（身份）就是门牌号（公钥）。你需要私钥时，总管家用他的万能模具给你配一把。但总管家手里有所有人的钥匙，他随时可以进你的房间。

3. 无证书公钥密码（CL-PKC）体系

无证书体系就是为了同时解决上面两个问题而设计的。它没有证书，也没有密钥托管。

无密钥托管： 因为KGC不知道你的“用户秘密值”，所以它无法计算出你的完整私钥，不能冒充你。

核心思想： 把你的私钥分成两半，由你和一个半可信的第三方（叫密钥生成中心，KGC）共同生成。

怎么工作：

部分私钥： 你向KGC注册你的身份和公钥。KGC用它的主私钥为你的身份信息生成一个部分私钥，并通过安全通道发给你。

用户秘密值： 你自己独立生成一个秘密的随机数，作为你的用户秘密值。这个值KGC不知道。

完整私钥： 你用收到的“部分私钥”和你自己掌握的“用户秘密值”，通过一个算法合成你的最终完整私钥。这个完整的私钥从未完整地经过KGC。

完整公钥： 你的公钥也由“部分公钥”（从部分私钥得来）和“用户秘密值”对应的公钥部分共同组成。

巨大优势：

无证书： 不需要像PKI那样维护复杂的证书链。

可证明安全性方法的一般步骤

1.确定密码方案的安全性目标；

2.形式化定义密码方案的安全性；

3.证明密码方案的安全性。

传统公钥加密方案的定义

三个算法：密钥生成算法(KeyGen)，加密算法(Encrypt)，解密算法(Decrypt)

公钥加密方案安全性相关概念及安全目标
数学概念：
Decisional Diffie-Hellman,DDH：判定性困难问题，DDH问题仅限于非双线性对。在双线性下，DDH不是困难问题。

DDH的表现形式：设G是一个大素数p阶群，g是群G的生成元，则给定元组$(g,g^x,g^y,T)\in G^4$，其中，$(x,y)\in Z_p^*$，判断T与$g^{xy}$是否相等是困难的，即没有多项时间算法能够区分T与$g^{xy}$，称$(g^x,g^y,g^{xy})$是一个Diffie-Hellman三元组。

CDH：计算性困难问题。

CDH的表现形式：设G是一个大素数p阶循环群，g是群G的生成元，则给定元组$(g,g^x,g^y)\in G^3$，其中，$(x,y)\in Z_p^*$，计算$g^{xy}$是困难的。

密码学概念:

公钥加密方案的安全性指方案在特定的敌手模型中所能达到的安全性目标。

解密谕言机：用于模拟敌手的能力及其所能得到的攻击条件。

语义安全性：即使已知某个明文的密文，敌手也的不出该明文的任何部分信息。

不可区分性：已知密文C是两个明文m_0和m_1之一的加密的结果，若没有多项式时间算法可区分出C是m_0还是m_1的密文，则称该方案满足不可区分性。

CPA(Chosen-Plaintext Attack)：选择明文攻击。攻击者可以加密任意他选中的明文，然后通过分析对应的密文是否相同来破解密钥。就像你有一个能随便用的魔法锁。你可以拿任何钥匙（明文）去捅它，看它变成什么形状（密文），从而猜出锁芯（密钥）的结构。

CCA(Chosen-Ciphertext Attaack)：选择密文攻击。攻击者可以解密任意他选中的密文，然后通过分析对应的明文来破解密钥。就像你有一个能随便开的魔法钥匙。你可以把它捅进任何锁（密文）里，看它能打开什么样的门（明文），从而反推出这把钥匙（密钥）的齿形。

CCA1：非适应性选择密文攻击；非适应性指的是敌手获得目标密文C后就不再允许询问解密谕言机。

CCA2：适应性选择密文攻击；CCA2在CCA1的基础上，敌手在给定目标密文C后，还可以适应性选择密文并询问谕言机获得相应解密，但敌手不允许将目标密文C作为解密谕言机的输入。【现有方案参考这个标准】

CCA安全的方案，必须是非可塑的，也就是说敌手输入的密文c’与真实的密文c不能内容相关。

最基本的安全目标：满足单向性加密(One Wayness, OW)【最弱】

常见安全性目标：单向性(OW)；语义安全性(Semantic Security, SS)；不可区分性(Indistinguish ability,IND)【SS与IND安全性等价】

最强安全性目标：非延展性(Non-Malleability,NM)【安全性最强，无法证明】

IND-CCA2被公认为公钥加密方案的标准安全性概念，也是当今公钥加密方案候选标准的最重要的要求之一。

通常，公钥加密方案满足选择密文安全性，指满足IND-CCA2安全性，简记为IND-CCA。

ElGamal加密方案:

ElGamal加密方案在CPA攻击下满足IND安全性，即IND-CPA安全性。

ElGamal加密方案的安全性基于DDH问题，是概率加密的思想。

KeyGen：生成一个p阶乘法循环群$G=<g>$，p为k比特大素数。随机选取$x \in Z_p^*$，计算$y=g^x$；输出公钥$pk=(p,g,y)$和私钥$sk=x$.

Encrypt(m,pk)：随机选择$r \in Z_p^*$，计算$U=g^r$和$V=y^r \cdot m$；输出密文C=(U,V)

Decrypt(C,sk)：输出明文 $m= V/U^x ={y^r \cdot m} / (g^r)^x = y^r \cdot m /y^r = m$

可证明安全性的基本方法是规约论断，即将密码方案的安全性规约为某个或多个极为本原的安全性或困难性。