Goldwasser–Micali method: Probabilistic Encryption

Method

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=pq\)

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 he determines:

\(a=\textrm{pseudosquare}(p, q)\)

For this we determine if we can find, for a given value of \(a\) which has no solutions this:

\(u^2 \equiv a \pmod p\)

\(u^2 \equiv a \pmod q\)

This means that there are no quadratic residues ([here]).

Bob's public key is \((N,a)\) and the private key is \((p,q)\).

Key generation

The key encryption method becomes:

Bob selects \(p\) and \(q\).

Bob selects \(a\) with \(\left(\frac{a}{p}\right) \) = \(\left(\frac{a}{q}\right) = -1\). This is a Jacobi symbol calculation.

Bob publishes \(N\) and \(a\).

Encryption

To encrypt for Bob:

Select a bit to encrypt \(m \in {0,1}\).

Alice uses Bob's values of \(N,a)\) to compute:

\(c = r^2 \pmod N\) if \(m=0\)

\(c = ar^2 \pmod N\) if \(m=1\)

Alice chooses \(r\) at random, and thus Eve will not be able to spot the message, as the random values will consist of all possible squares modulo N, when \(m=0\).

Alice sends \(c\) to Bob.

Decryption

Bob then computes \(\left( \frac{c}{p}\right)\) and gets:

\(m=0\) if \(\left( \frac{c}{p}\right) = 1\)

\(m=1\) if \(\left( \frac{c}{p}\right) = -1\)

Code

An outline of the code from here is:

# https://asecuritysite.com/encryption/goldwasser
# Based on https://gist.github.com/brunoro/5893701/
from unicodedata import normalize 
from string import ascii_letters
from random import randint
import sys
from functools import reduce

# Miller-Rabin probabilistic primality test (HAC 4.24)
# returns True if n is a prime number
# n is the number to be tested
# t is the security parameter


def miller_rabin(n, t):
    assert(n % 2 == 1)
    assert(n > 4)
    assert(t >= 1)

    # select n - 1 = 2**s * r
    r, s = n - 1, 0
    while r % 2 == 0:
        s += 1
        r >>= 1 #r = (n - 1) / 2 ** s

    for i in range(t):
        a = randint(2, n - 2) # this requires n > 4

        y = pow(a, r, n) # python has built-in modular exponentiation
        if y != 1 and y != n - 1:
            j = 1
            while j <= s - 1 and y != n - 1:
                y = pow(y, 2, n)
                if y == 1:
                    return False
                j += 1
            if y != n - 1:
                return False

    return True

def is_prime(n):
    if n in [2, 3]:
        return True
    if n % 2 == 0:
        return False

    return miller_rabin(n, 10)

def nearest_prime(n):
    if is_prime(n):
        return n

    if n % 2 == 0:
        n += 1

    i = 0
    while True:
        i += 1
        n += 2

        if is_prime(n):
            return n 

def big_prime(size):
    n = randint(1, 9)
    for s in range(size):
        n += randint(0, 9) * s**10

    return nearest_prime(n)

def is_even(x):
    return x % 2 == 0

# calculates jacobi symbol (a n)
def jacobi(a, n):
    if a == 0:
        return 0
    if a == 1:
        return 1

    e = 0
    a1 = a
    while is_even(a1):
        e += 1
        a1 =a1// 2
    assert 2**e * a1 == a

    s = 0

    if is_even(e):
        s = 1
    elif n % 8 in {1, 7}:
        s = 1
    elif n % 8 in {3, 5}:
        s = -1

    if n % 4 == 3 and a1 % 4 == 3:
        s *= -1

    n1 = n % a1
    
    if a1 == 1:
        return s
    else:
        return s * jacobi(n1, a1)

def quadratic_non_residue(p):
    a = 0
    while jacobi(a, p) != -1:
        a = randint(1, p)

    return a

def xeuclid(a, b):
    """ return gcd(a,b), x and y in 'gcd(a,b) = ax + by'.
    """
    x = [1, 0]
    y = [0, 1]
    sign = 1
 
    while b:
        q, r = divmod(a, b)
        a, b = b, r
        x[1], x[0] = q*x[1] + x[0], x[1]
        y[1], y[0] = q*y[1] + y[0], y[1]
        sign = -sign
 
    x = sign * x[0]
    y = -sign * y[0]
    return a, x, y
 
 
def gauss_crt(a, m):
    """ return x in ' x = a mod m'.
    """
    modulus = reduce(lambda a,b: a*b, m)
 
    multipliers = []
    for m_i in m:
        M = modulus // m_i
        gcd, inverse, y = xeuclid(M, m_i)
        multipliers.append(inverse * M % modulus)
 
    result = 0
    for multi, a_i in zip(multipliers, a):
        result = (result + multi * a_i) % modulus
    return result

def pseudosquare(p, q):
    a = quadratic_non_residue(p)
    b = quadratic_non_residue(q)

    return gauss_crt([a, b], [p, q])

def generate_key(prime_size = 6):
    p = big_prime(prime_size)
    q = big_prime(prime_size)
    while p == q:
        p2 = big_prime(prime_size)

    y = pseudosquare(p, q)
    n=p*q
    
    keys = {'pub': (n, y), 'priv': (p, q)}
    return keys

def int_to_bool_list(n):
    return [b == "1" for b in "{0:b}".format(n)]

def bool_list_to_int(n):
    s = ''.join(['1' if b else '0' for b in n])
    return int(s, 2)

def encrypt(m, pub_key):
    bin_m = int_to_bool_list(m)
    n, y = pub_key

    def encrypt_bit(bit):
        x = randint(0, n)
        if bit:
            return (y * pow(x, 2, n)) % n
        return pow(x, 2, n)
    return list(map(encrypt_bit, bin_m))

def decrypt(c, priv_key):
    p, q = priv_key
    def decrypt_bit(bit):
        e = jacobi(bit, p)
        if e == 1:
            return False
        return True

    m = list(map(decrypt_bit, c))
    return bool_list_to_int(m)

def normalize_str(s):
    u = str(s)
    valid_chars = ascii_letters + ' '
    un = ''.join(x for x in normalize('NFKD', u) if x in valid_chars).upper()
    return un.encode('ascii', 'ignore')

def int_encode_char(c):
    ind = c
    val = 27 # default value is space

    # A-Z: A=01, B=02 ... Z=26
    if ord('A') <= ind <= ord('Z'):
        val = ind - ord('A') + 1

    return "%02d" % val

def int_encode_str(s):
    return int(''.join(int_encode_char(c) for c in normalize_str(s)))

message='hello'

key = generate_key()
print(key)
m = int_encode_str(message)
print("\nMessage:",message, "Encoded:",m) 
enc = encrypt(m, key['pub'])
print("\nEncrypted:",enc)
dec = decrypt(enc, key['priv'])
print("\nDecrypted:",dec)

A sample run with the message of "hello" gives:

{'pub': (4232262339384161L, 1437503793545824L), 'priv': (46939117, 90164933)}

Message: hello Encoded: 805121215

Encrypted: [1835837186827820L, 3140813396076447L, 2990746254728634L, 1510036835586438L, 169446965992081L, 1357760858641767L, 522892758838421L, 3605506186322296L, 1614109525193245L, 610352056212238L, 3642063183497255L, 376169821568161L, 2228194295224742L, 3171103216413515L, 3494422732417692L, 1356339365224220L, 198206944933952L, 1991838395804232L, 1364411377244139L, 961257653676881L, 708201827556478L, 3209497044802980L, 2796387413915890L, 344864422239457L, 810082126842815L, 860038151313273L, 1769936740483701L, 1966083951460084L, 1608981715083026L, 2193342855525233L]

Decrypted: 805121215