8.3 DH问题与加密
-
本节学习基于循环群上离散对数问题的DH问题及Elgamal加密方案。
-
目录：循环群与离散对数，DH假设和应用，Elgamal加密方案。
-
循环群（Cyclic Groups）与生成元（Generators）
- G \mathbb{G} G 是一个群并且一个元素 g ∈ G g \in \mathbb{G} g∈G通过运算生成一个子群 $ \langle g \rangle \overset{\text{def}}{=} { g0,g1,\dotsc,} = { g0,g1,\dotsc, g^{i-1}}$。
- g g g 的阶是最小的正整数 i i i 令 g i = 1 g^i=1 gi=1。
- G \mathbb{G} G 是一个循环群（cyclic group）如果 ∃ g \exists\;g ∃g 有阶 m = ∣ G ∣ m = |\mathbb{G}| m=∣G∣. ⟨ g ⟩ = G \langle g \rangle = \mathbb{G} ⟨g⟩=G, g g g 是 G \mathbb{G} G 的生成元。注：循环群中存在一个元素通过指数运算可生成整个群中每个元素。
- 例题： 乘法下的 Z 6 ∗ \mathbb{Z}_6^* Z6∗, Z 7 ∗ \mathbb{Z}_7^* Z7∗,或 Z 8 ∗ \mathbb{Z}_8^* Z8∗ 是循环群吗? 找到生成元。
-
拉格朗日定理：子群阶可以整除群阶。
⟨
g
⟩
\langle g \rangle
⟨g⟩ 是
G
\mathbb{G}
G 子群，并且
∣
⟨
g
⟩
∣
∣
∣
G
∣
|\langle g \rangle| \mid |\mathbb{G}|
∣⟨g⟩∣∣∣G∣。
- 思路：由一个子群可以派生覆盖了整个群的若干子集，这些子集的阶与子群相同，并且这些子集彼此不相交。
- 设群 G \mathbb{G} G的子群 H H H，陪集（coset） g H gH gH（ g g g和 H H H中每个元素 h h h运算构成的集合）和子群 H H H的阶相同。
- 子群的任意两个陪集
g
1
H
g_1H
g1H和
g
2
H
g_2H
g2H。
- 或者相同，如果 g 1 − 1 g 2 ∈ H g_1^{-1}g_2 \in H g1−1g2∈H。 g 1 ( g 1 − 1 g 2 ) h ∈ g 1 H g_1(g_1^{-1}g_2 )h \in g_1H g1(g1−1g2)h∈g1H， g 2 h ∈ g 1 H g_2h \in g_1H g2h∈g1H。
- 或者没有交集，如果 g 1 − 1 g 2 ∉ H g_1^{-1}g_2 \notin H g1−1g2∈/H。采用反证法，如果有交集，则 g 1 h 1 = g 2 h 2 g_1h_1 = g_2h_2 g1h1=g2h2， g 1 − 1 g 2 = h 1 h 2 − 1 ∈ H g_1^{-1}g_2 = h_1h_2^{-1} \in H g1−1g2=h1h2−1∈H，矛盾。
- 因此，群可以划分为任意子群的若干不相交陪集，每个陪集阶相同，群的阶就是子群的整数倍。
- 推荐参考：https://brilliant.org/wiki/lagranges-theorem/
-
离散对数
- 如果 G \mathbb{G} G 是阶为 q q q 的循环群，那么 ∃ \exists ∃ 生成元 g ∈ G g \in \mathbb{G} g∈G 使得 { g 0 , g 1 , … , g q − 1 } = G \{ g^0,g^1,\dotsc,g^{q-1}\} = \mathbb{G} {g0,g1,…,gq−1}=G。
- ∀ h ∈ G \forall h \in \mathbb{G} ∀h∈G, ∃ \exists ∃ 唯一的 x ∈ Z q x \in \mathbb{Z}_q x∈Zq 使得 g x = h g^x = h gx=h。
- x = log g h x= \log_gh x=loggh 是以 g g g为底 h h h的离散对数（discrete logarithm）。
- 如果 g x ′ = h g^{x'}=h gx′=h, 那么 log g h = [ x ′ m o d q ] \log_gh = [x' \bmod q] loggh=[x′modq]。
- log g 1 = 0 \log_g1=0 logg1=0 并且 log g ( h 1 ⋅ h 2 ) = [ ( log g h 1 + log g h 2 ) m o d q ] \log_g(h_1\cdot h_2) = [(\log_gh_1+\log_gh_2) \bmod q] logg(h1⋅h2)=[(loggh1+loggh2)modq]。
-
离散对数算法概览
- 给定一个生成元 g ∈ G g \in \mathbb{G} g∈G 并且 y ∈ ⟨ g ⟩ y \in \langle g \rangle y∈⟨g⟩，求 x x x 使得 g x = y g^x=y gx=y.
- 蛮力： O ( q ) \mathcal{O}(q) O(q), q = o r d ( g ) q = \mathsf{ord}(g) q=ord(g) 是 ⟨ g ⟩ \langle g\rangle ⟨g⟩ 的阶。
- Baby-step/giant-step [Shanks]: O ( q ⋅ p o l y l o g ( q ) ) \mathcal{O}(\sqrt{q}\cdot \mathsf{polylog}(q)) O(q ⋅polylog(q)).
- Pohlig-Hellman算法：当 q q q 有较小因子。
- Index calculus 法: O ( exp ( n ⋅ log n ) ) \mathcal{O}(\exp{(\sqrt{n\cdot \log n})}) O(exp(n⋅logn )).
- 已知最好的算法是通用数域筛法： O ( exp ( n 1 / 3 ⋅ ( log n ) 2 / 3 ) ) \mathcal{O}(\exp(n^{1/3}\cdot(\log n)^{2/3})) O(exp(n1/3⋅(logn)2/3)).
- 椭圆曲线群 vs. Z p ∗ \mathbb{Z}_p^* Zp∗: 在保证安全性相同的同时，更高效。(1024-bit Z p ∗ \mathbb{Z}_p^* Zp∗ 和 132-bit 椭圆曲线都需要 2 66 2^{66} 266 步来破解。)
-
使用质数阶群
- 定理：如果 G \mathbb{G} G 是质数阶，那么 G \mathbb{G} G 是循环群。除单位元外，所有 g ∈ G g \in \mathbb{G} g∈G 是生成元。
- 注：根据拉格朗日定理，任意元素的阶都等于群的阶。
- 离散对数问题在质数阶群上是最难的。
- 在质数阶群上找一个生成元很简单。
- 任何非零指数在以质数阶为模下都可逆。
- DDH问题是难题的必要条件是 D H g ( h 1 , h 2 ) \mathsf{DH}_g(h_1,h_2) DHg(h1,h2) 与群中随机元素之间是不可区分的。在质数阶群上这基本成立。
-
产生质数阶（子）群
- 如果 p p p 是质数，那么 Z p ∗ \mathbb{Z}^*_p Zp∗ 是循环群。注：。
- y ∈ Z p ∗ y \in \mathbb{Z}^*_p y∈Zp∗ 是模 p p p下的二次剩余（quadratic residue modulo），如果 ∃ x ∈ Z p ∗ \exists x \in \mathbb{Z}^*_p ∃x∈Zp∗ 使得 x 2 ≡ y ( m o d p ) x^2 \equiv y \pmod p x2≡y(modp)
- 例题： Z 7 ∗ \mathbb{Z}_{7}^{*} Z7∗ 下的二次剩余？
- QR集合是一个子群（满足群条件），阶为 ( p − 1 ) / 2 (p-1)/2 (p−1)/2，因为 x 2 ≡ ( p − x ) 2 ( m o d p ) x^2 \equiv (p-x)^2 \pmod p x2≡(p−x)2(modp)。
- p p p 是一个强质数（strong prime），如果 p = 2 q + 1 p=2q+1 p=2q+1 且 q q q 是质数。
- 强质数下的二次剩余子群是一个循环群，因为群的阶是质数。
- 循环群生成算法：产生一个强质数 p p p，阶为 q = ( p − 1 ) / 2 q=(p-1)/2 q=(p−1)/2，随机选择一个 x ∈ Z p ∗ x \in \mathbb{Z}^*_p x∈Zp∗，得到生成元 g = x 2 g=x^2 g=x2，输出 p , q , g p, q, g p,q,g。
-
离散对数假设
- 离散对数（discrete logarithm）实验
D
L
o
g
A
,
G
(
n
)
\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n)
DLogA,G(n):
- 运行一个群生成算法 G ( 1 n ) \mathcal{G}(1^n) G(1n) 来产生 ( G , q , g ) (\mathbb{G},q,g) (G,q,g)，其中 G \mathbb{G} G 是阶为 q q q ( ∥ q ∥ = n \|q\|=n ∥q∥=n) 的循环群，并且 g g g 是 G \mathbb{G} G 的生成元。
- 挑选一个 h ← G h \gets \mathbb{G} h←G. ( x ′ ← Z q x' \gets \mathbb{Z}_q x′←Zq and h : = g x ′ h := g^{x'} h:=gx′)
- 敌手 A \mathcal{A} A 给定 G , q , g , h \mathbb{G}, q, g, h G,q,g,h，并且输出 x ∈ Z q x \in \mathbb{Z}_q x∈Zq.
- 实验成功 D L o g A , G ( n ) = 1 \mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n) = 1 DLogA,G(n)=1，如果 g x = h g^x = h gx=h, 否则 0 。
- 定义：离散对数问题相对于群 G \mathcal{G} G是难的，如果 ∀ \forall ∀ ppt 算法 A \mathcal{A} A, ∃ \exists ∃ n e g l \mathsf{negl} negl 使得 $ \Pr[\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n)=1] \le \mathsf{negl}(n).$
- 离散对数（discrete logarithm）实验
D
L
o
g
A
,
G
(
n
)
\mathsf{DLog}_{\mathcal{A},\mathcal{G}}(n)
DLogA,G(n):
-
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)）问题：区分 D H g ( h 1 , h 2 ) \mathsf{DH}_g(h_1,h_2) DHg(h1,h2) 与一个随机的群元素 h ′ h' h′.
- 定义：DDH问题与 G \mathcal{G} G相关的是难的，如果 ∀ \forall ∀ ppt A \mathcal{A} A, ∃ \exists ∃ n e g l \mathsf{negl} negl 使得 $ |\Pr[\mathcal{A}(\mathbb{G},q,g,gx,gy,g^z)=1] - \Pr[\mathcal{A}(\mathbb{G},q,g,gx,gy,g^{xy})=1]|\le \mathsf{negl}(n). $
- DL, CDH 和 DDH 的难解性：DDH 比 CDH 和 DL 容易。
-
安全密钥交换实验
-
密钥交换实验（key-exchange experiment） K E A , Π e a v ( n ) \mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n) KEA,Πeav(n):
- 双方持有安全参数 1 n 1^n 1n 执行协议 Π \Pi Π。 Π \Pi Π 执行的结果为对话记录 (transcript) t r a n s \mathsf{trans} trans 包含双方发送的所有消息，以及各方都输出的密钥 k k k 。
- 选择一个随机比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1} 。 如果 b = 0 b=0 b=0 那么选择 k ^ ← { 0 , 1 } n \hat{k} \gets \{0,1\}^n k^←{0,1}n u.a.r；如果 b = 1 b=1 b=1 那么令 k ^ : = k \hat{k} :=k k^:=k。
- 敌手 A \mathcal{A} A 给定 t r a n s \mathsf{trans} trans 和 k ^ \hat{k} k^, 并且输出一个比特 b ′ b' b′。
- K E A , Π e a v ( n ) = 1 \mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1 KEA,Πeav(n)=1 如果 b ′ = b b'=b b′=b， 否则 0 。
-
定义：一个密钥交换协议 Π \Pi Π 在出现窃听者攻击下是安全的，如果 ∀ \forall ∀ ppt A \mathcal{A} A, ∃ \exists ∃ n e g l \mathsf{negl} negl 使得
$ \Pr[\mathsf{KE}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n) = 1] < \frac{1}{2} + \mathsf{negl}(n). $
-
-
DH密钥交换协议
- K E ^ A , Π e a v \widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi} KE A,Πeav 表示一个实验，其中如果 b = 0 b=0 b=0 ，敌手被给予 k ^ ← G \hat{k} \gets \mathbb{G} k^←G。
- 定理：如果DDH问题与 G \mathcal{G} G相关是难的，那么DH 密钥交换协议 Π \Pi Π 在出现窃听者时是安全的 (对应改动的实验 K E ^ A , Π e a v \widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi} KE A,Πeav)。
- 不安全性：在主动的敌手，中间人，攻击下是不安全的 (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 b=1 b=1, 那么给真密钥；否则给随机的 g z g^z gz.
- $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(gx,gy,g^{xy})=1 \right] + \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(gx,gy,g^z)=0 \right] $
- $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(gx,gy,g^{xy})=1 \right] + \frac{1}{2}\cdot (1-\Pr\left[ \mathcal{A}(gx,gy,g^z)=1 \right]) $
- $= \frac{1}{2} + \frac{1}{2}\cdot \left( \Pr\left[ \mathcal{A}(gx,gy,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(gx,gy,g^z)=1 \right] \right) $
- $ \le \frac{1}{2} + \frac{1}{2}\cdot \mathsf{negl}(n) %\left| \Pr\left[ \mathcal{A}(gx,gy,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(gx,gy,g^z)=1 \right] \right| $
-
DHKE例子
- G = Z 11 ∗ \mathbb{G} = \mathbb{Z}^*_{11} G=Z11∗ ；群的阶 q = ? q = ? q=?
- 二次剩余子群 ?
- g = 3 g = 3 g=3 是生成元吗？
- 如果 x = 3 x = 3 x=3 且 y = 4 y = 4 y=4，Bob发给Alice消息是？
- Alice 如何计算密钥？
- Bob 如何计算密钥？
-
三方密钥交换
- DH基于的KE在2轮实现三方密钥交换，Key = g a b c =g^{abc} =gabc。
- Joux’s KE 在 1 轮实现三方密钥交换。在 bilinear map中，Key = e ( P , P ) a b c =e(P,P)^{abc} =e(P,P)abc 。
- 开放问题：如何在一轮中在4方之间交换密钥？
-
完美保密私钥加密引理
- 引理： G \mathbb{G} G 是有限群并且 m ∈ G m\in \mathbb{G} m∈G 是任意元素。那么选择随机 k ← G k \gets \mathbb{G} k←G 并令 c : = m ⋅ k c := m\cdot k c:=m⋅k ，将得到与随机选择的 c ← G c \gets \mathbb{G} c←G 相同的分布，即 ∀ g ∈ G \forall g \in \mathbb{G} ∀g∈G: $ \Pr[m\cdot k = g] = 1/|\mathbb{G}| $。
- 证明： g ∈ G g \in \mathbb{G} g∈G 是任意的，那么 $\Pr[m\cdot k = g] = \Pr[k = m^{-1}\cdot g] $。由于 k k k 均匀随机选择，选择 k k k 的概率与一个固定元素 m − 1 ⋅ g m^{-1}\cdot g m−1⋅g 相同，都是 1 / ∣ G 1/|\mathbb{G} 1/∣G|。
- 注：这是一种完美保密的私钥加密方案，将一个元素（明文）与另一个元素（密钥）的运算得到第三个元素（密文），与之前一个字母的移位密码是完美保密是类似的。
-
Elgamal加密方案
- 一个算法 G \mathcal{G} G, 输入 1 n 1^n 1n, 输出一个循环群 G \mathbb{G} G, 其阶为 q q q ( ∥ q ∥ = n \|q\| = n ∥q∥=n), 并且生成元为 g g g。
- 构造：
- G e n \mathsf{Gen} Gen: 运行 G ( 1 n ) \mathcal{G}(1^n) G(1n) 来产生 ( G , q , g ) (\mathbb{G},q,g) (G,q,g)。一个随机的 x ← Z q x \gets \mathbb{Z}_q x←Zq 和 h : = g x h := g^x h:=gx。 p k = ⟨ G , q , g , h ⟩ pk = \langle \mathbb{G},q,g,h \rangle pk=⟨G,q,g,h⟩ 并且 s k = ⟨ G , q , g , x ⟩ sk = \langle \mathbb{G},q,g,x \rangle sk=⟨G,q,g,x⟩。
- E n c \mathsf{Enc} Enc: 一个随机 y ← Z q y \gets \mathbb{Z}_q y←Zq 并且输入 ⟨ c 1 , c 2 ⟩ = ⟨ g y , h y ⋅ m ⟩ \langle c_1, c_2 \rangle = \langle g^y, h^y\cdot m\rangle ⟨c1,c2⟩=⟨gy,hy⋅m⟩。
- D e c \mathsf{Dec} Dec: m : = c 2 / c 1 x m:=c_2/c_1^x m:=c2/c1x。
- 定理：如果DDH问题与 G \mathcal{G} G相关是难的，那么Elgamal加密方案是CPA安全。
-
Elgamal加密例子
- 加密前首先对明文进行二进制串编码：
- 在模一个强质数 p = ( 2 q + 1 ) p = (2q+1) p=(2q+1) 的二次剩余子群中，
- 一个串 m ^ ∈ { 0 , 1 } n − 1 \hat{m} \in \{0,1\}^{n-1} m^∈{0,1}n−1, n = ∥ q ∥ n = \|q\| n=∥q∥。
- 将 m ^ \hat{m} m^ 映射到被加密的明文 m = [ ( m ^ + 1 ) 2 m o d p ] m = [(\hat{m}+1)^2 \bmod p] m=[(m^+1)2modp]。
- 映射是一对一且可逆的。
- 例子，略。
- 加密前首先对明文进行二进制串编码：
-
证明
- 思路：通过将DDH问题的算法 D D D规约到窃听者算法 A \mathcal{A} A来证明 Π \Pi Π 在窃听者出现时是安全的。
- 将 Π \Pi Π 改造为 Π ~ \tilde{\Pi} Π~： 加密是通过随机选择的 y ← Z q y \gets \mathbb{Z}_q y←Zq 和 z ← Z q z \gets \mathbb{Z}_q z←Zq 然后输出密文：$ \langle g^y, g^z\cdot m\rangle$。
- Π ~ \tilde{\Pi} Π~ 不是一个加密方案.
- g y g^y gy 独立于 m m m。
- g z ⋅ m g^z\cdot m gz⋅m 是独立于 m m m 的随机元素 (之前的私钥加密引理)。
- 实验成功概率与完美保密加密方案中是相同的。 Pr [ P u b K A , Π ~ e a v ( n ) = 1 ] = 1 2 . \Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1\right] = \frac{1}{2}. Pr[PubKA,Π~eav(n)=1]=21.
-
证明（续一）
- 将DDH问题的算法 D D D规约到窃听者算法 A \mathcal{A} A。
-
证明（续二）
-
情况1: g 3 = g z g_3 = g^z g3=gz, 密文是 ⟨ g y , g z ⋅ m b ⟩ \langle g^y, g^z\cdot m_b\rangle ⟨gy,gz⋅mb⟩.
$ \Pr[D(gx,gy,g^z)=1] = \Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1\right] = \frac{1}{2}. $
-
情况2: g 3 = g x y g_3 = g^{xy} g3=gxy, 密文是 ⟨ g y , g x y ⋅ m b ⟩ \langle g^y, g^{xy}\cdot m_b\rangle ⟨gy,gxy⋅mb⟩.
$ \Pr[D(gx,gy,g^{xy})=1] = \Pr\left[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1\right] = \varepsilon(n). $
-
由于DDH问题是难的，
$ \mathsf{negl}(n) \ge |\Pr[D(gx,gy,g^z)=1] - \Pr[D(gx,gy,g^{xy})=1]| =|\frac{1}{2}-\varepsilon(n)|. $
-
-
Elgamal加密中CCA
- Elgamal不是CCA安全的。
- 例题：构造明文
m
⋅
m
′
m\cdot m'
m⋅m′ 的密文。
- 给定 p k = ⟨ g , h ⟩ pk=\langle g, h\rangle pk=⟨g,h⟩, c = ⟨ c 1 , c 2 ⟩ c = \langle c_1, c_2\rangle c=⟨c1,c2⟩, c 1 = g y c_1=g^y c1=gy, c 2 = h y ⋅ m c_2=h^y\cdot m c2=hy⋅m,
- 方法1：计算 c 2 ′ : = c 2 ⋅ m ′ c_2' := c_2\cdot m' c2′:=c2⋅m′, 和 c ′ = ⟨ c 1 , c 2 ′ ⟩ c' = \langle c_1, c_2'\rangle c′=⟨c1,c2′⟩. $ \frac{c_2’}{c_1^x} = ? $
- 方法2：计算
c
1
′
′
:
=
c
1
⋅
g
y
′
′
c_1'' := c_1\cdot g^{y''}
c1′′:=c1⋅gy′′, 和
c
2
′
′
:
=
c
2
⋅
h
y
′
′
⋅
m
′
c_2'' := c_2\cdot h^{y''}\cdot m'
c2′′:=c2⋅hy′′⋅m′。
- $ c_1’’=g^y\cdot g^{y’’} = g^{y+y’’};\text{and}; c_2’’= ? $
- 所以 c ′ ′ = ⟨ c 1 ′ ′ , c 2 ′ ′ ⟩ c''=\langle c_1'',c_2''\rangle c′′=⟨c1′′,c2′′⟩ 是 m ⋅ m ′ m\cdot m' m⋅m′ 的密文。
-
Elgamal实现问题
- 共享公开参数：
G
\mathcal{G}
G 产生参数
G
,
q
,
g
\mathbb{G},q,g
G,q,g。
- 这些参数可以只产生一次并且为所有人所使用（ ``once-and-for-all’’）。
- 可以被多个接收者使用。
- 每个接收者必须选择各自的保密数值 x x x 并且发布他们自己的公钥包含 h = g x h=g^x h=gx。
- 参数共享：在 Elgamal 的情况下，公开参数可以被共享。在 RSA 情况下，参数可以被共享吗？
- 共享公开参数：
G
\mathcal{G}
G 产生参数
G
,
q
,
g
\mathbb{G},q,g
G,q,g。
-
总结
- 略