模拟RSA算法完整计算过程的计算

Question

以下为一道模拟RSA算法完整计算过程的计算题目
(1)取两个素数19和31为源，生成公私钥对，显然其中n＝19*31=589，选取公钥为（29,589）,求对应的私钥；
(2)假定现在有一个用公钥加密的密文为数字123，请解出原本的明文数据a是多少？
(3)验证你的解密计算是否正确：计算a^e(mod 589),若相等，说明(1)(2)的计算正确，并给出本步骤中的计算过程和中间数据；否则，回头查找(1)(2)步计算中存在的错误，排除错误直到等式成立

Answer 1

引自免费微信小程序：皆我百晓生

首先，我们按照要求一步步进行计算。

步骤1：生成公私钥对

给定两个质数p = 19, q = 31，我们可以计算n = p * q = 19 * 31 = 589。

接下来，我们需要选择一个与 (p-1)(q-1) 互质的大于1的整数 e，通常选择一个较小的质数，比如 e = 29。因为 (p-1)(q-1) = (19-1)*(31-1) = 648，29 和 648 是互质的。

步骤2：计算私钥 d

根据 RSA 算法，私钥 d 满足下面的关系：

d ≡ e^-1 (mod φ(n))

其中 φ(n) = (p-1)*(q-1)，即 φ(589) = 648。我们需要找到一个整数 d，使得:

d * e ≡ 1 (mod φ(n))

使用扩展欧几里得算法可以得到 e 的模逆元 d。在 Python 中，我们可以使用 math.gcd 函数来实现这个过程。

下面是 Python 代码示例：

def extended_euclidean(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_euclidean(b, a % b)
        return gcd, y, x - (a // b) * y

# 计算模逆元
phi_n = (p-1)*(q-1)
gcd, d, _ = extended_euclidean(e, phi_n)
d %= phi_n

运行这段代码后，我们会得到 d 的值。

步骤3：加密过程

使用公钥 (e, n) 对明文 a 进行加密，密文 c = a^e mod n。题目中给定的密文是 123，所以我们需要检查是否能通过解密恢复到原始的 a 值。

步骤4：解密过程

使用私钥 (d, n) 解密密文 c，得到明文 a' = c^d mod n。我们将 a' 与原始的 a 值比较，看它们是否相等。

下面是 Python 代码示例：

# 给定的密文
c = 123

# 使用私钥解密
a_prime = pow(c, d, n)

# 检查解密结果
if a_prime == a:
    print("解密正确，原文 a =", a)
else:
    print("解密错误，原文可能不是 a =", a)

将实际的 a 值替换到代码中，然后运行这段代码。如果输出 "解密正确"，那么意味着你在步骤1、步骤2和步骤3中的计算都是正确的。如果输出 "解密错误"，你需要重新检查你的计算，尤其是私钥 d 是否正确。

注意：在这个例子中，由于题目没有提供原始的明文 a，你需要自己设置一个明文 a 来进行测试。例如，你可以尝试设置 a = 123，然后按照上述步骤进行加密和解密操作。如果你的计算正确，最终解密后的 a' 应该等于你开始设置的 a 值。