|
1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。算法用他们三个人的名字命名，叫做 RSA 算法。直到现在，RSA 算法仍是最广泛使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。
生成秘钥
选取大素数\(p,q\);计算\(n=pq\)以及n的欧拉函数\(φ(n) = φ(p) φ(q)=(p-1)(q-1)\)。
选择一个\(e(1= 1
a = a * a % n
return d
def make_key(p, q, e):
"""
生成公私钥
参数1：大素数p
参数2：大素数q
参数3：随机生成e，满足 gcd(e,fin)
返回值：[公钥,私钥]-------[[n,e],[n,d]]
"""
n = p * q
fin = (p-1) * (q-1)
d = ex_gcd(e, fin)[0] # 辗转相除法求逆(广义欧几里得)
while d < 0:
d = (d+fin) % fin
return [[n, e], [n, d]]
def encryption(key, data):
"""
加密
参数1：列表[n,e]----公钥
参数2：待价密数据
返回值：密文
"""
n, e = key
plaintext = list(data)
ciphertext = []
for item in plaintext:
ciphertext.append(fast_expmod(ord(item), e, n))
return ciphertext
def decrypt(key, ciphertext):
"""
解密
参数1：key为私钥
参数2：密文数据
返回值：明文
"""
n, d = key
plaintext = ''
for item in ciphertext:
plaintext += (chr(fast_expmod(item, d, n)))
return plaintext
def make_p_q_e():
"""
返回值：[p,q,e]
"""
p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
e = 65537
return [p, q, e]
def test():
p, q, e = make_p_q_e()
# 获取数据
plaintext = input("待加密数据：")
# 公钥、私钥
public_key, private_key = make_key(p, q, e)
# 加密
ciphertext = encryption(public_key, plaintext)
print("加密后的数据：", ciphertext)
# 解密
plaintext = decrypt(private_key, ciphertext)
print("解密后的数据：", plaintext)
test()
|