【浅谈系列】混合加密

5 minute read

Published:

Hybrid Encryption 混合加密。

理论密码学课程报告,顺便水一篇博客。大部分内容教科书上都有,简单介绍一些概念和证明。

0. 参考资料

1. 基本概念

本部分给出基本概念的定义,相关证明详见教科书。

  • 语义安全

    语义安全就是指在计算意义下由密文得不到明文任何额外信息。

    • 私钥加密方案

      私钥加密方案 $\Pi = (Gen,Enc,Dec)$ 称为语义安全,如果对任意 $PPT$ 算法 $\mathcal{A}$,存在 $PPT$ 算法 $\mathcal{A}^{\prime}$,使得对任意概率总体 $\lbrace X_{\lambda} \rbrace_{\lambda \in \mathbb{N}}$,任意多项式有界函数 $f_{\lambda}(\cdot)$,$h_{\lambda}(\cdot): \lbrace 0,1 \rbrace ^{\ast} \rightarrow \lbrace 0,1 \rbrace ^{\ast}$,以及任意多项式 $p(\cdot)$,下式对充分大的 $\lambda$ 成立。

      \[\text{Pr}[\mathcal{A}(1^{\lambda}, Enc_{Gen_1(1^{\lambda})}(X_{\lambda}), 1^{\mid X_{\lambda} \mid}, h_{\lambda}(1^{\lambda},X_{\lambda})) = f_{\lambda}(1^{\lambda},X_{\lambda})] \\ \leq \text{Pr}[\mathcal{A}(1^{\lambda}, 1^{\mid X_{\lambda} \mid}, h_{\lambda}(1^{\lambda},X_{\lambda})) = f_{\lambda}(1^{\lambda},X_{\lambda})] + \frac{1}{p(\lambda)}\]

      注:其中概率关于 $X_{\lambda}$ 以及算法 $Gen,Enc$ 和 $\mathcal{A},\mathcal{A^{\prime}}$ 的内部投币。函数 $h_{\lambda},f_{\lambda}$ 不一定可有效计算。$h_{\lambda}(1^{\lambda},X_{\lambda})$ 表示关于明文的先验信息,$f_{\lambda}(1^{\lambda},X_{\lambda})$ 表示敌手想获取的信息(攻击目标)。

    • 公钥加密方案

      公钥加密方案 $\Pi = (Gen,Enc,Dec)$ 称为语义安全,如果对任意 $PPT$ 算法 $\mathcal{A}$,存在 $PPT$ 算法 $\mathcal{A}^{\prime}$,使得对任意概率总体 $\lbrace X_{\lambda} \rbrace_{\lambda \in \mathbb{N}}$,任意多项式有界函数 $f_{\lambda}(\cdot)$,$h_{\lambda}(\cdot): \lbrace 0,1 \rbrace ^{\ast} \rightarrow \lbrace 0,1 \rbrace ^{\ast}$,以及任意多项式 $p(\cdot)$,下式对无穷多个 $\lambda$ 成立。

      \[\text{Pr}[\mathcal{A}(1^{\lambda}, Gen_1(1^{\lambda},) Enc_{Gen_1(1^{\lambda})}(X_{\lambda}), 1^{\mid X_{\lambda} \mid}, h_{\lambda}(1^{\lambda},X_{\lambda})) = f_{\lambda}(1^{\lambda},X_{\lambda})] \\ \leq \text{Pr}[\mathcal{A}(1^{\lambda}, Gen_1(1^{\lambda},) 1^{\mid X_{\lambda} \mid}, h_{\lambda}(1^{\lambda},X_{\lambda})) = f_{\lambda}(1^{\lambda},X_{\lambda})] + \frac{1}{p(\lambda)}\]

      注:其中概率关于 $X_{\lambda}$ 以及算法 $Gen,Enc$ 和 $\mathcal{A},\mathcal{A^{\prime}}$ 的内部投币。

  • IND 不可区分安全

    若加密方案绝对安全,则密文在密文空间上的分布与明文完全独立,因此,不同明文的密文是计算不可区分的。

    • 私钥加密方案

      私钥加密方案 $\Pi = (Gen,Enc,Dec)$ 称为是密文不可区分安全的,如果对任意多项式规模电路组 ${\lbrace C_{\lambda} \rbrace}_{\lambda \in \mathbb{N}}$ 和任意多项式 $l(\cdot), p(\cdot)$,对充分大的 $\lambda$ 与任意 $x,y \in \lbrace 0,1 \rbrace^{l(\lambda)}$,有

      \[\mid \text{Pr}[C_{\lambda}(Enc_{Gen_1(1^{\lambda})}(x)) = 1] - \text{Pr}[C_{\lambda}(Enc_{Gen_1(1^{\lambda})}(y)) = 1] \mid < \frac{1}{p(\lambda)}\]

      这里的概率是关于算法 $Gen,Enc$ 的内部投币。

      用电路族定义得到的不可区分性是非一致不可区分性,若敌手改用 $PPT$ 算法 $\mathcal{A}$ 来表示,则不等式写为

      \[\mid \text{Pr}[\mathcal{A}(1^{\lambda}, Enc_{Gen_1(1^{\lambda})}(x), x, y) = 1] - \text{Pr}[\mathcal{A}(1^{\lambda}, Enc_{Gen_1(1^{\lambda})}(y), x, y) = 1] \mid < \frac{1}{p(\lambda)}\]

      则得到的是私钥加密方案的一致不可区分性。

    • 公钥加密方案

      公钥加密方案 $\Pi = (Gen,Enc,Dec)$ 称为是密文不可区分安全的,如果对任意多项式规模电路组 ${\lbrace C_{\lambda} \rbrace}_{\lambda \in \mathbb{N}}$ 和任意多项式 $l(\cdot), p(\cdot)$,对充分大的 $\lambda$ 与任意 $x,y \in \lbrace 0,1 \rbrace^{l(\lambda)}$,有

      \[\mid \text{Pr}[C_{\lambda}(Gen_1(1^{\lambda}), Enc_{Gen_1(1^{\lambda})}(x)) = 1] - \text{Pr}[Gen_1(1^{\lambda}), C_{\lambda}(Enc_{Gen_1(1^{\lambda})}(y)) = 1] \mid < \frac{1}{p(\lambda)}\]

      这里的概率是关于算法 $Gen,Enc$ 的内部投币。

      用电路族定义得到的不可区分性是非一致不可区分性,若敌手改用 $PPT$ 算法 $\mathcal{A}$ 来表示,则不等式写为

      \[\mid \text{Pr}[\mathcal{A}(1^{\lambda}, e, Enc_e(x), x, y) = 1] - \text{Pr}[\mathcal{A}(1^{\lambda}, e, Enc_e(y), x, y) = 1] \mid < \frac{1}{p(\lambda)}\]

      其中 $e = Gen_1(1^{\lambda})$,得到的是公钥方案的密文一致不可区分性。

  • Att 安全

    公私钥加密方案 $\Pi = (Gen,Enc,Dec)$ 是 Att-语义安全 的当且仅当 $\Pi$ 是 Att-不可区分安全 的。Att-不可区分安全 定义如下,语义安全可参考教科书类似定义。

    公私钥加密方案 $\Pi = (Gen,Enc,Dec)$ 是 IND-Att 安全的,也就是 Att-不可区分 的,其中 $Att \in \lbrace CPA,CCA1,CCA2 \rbrace$,如果对任意多项式时间的 Oracle 的敌手 $\mathcal{A} = (\mathcal{A_1},\mathcal{A_2})$ 及任意 $z \in \lbrace 0,1 \rbrace^{poly(\cdot)}$,其区分优势

    \[\begin{align} Adv_{\mathcal{A},\Pi}^{IND-Att}(\lambda) &= \lvert \underset{\mathcal{A},Gen,Enc}{\text{Pr}}[Expt_{\mathcal{A},\Pi,z}^{IND-Att}(1^{\lambda},0)=0] - \underset{\mathcal{A},Gen,Enc}{\text{Pr}}[Expt_{\mathcal{A},\Pi,z}^{IND-Att}(1^{\lambda},1)=0] \rvert \\ &= 2 \lvert \underset{\mathcal{A},Gen,Enc \\ b \leftarrow \lbrace 0,1 \rbrace}{\text{Pr}}[Expt_{\mathcal{A},\Pi,z}^{IND-Att}(1^{\lambda},b)=0] - \frac{1}{2} \rvert \end{align}\]

    是可以忽略的。

2. KEM/DEM

2.1 KEM

KEMKey-Encapsulation Mecahanism 的缩写,顾名思义,它就是一个对密钥进行加密的过程,而这个被加密的密钥之后会用于对明文的加密。和一般的公钥加密方案类似,KEM 包含三个算法,密钥生成、对之后要用的那个密钥加密、对该密钥解密,可以表示为 $(Gen,Encaps,Decaps)$。

KEM 的一般定义如下:

  • (Definition 1) 一个 KEM 由一系列多项式时间算法 $(Gen,Encaps,Decaps)$ 组成:

    • $Gen$:这个是密钥生成算法,和一般的公钥加密方案类似,输入是一个安全参数 $1^{n}$,输出是一对公私钥对 $(pk,sk)$。其中 $n$ 表示公私钥对长度至少为 $n$。

    • $Encaps$:这个是对后面要用的密钥进行加密的算法。后面用的新的密钥是随机生成的,而对它加密的则是我们之前生成的公私钥对。输入为公钥 $pk$ 和一个安全参数 $1^n$。输出为一个密文 $c$ 和一个密钥 $k \in \lbrace 0,1 \rbrace^{l(n)}$,其中 $l$ 表示密钥 $k$ 的长度。整个过程可以表示为 $(c,k) \longleftarrow Encaps(1^n)$。

    • $Decaps$:这个是之后对被加密的密钥解密,还原出密钥的算法。输入为之前生成的公私钥对中的私钥 $sk$ 和一个密文 $c$,然后输出一个密钥 $k$,如果解密失败,则用一个特殊的记号 $\bot$ 表示。这个过程可以表示为 $k:=Decaps_{sk}(c)$。

2.2 DEM

DEMdata-encapsulation mechanism 的缩写。顾名思义,它就是用对数据,也就是明文进行加密的那个部分。在混合加密中,它使用的加密密钥是前一部分的 KEM 所生成的那个 $k$。从一般的角度来看,DEM 就是一个一般的私钥加密方案,把明文加密成密文,发送给接收者。此外还要发送之前加密的密钥,也就是要发送 $(c,c^{SKE})$。

一般的私钥加密方案可以定义如下:

  • (Definition 2) 设 $\mathcal{F} = \lbrace F_n: \lbrace 0,1 \rbrace^n \times \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace^d \rbrace$ 为可有效计算的函数总体,函数抽样算法为 $I$,即对任意 $k \leftarrow I(1^n),f_k(\cdot) = f(k,\cdot):\lbrace 0,1 \rbrace^l \rightarrow \lbrace 0,1 \rbrace^d$,其中 $l,d$ 均为关于 $n$ 的多项式函数。以此构造私钥加密方案 $\Pi = (Gen,Enc,Dec)$,由三个多项式时间算法组成:

    • $Gen$:抽取函数 $k \leftarrow I(1^n)$,然后令 $Gen(1^n) = k$

    • $Enc$:对任意明文或消息 $x \in \lbrace 0,1 \rbrace^d$ 和 $Gen(1^n)=k$,随机选取 $r \in_R \lbrace 0,1 \rbrace^l$,令

      \[c = Enc_k(x) \overset{def}{=} (r,f_k(r) \bigoplus x)\]
    • $Dec$:对密文 $c=(r,y)$ 和密钥 $k$,令

      \[x^{\prime} = Dec_k(r,y) \overset{def}{=} f_k(r) \bigoplus y\]

若 $\mathcal{F}$ 是伪随机函数簇,则此私钥加密方案是多消息密文不可区分的。

3. Hybrid Encryption

3.1 简介

混合加密 Hybrid Encryption 是以上面所说的两个概念为基础的。什么是混合加密?简单来说,就是这个加密方案将一个公钥加密方案和一个私钥加密方案整合在一起,因此称为混合加密。密码学中这样的设计并不少见,比如认证加密 AE,就是将私钥加密方案和消息认证码整合在一起。

混合加密这样去整合一个公钥一个私钥方案,好处在于它综合了两者的优势,而一定程度上避免了两者的劣势。公钥方案 PKE 相比于私钥加密方案 SKE,无需安全的信道来传输密钥,它的密钥分发是非常有优势的,但同时,PKE 在计算开销和速度上远远不如 SKE,尤其是在一些轻量的场景下,使用公钥无异于杀鸡用牛刀。混合加密则恰好可以取长补短。

我们不妨将混合加密记作 Hyb。先给出它的一个简单实现如下。

  • (Definition 3) 混合加密简单实现如下:

    • $Gen^{Hyb}$:和 $Gen^{PKE}$ 一样

    • $Enc^{Hyb}$:首先 $Gen^{SKE}$ 均匀采样得到一个密钥 $k$,这个密钥经过 $Enc^{PKE}$ 用公钥 $pk$ 加密得到密文 $c^{PKE}$ 的第一部分。然后 $Enc^{SKE}$ 使用上一步的私钥 $k$ 加密明文消息 $m$,得到密文的第二部分。

    • $Dec^{Hyb}$:首先,使用 $Dec^{PKE}$ 和私钥 $sk$ 从密文 $c^{PKE}$ 第一部分中还原密钥 $k$。然后使用 $k$ 和 $Dec^{SKE}$ 对密文第二部分进行解密得到明文消息 $m$。

整个流程如下图所示。

上面这个简单实现共享 $k$ 是先均匀采样,再通过一个公钥加密方案对其加密。更直观的,我们可以将这两步整合为一步,也就是使用我们上一部分所说的 KEM/DEM。给出具体定义如下:

  • (Definition 4) 混合加密借助 KEM/DEM 实现如下:

    设 $\Pi = (Gen,Encaps,Decaps)$ 是一个密钥长度为 $n$ 的 KEM,设 $\Pi^{SKE}$ 是一个私钥加密方案。设一个混合加密方案为 $\Pi^{Hyb} = (Gen^{Hyb},Encaps^{Hyb},Decaps^{Hyb})$ 如下。

    • $Gen^{Hyb}$:输入为安全参数 $1^n$,运行 $Gen(1^n)$,得到输出一对公私钥对 $(pk,sk)$。

    • $Enc^{Hyb}$:输入为公钥 $pk$ 和明文消息 $m \in \lbrace 0,1 \rbrace^{\ast}$,执行如下步骤:

      计算 $(c,k) \leftarrow Encaps(1^n)$

      计算 $c^{SKE} \leftarrow Enc_k^{SKE}(m)$

      输出密文 $\langle c, c^{SKE} \rangle$

    • $Dec^{Hyb}$:输入为私钥 $sk$ 和一个密文 $\langle c,c^{SKE} \rangle$,执行如下步骤:

      计算 $k:=Decaps(c)$

      输出消息 $m:=Dec_k^{SKE}(c^{SKE})$

整个流程如下图所示。

3.2 效率

设 $\alpha,\beta$ 分别为使用 PKESKE 加密一比特消息的开销,其中 $\alpha$ 在数量级上高于 $\beta$。设混合加密方案的消息长度为 $\lvert m \rvert$,密钥长度为 $n$,那么使用混合加密加密一比特消息开销如下:

\[\text{cost}^{Hyb} = \frac{n \alpha + \lvert m \rvert \beta}{\lvert m \rvert} = \frac{n \alpha}{\lvert m \rvert} + \beta\]

因此,从上式不难看出,当消息明文足够长的时候,混合加密的开销和私钥加密方案几乎一样,但在密钥分发上又具备了公钥加密方案的优势。

4. 不可区分安全

加密方案的最基本目标是保护消息的私密性,可以用两种相互等价的方式表示,即语义安全与不可区分安全。不可区分性可以保证密文的机密性,但不能满足所有的安全需求,比如在某些场景如签名,敌手可能是要产生合法的密文,这就涉及到 2000 年提出的不可延展性的概念。

公钥加密的不可延展性与不可区分性有如下关系:

本文此处只讨论不可区分性。

4.1 IND-CPA

  • (Definition 5) KEMIND-CPA 实验可以定义如下:

    • 首先,运行 $Gen(1^n)$,获得密钥对 $(pk,sk)$。其次,运行 $Encaps_{pk}(1^n)$ 生成 $(c,k)$

    • 然后,均匀的选择一个比特 $b \in \lbrace 0,1 \rbrace$,如果 $b=0$,设置 $k^{\prime}:=k$,否则均匀随机选择一个 $k^{\prime} \in \lbrace 0,1 \rbrace^n$

    • 最后,把 $(pk,c,k^{\prime})$ 交给敌手 $\mathcal{A}$,敌手输出一比特 $b^{\prime}$,如果 $b^{\prime} = b$,实验成功输出 $1$,否则实验失败输出 $0$。

因此,根据这个实验,定义 KEM 的选择明文不可区分性如下:

  • (Definition 6) 一个 KEM $\Pi$ 是 IND-CPA 的,如果对于所有概率多项式时间的敌手 $\mathcal{A}$,存在一个可忽略的函数 $negl$ 满足

    \[\text{Pr}[KEM_{\mathcal{A},\Pi}^{IND-CPA}(n)=1] \leq \frac{1}{2} + negl(n)\]

根据以上定义,于是关于混合加密的选择明文不可区分性有定理如下:

  • (Theorem 1) 如果某个 KEM $\Pi$ 是 IND-CPA 的,且某个 SKE $\Pi^{SKE}$ 是密文不可区分的,那么由两者生成的混合加密方案 $\Pi^{Hyb}$ 是 IND-CPA 的。

4.2 简单证明

定理一证明如下:

为了方便表述,不妨假设 $X \equiv Y$ 表示不存在多项式时间的敌手可以区分两个分布 $X,Y$。设 $Encaps_{pk}^{(1)}(1^n),Encaps_{pk}^{(2)}(1^n)$ 分别表示 Encaps 输出的密文和密钥。于是我们就是要证明

\[(pk,Encaps_{pk}(1^n),Enc_k^{SKE}(m_0)) \equiv (pk,Encaps_{pk}(1^n),Enc_k^{SKE}(m_1))\]

证明思路分为如下三步:

  • 第一步,证明

    \[(pk,Encaps_{pk}^{(1)}(1^n),Enc_k^{SKE}(m_0)) \equiv (pk,Encaps_{pk}^{(1)}(1^n),Enc_{k^{\prime}}^{SKE}(m_0))\]

    这一步区别在于密钥,也就是公钥方案的输出之一,直接归约到 $\Pi$ 的 IND-CPA 即可。

  • 第二步,证明

    \[(pk,Encaps_{pk}^{(1)}(1^n),Enc_{k^{\prime}}^{SKE}(m_0)) \equiv (pk,Encaps_{pk}^{(1)}(1^n),Enc_{k^{\prime}}^{SKE}(m_1))\]

    这一步区别在于消息明文,归约到 $\Pi^{SKE}$ 的密文不可区分性即可。

  • 第三步,证明

    \[(pk,Encaps_{pk}^{(1)}(1^n),Enc_{k^{\prime}}^{SKE}(m_1)) \equiv (pk,Encaps_{pk}^{(1)}(1^n),Enc_k^{SKE}(m_1))\]

    这一步的证明和第一步完全一样。

因此,综上三个步骤,混合加密的 IND-CPA 可以证明。

4.3 IND-CCA

类似 IND-CPA,我们可以定义 KEMIND-CCA 实验如下:

  • (Definition 7) KEMIND-CCA 实验可以定义如下:

    • 首先,运行 $Gen(1^n)$,获得密钥对 $(pk,sk)$。运行 $Encaps_{pk}(1^n)$ 生成 $(c,k)$。

    • 其次,均匀的选择一个比特 $b \in \lbrace 0,1 \rbrace$,如果 $b=0$,设置 $k^{\prime}:=k$,否则均匀随机选择一个 $k^{\prime} \in \lbrace 0,1 \rbrace^n$

    • 然后,敌手被给予 $pk,c,k^{\prime}$,以及连接到 $Decaps_{sk}(\cdot)$ 的权限,除了 $c$ 以外的都可以进行解密询问。

    • 最后,敌手输出一比特 $b^{\prime}$,如果 $b^{\prime} = b$,实验成功输出 $1$,否则实验失败输出 $0$。

因此,根据这个实验,定义 KEM 的选择密文不可区分性如下:

  • (Definition 8) 一个 KEM $\Pi$ 是 IND-CCA 的,如果对于所有概率多项式时间的敌手 $\mathcal{A}$,存在一个可忽略的函数 $negl$ 满足

    \[\text{Pr}[KEM_{\mathcal{A},\Pi}^{IND-CCA}(n)=1] \leq \frac{1}{2} + negl(n)\]

根据以上定义,于是关于混合加密的选择密文不可区分性有定理如下:

  • (Theorem 2) 如果某个 KEM $\Pi$ 是 IND-CCA 的,且某个 SKE $\Pi^{SKE}$ 是 IND-CCA 的,那么由两者生成的混合加密方案 $\Pi^{Hyb}$ 是 IND-CCA 的。

这个定理是充分不必要的,也就是说,可能存在不满足 IND-CCA 的稍弱一些的 KEM,使得混合加密依然是 IND-CCA 的。

定理的证明和上面的 IND-CPA 类似,此处不赘述。

5. 实例:TLS 协议

传输层安全性协议,英文为 Transport Layer Security,缩写为 TLS,它是一种安全协议,目的是为网络通讯提供安全与资料完整性保障,也就是为通信的双方提供一个安全的通道。目前最新的版本是 TLS 1.3

协议主要由两个部分组成,握手部分和记录部分。握手部分主要处理在通信双方之间进行认证的所有流程,包括密钥协商、参数协商、建立共享密钥,它往往采用公钥方案来实现。记录部分使用由握手协议建立的参数来保护流量,它可以类似地看作一个私钥加密方案。

TLS 的完整握手流程如下图所示:

可以看到,握手的本质就是互相认证,然后交换密钥。而之后的通信都有交换的密钥来完成加密解密。因此,这很显然用了混合加密的技术,用公钥加密方案对通信的密钥进行加密并交换密钥,而后利用交换的密钥加密解密消息,完成通信,既有公钥方案密钥容易分发的好处,又享有私钥加密方案计算开销小,速度快的好处。


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.