# 计算a在模m下的乘法逆元
# 乘法逆元是指对于整数a和模数m,存在一个整数x,使得(a * x) % m = 1
def modinv(a, m):
m0, x0, x1 = m, 0, 1
while a > 1:
# 计算商q,a%m是余数
q = a // m
m, a = a % m, m
x0, x1 = x1 - q * x0, x0
return x1 + m0 if x1 < 0 else x1
modinv(a, m)
接收两个参数 a 和 m,分别代表乘法逆元的基数和模数。q = a // m
,将 a 除以 m 的商保存在变量 q 中。m, a = a % m, m
。m 更新为 a 对 m 取余的结果,a 更新为之前的 m。x0, x1 = x1 - q * x0, x0
。根据扩展欧几里德算法的公式更新 x0 和 x1。# 生成密钥函数
def generate_key(p, q, e):
n = p * q
fyn = (p - 1) * (q - 1)
d = modinv(e, fyn)
# print(d)
return ((n, e), (n, d))
# 加密函数
def encrypt(public_key, plaintext):
n, e = public_key
# C = M^e mod n
ciphertext = pow(plaintext, e, n)
return ciphertext
# 解密函数
def decrypt(private_key, ciphertext):
n, d = private_key
# M = C^d mod n
plaintext = pow(ciphertext, d, n)
return plaintext
# 测试数据
data = [
{'p': 3, 'q': 11, 'e': 7, 'M': 5},
{'p': 5, 'q': 11, 'e': 3, 'M': 9},
{'p': 7, 'q': 11, 'e': 17, 'M': 8},
{'p': 11, 'q': 13, 'e': 11, 'M': 7},
{'p': 17, 'q': 31, 'e': 7, 'M': 2}
]
# 对每组数据进行加密与解密
for d in data:
p, q, e, M = d['p'], d['q'], d['e'], d['M']
public_key, private_key = generate_key(p, q, e)
encrypted_text = encrypt(public_key, M)
decrypted_text = decrypt(private_key, encrypted_text)
print(f"原始数据: {M}, 加密后: {encrypted_text}, 解密后: {decrypted_text}")