Python手动实现RSA加密算法解密结果随机失败问题求助

核心问题定位 #

• 第一处致命错误：sec_rand() 函数仅保证生成3位奇数，完全没有做质数校验。RSA算法要求prime1、prime2必须为质数，只有当你随机生成的两个奇数恰好都是质数时，解密才会得到正确结果，其余情况密钥计算完全错误，这就是你解密结果随机错误的直接原因。
• 第二处潜在错误：公钥e必须和卡迈克尔函数输出ntotient互质，你当前固定使用65537作为公钥，若生成的ntotient和65537存在公共因子，会导致模逆计算失败，解密直接报错。
• 第三处可优化点：加解密时可以直接使用Python内置的三参数pow(base, exp, mod)，比先算幂再取模的效率高得多，也避免大整数运算的性能损耗。

修复后完整代码 #

所有逻辑均自主实现，未引入第三方RSA相关库，符合学习需求：

#! /usr/bin/python3
from random import SystemRandom
from string import digits
from math import gcd

# 新增小质数校验函数，无第三方依赖
def is_prime(n):
    if n <= 1:
        return False
    if n <=3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i+2) == 0:
            return False
        i += 6
    return True

def lcm(x, y):
    return x*y // gcd(x,y)

def modinv(x, y):
    try:
        inverted = pow(x, -1, y)
        return inverted
    except ValueError:
        raise ValueError('无法计算模逆，公钥和totient不互质')

def sec_rand_prime():
    sys_rand = SystemRandom()
    while True:
        # 生成3位奇数
        x = int(''.join(sys_rand.choice(digits) for _ in range(3)))
        if x % 2 == 0:
            continue
        # 新增质数校验
        if is_prime(x):
            return x

def encrypt(message, public_key, n):
    # 改用三参数pow提升效率
    return pow(message, public_key, n)

def decrypt(private_key, crypted, n):
    # 私钥提前计算，避免每次解密重复生成模逆
    return pow(crypted, private_key, n)

def main():
    prime1 = sec_rand_prime()
    prime2 = sec_rand_prime()
    # 避免两个质数相同
    while prime1 == prime2:
        prime2 = sec_rand_prime()
    print("Prime 1: " + str(prime1))
    print("Prime 2: " + str(prime2))
    n = prime1 * prime2
    ntotient = lcm(prime1 - 1, prime2 - 1)
    plaintext = 59 
    e = 65537 # Public Key
    # 校验公钥和totient互质，不互质则重新生成质数对
    while gcd(e, ntotient) != 1:
        prime1 = sec_rand_prime()
        prime2 = sec_rand_prime()
        while prime1 == prime2:
            prime2 = sec_rand_prime()
        n = prime1 * prime2
        ntotient = lcm(prime1 - 1, prime2 - 1)
    # 提前计算私钥
    private_key = modinv(e, ntotient)
    print("Plaintext: " + str(plaintext))
    encrypted = encrypt(plaintext, e, n)
    print("Encrypted: " + str(encrypted))
    decrypted = decrypt(private_key, encrypted, n)
    print("Decrypted: " + str(decrypted))

if __name__ == "__main__":
    main()

内容的提问来源于stack exchange，提问作者aspiringlearner