[现代密码学原理] - 密钥管理和其他公钥密码系统（学习笔记）

???? 前言：本章首先介绍最早、最简单的PKCS——Diffe-Hellman密钥交换，然后介绍另一个重要方案——EIGamal PKCS。

---

???? 0. 思维导图

???? 1. Diffie-Hellman密钥交换

• 1976年，Diffie和Hellman首次公开提出了一种公钥算法，常被称为Diffie-Hellman密钥交换
• DH算法用到的数学基础：本原根、离散对数

DH算法 | 迪菲-赫尔曼Diffie–Hellman 密钥交换
Diffie-Hellman密钥交换 Diffie-Hellman_Key_Exchange

???? 1.1 本原根（primitive root）

对于一个素数$\mathbf{q}$ ，如果数值$a\mathbf{mod}\mathbf{q}，a^2\mathbf{mod}\mathbf{q}，a^3\mathbf{mod}\mathbf{q}，...a^{(\mathbf{q}-1)}\mathbf{mod}\mathbf{q}$是各不相同的整数，并且以某种排列方式组成了从1到???? -1的所有整数，则称整数????是素数????的一个本原根。

3是素数19的一个本原根，则：
3mod19=3 3² mod19=9 3³ mod19=8
3⁴ mod19=5 3⁵ mod19=15 3⁶ mod19=7
3⁷ mod19=2 3⁸ mod19=6 3⁹ mod19=18
3¹⁰ mod19=16 3¹¹ mod19=10 3¹² mod19=11
3¹³ mod19=14 3¹⁴ mod19=4 3¹⁵ mod19=12
3¹⁶ mod19=17 3¹⁷ mod19=13 3¹⁸ mod19=1

???? 1.2 离散对数（discrete logarithm）

对于一个整数????和素数????的一个本原根????，可以找到一个唯一的指数???? ，使得：$\mathbf{b}=a^{\mathbf{i}}\mathbf{mod}\mathbf{q}(0\le \mathbf{i}\le \mathbf{q}-1)$成立，则指数????称为????的以????为底数的模????的离散对数。

离散对数的难解性

• 给定????、 ????和???? ，容易计算出????
• 给定???? 、????和???? ，计算出????一般非常困难

???? 1.3 密钥交换过程

• Alice和Bob要进行密钥交换，首先他们共享一个素数$q$以及整数????，并公开
• ????<????，????是素数q的本原根
• Alice 选择随机整数${\mathbf{X}}_{\mathbf{A}}<\mathbf{q}，{\mathbf{X}}_{\mathbf{A}}$是私有的，只有Alice自己知道，即Alice的私钥
• Bob 也选择一个随机整数${\mathbf{X}}_{\mathbf{B}}<\mathbf{q}$，作为Bob 的私钥
• Alice 计算${\mathbf{Y}}_{\mathbf{A}}=a^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$，计算得到的${\mathbf{Y}}_{\mathbf{A}}$是公开可访问的，即Alice的公钥
• Bob 也计算他的公钥${\mathbf{Y}}_{\mathbf{B}}=a^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$
• Alice 将自己的公钥${\mathbf{Y}}_{\mathbf{A}}$发送给 Bob，Bob获取到了Alice 的公钥
• Bob 也将他的公钥${\mathbf{Y}}_{\mathbf{B}}$发送给了Alice
• Alice 计算 $\mathbf{K}=({\mathbf{Y}}_{\mathbf{B}}{)}^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$
• Bob 也使用该方法计算 $\mathbf{K}=({\mathbf{Y}}_{\mathbf{A}}{)}^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$
• 二人计算结果相同，至此双方完成了$K$的交换
• $K$值在双方本地生成，且只有双方已知，因此常将这个$K$值作为对称密码的密钥

证明：$\mathbf{K}=({\mathbf{Y}}_{\mathbf{B}}{)}^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$
= $(a^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}{)}^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$
=$(a^{{\mathbf{X}}_{\mathbf{B}}}{)}^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$
=$a^{{\mathbf{X}}_{\mathbf{B}}{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}$
=$(a^{{\mathbf{X}}_{\mathbf{A}}}{)}^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$
=$(a^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}{)}^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$
=${({\mathbf{Y}}_{\mathbf{A}})}^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$

练习题
已知A和B使用Diffie-Hellman密钥交换算法，共享参数q=11，它的一个本原根a=2，A的私钥为3，B的私钥为4，计算通信密钥K。
答：已知$q=11,a=2,X_A=3,X_B=4$
则$Y_A=a^{X_A}modq=2^{3}mod11=8$
$K=(Y$

上一篇： 安全及应用（更新）

下一篇： 密钥管理技术

推荐阅读

• [现代密码学原理] - 密钥管理和其他公钥密码系统（学习笔记）