Diffine-Hellman密钥交换协议/算法

1.概述Diffine-Hellman密钥交换协议/算法机制的妙处在于需要安全通信的双方可以用这个方法确定对称密钥，然后可以用这个密钥进行加密和解密，但是要注意的是，Diffine-Hellman密钥交换协议/算法只能用于密钥交换而不能用于消息的加密和解密。双方确定要用的密钥后，要是用其他的对称密钥操作加密算法实际加密和解密消息。2.算法描述假设Alice和Bob要确定双方加密与解密消息所用的密钥

ZhInen丶

1496人浏览 · 2020-06-21 14:08:15

ZhInen丶 · 2020-06-21 14:08:15 发布

1.概述

Diffine-Hellman密钥交换协议/算法机制的妙处在于需要安全通信的双方可以用这个方法确定对称密钥，然后可以用这个密钥进行加密和解密，但是要注意的是，Diffine-Hellman密钥交换协议/算法只能用于密钥交换而不能用于消息的加密和解密。双方确定要用的密钥后，要是用其他的对称密钥操作加密算法实际加密和解密消息。

2.算法描述

假设Alice和Bob要确定双方加密与解密消息所用的密钥，则可以按如下步骤使用Diffine-Hellman密钥交换协议/算法：
（1）首先，Alice和Bob确定两个大素数n和g，这两个大整数不必保密，Alice和Bob可以用不安全信道确定这两个数。
（2）Alice选择另一个大随机数x，并如下计算A：
$A=g^x\ mod\ n$
（3）Alice将A发送给Bob。
（4）Bob选择另一个大随机数y，并如下计算B：
$B=g^y\ mod\ n$
（5）Bob将B发送给Alice。
（6）计算秘密密钥K1如下：
$K1=B^x\ mod\ n$
（7）计算秘密密钥K2如下：
$K2=A^y\ mod\ n$
其实K1和K2相等，即K1=K2=K是个对称密钥，Alice和Bob将其保密，用于双方加密和解密消息。

3.算法示例

下面用一个简单示例来介绍Diffine-Hellman密钥交换算法的工作过程：
（1）首先，Alice和Bob确定两个大素数n和g，这两个大整数不必保密，Alice和Bob可以用不安全信道确定这两个数。
设n=11，g=7
（2）Alice选择另一个大随机数x，并如下计算A：
$A=g^x\ mod\ n$
设x=3，那么 $A=7^3\ mod\ 11=343\ mod\ 11=2$
（3）Alice将A发送给Bob。
Alice将2发送给Bob
（4）Bob选择另一个大随机数y，并如下计算B：
$B=g^y\ mod\ n$
设y=6，那么 $A=7^6\ mod\ 11=117649\ mod\ 11=4$
（5）Bob将B发送给Alice。
Bob将4发送给Alice
（6）计算秘密密钥K1如下：
$K1=B^x\ mod\ n$
有 $K1=4^3\ mod\ 11=64\ mod\ 11=9$
（7）计算秘密密钥K2如下：
$K2=A^y\ mod\ n$
有 $K2=2^6\ mod\ 11=64\ mod\ 11=9$

4.数学理论知识

Diffine-Hellman密钥交换协议/算法的安全性在于，在有限域中的离散对数计算难度比同一个域中的指数计算难得多。下面用简单的术语来解释这个含义：
（a）首先看看Alice的工作，Alice计算：
$K1=B^x\ mod\ n$
$B=g^y\ mod\ n$
如果把B带入K1计算公式中，则得到下列方程：
$K1=(g^y)^x\ mod\ n=g^{yx} \ mod\ n$
（b）再看看Bob的工作，Bob计算：
$K2=A^y\ mod\ n$
$A=g^x\ mod\ n$
如果把A带入K2计算公式中，则得到下列方程：
$K2=(g^x)^y\ mod\ n=g^{yx} \ mod\ n$
因此有K1=K2=K

5.算法的工作原理

Alice和Bob共享对称密钥由三部分组成：g，x和y，如下图所示：
在这里插入图片描述
密钥g的第一部分是一个公开数字，该密钥的其他两个部分（即x和y）必须只有Alice和Bob才知道。Alice负责添加第二部分（x），而Bob添加的是第三部分（y）。尽管Alice的密钥生成是按照g-y-x的顺序，而Bob的密钥则是按照g-x-y的顺序，这两个密钥是相同的，因为 $g^{xy}=g^{yx}$ 。

6.算法实现

其算法的python代码如下：

#Diffine-Hellman密钥交换协议/算法
import math
import random
#判断是否是素数
def is_prime(p):
    #p小于1不是素数
    if p<=1:
        return False
    i=2
    #如果小于根号p的整数，不能整除p，则为素数
    while i*i<=p:
        #判断是否能整除
        if p%i==0:
            return False
        i+=1
    return True
#生成随机数函数
def random_data(n):
    #获得随机整数
    randomdata=random.randint(2, n)
    return randomdata
#得到计算数
def Calculation_number(g,n,z):
    #指数的实现
    number=(g**z)%n
    return number
#计算秘密密钥
def Compute_key(g,n,z):
    #指数的实现
    k=(g**z)%n
    return k
#主函数
if __name__ == "__main__":
    #标志位
    flag=False
    #循环，直到n是一个素数
    while flag==False:
        print('请输入素数n: ',end = '')
        n=input()
        n =int(n)
        flag=is_prime(n)
    #重新设置标志位
    flag=False
    #循环，直到g是一个素数
    while flag==False:
        print('请输入素数g: ', end = '')
        g = input()
        g = int(g)
        flag=is_prime(g)
    #生成大随机数   
    x=random_data(n)
    #x=3
    print('Alice选择的随机数为：',x)
    y=random_data(g)
    #y=6
    print('Bob选择的随机数为：',y)
    #得到Alice和Bob的计算数
    A=Calculation_number(g,n,x)
    print('Alice的计算数为：',A)
    B=Calculation_number(g,n,y)
    print('Bob的计算数为：',B)
    #计算Alice得到密钥
    K1=Compute_key(B,n,x)
    print('Alice生成的密钥为：',K1)
    #计算Bob得到密钥
    K2=Compute_key(A,n,y)
    print('Alice生成的密钥为：',K2)

运行的结果图如下：
在这里插入图片描述

7.算法的问题

Diffine-Hellman密钥交换协议/算法并没有解决了所有的密钥交换问题，此算法可能会受到中间人攻击或者桶队攻击，其工作过程如下：
在这里插入图片描述
Tom截获了从Alice发送给Bob的值A，并将自己的A发送给Bob；Tom截获了从Bob发送给Alice的值B，并将自己的B发送给Alice，这里Tom需要两个密钥，这是因为，一方面Tom需要用共享对称密钥与Alice安全通信，另一方面Tom要用另一个共享对称密钥与Bob安全通信。可以看出，可以用中间人攻击破解Diffine-Hellman密钥交换协议/算法，使其失败，因为中间人攻击使通信双方以为互相通信，而实际上是中间人与他们通信。