Challenge

RSA 暗号で素数を使い回すことにしました!

import os
from Crypto.Util.number import getPrime, bytes_to_long

flag = os.environ.get("FLAG", "Alpaca{****** REDACTED ******}").encode()
assert len(flag) == 30

p = getPrime(128)
n = p * p  # !?

e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

The modulus is not p*q, but a prime square: n = p^2.

Solution

Since n = p^2, we can recover p immediately by:

p = isqrt(n)

For prime powers:

$\phi(p^2)=p^2-p=p(p-1)$

Then standard RSA steps work:

1. Compute $d= e^{-1} \mod \phi$
2. Recover $m=c^{-1} \mod n$

Final Script

import math
from Crypto.Util.number import *
n = 66579369096057840799275275806551056825754855027296356876541315429102104919401
p = math.isqrt(n)
phi = p*(p-1)
e = 65537
d = pow(e, -1, phi)
c = 23240514848563033397887056861198100244595942784363115352574337396646368790635
m = pow(c, d, p*p)
print(long_to_bytes(m))