为什么我的 p、q、e = 3 的 RSA 值会导致解密失败？

Question

实际上我正在尝试解决密码集 5 挑战 39。我正在尝试为一些更大的素数 p 和 q，e = 3 实施 RSA。我一直对此感到困惑小时.

为了生成素数，我正在点击 API 来获取每个素数。我一直生成 p 直到 gcd(p - 1, e) == 1，然后重复生成 q 直到 gcd(q - 1, e) == 1。我测试了 gcd((p - 1) * (q - 1), e) == 1 也是。例如，我最终得到 p == 16226322033026808497，而 q == 14712923008023747557.

然后我进行简单的 RSA 数学运算来计算其他项，加密消息 42（无填充），解密该密码，并将生成的明文与原始消息进行比较。我已经生成了很多很多 ps 和 qs，但它从来没有匹配过。

有人可以解释为什么这不起作用，并帮我生成一些好的参数吗？

Python:

p = 16226322033026808497
q = 14712923008023747557
e = 3
print(f'1 == gcd(p - 1, e) == {gcd(p - 1, e)}')
print(f'1 == gcd(p - 1, e) == {gcd(q - 1, e)}')

phi = (p - 1) * (q - 1)
print(f'phi == {phi}')
print(f'1 == gcd(phi, e) == {gcd(phi, e)}')
n = p * q
print(f'n == {n}')
d = invmod(e, phi)
print(f'd == {d}')
print(f'1 == (d * e) % phi == {(d * e) % phi}')

m = 42
c = pow(m, e, n);
print(f'c == m**e % n == {c}')
p = pow(c, d, n);
print(f'p == c**d % n == {p}')

输出：

1 == gcd(p - 1, e) == 1
1 == gcd(p - 1, e) == 1
phi == 238736626775322802092761613952260035776
1 == gcd(phi, e) == 1
n == 238736626775322802123700858993310591829
d == 159157751183548534728507742634840023851
1 == (d * e) % phi == 1
c == m**e % n == 74088
p == c**d % n == 145835535613124975159078105657928869819

Answer 1

我用来生成质数的API实际上是合成的，这阻止了有意义的解密。使用更可靠的来源生成，例如，我发现 p == 18015945217661527751、q == 11788823512629961979 实际上是质数。我现在可以成功解密回原始消息。

我发现 https://asecuritysite.com/encryption/random3 给出了一些合理的素数。

为什么我的 p、q、e = 3 的 RSA 值会导致解密失败？

Why do my RSA values for p, q, e = 3 result in unsuccessful decryption?

python

rsa