0
$\begingroup$

Referring to the following URL: http://cryptowiki.net/index.php?title=Goldwasser_Micali_cryptosystem

The decryption of the message is based on wether the bit is a QRn or not, but how do we know/verify (the mathematical operations) if it is a QRn or not.

$\endgroup$
2
$\begingroup$

Well, we know that the ciphertext $c$ is a Quadratic Residue, then both $c \bmod p$ is a QR (modulo $p$) and $c \bmod q$ is a QR (modulo $q$). And, we know that (for valid ciphertexts) $c$ has a Jacobi of 1, and so if it is not a QR, then both $c \bmod p$ is a non-QR (modulo $p$) and $c \bmod q$ is a nonQR (modulo $q$).

And, we have the private key, and so we can have the value of $p$. So, one simple way to decrypt $c$ is to first evaluate $c \bmod p$, and then check if it is a QR; for example, check the value of $(c \bmod p)^{(p-1)/2} \mod p$; if it evaluates to 1, then $c$ is a QR (and so the plaintext is 0); if it evaluates to $p-1$, then $c$ is not a QR (and so the plaintext is 1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.