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

2020-05-30 cryptography 密码学 DH 秘钥交换

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

设想一个系统有 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 秘钥交换的增强协议,在协议中同时完成对于通信双方身份的认证。

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-dh-exchange/

如有其它需要,请邮件联系!版权所有,违者必究!