Roll Your Own

cryptohack

Task: a discrete-log 'prove me wrong' game. Server picks a 512-bit prime q, you submit (g,n) with pow(g,q,n)==1, it returns h=pow(g,x,n) for a secret x in [0,q] and asks you to recover x. Solution: choose n=q^2 and g=1+q (the Paillier generator). Then pow(g,q,n)=(1+q)^q = 1 mod q^2 (binomial higher terms vanish), and g^x = 1 + q*x mod q^2, so the discrete log is linear: x = ((h-1)//q) mod q. Submit x and get the flag.