RSA密钥生成函数运行异常：大素数输入后程序终止

问题现象 #

输入小素数（如p=7、q=11）时，程序能正常输出公钥与私钥；但输入较大素数（如p=67、q=83）时，程序仅打印e的值后就停滞，无法输出密钥，云环境测试问题依旧。

原代码 #

import random
import math

def create_key_set():
    p = int(input('Insert prime number for value of p: '))
    q = int(input('Insert new prime number for value of q: '))
    N = p * q
    y = (p-1) * (q-1)
    while True:
        cop = random.randint(2, y-1)
        gcd = math.gcd(cop, y)
        if gcd == 1:
            break
    e = cop
    print(e)
    pubkey = [e, N]
    while True:
        d = random.randint(1, 150)
        g, x = divmod((e*d), y)
        if x == 1:
            break
    print(d)
    privkey = [d, N]
    print('Public Key is: ', pubkey)
    print('Private Key is: ', privkey)

问题排查 #

1. 私钥生成逻辑致命缺陷：当前代码限制d在1-150之间随机查找，但根据RSA定义，d是e在模y下的乘法逆元，必须满足(e*d) mod y = 1。当y=(67-1)*(83-1)=5412时，e和y互质，逆元d必然存在，但d的取值范围是1到y-1（即5411），远大于150，导致循环永远找不到符合条件的d，程序陷入无限循环，并非计算资源不足问题。
2. 随机查找效率极低：即使小素数场景能偶然命中d，这种随机枚举的方式在y较大时完全不可行，时间复杂度为O(n)，极端情况会一直卡住。

优化建议 #

1. 用扩展欧几里得算法求逆元：这是计算乘法逆元的标准高效方法，时间复杂度O(log y)，能快速求出合法的d，彻底解决无限循环问题。
2. 增加素数合法性校验：原代码未验证输入的p、q是否为素数，若输入非素数会直接破坏RSA的数学基础，必须添加校验逻辑。
3. 优化e的生成逻辑：可以固定选择常用的e值（如65537），该值既满足与y互质的要求，又能提升加密效率，避免随机生成的开销。

优化后的代码 #

import math
import random

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 extended_gcd(a, b):
    # 扩展欧几里得算法，用于求乘法逆元
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

def mod_inverse(a, m):
    # 计算a在模m下的乘法逆元
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # RSA场景下e和y互质，不会触发此情况
    else:
        return x % m

def create_key_set():
    # 输入并校验素数p
    while True:
        p = int(input('Insert prime number for value of p: '))
        if is_prime(p):
            break
        print("输入不是素数，请重新输入。")
    
    # 输入并校验素数q（需与p不同）
    while True:
        q = int(input('Insert new prime number for value of q: '))
        if is_prime(q) and q != p:
            break
        print("输入不是合法素数（需与p不同），请重新输入。")
    
    N = p * q
    y = (p - 1) * (q - 1)
    
    # 优先使用常用e值65537，若不互质则随机生成
    e = 65537
    while math.gcd(e, y) != 1:
        e = random.randint(2, y-1)
    
    # 用扩展欧几里得算法快速求d
    d = mod_inverse(e, y)
    
    pubkey = (e, N)
    privkey = (d, N)
    
    print('Public Key is: ', pubkey)
    print('Private Key is: ', privkey)

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