RSA Backdoor Viability

cryptohack

Task: RSA where one prime is a special 'complex multiplication' prime p=(D*s^2+1)/4 with D=427, so 4p-1 = 427*s^2 is square-free-times-a-square — a known backdoor enabling fast factorization. Solution: the 4p-1 / Cheng method uses the Hilbert class polynomial for discriminant -427 (class number 2) to recover p from n; in practice the CTF modulus was already factored in factordb (status FF), so we pull p,q, build d = e^{-1} mod phi, and RSA-decrypt the flag.