06 公钥加密

寻求新的解决方案

在私钥加密的背景下，我们假设消息的发送方与接收方提前约定了只有双方知道的密钥。然而，私钥的约定必须提前在一个安全的信道上完成，这在很多时候是不方便甚至无法实现的。

考虑$n$个人的团队需要安全地互相通信的场景。如果需要用私钥加密保证团队中的人两两能够安全通信，那么每个人都要提前存储余下$n-1$个人的私钥，随着需要保密存储的内容越来越多，安全性的保障就越来越低。如果这个团队有一个新人加入，那么需要为所有人分配新的密钥。如果这些用户分布在全球范围内，那么安全信道（例如物理接触）更加难以实现。并且，在网购等事先不知道对方用户身份的场景下，事先约定好密钥几乎是不可能的。以上这些问题让我们想要突破私钥加密的背景，寻求新的解决方案。

我们首先可以对“两两储存私钥”做一点优化。假设存在一个可信的“中心服务器”，也即假设存在一个$n$个人都可以通信的对象，那么我们可以提出以下这种通信方案：每个人都存储一个与中心通信的密钥$k_i$，中心存储着所有这些密钥$k_1,\cdots,k_n$。当编号为$a$的人想要和编号为$b$的人通信时，可以首先给中心发送信息“我要和$b$通信”，这一消息可以用$k_a$加密并认证。中心接收到这条消息以后，会随机生成一个临时密钥$k$，分别发送给$a$和$b$（这个过程分别用$k_a$和$k_b$加密并认证），于是$a$和$b$就拥有了一个临时的共同密钥$k$——也就是一个临时的私钥。这个临时私钥通常称为会话密钥(session key)。$a$和$b$可以用会话密钥实现安全通信，在会话结束以后销毁会话密钥，每当再次需要通信时就再次向中心获取会话密钥。所以我们把这个中心服务器称为“密钥分发中心(Key Distribution Center, KDC)”。相比于两两储存私钥的算法，这个算法有很大的优势：每个用户只需保存一个和KDC通信的密钥；如果这个团队有新成员加入，其他用户并不会受到影响，只需要中心为新用户生成新密钥。

通过KDC的方案，我们避免了用户两两间储存特定的私钥，而是让私钥由一个“中心”来临时生成。而这建立在用户与中心间能够安全通信的假设之上。事实上这一点依然是难以保证的，例如在互联网上任何通信都可能被监听或篡改，以致于“能够和中心安全通信”也是无法保证的。能否在一个完全公开的通信环境下，实现临时私钥的分配呢？长期以来，这被认为是不可能的，因为这将意味着两个人可以在事先没有约定任何对外保密信息的情况下实现加密通信。直到1976年，Diffie与Hellman提出了第一个解决方案，开启了“公钥加密”这一全新的密码学领域。

传统的私钥加密方法中，通信双方是完全对称的：他们掌握相同的私钥，掌握相同的加密算法和解密算法，任何一方都可以作为发送方发起通信。换言之，这是一种对称的物理现象。然而人们逐渐意识到，很多物理现象并不是对称的。例如我们可以正向转动门锁把门关上，却不能反向转动门锁把门打开。存在一个高效的算法把两个质数相乘，但不存在一个同样高效的算法把一个大整数分解。公钥加密的提出，正是基于物理世界的非对称性。

Public Key-Exchange

我们定义一个Public Key-Exchange方案。也即，通信双方Alice和Bob想在完全公开的环境下约定一个密钥，并且防止窃听者获知这个密钥是什么。基本的setting是：Alice和Bob公开约定一个$n$，公开一个协议$\Pi$。一个协议是一套先后运行Alice和Bob计算机上的程序的方法，它能够确保最后Alice会得到一个key $k_A$，Bob会得到一个key $k_B$，满足$k_A=k_B$。因为我们总是要求这两个key是相等的，所以我们把key简记为$k$。窃听者如果无法以显著概率猜出$k$，这就是一个安全的Key-Exchange方案。

下面严格定义Key-Exchange方案的安全性：我们用experiment来定义，设敌手$\mathcal{A}$能监视Alice和Bob在协议$\Pi$执行期间互相发送的所有通信内容；我们给敌手一个$\hat k$，$\hat k$有$1/2$的概率是Alice和Bob最终生成的密钥$k$，有$1/2$的概率是一个纯随机的串；敌手给出一个猜测$b$，如果敌手猜中密钥而不是随机串，就称敌手成功；如果任何敌手成功的概率都满足$\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1]\leq 1/2+\text{negl}$，就称该方案是KE-secure的。

有了一个安全的Key-Exchange方案以后，就可以基于生成的密钥进行私钥加密和私钥认证。换言之，原先的所有私钥方案中，提前约定密钥的操作都可以替换为以上Key-Exchange方案，而依然保证安全性（这一点需要严格证明，按定义证即可，应该不难）。也就是说，基于Key-Exchange我们可以最终实现“两个人可以在事先没有约定任何对外保密信息的情况下实现加密通信”。

The Diffie–Hellman Key-Exchange Protocol

如何设计一个KE-secure的方案呢？在私钥加密中，方案的安全性往往建立在一些基本假设上，比如伪随机生成器存在和伪随机函数存在。在public情形下，我们也有这样一些基本假设，比如质因数分解没有多项式算法，对一些特殊的群离散对数没有多项式算法等等。最早的对Key-Exchange Protocol的安全构造来自Diffie与Hellman，这一方案是基于离散对数的。

离散对数问题(discrete-logarithm problem)是指，对于一个给定的循环群$G$，已知$G$的大小$|G|=q$，$G$的生成元为$g$（也即$\lang g\rang=G$），现在对于任意的输入$h\in G$，我们想求出$h$在循环群里的order $y$，也即要求出$y$使得$g^y=h$。记$y=\log_g h$，称$y$是$h$关于$g$的离散对数。这正是因为，循环群是刻画指数运算的离散代数结构。

Diffie与Hellman注意到存在特殊的一些循环群，其中离散对数的计算对于多项式敌手来说是困难的。具体的，对于某个精心构造的循环群$G=\lang g\rang$，取$h_1,h_2\in G$，定义$DH_g(h_1,h_2)=g^{\log _g h_1 \cdot \log_g h_2}$。计算意义下(computational)的Diffie-Hellman假设(CDH)是：任意多项式敌手在给定$h_1,h_2$时，能正确计算并输出$DH_g(h_1,h_2)$的值的概率不超过$\text{negl}$；判定意义下(decisional)的Diffie-Hellman假设(DDH)是：任意多项式敌手在给定$h_1,h_2$时，能正确分辨$DH_g(h_1,h_2)$与群中随机的某个元素$g^z$的概率不超过$1/2+\text{negl}$。注意，CDH假设和DDH假设并不等价，前者假设更强：如果CDH被攻破，那么DDH也一定能被攻破；反之，能构造出这样的循环群使得DDH能被攻破而CDH被认为是（在另外一些我们相信的假设下）依然无法攻破的。

基于DDH假设，Diffie与Hellman对$\Pi$的构造如下（注意因为现在发送方和接收方两人是不对称的，所以我们强调发送方是Alice，接收方是Bob）：输入$n$，在发送方Alice的设备上运行程序$\mathcal{G}(n)$，生成三元组$(G,q,g)$，分别代表循环群$G$，群的大小$q$和群的生成元$g$。它们都是以特定方式编码的二进制串（有限对象总是可以二进制编码的，既然描述清楚一个循环群只需要有限个汉字，那么一定只需要有限个二进制位就可以描述清楚$G$）。其中，保证$q$的二进制串长度为$n$。接下来，Alice在$\Z_q=\{0,1,\cdots,q-1\}$中随机选择一个整数$x$，计算出$h_A=g^x$，这一步只需要多项式时间（因为我们可以对指数用快速幂，而每次群元素相乘都是多项式的）。Alice把四元组$(G,q,g,h_A)$发送给Bob。Bob在接受到以后，也从$\Z_q$中随机选择一个整数$y$，求出$h_B=g^y$，然后把$h_B$发送给Alice。这之后的协议中，双方不再通信，Alice在本地求出$k_A=h_B^x$，Bob在本地求出$k_B=h_A^y$。显然有$k_A=k_B$，这就是协议生成的共同密钥。

下面我们证明，如果关于$G$的DDH假设成立，那么协议$\Pi$是KE-secure的。根据DDH假设，任意敌手$\mathcal{A}_0$，$|\Pr[\mathcal{A}_0(G,q,g,g^x,g^y,g^{xy})=1]$ $-\Pr[\mathcal{A}_0(G,q,g,g^x,g^y,g^z)=1]|$ $\leq 1/2+\text{negl}$。其中$g^z,z\leftarrow \Z_q$。在KE-secure的实验中，敌手$\mathcal{A}$会以$1/2$的概率得到$\hat k = g^{xy}$，以$1/2$的概率得到$\hat k = g^z$，因此$\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1]$ $=1/2\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1\mid \hat k = g^z]+$ $1/2\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1\mid \hat k = g^{xy}]$。其中，$\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1\mid \hat k = g^z]$ $=\Pr[\mathcal{A}(G,q,g,g^x,g^y,g^z)=0]=1-\Pr[\mathcal{A}(G,q,g,g^x,g^y,g^z)=1]$，又有$\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1\mid \hat k = g^{xy}]=\mathcal{A}(G,q,g,g^x,g^y,g^{xy})$。因此$\Pr[KE_{\mathcal{A},\Pi}^{eav}(n)=1]=1/2+1/2\left(\Pr[\mathcal{A}_0(G,q,g,g^x,g^y,g^z)=1]-\Pr[\mathcal{A}_0(G,q,g,g^x,g^y,g^{xy})=1]\right)$ $\leq 1/2+1/2\text{negl}$。证毕。

注意在KE-secure的定义中，我们要求敌手无法分辨密钥和一个随机串。而上面的证明由于是基于DDH假设，我们只能得到敌手无法分辨密钥和一个群中的随机元素。为了弥补这一点，我们可以让通信双方在计算得到密钥之后再套一层key-derivation函数，此处省略。

特殊循环群的构造

我们应该怎样构造特殊的循环群，使得离散对数问题是困难的呢？

。。。

公钥加密

Diffie-Hellman Protocal对于有篡改能力的敌手是完全不安全的，所以“公开生成密钥再套用私钥加密方案”这条路并不总是安全的，因为受到有篡改能力的敌手干扰，“公开生成密钥”这一行为不一定能得到实现。但是，人们基于与Diffie-Hellman类似的“非对称”的思想，找到了许多在公开环境下通信的安全方案。这开启了密码学的一个全新的时代——公钥加密。

这些全新的方案有如下的特征：当发送方Alice想要和接收方Bob通信时，Bob会生成两个密钥，一个称为公钥(public key) $k_p$，一个称为私钥(secret key) $k_s$；Bob把公钥$k_p$在公开信道上发送给Alice，这相当于把公钥像全世界公开；Alice用公钥加密自己要发送的信息；Bob接受到以后，用$k_s$解密。由此可见，尽管全世界都可以用公钥做加密然后发消息给Bob，但因为只有Bob有私钥，所以只有Bob一人知道如何解密，连Alice也不知道！也就是说，Bob无法安全地发消息给Alice，公钥加密实现的信道是单向的。所以我们也把公钥加密称为非对称加密，把私钥加密称为对称加密。

这样，我们可以像私钥加密一样，把一个公钥加密方案也看作一个三元组$(\text{Gen},\text{Enc},\text{Dec})$。$\text{Gen}(n)$输出$(k_p,k_s)$，$\text{Enc}_{k_p}(m)=c$，$\text{Dec}_{k_s}(c)=m$。在公钥加密中，我们允许$\text{Dec}_{k_s}(\text{Enc}_{k_p}(m))=m$这一等式在negligible的概率下出错（因为我们可能会要选取一个质数，但我们可能会有小概率选到一个合数等等）。从下面开始除非特殊说明，我们假定消息长度是固定的。

既然有了公钥加密方案，为什么还需要学习私钥加密方案呢？在实际中，虽然公钥加密方案理论上总是强于私钥加密方案，但它们往往在复杂性上大2~3个数量级。在保证同样安全性但更需要追求效率的情形下，往往还是需要私钥加密方案。

EAV-security & CPA-security

我们可以仿照私钥加密中EAV-security的定义，给出公钥加密方案的EAV-security定义。注意EAV-security是指敌手在窃听恰好一条密文的情况下能否破译的安全性。很自然地，EAV-security的实验应当定义如下：

输入$n$，运行$\text{Gen}(n)$得到$(p_k,p_s)$。对于敌手$\mathcal{A}$，把公钥交给它$p_k$，敌手基于公钥输出两个等长的明文$m_0,m_1$；我们选择其一做加密$c=\text{Enc}_{p_k}(m_b)$，并把$c$交给$\mathcal{A}$；$\mathcal{A}$需要输出他的判断，如果判断正确就称$\mathcal{A}$成功。如果任意PPT敌手$\mathcal{A}$成功的概率都不超过$1/2+\text{negl}$，就称这一方案是EAV-secure的。

我们注意到，以上实验中最重要的一点就是我们把公钥交给了敌手。这对应于现实中，公钥是对于敌手公开的。有了公钥，敌手其实就就相当于拥有了访问加密oracle的能力，因为公钥加密本身就假定所有敌手都有加密消息的能力。换言之，以上定义的EAV-security中的敌手本身就具有选择明文攻击的能力！所以我们得到，在公钥加密中，EAV-security等价于CPA-security。

既然确定性加密算法不可能是CPA-secure的（显而易见这一点对于公钥情形也是成立的），这意味着确定性算法也不可能是EAV-secure的。

这也意味着，在公钥加密中不存在一个像one-time-pad那样信息论意义安全的方案，因为既然敌手有能力做选择明文攻击，如果它的算力没有上限它总可以穷举所有明文对应的所有密文从而攻破任何加密方案。

El Gamal Encryption

下面我们来构造一个CPA-secure的公钥加密方案El Gamal Encryption，它同样是基于离散对数的。我们可以把这一方案看作是对Diffie–Hellman Key-Exchange Protocol的一个改造。

输入$n$，$\text{Gen}(n)$首先生成一个循环群$G$，群的大小$q$和生成元$g$，接着均匀随机选取$x \in \Z_q$，计算得到$h=g^x$，输出$(G,q,g,h)$作为公钥$k_p$，输出$(G,q,g,x)$作为私钥$k_s$（注意，我们认为群$G$本身就是整个消息空间）；给定公钥$k_p$和消息$m\in G$，$\text{Enc}$会均匀随机生成$y\in \Z_q$，生成密文$c=(g^y,h^y\cdot m)$；输入密文$(c_1,c_2)$，利用私钥中的$x$可以做解密$\text{Dec}_{k_s}(c)=c_2\cdot (c_1^x)^{-1}=h^y\cdot m\cdot g^{-xy}=m$。

下面我们证明，如果DDH假设关于$G$成立，那么以上构造方案$\Pi$是CPA-secure的。假设$\Pi$不是CPA-secure的，那么存在一个敌手$\mathcal{A}$能攻破$\Pi$，那么我们可以基于$\mathcal{A}$构造一个敌手$\mathcal{A}_0$使得DDH假设关于$G$不成立：在DDH假设的实验中，$\mathcal{A}_0$会被给定输入$(G,q,g,h_1,h_2,h_3)$，其中$h_1=g^x,h_2=g^y,h_3=g^z$或$g^{xy}$，这里$x,y,z$都是随机的；于是，我们在$\mathcal{A}$的CPA实验中把$(G,q,g,h_1)$当作公钥交给$\mathcal{A}$，$\mathcal{A}$会输出$m_0,m_1$作为challenge，那么我们随机一个$b\in \{0,1\}$，令$c_1=h_2,c_2=h_3\cdot m_b$；把$(c_1,c_2)$返回给$\mathcal{A}$；如果$\mathcal{A}$猜对，$\mathcal{A}_0$就返回$h_3=g^{xy}$；否则返回$h_3=g^z$。我们来分析上面的$\mathcal{A}_0$：如果$h_3=g^z$，那么对$\mathcal{A}$来说它总是得到密文$(g^y,g^z\cdot m_b)$，也即它总是得到群中随机的两个元素作为密文，没有包含任何有关消息的信息，因此成功的概率一定恰好为$1/2$；如果$h_3=g^{xy}$，那么对$\mathcal{A}$来说$\mathcal{A}_0$完美地模拟了实际实验中的情况，因此根据假设它有超过$1/2+\text{negl}$的概率攻破。那么综上，$\mathcal{A}_0$也恰好有$>1/2\cdot 1/2+1/2(1/2+\text{negl})=1/2+\text{negl}$的概率进行分辨，因此DDH假设不成立。

值得一提的是，我们发现El Gamal Encryption有下面这样一个加密上的同态性质(homomorphic property)：设$\text{Enc}_{k_p}(m_1)=c_1=(g^{y_1},h^{y_1}m_1)$，$\text{Enc}_{k_p}(m_2)=c_2=(g^{y_2},h^{y_2}m_2)$，那么有$\text{Dec}_{k_s}(c_1c_2)=\text{Dec}_{k_s}((g^{y_1+y_2},$ $h^{y_1+y_2}m_1m_2))$ $=m_1m_2$。换言之，在密文和解密后的明文上该方案有保乘法运算的性质。所以我们称El Gamal方案是乘法同态加密算法。它可以在我们委托第三方对数据做乘法运算时起到保密数据的作用（比如云端的大模型等等）。同样的，如果有加法同态加密算法，就可以委托第三方做加法运算。如果对于任意函数都满足同态性质，就称这是个全同态(full homomorphic)加密算法，可以委托给第三方做任何运算。

CCA-security

同样的，我们可以仿照私钥加密的情形定义公钥加密的CCA-security：

输入$n$，运行$\text{Gen}(n)$得到$(p_k,p_s)$。对于敌手$\mathcal{A}$，把公钥$p_k$交给它；敌手全程可以访问解密oracle多项式次；敌手输出两个等长的明文$m_0,m_1$；我们选择其一做加密$c=\text{Enc}_{p_k}(m_b)$，并把$c$交给$\mathcal{A}$；$\mathcal{A}$需要输出他的判断，如果判断正确就称$\mathcal{A}$成功。如果任意PPT敌手$\mathcal{A}$成功的概率都不超过$1/2+\text{negl}$，就称这一方案是CCA-secure的。