RSA加密当p==q时

Question

我两天前参加了DawgCTF比赛。 我当时正在尝试解决RSA问题，但是没有成功。

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

于是，我使用factordb分解了n，结果显示n只有一个质数的平方。（即n=p^2）
在RSA加密中，我从未见过p和q相等的情况。 无论如何，我让phi为(p-1)(q-1)，并按照下面的代码写了程序。(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*(p-1)，而不是(p-1)^2。 但是，我不知道为什么... 当p==q时，为什么phi应该是p*(p-1)？

如果您能解释一下，我会非常感激。

- y J.

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)）。

- Topaco