is a quadratic residue mod N. Key generation The modulus used in GM encryption is generated in the same manner as in the RSA cryptosystem. (See RSA, key generation for details.) Alice generates two distinct large prime numbers p and q, randomly and independently of each other. Alice computes N = p q. She then finds some non-residue x such that the Legendre symbols satisfy and hence the Jacobi symbol is +1. The value x can for example be found by selecting random values and testing the two Legendre symbols. If p, q = 3 mod 4 (i.e., N is a Blum integer), then the value N − 1 is guaranteed to have the required property. The public key consists of (x, N). The secret key is the factorization (p, q). Message encryption Suppose Bob wishes to send a message m to Alice: Bob first encodes m as a string of bits (m1, ..., mn). For every bit , Bob generates a random value from the group of units modulo N, or . He outputs the value . Bob sends the ciphertext (c1, ..., cn). Message decryption Alice receives (c1, ..., cn). She can recover m using the following procedure: For each i, using the prime factorization (p, q), Alice determines whether the value ci is a quadratic residue; if so, mi = 0, otherwise mi = 1. Alice outputs the message m = (m1, ..., mn). Security properties There is a simple reduction from breaking this cryptosystem to the problem of determining whether a random value modulo N with Jacobi symbol +1 is a quadratic residue. If an algorithm A breaks the cryptosystem, then to determine if a given value x is a quadratic residue modulo N, we test A to see if it can break the cryptosystem using (x,N) as a public key. If x is a non-residue, then A should work properly. However, if x is a residue, then every "ciphertext" will simply be a random quadratic residue, so A cannot be correct more than half of the time. Furthermore, this problem is random self-reducible, which ensures that for a given N, every public key is just as secure as every other public key. The GM cryptosystem has homomorphic properties, in the sense that if c0, c1 are the encryptions of bits m0, m1, then c0c1 mod N will be an encryption of . For this reason,