#!/usr/local/bin/python3

# An implementation of the Goldwasser-Micali encryption algorithm which transmits a quadratic
# residue for a 0 bit and a quadratic non-residue for a 1 bit. The cipertext is one integer
# for each plaintext bit.

from sympy import isprime, randprime
from random import randint

def text_to_bits(text):
    bits = bin(int.from_bytes(text.encode(), 'big'))[2:]
    
    return list(map(int, bits.zfill(8 * ((len(bits) + 7) // 8))))

def bits_to_text(bits):
    n = int(''.join(map(str, bits)), 2)
    
    return n.to_bytes((n.bit_length() + 7) // 8, 'big').decode() 

def legendre(a, p):
    assert(p != 2 and isprime(p))
    if a % p == 0:
        l = 0
    else:
        l = pow(a, (p - 1) // 2, p)
        if l == p - 1:
            l = -1

    return l
    
def test_bit(b, p, q):
    result = 1
    if legendre(b, p) == 1 and legendre(b, q) == 1:
        result = 0
        
    return result

def encrypt(n, z, b):
    e = pow(randint(1, n), 2, n)
    if b == 1:
        e = (e * z) % n

    return e

n_max = 10000000

p = randprime(1, n_max)
print('p = {0:d}'.format(p))

# Don't want n to be p squared. Too easy to factor.
while True:
    q = randprime(1, n_max)
    if p != q:
        break;
        
print('q = {0:d}'.format(q))

# Give choice of z some room to breathe by starting "small"
z = (p - 1) // 2
while True:
    if legendre(z, p) == -1 and legendre(z, q) == -1: 
        break
    z += 1
    
print('z = {0:d}'.format(z))

n = p * q
print('n = p * q = {0:d}'.format(n))

pt = '''Whose woods these are I think I know.
His house is in the village, though;'''
print('\nPlaintext before:')
print(pt)
digs = text_to_bits(pt)

es = [encrypt(n, z, b) for b in digs]
print('\nCiphertext:')
print(es)

digs_after = [test_bit(e, p, q) for e in es]
print('\nDeencrypted ciphertext:')
print(bits_to_text(digs_after))

# Sample Output:

# p = 1203193
# q = 6717713
# z = 601599
# n = p * q = 8082705257609

# Plaintext before:
# Whose woods these are I think I know.
# His house is in the village, though;

# Ciphertext:
#[1292575848261, 5839775397279, 5554308066094, 330297141326, 7512773820554, 
# ...
# 4397218752399, 5621202712249]

# Deencrypted ciphertext:
# Whose woods these are I think I know.
# His house is in the village, though;