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

目录

  • 0. 思维导图
  • 1. Diffie-Hellman密钥交换
    • 1.1 本原根（primitive root）
    • 1.2 离散对数（discrete logarithm）
    • 1.3 密钥交换过程
    • 1.4 应用
  • 2. 中间人攻击（man-in-the-middle attack）
  • 3. EIGamal密码体制

0. 思维导图

1. Diffie-Hellman密钥交换

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


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

1.1 本原根（primitive root）

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

3是素数19的一个本原根，则：
3mod19=3 32 mod19=9 33 mod19=8
34 mod19=5 35 mod19=15 36 mod19=7
37 mod19=2 38 mod19=6 39 mod19=18
310 mod19=16 311 mod19=10 312 mod19=11
313 mod19=14 314 mod19=4 315 mod19=12
316 mod19=17 317 mod19=13 318 mod19=1

1.2 离散对数（discrete logarithm）

对于一个整数和素数的一个本原根，可以找到一个唯一的指数 ，使得：= a(≤≤−)=a^ \\ (≤≤−)b=aimodq(0≤i≤q−1)成立，则指数称为的以为底数的模的离散对数。

离散对数的难解性

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

1.3 密钥交换过程

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

证明：=( )=(_)^{_} \\K=(YB​)XA​modq
= ( a )(a^{_ } \\)^{_} \\(aXB​modq)XA​modq
=( a )(a^{_ })^{_} \\(aXB​)XA​modq
= aa^{_ _ } \\aXB​XA​modq
=( a )(a^{_ })^{_} \\(aXA​)XB​modq
=( a )(a^{_ } \\ )^{_} \\(aXA​modq)XB​modq
= () {(_)}^{_ } \\(YA​)XB​modq

练习题
已知A和B使用Diffie-Hellman密钥交换算法，共享参数q=11，它的一个本原根a=2，A的私钥为3，B的私钥为4，计算通信密钥K。
答：已知q=11,a=2, X A=3, X B=4q=11, a=2, X_A=3, X_B=4 q=11,a=2,XA​=3,XB​=4
则 Y A= a XA modq= 2 3mod11=8Y_A=a^{X_A} \ mod \ q\ = \ 2^3 \ mod \ 11 \ = \ 8 YA​=aXA​modq=23mod11=8
K=( Y A ) XB modq= 8 4mod11=4K \ = (Y_A)^{X_B} \ mod \ q = 8^4 \ mod \ 11 = 4 K=(YA​)XB​modq=84mod11=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 生成两个随机私钥 、 _{}、_{} XD1​、XD2​，并计算相应的公钥 、 _{}、_{} YD1​、YD2​
  • Alice将自己的公钥_ YA​传递给Bob
  • Darth将报文截获，修改成自己的公钥 _{} YD1​发给Bob
  • Darth用 _{} YD1​仿冒Alice
  • Bob收到 _{} YD1​，认为这是Alice的公钥
  • Bob 计算密钥=()_=(_{})^{_} \\K1​=(YD1​)XB​modq
  • Darth 也计算密钥=(B )D 1 _=(_{B})^{_{D1}} \\K1​=(YB​)XD1​modq
  • Bob 将自己的公钥_ YB​传递给Alice
  • Darth将报文截获，修改成自己的公钥 _{} YD2​发给Alice
  • Darth用 _{} YD2​仿冒Bob
  • Alice收到 _{} YD2​，认为这是Bob的公钥
  • Alice 计算密钥2=(2) A _2=(_{2})^{_A} \\K2​=(YD2​)XA​modq
  • Darth 也计算密钥2=(A )D 2 _2=(_{A})^{_{D2}} \\K2​=(YA​)XD2​modq
  • Alice和Bob以为他们已经交换好了KK K
  • 实际上Bob是与Darth共享密钥 K 1K_1 K1​
  • Alice是与Darth共享密钥 K 2K_2 K2​
  • 若Alice使用 K 2K_2 K2​给Bob发送消息Y=E( K 2,X)Y=E(K_2,X) Y=E(K2​,X)
  • Darth截获后，使用与其共享的密钥 K AK_A KA​进行解密X=D( K 2,Y)X=D(K_2,Y) X=D(K2​,Y)
  • Darth可以将XX X直接使用与Bob共享的密钥 K 1K_1 K1​加密，也可以修改后加密发出

3. EIGamal密码体制

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

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

  • = , a ==,a=q=19,a=10

  • Alice 选择私钥 = _=XA​=5（ XA< q − 1X^A <q-1XA<q−1），计算 = a= = _=a^{_} \\= ^ \\= YA​=aXA​modq=105mod19=3

  • Alice 的公钥对为： {, a , } = { , ,}\{,a,_\}=\{,,\}{q,a,YA​}={19,10,3}

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

  • 收到Alice的公钥{19,10,3}，计算密钥= ( )== =(_)^ \\=^ \\= K=(YA​)kmodq=36mod19=7

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

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

  • = a= =_=a^ \\=^ \\ =C1​=akmodq=106mod19=11

  • = =×= _= \\=× \\ =C2​=KMmodq=7×17mod19=5

  • Bob 将密文 、_、_C1​、C2​发送给Alice

  • Alice 根据_C1​计算密钥= ( )= =(_)^{_} \\ =K=(C1​)XA​modq=7

  • 根据_C2​还原消息 = ( −) ==(_ ^− ) \\ =M=(C2​K−)modq=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=4M=5, k=3, q=11, a=2, X_A=4 M=5,k=3,q=11,a=2,XA​=4
Y A= a XA modq= 2 4mod11=5Y_A=a^{X_A} \ mod \ q = 2^4 \ mod \ 11 = 5 YA​=aXA​modq=24mod11=5
K=( Y A ) kmodq= 5 3mod11=4K = (Y_A)^k \ mod \ q = 5^3 \ mod \ 11 = 4 K=(YA​)kmodq=53mod11=4
C 1= a kmodq= 2 3mod11=8C_1 = a^k \ mod \ q = 2^3 \ mod \ 11 = 8 C1​=akmodq=23mod11=8
C 2=KMmodq=4×5mod11=9C_2 = KM \ mod \ q = 4×5 \ mod \ 11 = 9 C2​=KMmodq=4×5mod11=9

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

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