# Boston Key Party: El Gamal

If you connected to the El Gamal service, the service asked for an simple captcha (something like this):

It’s easy to solve this problem via brute force

Then it came back with some numbers for El Gamal encryption

If you send two integers it will respond with something like this:

If you guess the number right, it will request again for two numbers and you have to repeat the procedure 64 times. If you guessed all 64 right, you’ll receive the flag.

To solve this, we used the Legendre symbol, we will use it as a function $L(x,p)$, which returns -1 or 1.

So we got $p$, $g$ and $h = g^y$ and the ciphertext $(c_1,c_2)$ which is $(g^y, m\cdot h^y)$.
$h$ is a generator in $p$, therefore is $L(h^y, p) == L(g^y)$. Now we choose our numbers $m_1$ and $m_2$ follow the conditions $L(m_1, p) == 1$ and $L(m_2, p) == -1$.
$L(c_1, p) = L(g^y, p)$ will give the same result as $L(c_2, p) = L(m \cdot h^y, p) = L(m, p) \cdot L(h^y, p)$, if $m$ was $m_1$.

Using this knowledge, we ended up in the following python script.