D-H密钥协商协议

在基于对称加密进行安全通信的过程中，通信双方需要持有一个共享的密钥。只有这样，由任何一方加密的信息才能由另一方使用相同的密钥解密。但是在能够安全的通信之前，通信双方应该如何约定一个共享的密钥呢？这就是安全中的经典问题：密钥配送问题

解决密钥配送问题通常有三种方式：线下约定共享密钥、通过公钥密码体系配送共享密钥、以及Diffie-Hellman密钥交换协议

D-H密钥协商协议是基于离散对数困难问题的密钥交换协议，首先

  • 由协议双方A和B先协商好大素数pp以及pp的原根GG，并且公开这两个值
  • A取一个私钥aa，发送给B计算结果A=Ga mod pA=G^a\ mod\ {p}
  • 类似的，B取一个私钥bb发给A计算结果B=Gb mod pB=G^b\ mod\ {p}
  • A计算出S=Bamod  p=(gb)amod  p=gabmod  pS=B^a\mod{p}=(g^b)^a\mod{p}=g^{ab}\mod{p}
  • B也能计算出S=Abmod  p=(ga)bmod  p=gabmod  pS=A^b\mod{p}=(g^a)^b\mod{p}=g^{ab}\mod{p}
  • A与B得到共享密钥S

python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import math
import random
from Crypto.Util.number import *
 

#求最小原根
def get_generator(n):
    k=(n-1)//2
    for i in range(2,n-1):
        if multimod(i,k,n)!=1:
            return i
        
def multimod(a,k,n):    #快速幂取模
    ans=1
    while(k!=0):
        if k&1:
            ans = (ans * a) % n
        a=(a*a)%n
        k=k>>1
    return ans

if __name__ == "__main__":
	
	#得到规定的素数
    p=getPrime(512)
    print("得到生成的随机素数为："+str(p))
	#得到素数的一个原根
    G = get_generator(p)
    print(str(p) + ' 的一个原根为：'+str(G))
	
	#得到A的私钥
    a = random.randint(0, p-1)
    print('A随机生成的私钥为：',a)
	
	#得到B的私钥
    b = random.randint(0, p-1)
    print('B随机生成的私钥为：',b)
	
	#得到A的公钥
    A=multimod(G,a,p)
    print('A的公钥为：%d'%A)
	
	#得到B的公钥
    B=multimod(G,b,p)
    print('B的公钥为：%d'%B)

    #AB进行公钥交换，攻击者只能获取到两个公钥
    #AB分别用自己的私钥再对对方发来的公钥进行计算

    #交换后A的密钥
    S1 = pow(B,a,p)
    print('A最后得到的密钥：%d'%S1)
    #交换后B的密钥
    S2 = pow(A,b,p)
    print('B最后得到的密钥：%d'%S2)

    #最后计算的结果都是
    #g^ab % p
    #AB完成密钥交换

ElGamal算法

1
该算法与Difffie-Hellman非常类似，ElGamal的系统用户在循环群G内选择一个大素数p，g是p的原根，将p和g公开

密钥生成

  • A从[2,p−2][2,p-2]中选取一个整数xx
  • 计算A的公钥y=gxmod  py=g^x\mod{p}

可以得到私钥xx，公钥为{G，p，g，y{G，p，g，y}}，公开公钥。

加密

B使用A公开的{G，p，g，y{G，p，g，y}}给A发送消息：

  • 用户B要发送消息MM给A，先将MM映射到循环群GG中得到mm
  • B从[2,p−2][2,p-2]中随机选择一个kk，计算c1=gkmod  pc_1=g^k\mod{p}
  • B计算c2=m∗ykmod  pc_2=m*y^k\mod{p}
  • 发送密文(c1,c2)(c_1,c_2)给A

解密

A拿到B发送过来的密文之后

  • 计算B使用的密钥k=c1xmod  pk=c_1^x\mod{p}
  • 由于kk是在循环群内选取的，所可以计算出逆元k−1k^{-1}
  • 计算m=c2∗k−1mod  pm=c_2*k^{-1}\mod{p}

python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import random
from Crypto.Util.number import *
import gmpy2

def e_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = e_gcd(b, a%b)
    return g, y, x-a//b*y  #1.gcd 2.a^-1 mod b 3.b^-1 mod a

#求最小原根
def get_generator(n):
    k=(n-1)//2
    for i in range(2,n-1):
        if multimod(i,k,n)!=1:
            return i
        
def multimod(a,k,n):    #快速幂取模
    ans=1
    while(k!=0):
        if k&1:
            ans = (ans * a) % n
        a=(a*a)%n
        k=k>>1
    return ans

def encrypt(m, p, y,g):
    k = random.randint(1, p - 1)
    C1=multimod(g,k,p)# c1=g^k%p
    #计算m*y^k %p
    C2=(m*multimod(y,k,p)) % p
    return C1,C2,k

def decrypt(C1, C2, x,p):
    s = multimod(C1,x,p)
    s_ = e_gcd(s, p)[1]
    m = C2*s_ % p
    return m
# Driver code
def main():
    m = '1234567'
    print("明文 :", m)

    p = getPrime(512)
    x = random.randint(1, p-1)#私钥

    g = get_generator(p)
    y = multimod(g, x, p)#公钥


    C1, C2, k = encrypt(int(m), p, y, g)
    m_ = decrypt(C1, C2, x, p)
    print("解密后明文 :", m_)
    
    print('p='+str(p))
    print('g='+str(g))
    print('x='+str(x))
    print('k='+str(k))
    print('密文：C1='+str(C1))
    print('C2='+str(C2))


if __name__ == '__main__':
    main()