Probabilistic Encryption using the Goldwasser–Micali (GM) method

And a hint of homomorphic encryption

With public key encryption, Alice could have two possible messages (a ‘0’ or a ‘1’) that she sends to Bob. If Eve knows the possible messages (a ‘0’ or a ‘1’), she will then cipher each one with Bob’s public key and then matches the results against the cipher message that Alice sends. Eve can thus determine what Alice has sent to Bob. In order to overcome this the Goldwasser–Micali (GM) method implements a probabilistic public-key encryption scheme. It also supports the usage of homomorphic encryption and was developed by Shafi Goldwasser and Silvio Micali in 1982.

Method

A demonstration of the method here.

In a probabilist encryption method, Alice selects the plaintext (m) and a random string (r). Next she uses Bob public key to encrypt the message pair of (m,r). If the value is random, then Eve will not be able to range of messages and random values used.

If Bob wants to create his public and private keys. He first selects two random prime numbers for his private key, and then calculates N:

N=p q

The values of p and q will be his private key and N will form part of his public key. For the second part of his public key…