D-H密钥协商协议与EIGamal算法

D-H密钥协商协议

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

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

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

• 由协议双方A和B先协商好大素数$p$以及$p$的原根$G$，并且公开这两个值
• A取一个私钥$a$，发送给B计算结果$A=G^a \mod {p}$
• 类似的，B取一个私钥$b$发给A计算结果$B=G^b\ mod\ {p}$
• A计算出$S=B^a\mod{p}=(g^b)^a\mod{p}=g^{ab}\mod{p}$
• B也能计算出$S=A^b\mod{p}=(g^a)^b\mod{p}=g^{ab}\mod{p}$
• A与B得到共享密钥$S$

python实现如下：

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算法

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

密钥生成

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

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

加密

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

• 用户B要发送消息$M$给A，先将$M$映射到循环群$G$中得到$m$
• B从$[2,p-2]$中随机选择一个$k$，计算$c_1=g^k\mod{p}$
• B计算$c_2=m*y^k\mod{p}$
• 发送密文$(c_1,c_2)$给A

解密

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

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

python实现如下：

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()