HappyTown's CrackME_0030

[difficulty: 4][protection: 2nd order polynomial over Zn]

This crackme made me read the "quadratic residue" Wikipedia page AGAIN. One day I might have it memorized :)

You end up having to solve:

C*X^2 + Y^2 = U (mod N)

Where C is constant, U is a number derived from your username, and N is the product of two large primes P and Q. The X and Y are the components of the serial.

First you can randomly produce values for either X^2 or Y^2 and solve for the other. Whatever values you use, you must make sure that they're truly squares (mod N) [thus squares both (mod P) and (mod Q)] using Euler's criterion. Luckily, both P and Q are congruent 3 (mod 4) so we get the easy path in deriving X and Y.

But not so fast! Like "D-Racinez Moi" from decades past, solving for either X or Y must be done in pieces, as the modulus is composite, (one piece for P and one piece for Q). You'll have two answers:

X = <something> (mod P)
X = <something> (mod Q)

As primes, GCD(P,Q) = 1, and that means the Chinese remainder theorem will be making a guest appearance as the final step in generating keys.

Also, author notes that "Public Key algorithm INSIDE." - does anybody recognize this algorithm?