RSA密钥生成、签名及验证未达预期结果，代码问题排查求助

问题根源分析与修正 #

1. 私钥d的计算逻辑错误 #

RSA中，私钥d是公钥e在模φ(n)下的乘法逆元，而非你当前代码中计算的e^(φ(n)-1) mod n。你混淆了模运算的模数，正确的模数应该是φ(n)，而非n。

修正方式：

替换generate_RSA_keys函数中d的计算代码，改为求e的模φ(n)逆元。可以选择使用Python内置的pow函数（支持求逆元），或者自己实现扩展欧几里得算法：

方法一：使用内置pow函数

def generate_RSA_keys(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    # 计算e在模phi下的逆元
    d = pow(e, -1, phi)
    return e, d, n

方法二：自己实现扩展欧几里得求逆元

def mod_inverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x += m0
    return x

def generate_RSA_keys(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return e, d, n

2. 签名验证的比较逻辑错误 #

• 你使用了is运算符比较数值，is用于判断对象身份是否一致，而非数值相等，应该改用==。
• 根据RSA签名原理，验证时计算得到的signature^e mod n应该等于digest mod n（而非原始digest，当digest大于n时，原始值和模n后的值会不一致）。

修正后的验证函数：

def RSA_signature_verification(message, e, n, signature):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    verification_result = fast_modular_exponentiation(signature, e, n)
    # 比较模n后的结果
    return verification_result == (digest % n)

修正后的完整代码 #

import hashlib

def fast_modular_exponentiation(a, b, n):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % n
        a = (a * a) % n
        b //= 2
    return result

def generate_RSA_keys(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = pow(e, -1, phi)
    return e, d, n

def RSA_signature_generation(message, d, n):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    # 签名前先对digest取模n，避免数值过大
    signature = fast_modular_exponentiation(digest % n, d, n)
    return signature

def RSA_signature_verification(message, e, n, signature):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    verification_result = fast_modular_exponentiation(signature, e, n)
    return verification_result == (digest % n)

# generate RSA keys
e, d, n = generate_RSA_keys(23, 47)

# message to be signed
message = b"hello world"

# generate RSA signature
signature = RSA_signature_generation(message, d, n)

# verify RSA signature
verification = RSA_signature_verification(message, e, n, signature)

print(verification) # 现在输出True

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