RSA的实现
1.加密算法
其中public_key是一个元组，格式(e, n)，相应的算法是遍历plainText，将其char值转化为ascii，并通过 c = m ** e mod n来进行加密，
def encrypt(public_key, plainText):
e, n = public_key
templist = []
# 取字符的ascii码来进行加密 c = m ** e mod n
for text in list(plainText):
templist.append(chr(ord(text)**e % n))
cipherText = ''.join(templist)
return cipherText
2.解密算法
类似于加密算法，只是通过 m = ** d mod n 来解密
def decrypt(private_key, cipherText):
d, n = private_key
templist = [chr(ord(text)**d % n) for text in cipherText]
return ''.join(templist)
3.求乘法逆元算法
利用了EGCD算法
def inverse(e, euler):
d = 0
x1 = 0
x2 = 0
y1 = 0
temp = euler
'''
# 利用欧几里德算法求乘法逆元 (x1, x2, x3) = (1, 0, euler) (y1, y2, y3)=(0, 1, e)
# 第一步：Q = x3 / y3
# 第二步：t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
# 第三步: x1, x2, x3 = y1, y2, y3
# 第四步：y1, y2, y3 = t1, t2, t3
# 利用其算法直到 y3 == 1 为止，d = y2
# 若 y3 == 0 不存在逆元
'''
while e > 0:
temp1 = temp / e
temp2 = temp - temp1 * e
temp = e
e = temp2
x = x2 - temp1 * x1
y = d - temp1 * y1
x2 = x1
x1 = x
d = y1
y1 = y
if temp == 1:
return d + euler
4.生成公钥密钥算法
生成的公钥密钥是存储在数组key里面的，其中key[0]是公钥，key[1]是密钥
import random
# 求最大公约数算法
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
def gen(p, q):
n = p * q
euler = (p - 1) * (q - 1)
# generate (e,n)
e = random.randrange(1, euler)
# 确保 e 是在Zn*域中
while gcd(e, euler) != 1:
e = random.randrange(1, euler)
# 求解密密钥d
d = inverse(e, euler)
return [(e, n), (d, n)]
5.签名和验签的实现
这里的加密算法使用了RSA中的加密方式，使用了hashlib中的sha256来生成摘要h(m)，然后再通过私钥加密。
验证里面即是通过相同的h(mes)的计算方法来和signed_text通过公钥解密后的h(m)对比是否相同来确定正确与否。
以下是相关实现代码
import hashlib
#使用了自己的私钥对m摘要的 h(m) 进行加密
def sign(text, private_key):
h = hashlib.sha256()
hashValue = h.update(text).hexdigest()
return encrypt(private_key, hashValue)
def checkSign(signed_text, mes, public_key):
h = hashlib.sha256()
hashValue = h.update(mes).hexdigest()
return (hashValue == decrypt(public_key, signed_text))
Diffie-Hellman秘钥交换协议
这是一个通过共享的素数p和生成元r来生成交换的公钥的函数
# a prime number: p
# a primitive root of p: r
def diffieHellman(p, r, private_key):
"""
:type p: int
:type r: int
:type private_key: int
:rtype: int
"""
return r ** private_key % p
之后就将自身计算得出的公钥发给对方
当得到对方的公钥后，再通过自身的私钥来计算sercet_key
公式是sercet_key = public_key ** private_key % p
def genShareKey(p, private_key, public_key):
"""
:type p: int
:type private_key: int
:type public_key: int
:rtype: int
"""
return public_key ** private_key % p
