# Blum-Goldwasser Probabilistic 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 Blum-Goldwasser method is a public key algorithm that uses a probabilistic public-key encryption scheme [here]:

The encryption method uses the Blum-Blum-Shub (BBS) technique to generate the keystream [here]. Initially we create two prime numbers (p and q), and then calculate N:

N = pq

The public key is N, and the private key is p and q, and where p and q:

p (mod 4) = 3

q (mod 4) = 3

For example we can select p= 239, q= 179, as both will give us 3 when we do a (mod 4) operation:

`>>> p=239>>> q=179>>> p%43>>> q%43`

The basic method, as defined by Wikipedia, is:

The code is as follows [here]:

`import numpy as npimport binasciiimport Crypto.Util.numberfrom Crypto import Randomimport sysimport randomdef xgcd(a, b):    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""    x0, x1, y0, y1 = 0, 1, 1, 0    while a != 0:        (q, a), b = divmod(b, a), a        y0, y1 = y1, y0 - q * y1        x0, x1 = x1, x0 - q * x1    return b, x0, y0# Method from https://stackoverflow.com/questions/7396849/convert-binary-to-ascii-and-vice-versadef to_bits(text, encoding='utf-8', errors='surrogatepass'):    bits = bin(int(binascii.hexlify(text.encode(encoding, errors)), 16))[2:]    return bits.zfill(8 * ((len(bits) + 7) // 8))def from_bits(bits, encoding='utf-8', errors='surrogatepass'):    n = int(bits, 2)    return int2bytes(n).decode(encoding, errors)def int2bytes(i):    hex_string = '%x' % i    n = len(hex_string)    return binascii.unhexlify(hex_string.zfill(n + (n & 1)))# Derived from https://github.com/coenvalk/blum-goldwasser-probabilistic-encryption/blob/master/blumgoldwasser.pydef BGW_enc(p, q, x, m):    n = p * q    # assert p%4 == 3 and q%4 == 4    k = int(np.log2(n))    h = int(np.log2(k))    t = len(m) / h    xi = x    c = ''    for i in range(t):        mi = m[i*h:(i + 1)*h]        xi = (xi ** 2) % n        xi_bin = bin(xi)        pi = xi_bin[-h:]        mi_int = int(mi, 2)        pi_int = int(pi, 2)        ci = pi_int ^ mi_int        ci_bin = format(ci, '0' + str(h) + 'b')        c += ci_bin    xt = (xi ** 2) % n    return c, xt            def BGW_dec(p, q, a, b, xt, c):    assert a*p + b*q == 1    n=p*q    k = int(np.log2(n))    h = int(np.log2(k))    t = len(c) / h    d1 = (((p + 1) / 4)**(t + 1)) % (p - 1)    d2 = (((q + 1) / 4)**(t + 1)) % (q - 1)    u = pow(xt,d1,p)    v = pow(xt,d2, q)    x0 = (v*a*p + u*b*q) % n    xi = x0    m = ''    for i in range(t):        ci = c[i*h:(i + 1)*h]        xi = (xi**2) % n        xi_bin = bin(xi)        pi = xi_bin[-h:]        ci_int = int(ci, 2)        pi_int = int(pi, 2)        mi = pi_int ^ ci_int        mi_bin = format(mi, '0' + str(h) + 'b')        m += mi_bin    return mp = 499q = 547bits=10msg='Hello'if (len(sys.argv)>1):        bits=int(sys.argv)if (len(sys.argv)>2):        msg=(sys.argv)while True:	p=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)	if (p%4==3): breakwhile True:	q=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)	if (q%4==3): breakm=to_bits(msg)a=1b=1_,a,b=xgcd(p,q)r= random.getrandbits(bits)x0 = (a*p*r + b*q+r) % (p*q)       c, xt = BGW_enc(p, q, x0, m)print ("Message: %s" % msg)print ("   %s" % m)print ("\nNo of bits in prime is %d" % bits)print ("p= %d" % p)print ("q= %d" % q)print ("a= %d" % a)print ("b= %d" % b)print ("r= %d" % r)print ("x0= %d" % x0)print ("ap+bq: %d" % (a*p+b*q))print "\nCiphertext:", cd = BGW_dec(p, q, a, b, xt, c)    print ("Decrypted: %s" % from_bits(d))`

A sample run is [here]:

`Message: Hello   0100100001100101011011000110110001101111No of bits in prime is 16p= 65447q= 34231a= -7482b= 14305r= 37115x0= 1908144401ap+bq: 1Ciphertext: 0011100101011111010000110011100011010010Decrypted: Hello`

Written by