4

I participated in DawgCTF 2 days ago. And I was about to solve RSA problem but I couldn't solve.

DawgCTF's RSA problem was given n, e, c.

so, I factorized n using factordb, and the result of n was the square of only one prime.(That is, n=p^2)
I've never seen a case where p and q are the same in RSA Crypto. Anyway, I let phi be (p-1)(q-1) and wrote the code as below. (phi means Euler's 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)

But, it didn't work!!!

After CTF, I looked for a write-up, in which he did not put phi as (p-1)^2, but p*(p-1). But, I don't know why... Why phi should be p*(p-1) when p==q??

I'd really appreciate it if you could explain.

y J.
  • 131
  • 4

1 Answers1

4

The first equal sign in phi(p * q) = phi(p) * phi(q) = (p - 1) * (q - 1) assumes that p and q are coprime (see [1]), while the second equal sign assumes that p and q are prime (see [2], k = 1). p = q violates the first condition, which is why this relation is not valid for p = q.

On the other hand, for k = 2, it follows from [2] phi(p * p) = p * (p - 1), i.e. the relation used in the CTF solution for p = q.

For RSA in practice, however, p != q is a prerequisite, see [3] and [4] (otherwise p and q could be determined quickly: p = q = sqrt(N)).

Topaco
  • 40,594
  • 4
  • 35
  • 62