-
本节学习基于循环群上离散对数问题的DH问题及Elgamal加密方案。
-
目录：循环群与离散对数，DH假设和应用，Elgamal加密方案。
-
循环群（Cyclic Groups）与生成元（Generators）
-
$\mathbb{G}$ 是一个群并且一个元素$g \in \mathbb{G}$ 通过运算生成一个子群 $ \langle g \rangle \overset{\text{def}}{=} { g^0,g^1,\dotsc,} = { g^0,g^1,\dotsc, g^{i-1}}$。 -
$g$ 的阶是最小的正整数$i$ 令$g^i=1$ 。 -
$\mathbb{G}$ 是一个循环群（cyclic group）如果$\exists;g$ 有阶$m = |\mathbb{G}|$ .$\langle g \rangle = \mathbb{G}$ ,$g$ 是$\mathbb{G}$ 的生成元。注：循环群中存在一个元素通过指数运算可生成整个群中每个元素。 - 例题： 乘法下的$\mathbb{Z}_6^$, $\mathbb{Z}_7^
$,或 $ \mathbb{Z}_8^*$ 是循环群吗? 找到生成元。
-
-
离散对数
- 如果
$\mathbb{G}$ 是阶为$q$ 的循环群，那么$\exists$ 生成元$g \in \mathbb{G}$ 使得${ g^0,g^1,\dotsc,g^{q-1}} = \mathbb{G}$ 。 -
$\forall h \in \mathbb{G}$ ,$\exists$ 唯一的$x \in \mathbb{Z}_q$ 使得$g^x = h$ 。 -
$x= \log_gh$ 是以$g$为底$h$的离散对数（discrete logarithm）。 - 如果
$g^{x'}=h$ , 那么$\log_gh = [x' \bmod q]$ 。 -
$\log_g1=0$ 并且$\log_g(h_1\cdot h_2) = [(\log_gh_1+\log_gh_2) \bmod q]$ 。
- 如果
-
离散对数算法概览
- 给定一个生成元
$g \in \mathbb{G}$ 并且$y \in \langle g \rangle$ ，求$x$ 使得$g^x=y$ . - 蛮力：
$\mathcal{O}(q)$ ,$q = \mathsf{ord}(g)$ 是$\langle g\rangle$ 的阶。 - Baby-step/giant-step [Shanks]:
$\mathcal{O}(\sqrt{q}\cdot \mathsf{polylog}(q))$ . - Pohlig-Hellman算法：当
$q$ 有较小因子。 - Index calculus 法:
$\mathcal{O}(\exp{(\sqrt{n\cdot \log n})})$ . - 已知最好的算法是通用数域筛法：$\mathcal{O}(\exp(n^{1/3}\cdot(\log n)^{2/3}))$.
- 椭圆曲线群 vs. $\mathbb{Z}_p^$: 在保证安全性相同的同时，更高效。(1024-bit $\mathbb{Z}_p^$ 和 132-bit 椭圆曲线都需要
$2^{66}$ 步来破解。)
- 给定一个生成元
-
使用质数阶群
- 定理：如果
$\mathbb{G}$ 是质数阶，那么$\mathbb{G}$ 是循环群。除单位元外，所有$g \in \mathbb{G}$ 是生成元。 - 根据拉格朗日定理，任意元素的阶都等于群的阶。
-
拉格朗日定理：子群阶可以整除群阶。$\langle g \rangle$ 是
$\mathbb{G}$ 子群，并且$|\langle g \rangle| \mid |\mathbb{G}|$ 。- 思路：由一个子群可以派生覆盖了整个群的若干子集，这些子集的阶与子群相同，并且这些子集彼此不相交。
- 设群$\mathbb{G}$的子群$H$，陪集（coset）$gH$（$g$和$H$中每个元素$h$运算构成的集合）和子群$H$的阶相同。
- 子群的任意两个陪集$g_1H$和$g_2H$。
- 或者相同，如果$g_1^{-1}g_2 \in H$。$g_1(g_1^{-1}g_2 )h \in g_1H$，$g_2h \in g_1H$。
- 或者没有交集，如果$g_1^{-1}g_2 \notin H$。采用反证法，如果有交集，则$g_1h_1 = g_2h_2$，$g_1^{-1}g_2 = h_1h_2^{-1} \in H$，矛盾。
- 因此，群可以划分为任意子群的若干不相交陪集，每个陪集阶相同，群的阶就是子群的整数倍。
- 推荐参考：https://brilliant.org/wiki/lagranges-theorem/
- 离散对数问题在质数阶群上是最难的。
- 在质数阶群上找一个生成元很简单。
- 任何非零指数在以质数阶为模下都可逆。
- DDH问题是难题的必要条件是
$\mathsf{DH}_g(h_1,h_2)$ 与群中随机元素之间是不可区分的。在质数阶群上这基本成立。
- 定理：如果
-
产生质数阶（子）群
- 如果
$p$ 是质数，那么$\mathbb{Z}^*_p$ 是循环群。注：。 - $y \in \mathbb{Z}^_p$ 是模$p$下的二次剩余（quadratic residue modulo），如果 $\exists x \in \mathbb{Z}^_p$ 使得
$x^2 \equiv y \pmod p$ - 例题：$\mathbb{Z}_{7}^{*}$ 下的二次剩余？
- QR集合是一个子群（满足群条件），阶为
$(p-1)/2$ ，因为$x^2 \equiv (p-x)^2 \pmod p$ 。 -
$p$ 是一个强质数（strong prime），如果$p=2q+1$ 且$q$ 是质数。 - 强质数下的二次剩余子群是一个循环群，因为群的阶是质数。
- 循环群生成算法：产生一个强质数$p$，阶为$q=(p-1)/2$，随机选择一个$x \in \mathbb{Z}^*_p$，得到生成元$g=x^2$，输出$p, q, g$。
- 如果
-
离散对数假设
- 离散对数（discrete logarithm）实验
$\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n)$ :- 运行一个群生成算法
$\mathcal{G}(1^n)$ 来产生$(\mathbb{G},q,g)$ ，其中$\mathbb{G}$ 是阶为$q$ ($|q|=n$ ) 的循环群，并且$g$ 是$\mathbb{G}$ 的生成元。 - 挑选一个
$h \gets \mathbb{G}$ . ($x' \gets \mathbb{Z}_q$ and$h := g^{x'}$ ) - 敌手
$\mathcal{A}$ 给定$\mathbb{G}, q, g, h$ ，并且输出$x \in \mathbb{Z}_q$ . - 实验成功
$\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n) = 1$ ，如果$g^x = h$ , 否则 0 。
- 运行一个群生成算法
- 定义：离散对数问题相对于群$\mathcal{G}$是难的，如果
$\forall$ ppt 算法$\mathcal{A}$ ,$\exists$ $\mathsf{negl}$ 使得 $ \Pr[\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n)=1] \le \mathsf{negl}(n).$
- 离散对数（discrete logarithm）实验
-
DH假设
- 计算性DH（Computational Diffie-Hellman, CDH）问题：$ \mathsf{DH}_g(h_1,h_2) \overset{\text{def}}{=} g^{\log_gh_1\cdot \log_gh_2} $
- 判断性DH（Decisional Diffie-Hellman, DDH)）问题：区分
$\mathsf{DH}_g(h_1,h_2)$ 与一个随机的群元素$h'$ . - 定义：DDH问题与$\mathcal{G}$相关的是难的，如果
$\forall$ ppt$\mathcal{A}$ ,$\exists$ $\mathsf{negl}$ 使得 $ |\Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^z)=1] - \Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]|\le \mathsf{negl}(n). $ - DL, CDH 和 DDH 的难解性：DDH 比 CDH 和 DL 容易。
-
安全密钥交换实验
-
密钥交换实验（key-exchange experiment）
$\mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)$ :- 双方持有安全参数
$1^n$ 执行协议$\Pi$ 。$\Pi$ 执行的结果为对话记录 (transcript)$\mathsf{trans}$ 包含双方发送的所有消息，以及各方都输出的密钥$k$ 。 - 选择一个随机比特
$b \gets {0,1}$ 。 如果$b=0$ 那么选择$\hat{k} \gets {0,1}^n$ u.a.r；如果$b=1$ 那么令$\hat{k} :=k$ 。 - 敌手
$\mathcal{A}$ 给定$\mathsf{trans}$ 和$\hat{k}$ , 并且输出一个比特$b'$ 。 -
$\mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1$ 如果$b'=b$ ， 否则 0 。
- 双方持有安全参数
-
定义：一个密钥交换协议
$\Pi$ 在出现窃听者攻击下是安全的，如果$\forall$ ppt$\mathcal{A}$ ,$\exists$ $\mathsf{negl}$ 使得$ \Pr[\mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n) = 1] < \frac{1}{2} + \mathsf{negl}(n). $
-
-
DH密钥交换协议
-
$\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$ 表示一个实验，其中如果$b=0$ ，敌手被给予$\hat{k} \gets \mathbb{G}$ 。 - 定理：如果DDH问题与$\mathcal{G}$相关是难的，那么DH 密钥交换协议
$\Pi$ 在出现窃听者时是安全的 (对应改动的实验$\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$ )。 - 不安全性：在主动的敌手，中间人，攻击下是不安全的 (Man-In-The-Middle)。敌手在中间与双方分别通信，通信双方无法发现在与敌手通信，敌手可以与双方分别协商出密钥。
-
-
证明
- $\Pr \left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}{\mathcal{A},\Pi} =1\right] $ $= \frac{1}{2}\cdot \Pr\left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}{\mathcal{A},\Pi} =1 | b=1\right] + \frac{1}{2}\cdot \Pr\left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi} =1 | b=0\right] $
- 如果
$b=1$ , 那么给真密钥；否则给随机的$g^z$ . $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] + \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=0 \right] $ $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] + \frac{1}{2}\cdot (1-\Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right]) $ $= \frac{1}{2} + \frac{1}{2}\cdot \left( \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right] \right) $ - $ \le \frac{1}{2} + \frac{1}{2}\cdot \mathsf{negl}(n) %\left| \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right] \right| $
-
DHKE例子
-
$\mathbb{G} = \mathbb{Z}^*_{11}$ ；群的阶$q = ?$ - 二次剩余子群 ?
-
$g = 3$ 是生成元吗？ - 如果
$x = 3$ 且$y = 4$ ，Bob发给Alice消息是？ - Alice 如何计算密钥？
- Bob 如何计算密钥？
-
-
三方密钥交换
- DH基于的KE在2轮实现三方密钥交换，Key$=g^{abc}$。
- Joux's KE 在 1 轮实现三方密钥交换。在 bilinear map中，Key$=e(P,P)^{abc}$ 。
- 开放问题：如何在一轮中在4方之间交换密钥？
-
完美保密私钥加密引理
- 引理：$\mathbb{G}$ 是有限群并且
$m\in \mathbb{G}$ 是任意元素。那么选择随机$k \gets \mathbb{G}$ 并令$c := m\cdot k$ ，将得到与随机选择的$c \gets \mathbb{G}$ 相同的分布，即$\forall g \in \mathbb{G}$ : $ \Pr[m\cdot k = g] = 1/|\mathbb{G}| $。 - 证明：$g \in \mathbb{G}$ 是任意的，那么
$\Pr[m\cdot k = g] = \Pr[k = m^{-1}\cdot g] $ 。由于$k$ 均匀随机选择，选择$k$ 的概率与一个固定元素$m^{-1}\cdot g$ 相同，都是$1/|\mathbb{G}$ |。 - 注：这是一种完美保密的私钥加密方案，将一个元素（明文）与另一个元素（密钥）的运算得到第三个元素（密文），与之前一个字母的移位密码是完美保密是类似的。
- 引理：$\mathbb{G}$ 是有限群并且
-
Elgamal加密方案
- 一个算法
$\mathcal{G}$ , 输入$1^n$ , 输出一个循环群$\mathbb{G}$ , 其阶为$q$ ($|q| = n$ ), 并且生成元为$g$ 。 - 构造：
-
$\mathsf{Gen}$ : 运行$\mathcal{G}(1^n)$ 来产生$(\mathbb{G},q,g)$ 。一个随机的$x \gets \mathbb{Z}_q$ 和$h := g^x$ 。$pk = \langle \mathbb{G},q,g,h \rangle$ 并且$sk = \langle \mathbb{G},q,g,x \rangle$ 。 -
$\mathsf{Enc}$ : 一个随机$y \gets \mathbb{Z}_q$ 并且输入$\langle c_1, c_2 \rangle = \langle g^y, h^y\cdot m\rangle$ 。 -
$\mathsf{Dec}$ :$m:=c_2/c_1^x$ 。
-
- 定理：如果DDH问题与$\mathcal{G}$相关是难的，那么Elgamal加密方案是CPA安全。
- 一个算法
-
Elgamal加密例子
- 加密前首先对明文进行二进制串编码：
- 在模一个强质数
$p = (2q+1)$ 的二次剩余子群中， - 一个串
$\hat{m} \in {0,1}^{n-1}$ ,$n = |q|$ 。 - 将
$\hat{m}$ 映射到被加密的明文$m = [(\hat{m}+1)^2 \bmod p]$ 。- 这里的加1是为了保证在消息为“0”时，明文也在这个乘法群里
- 映射是一对一且可逆的。
- 在模一个强质数
- 例子，略。
- 加密前首先对明文进行二进制串编码：
-
证明
- 思路：通过将DDH问题的算法$D$规约到窃听者算法$\mathcal{A}$来证明
$\Pi$ 在窃听者出现时是安全的。 - 将
$\Pi$ 改造为$\tilde{\Pi}$ ： 加密是通过随机选择的$y \gets \mathbb{Z}_q$ 和$z \gets \mathbb{Z}_q$ 然后输出密文：$ \langle g^y, g^z\cdot m\rangle$。 -
$\tilde{\Pi}$ 不是一个加密方案. -
$g^y$ 独立于$m$ 。 -
$g^z\cdot m$ 是独立于$m$ 的随机元素 (之前的私钥加密引理)。 - 实验成功概率与完美保密加密方案中是相同的。
$\Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1\right] = \frac{1}{2}.$
- 思路：通过将DDH问题的算法$D$规约到窃听者算法$\mathcal{A}$来证明
-
证明（续一）
- 将DDH问题的算法$D$规约到窃听者算法$\mathcal{A}$。
-
证明（续二）
-
情况1:
$g_3 = g^z$ , 密文是$\langle g^y, g^z\cdot m_b\rangle$ .$ \Pr[D(g^x,g^y,g^z)=1] = \Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1\right] = \frac{1}{2}. $
-
情况2:
$g_3 = g^{xy}$ , 密文是$\langle g^y, g^{xy}\cdot m_b\rangle$ .$ \Pr[D(g^x,g^y,g^{xy})=1] = \Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1\right] = \varepsilon(n). $
-
由于DDH问题是难的，
$ \mathsf{negl}(n) \ge |\Pr[D(g^x,g^y,g^z)=1] - \Pr[D(g^x,g^y,g^{xy})=1]| =|\frac{1}{2}-\varepsilon(n)|. $
-
-
Elgamal加密中CCA
- Elgamal不是CCA安全的。
- 例题：构造明文
$m\cdot m'$ 的密文。- 给定
$pk=\langle g, h\rangle$ ,$c = \langle c_1, c_2\rangle$ ,$c_1=g^y$ ,$c_2=h^y\cdot m$ , - 方法1：计算
$c_2' := c_2\cdot m'$ , 和$c' = \langle c_1, c_2'\rangle$ . $ \frac{c_2'}{c_1^x} = ? $ - 方法2：计算
$c_1'' := c_1\cdot g^{y''}$ , 和$c_2'' := c_2\cdot h^{y''}\cdot m'$ 。- $ c_1''=g^y\cdot g^{y''} = g^{y+y''};\text{and}; c_2''= ? $
- 所以
$c''=\langle c_1'',c_2''\rangle$ 是$m\cdot m'$ 的密文。
- 给定
-
Elgamal实现问题
- 共享公开参数：$\mathcal{G}$ 产生参数
$\mathbb{G},q,g$ 。- 这些参数可以只产生一次并且为所有人所使用（ ``once-and-for-all''）。
- 可以被多个接收者使用。
- 每个接收者必须选择各自的保密数值
$x$ 并且发布他们自己的公钥包含$h=g^x$ 。
- 参数共享：在 Elgamal 的情况下，公开参数可以被共享。在 RSA 情况下，参数可以被共享吗？
- 共享公开参数：$\mathcal{G}$ 产生参数
-
椭圆曲线密码学
- 在椭圆曲线群上构造的离散对数问题
- 其他密码学上的应用在1985年被提出
- 类比离散对数，DH密钥交换，ElGamal加密和DSA，在椭圆曲线上有，ECDL，ECDHKE，ElGamal ECC，ECDSA
- 比自然数域上更有效，密钥长度是所需蛮力搜索指数长度的二倍。
- 二倍的原因是，离散对数问题的蛮力搜索所需指数长度是群阶指数长度的一半
-
椭圆曲线群
- 椭圆曲线群是在一个有限域中的一个平面代数曲线上的点之间“加法”操作
- 在有限域中取模是关键，单位元是无穷远点
-
在椭圆曲线点上做加法构成循环群
- 每条直线和曲线有三个交点
- 一条直线与曲线的切点算2次
- 垂直线上，无穷远点计做一个点
- 点上的加法
- 三点成一线，三点之和为无穷远点
- 密钥生成
- 私钥是$d$，公钥为$dP$
- 每条直线和曲线有三个交点
-
ECDHKE的一个例子
- 计算ECDHKE的密钥，这里枚举了生成元为（3，4）的所有指数结果
- 密钥计算是从（7，6）开始，向后数5个点
-
实践中的椭圆曲线密码系统
- P256有一定风险，Curve25519更安全高效
-
总结
- DHKE，ElGamal加密来自于CDH，DDH问题，后者来自于在指数阶群上的离散对数问题
- 椭圆曲线密码学更有效并且被广泛使用