p==q 时的 RSA 加密

RSA crypto when p==q

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

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

所以,我用factordb对n进行了因式分解,n的结果是只有一个素数的平方。(即n=p^2)
我从未见过 RSA Crypto 中 p 和 q 相同的情况。 无论如何,我让 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之后,我找了一篇write-up,他没有把phi写成(p-1)^2,而是p*(p-1)。 但是,我不知道为什么... 为什么当 p==q 时 phi 应该是 p*(p-1)?

如果你能解释一下,我将不胜感激。

phi(p * q) = phi(p) * phi(q) = (p - 1) * (q - 1) 中的第一个等号假定 pq 互质(参见 [1]), while the second equal sign assumes that p and q are prime (see [2]k = 1)。 p = q 违反了第一个条件,这就是为什么这个关系 p = q 无效

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

然而,对于 RSA 在实践中,p != q 是先决条件,参见 [3] and [4](否则可以快速确定 pqp = q = sqrt(N) ).