python - p==q 时的 RSA 加密

Question

两天前我参加了 DawgCTF。我正要解决 RSA 问题，但我无法解决。

DawgCTF 的 RSA 问题给出了 n、e、c。

所以，我使用 factordb 对 n 进行因式分解，n 的结果是只有一个素数的平方。（即 n=p^2）
我从未见过 p 和 q 在 RSA Crypto 中相同的情况。无论如何，我让 phi 为 (p-1)(q-1) 并编写如下代码。（phi 表示欧拉的 phi）

from Crypto.Util.number import inverse, long_to_bytes
import string

n = ~~~ 
e = 65537
c = ~~~
p = ~~~ # I omit q because p==q


phi = (p-1) * (p-1)
d = inverse(e, phi)
m = pow(c, d, n)

m = long_to_bytes(m)
print(m)

但是，没有用！！！

在 CTF 之后，我找了一篇文章，其中他没有将 phi 设置为 (p-1)^2，而是 p*(p-1)。但是，我不知道为什么......为什么当 p==q 时 phi 应该是 p*(p-1)？

如果您能解释一下，我将不胜感激。

标签： pythoncryptographyrsactf

Answer 1

第一个等号phi(p * q) = phi(p) * phi(q) = (p - 1) * (q - 1)假设p和q是互质的（参见[1]），而第二个等号假设p和q是素数（参见[2]，k = 1）。p = q违反了第一个条件，这就是为什么这种关系对无效p = q。

另一方面，对于k = 2，它来自[2] phi(p * p) = p * (p - 1)，即 CTF 解决方案中使用的关系p = q。

然而，对于 RSA 在实践中，这p != q是一个先决条件，请参阅[3]和[4]（否则p可以q很快确定：）p = q = sqrt(N)。