【现代密码学原理】——密钥管理和其他公钥密码体制（学习笔记）

📖 前言：本章首先介绍最早、最简单的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_A{)}^{X_B}modq=8^{4}mod11=4$

🕘 1.4 应用

• 对于连接在同一LAN下的不同用户，每人产生一个在较长时间内有效的私钥X，计算出公钥Y
  

• 将全体用户的公钥存放于中心目录下

• 当某用户要与其他用户通信时，只需访问中心目录即可获取对方公钥，计算出通信的密钥K

• DH算法几乎已经渗透到互联网每个安全传输协议中，包括HTTPS中的加密标准SSL协议、SSH加密通信协议、IPSec等等

• IPsec是一种安全的网络协议套件，通过网络在两台计算机之间提供安全的加密通信，它常用于VPN。

• IKE是IPSec套件中的一部分，为IPSec提供了自动协商密钥。
  

扩展阅读
SSH或Secure Shell是一种加密网络协议，用于通过不安全的网络安全地运行网络服务。典型的应用程序包括远程命令行，登录和远程命令执行，但是任何网络服务都可以使用SSH进行保护。其中，SSH进行密钥交换使用的就是Diffie-Hellman的密钥交换方案。

Internet协议安全性（IPsec）是一种安全的网络协议套件，可对数据包进行身份验证和加密，以通过Internet协议网络在两台计算机之间提供安全的加密通信。 它用于虚拟专用网络（VPN）。
IKE是IPSec套件中的一部分。IKE为IPSec提供了自动协商密钥、建立IPSec安全联盟的服务，能够简化IPSec的使用和管理，大大简化IPSec的配置和维护工作。
对等体之间建立一个IKE SA完成身份验证和密钥信息交换后，在IKE SA的保护下，根据配置的AH/ESP安全协议等参数协商出一对IPSec SA。
其中，IKE用到的密钥信息交换方案就是Diffie-Hellman的密钥交换方案。

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页

🕒 2. 中间人攻击（man-in-the-middle attack）

• Alice和Bob交换密钥，Darth攻击
• Darth 生成两个随机私钥${\mathbf{X}}_{\mathbf{D}1}、{\mathbf{X}}_{\mathbf{D}2}$，并计算相应的公钥${\mathbf{Y}}_{\mathbf{D}1}、{\mathbf{Y}}_{\mathbf{D}2}$
• Alice将自己的公钥${\mathbf{Y}}_{\mathbf{A}}$传递给Bob
• Darth将报文截获，修改成自己的公钥${\mathbf{Y}}_{\mathbf{D}1}$发给Bob
• Darth用${\mathbf{Y}}_{\mathbf{D}1}$仿冒Alice
• Bob收到${\mathbf{Y}}_{\mathbf{D}1}$，认为这是Alice的公钥
• Bob 计算密钥${\mathbf{K}}_1=({\mathbf{Y}}_{\mathbf{D}1}{)}^{{\mathbf{X}}_{\mathbf{B}}}\mathbf{mod}\mathbf{q}$
• Darth 也计算密钥${\mathbf{K}}_1=({\mathbf{Y}}_B{)}^{{\mathbf{X}}_{D1}}\mathbf{mod}\mathbf{q}$
• Bob 将自己的公钥${\mathbf{Y}}_{\mathbf{B}}$传递给Alice
• Darth将报文截获，修改成自己的公钥${\mathbf{Y}}_{\mathbf{D}2}$发给Alice
• Darth用${\mathbf{Y}}_{\mathbf{D}2}$仿冒Bob
• Alice收到${\mathbf{Y}}_{\mathbf{D}2}$，认为这是Bob的公钥
• Alice 计算密钥${\mathbf{K}}_2=({\mathbf{Y}}_{\mathbf{D}2}{)}^{{\mathbf{X}}_A}\mathbf{mod}\mathbf{q}$
• Darth 也计算密钥${\mathbf{K}}_2=({\mathbf{Y}}_A{)}^{{\mathbf{X}}_{D2}}\mathbf{mod}\mathbf{q}$
• Alice和Bob以为他们已经交换好了$K$
• 实际上Bob是与Darth共享密钥$K_1$
• Alice是与Darth共享密钥$K_2$
• 若Alice使用$K_2$给Bob发送消息$Y=E(K_2,X)$
• Darth截获后，使用与其共享的密钥$K_A$进行解密$X=D(K_2,Y)$
• Darth可以将$X$直接使用与Bob共享的密钥$K_1$加密，也可以修改后加密发出

🕒 3. EIGamal密码体制

• 1981年，数学家T.ElGamal在DH算法的基础上提出了另外一种公钥密码
• ElGamal密码 是国际公认的较理想公钥密码体制，在数字签名标准DSS、电子邮件标准S/MIME中应用

注：ElGamal不再用于密钥交换，而是像RSA这样用作加解密操作。

• $\mathbf{q}=19,a=10$

• Alice 选择私钥${\mathbf{X}}_{\mathbf{A}}=5$（$X^A<q-1$），计算${\mathbf{Y}}_{\mathbf{A}}=a^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}=10^5\mathbf{mod}19=3$

• Alice 的公钥对为： { 𝒒 , a , 𝒀 𝑨 } = { 𝟏 𝟗 , 𝟏 𝟎 , 𝟑 } \{𝒒,a,𝒀_𝑨\}=\{𝟏𝟗,𝟏𝟎,𝟑\} {q,a,YA​}={19,10,3}

• Bob 生成一个整数$k=6$（$k<q$）

• 收到Alice的公钥{19,10,3}，计算密钥$\mathbf{K}=({\mathbf{Y}}_{\mathbf{A}}{)}^{\mathbf{k}}\mathbf{mod}\mathbf{q}=3^6\mathbf{mod}19=7$

• Alice的公钥{19,10,3}

• Bob 要给Alice发送消息M=17，因此计算

• ${\mathbf{C}}_1=a^{\mathbf{k}}\mathbf{mod}\mathbf{q}=10^6\mathbf{mod}19=11$

• ${\mathbf{C}}_2=\mathbf{KM}\mathbf{mod}\mathbf{q}=7\times 17\mathbf{mod}19=5$

• Bob 将密文${\mathbf{C}}_1、{\mathbf{C}}_2$发送给Alice

• Alice 根据${\mathbf{C}}_1$计算密钥$\mathbf{K}=({\mathbf{C}}_1{)}^{{\mathbf{X}}_{\mathbf{A}}}\mathbf{mod}\mathbf{q}=7$

• 根据${\mathbf{C}}_2$还原消息 $\mathbf{M}=({\mathbf{C}}_2{\mathbf{K}}^{-})\mathbf{mod}\mathbf{q}=17$

练习题
已知B要给A发送消息5，使用ElGamal加密，k=3，q=11，a=2，A的私钥为4，给出密钥K、密文C1与密文C2。
答：已知$M=5,k=3,q=11,a=2,X_A=4$
$Y_A=a^{X_A}modq=2^{4}mod11=5$
$K=(Y_A{)}^{k}modq=5^{3}mod11=4$
$C_1=a^{k}modq=2^{3}mod11=8$
$C_2=KMmodq=4\times 5mod11=9$

---

OK，以上就是本期知识点“密钥管理和其他公钥密码体制”的知识啦~~ ，感谢友友们的阅读。后续还会继续更新，欢迎持续关注哟📌~
💫如果有错误❌，欢迎批评指正呀👀~让我们一起相互进步🚀
🎉如果觉得收获满满，可以点点赞👍支持一下哟~

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页