1.Diffie-Hellman
密钥交换算法
(
1
)有两个全局公开的参数,一个素数
p
和一个整数
a
,
a
是
p
的一个原根(对于正整数
gcd(a,m)=1
,如果
a
是模
m
的原根,那么
a
是整数模
m
乘法群的一个生产元);
(
2
)假设用户
A
和
B
希望交换一个密钥,用户
A
选择一个作为私有密钥的随机数
XA<p
,并计算公开密钥YA = a^XA mod p
,
A
对
XA
的值保密存放而使
YA
能被
B
公开获得。类似地,用户
B
选择一个私有的随机数
XB<p
,并计算公开密钥YB = a^XB mod p
。
B
对
XB
的值保密存放而使
YB
能被
A
公开获得。
(
3
)用户
A
产生共享秘密密钥的计算方式是K = (YB)^XA mod p
。同样,用户
B
产生共享秘密密钥的计算是K = (YA)^XB mod p
。这两个计算产生相同的结果.
因此相当于双方已经交换了一个相同的秘密密钥。
2.
关于原根的生成
在求解原根的时候采用的是暴力求解的方法,按照的规定就是
a
是
p
的原根,就是a^(p - 1) = 1(mod p)
当且仅当指数为
p-1
的时候成立,所以我使用的办法就是取a在[2, p-1]之间进行取值
,若是其中有满足上述式子的
a
则放到列表中,最后在自动生成原根的时候是人为的取得最大的那个数值作为原根。
例如当
p = 7
时,
a
从
2
开始取值,因为2^3 = 1(mod 7)
,3!=6,
所以
2
不是
p
的原根;
当
a = 3
时,3^1 = 3(mod 7),3^2 = 3(mod 7),3^3 = 6(mod 7),3^4 = 4(mod 7),3^5 = 5(mod 7),3^6 = 1(mod 7)
所以
p = 7
的一个原根就是
3
,同样的道理可以求出
p
的所有的原根。
3.
密钥交换协议小例子
假设密钥交换基于素数p
= 97
和
97
的一个原根
a = 5
。
A
和
B
分别选择私有密钥
XA = 36
和
XB = 58
。每人计算其公开密钥
YA = 536 = 50 mod 97
YB = 558 = 44 mod 97
在他们相互获取了公开密钥之后,各自通过计算得到双方共享的秘密密钥如下:
从
[50, 44]
出发,攻击者要计算出
75
很不容易。
4.
算法实现流程
(
1
)提示用户输入一个素数
p
,判断用户输入是否为素数,若是则生成其生成元
a
,若不是则提示用户继续输入,直到输入符合要求为止;
(
2
)定义函数
judge_prime
判断用户输入是否为素数;
(
3
)定义函数
get_generator
来得到
p
的生成元
a
;
(
4
)
A,B
各自选择小于
p
随机数作为自己的私钥
XA
,
XB
,并根据
得到各自的计算数;
(5)
交换彼此的计算数;
(6)
对对方交换的数进行计算,若是得到的结果相同则是公共密钥。
5.
算法的设计流程图
6.运行结果
import math
import random
def judge_prime(p):
#素数的判断
if p <= 1:
return False
i = 2
while i * i <= p:
if p % i == 0:
return False
i += 1
return True
def get_generator(p):
#得到所有的原根
a = 2
list = []
while a < p:
flag = 1
while flag != p:
if (a ** flag) % p == 1:
break
flag += 1
if flag == (p - 1):
list.append(a)
a += 1
return list
#A,B得到各自的计算数
def get_calculation(p, a, X):
Y = (a ** X) % p
return Y
#A,B得到交换计算数后的密钥
def get_key(X, Y, p):
key = (Y ** X) % p
return key
if __name__ == "__main__":
#得到规定的素数
flag = False
while flag == False:
print('Please input your number(It must be a prime!): ', end = '')
p = input()
p = int(p)
flag = judge_prime(p)
print(str(p) + ' is a prime! ')
#得到素数的一个原根
list = get_generator(p)
print(str(p) + ' 的一个原根为:', end = '')
print(list[-1])
print('------------------------------------------------------------------------------')
#得到A的私钥
XA = random.randint(0, p-1)
print('A随机生成的私钥为:%d' % XA)
#得到B的私钥
XB = random.randint(0, p-1)
print('B随机生成的私钥为:%d' % XB)
print('------------------------------------------------------------------------------')
#得待A的计算数
YA = get_calculation(p, int(list[-1]), XA)
print('A的计算数为:%d' % YA)
#得到B的计算数
YB = get_calculation(p, int(list[-1]), XB)
print('B的计算数为:%d' % YB)
print('------------------------------------------------------------------------------')
#交换后A的密钥
key_A = get_key(XA, YB, p)
print('A的生成密钥为:%d' % key_A)
#交换后B的密钥
key_B = get_key(XB, YA, p)
print('B的生成密钥为:%d' % key_B)
print('---------------------------True or False------------------------------------')
print(key_A == key_B)
1.Diffie-Hellman密钥交换算法(1)有两个全局公开的参数,一个素数p和一个整数a,a是p的一个原根(对于正整数gcd(a,m)=1,如果a是模m的原根,那么a是整数模m乘法群的一个生产元);(2)假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA,并计算公开密钥YA = a^XA mod p,A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选
d1 = pyDH . DiffieHellman ()
d2 = pyDH . DiffieHellman ()
d1_pubkey = d1 . gen_public_key ()
d2_pubkey = d2 . gen_public_key ()
d1_sharedkey = d1 . gen_shared_key ( d2_pubkey )
d2_sharedkey = d2 . gen_shared_key ( d1_pubkey )
d1_sharedkey == d2_sharedkey
默认情况下,它使用组 14(2048 位)。 使用另一个组(例如,15):
d1 = pyDH . DiffieHellman (
1、Diffie-Hellman算法简介
Diffie-Hellman算法(以下简称为:DH算法),是最早的密钥交换算法之一,它使得通信的双方能在非安全的信道中安全的交换密钥,用于加密后续的通信消息。
起基本流程原理如下:
假定小明和小红期望在一个不安全的网络中协商一个共同的密钥,那么进行如下步骤:
两人先说好大素数(质数)p和它的原始根g。
小明随机产生一个数a,并计算A = p^a mod g, 发送给小红。
小红随机产生一个数b,并计算......
1.实施RSA加密方案。
加密应用程序:用户输入文本(.txt)和公共密钥。 该应用程序通过RSA加密方案返回加密的文本(.txt)。
解密的应用:用户输入文本(加密的.txt)和您的私钥。 该应用程序返回解密的文本(.txt)。
2.通过RSA实施数字签名。
签名应用程序:用户输入文本(.txt)并使用您的私钥。 应用程序返回文本(另一个.txt)。
签名验证应用程序:用户输入一个文本(.txt),在该文本(.txt)上输入一个签名,然后输入签名者的公钥。 应用程序返回“是”(签名有效)或“否”(签名无效)。
3.实施Di? E-Hellman分配方案。
让我们假设A
DH-度娘版
算法描述
假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA(XA<q),并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选择一个私有的随机数XB<q,并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得。
看完感觉懵懵的
——来自度娘的例子
密钥交换基于素数q = 97和97
Diffie-Hellman密钥交换是一种公开密钥加密算法,用于在不安全的通信渠道上交换密钥。它是由惠特菲尔德·迪菲和马丁·赫尔曼·赫尔曼于1976年共同发明的。
Diffie-Hellman密钥交换算法基于离散对数问题,假设存在一个质数p和一个整数g,使得g是模p的原根。通信双方Alice和Bob分别选择一个私有密钥a和b,然后计算出公开的值A和B。然后,Alice和Bob分别使用对方的公开值和自己的私有密钥计算出一个共享的密钥K。这个共享的密钥K可以用于对后续通信进行加密。
Diffie-Hellman密钥交换算法的优点是,它使用了公开密钥和私有密钥,避免了传统的密钥交换算法中需要通过一个安全的渠道交换密钥的问题。同时,它也避免了使用相同的密钥对所有通信进行加密的问题。