# Is it possible to perfom quadratic residues attack on elgamal cryptosystem?

I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.

First, some background on Quadratic Residues:

• A Quadratic Residue (QR) is a number $$x$$ such that there exists some number $$y$$ with $$x \equiv y^2 \pmod p$$ (where $$p$$ is the modulus we're talking about - I'll make it implicit here on out), and it doesn't matter what $$y$$ is, only that whether such a $$y$$ exists.

• There exists an efficient test where we can determine whether any value $$x$$ is a QR or not.

• The value $$x \times y$$ is q QR if either both $$x, y$$ are QRs, or neither is. If one is a QR and the other is not, then $$x \times y$$ will not be.

• The value $$x^n$$ is QR if either $$x$$ is a QR or $$n$$ is even (or both) - if $$x$$ is not a QR and $$n$$ is odd, then $$x^n$$ will not be a QR either.

With that in mind, the El Gamal encryption of a message $$m$$ is the pair:

$$(g^r, h^r \times m)$$

where $$g$$ is publicly known generator, $$h$$ is the public key (which we assume that the attacker knows, and which will be $$g$$ raised to some unknown power), and $$r$$ is a random number selected by the encryptor (and hence unknown).

What we do is determine whether $$h^r$$ is a QR or not (which might sound a bit tricky, as we don't know the value of $$h^r$$, and so we can't use our efficient test). However, we can deduce it based on the following cases:

• If $$h$$ is a QR, then $$h^r$$ will be as well.
• If $$h$$ is not a QR, that implies $$g$$ is not a QR either (because $$h$$ is $$g$$ raised to some power). In this case, we check if $$g^r$$ is a QR or not - if it is, then $$r$$ is even (and so $$h^r$$ is a QR). If $$g^r$$ is not a QR, then $$r$$ is odd (and so $$h^r$$ is not a QR).

Once we have determined that, we then check if $$h^r \times m$$ is a QR. If the QR-ness of $$h^r$$ and $$h^r \times m$$ are the same (that is, both are a QR, or neither is), then $$m$$ must be a QR. If they differ, $$m$$ must not be a QR.

Hence, in all cases, we can determine whether $$m$$ is a QR or not, by examining the ciphertext and the public key.

• Addition: having determined if $m$ is a quadratic residue or not about halves the possibilities for $m$. If we know that $m$ is a name on the class roll, or is a dice value, that can be a useful information. – fgrieu Jan 23 '20 at 15:52