Python实现RSA时模运算结果异常的技术求助

问题描述 #

用Python实现RSA算法时，计算C = M^d mod n得到结果43，但手动计算应为63；解密后无法得到原明文，参数确认无误但结果异常。

原代码 #

import numpy as np

def solve_diophantine_eqn(a: int, b: int, d: int):
    '''
    Solving ax + by = d, where a, b and d are given. \
    Solving for x and y, where d is multiple of gcd(a, b)
    '''
    d_sol_gcd, d_sol_0 = apply_extended_euclidean(np.array((a, 1, 0)), np.array((b, 0, 1)))
    if d == 0:
        return d_sol_0[1], d_sol_0[2]
    return d_sol_gcd[1:] * d // d_sol_gcd[0]

def apply_extended_euclidean(a: np.ndarray, b: np.ndarray, d = 1):
    '''
    Solving ax + by = d, where a, b and d are given \
    Solving for x and y, where d is multiple of gcd(a, b) \
    Default case stopping at d = 0, because 0 is multiple of every integer
    '''
    if b[0] < d:
        return a, b
    q = a[0] // b[0]
    return apply_extended_euclidean(b, a - q*b, d)

message = 7
p = 11                                      # Select any large prime p
q = 7                                       # Select any large prime q
n = p * q                                   # Let large natural number n be p*q
t_n = (p-1)*(q-1)                           # theta(n) is euler totient of n
e = t_n - 1                                 # e is coprime with theta(n)
d, _ = solve_diophantine_eqn(e, t_n, 1)     # Solve equation e*d + theta(n) * y = 1
d = d % t_n                                 # If d < 0, make d positive
print(d)
public_key = (e, n)
private_key = (d, n)
print(public_key)
print(private_key)
plaintext = message
print(plaintext)
ciphertext = plaintext ** d % n
print(ciphertext)
recievedtext = ciphertext ** e % n
print(recievedtext)

程序输出 #

59
(59, 77)
(59, 77)
7
43
63

错误原因及修复 #

1. 加密解密逻辑完全颠倒 #

RSA的核心规则是：

• 加密：用公钥(e, n)，即 密文 = 明文^e mod n
• 解密：用私钥(d, n)，即 明文 = 密文^d mod n

原代码错误地使用私钥指数d加密，公钥指数e解密，导致结果完全错误。

修复代码：

# 修正加密解密逻辑
ciphertext = plaintext ** e % n  # 公钥加密
recievedtext = ciphertext ** d % n  # 私钥解密

修正后，加密结果应为63，解密后得到原明文7。

2. 扩展欧几里得算法终止条件错误 #

apply_extended_euclidean函数的终止条件if b[0] < d:不符合扩展欧几里得算法的要求，该算法应在余数为0时停止（即b[0] == 0）。当前条件在某些场景下会导致计算出的最大公约数（gcd）错误，进而影响模逆元d的正确性。

修复代码：

def apply_extended_euclidean(a: np.ndarray, b: np.ndarray, d = 1):
    '''
    Solving ax + by = d, where a, b and d are given \
    Solving for x and y, where d is multiple of gcd(a, b) \
    Default case stopping at d = 0, because 0 is multiple of every integer
    '''
    # 修正终止条件：当余数为0时返回
    if b[0] == 0:
        return a, b
    q = a[0] // b[0]
    return apply_extended_euclidean(b, a - q*b, d)

3. 额外优化建议 #

• 避免使用numpy数组处理小整数运算，直接用Python原生int即可，减少不必要的复杂度。
• 模幂运算可使用Python内置的pow函数，效率更高：pow(plaintext, e, n) 等价于 plaintext**e %n，但对于大指数运算性能提升明显。

最终修正后的完整代码 #

def solve_diophantine_eqn(a: int, b: int, d: int):
    '''
    Solving ax + by = d, where a, b and d are given. 
    Solving for x and y, where d is multiple of gcd(a, b)
    '''
    d_sol_gcd, d_sol_0 = apply_extended_euclidean((a, 1, 0), (b, 0, 1))
    if d == 0:
        return d_sol_0[1], d_sol_0[2]
    return (d_sol_gcd[1] * d // d_sol_gcd[0], 
            d_sol_gcd[2] * d // d_sol_gcd[0])

def apply_extended_euclidean(a: tuple, b: tuple):
    '''
    Solving ax + by = d, where a, b and d are given 
    Solving for x and y, where d is multiple of gcd(a, b) 
    '''
    if b[0] == 0:
        return a, b
    q = a[0] // b[0]
    # 计算新的余数和系数，用原生tuple代替numpy数组
    new_a = b
    new_b = (a[0] - q*b[0], a[1] - q*b[1], a[2] - q*b[2])
    return apply_extended_euclidean(new_a, new_b)

message = 7
p = 11
q = 7
n = p * q
t_n = (p-1)*(q-1)
e = t_n - 1
d, _ = solve_diophantine_eqn(e, t_n, 1)
d = d % t_n

public_key = (e, n)
private_key = (d, n)

print("d:", d)
print("公钥:", public_key)
print("私钥:", private_key)

plaintext = message
print("明文:", plaintext)

# 用pow优化模幂运算，修正加密逻辑
ciphertext = pow(plaintext, e, n)
print("密文:", ciphertext)

# 修正解密逻辑
recievedtext = pow(ciphertext, d, n)
print("解密后明文:", recievedtext)

运行结果 #

d: 59
公钥: (59, 77)
私钥: (59, 77)
明文: 7
密文: 63
解密后明文: 7

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