Source code for pkenc_gm82

'''
**Goldwasser-Micali Public Key Encryption Scheme (GM82)**

*Authors:* S. Goldwasser, S. Micali

| **Title:** "Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information"
| **Published in:** 14th Symposium on Theory of Computing (STOC), 1982
| **Available from:** http://groups.csail.mit.edu/cis/pubs/shafi/1982-stoc.pdf
| **Notes:**

.. rubric:: Scheme Properties

* **Type:** encryption (public key)
* **Setting:** Integer
* **Assumption:** Quadratic Residuosity

.. rubric:: Implementation

:Authors: Guillermo Ramos
:Date: 01/2015
'''

from charm.core.math.integer import legendre, gcd
from charm.toolbox.integergroup import RSAGroup, integer
from charm.toolbox.PKEnc import PKEnc

# Upper bound to the number of rounds the keygen is able to make
# to search for a quadratic non-residue
maxtimes = 30

# Is x a quadratic residue of N = p1*p2?


def isResidue(x, p1, p2):
    return legendre(x, p1) == 1 or legendre(x, p2) == 1


# Goldwasser-Micali cryptosystem


class GM82(PKEnc):
    """
    >>> gm82 = GM82()
    >>> (pk, sk) = gm82.keygen(512)
    >>> zero = gm82.encrypt(pk, 0)
    >>> one = gm82.encrypt(pk, 1)
    >>> gm82.decrypt(sk, zero)
    0
    >>> gm82.decrypt(sk, one)
    1
    >>> gm82.decrypt(sk, gm82.xor(pk, zero, zero))
    0
    >>> gm82.decrypt(sk, gm82.xor(pk, zero, one))
    1
    >>> gm82.decrypt(sk, gm82.xor(pk, one, zero))
    1
    >>> gm82.decrypt(sk, gm82.xor(pk, one, one))
    0
    """
    def __init__(self):
        PKEnc.__init__(self)
        self.group = RSAGroup()



    def keygen(self, secparam):
        self.group.paramgen(secparam)

        # Find a random quadratic non-residue in the group
        x = self.group.random()
        times = 1
        while times < maxtimes and isResidue(x, self.group.p, self.group.q):
            x = self.group.random()
            times += 1

        # If we are not able to find a quadratic non-residue after 'maxtimes'
        # trials, abort and output error
        if times == maxtimes:
            print("ERROR: non-residue not found after {} trials.".format(times))
            return None

        pk = (self.group.n, x)
        sk = (self.group.p, self.group.q)
        return (pk, sk)




    def encrypt(self, pk, m):
        (n, x) = pk

        y = self.group.random()
        while gcd(n, y) != 1:
            y = self.group.random()

        if m == 0:
            return y**2 % n
        else:
            return y**2 * x % n




    def decrypt(self, sk, c):
        (p, q) = sk
        return 0 if isResidue(c, p, q) else 1


    # Homomorphic XOR over ciphertexts


    def xor(self, pk, c1, c2):
        (n, _) = pk
        return (c1 * c2) % n