密码学专题| 七、公钥密码体系和 Diffin-Hellman 交换

从对称密码体系到公钥密码体系

设想一个系统有 N 个人希望进行互相通信。如果使用原始的对称密码体系，则每一个人需要维护 N-1 个秘钥。整个系统需要维护 （N-1)N/2 个秘钥。这个方案是非常不“优雅”的：

1. 需要与两两之间都需要可靠的信道进行秘钥分配
2. 秘钥管理非常繁琐
3. 开放系统只几乎是不可能的
4. 人员的进入和退出时复杂的

在一个封闭式的系统中，可以使用 Needham-Schroeder 秘钥分配方案。系统中引入了一个秘钥分配中心 KDC 的角色。每一个参与者都需要维护一个与 KDC 之间的秘钥。

Alice -> KDC: 
    <Alice, Bob>
KDC -> Alice: 
    < E_{k_{Alice}}(Alice,Bob, session_key, other_information)
    E_{k_{Bob}}(Alice,Bob, session_key, other_information)>
Alice -> Bob:
    E_{k_{Bob}}(Alice,Bob, session_key, other_information)>

但是该方案依然有不足：

1. 方案是封闭的
2. 安全性依赖于 KDC 的安全性
3. KDC 可能存在单点瓶颈（SPOF）

使用公钥密码体系

使用公钥密码体系引入了下面三个新的密码学原语言：

1. 数字信封：对标对称加密的公钥加密算法
2. 数字签名：对标消息认证码的私钥签名算法
3. DH 秘钥交换：用于分布式的进行会话秘钥的协商

DH 秘钥交换

秘钥交换实验描述如下：

1. 两个持有 \(1^n\) 的通信双方执行协议 \(\Pi\)。之后得到会话秘钥 k 和通信消息 m
2. 随机选取一个比特 \( b \leftarrow \lbrace 0,1 \rbrace^n \)。如果 b = 1，则 \(k’ = k)。否则 \( k’ \leftarrow \lbrace 0,1 \rbrace^ n \)。
3. 给多项式运行时间的敌手 A 输入 k’ 和 m，输出一个比特 \(b’\)
4. 当且仅当 \(b’ = b\) ，记 \(Adv_{A,\Pi}^{KE} = 1\)

秘钥交换协议是计算安全的，当且仅当： \[ Pr[Adv_{A,\Pi}^{KE} = 1] \le \frac{1}{2} + negl(n) \]

Diffin-Hellman 交换协议定义如下：

输入参数 \(1^n\)

1. Alice 执行 \(gen(1^n) \) 得到 \( (G,q,g) \)
2. Alice 选取 \( x \leftarrow Z_q \) 并计算 \(h_1 = g^x \)
3. Alice 向 Bob 发送 \( (G,q,g,h_1) \)
4. Bob 选取 \( y \leftarrow Z_q \) 并计算 \(h_2 = g^y \)
5. Bob 向 Alice 发送 \(h_2\)，并计算会话秘钥 \(k_B = h_1^y \)
6. Alice 接受 \(h_2\)，并计算会话秘钥 \(k_A = h_2^x \)

可以看到 \[ k_B = h_1^y = (g^x)^y = g^ {(x \cdot y)}\] \[ k_A = h_2^x = (g^y)^x = g^ {(y \cdot x)}\] \[ \therefore k_B = k_A \]

可以证明 DH 交换是满足上述秘钥交换的实验的。但是上述实验只定义了被动攻击，实则 DH 秘钥交换受到中间人 (MITM, man in the middle) 攻击。此时需要使用 DH 秘钥交换的增强协议，在协议中同时完成对于通信双方身份的认证。