Shafrira Goldwasser
Shafrira Goldwasser
Where have all the inventors gone? Well, to create the companies of the future we need more people like Shafi Goldwasser. Among the many things she invented, was the co-invention of probabilistic encryption [here][1]:
and the co-invented of zero-knowledge proofs [2]:
She is currently the RSA Professor of Electrical Engineering and Computer Science at MIT [here]. Over her career Shafi was awarded many prizes, including, in 2012, the Turing Award, and, in 2019, an Honorary Doctorate of Science by the University of Oxford. Shafi obtained her degree in 1979 (Carnegie Mellon University) and then was awarded a PhD in 1984 (from the University of California) [here]:
She was also placed as the 12th most influential computer science researcher in the world from 2010 to 2020.
Blum-Goldwasser Probabilistic Encryption
Shafi’s PhD supervisor was the mighty Manuel Blum, and together they co-created 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 = p.q
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%4
3
>>> q%4
3
The basic method, as defined by Wikipedia, is:
The code is as follows [here]:
iimport numpy as np
import binascii
import Crypto.Util.number
from Crypto import Random
import sys
import random
def 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-versa
def 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.py
def 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 = pow((p + 1) // 4,(t + 1) , (p - 1))
d2 = pow((q + 1) // 4,(t + 1) , (q - 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 m
p = 499
q = 547
bits=10
msg='Hello'
if (len(sys.argv)>1):
bits=int(sys.argv[1])
if (len(sys.argv)>2):
msg=(sys.argv[2])
while True:
p=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
if (p%4==3): break
while True:
q=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
if (q%4==3): break
m=to_bits(msg)
a=1
b=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:", c)
d = BGW_dec(p, q, a, b, xt, c)
print(("Decrypted: %s" % from_bits(d)))
A sample run is [here]:
Message: Hello
0100100001100101011011000110110001101111
No of bits in prime is 16
p= 44119
q= 50647
a= 24633
b= -21458
r= 14161
x0= 2119402684
ap+bq: 1
Ciphertext: 0001011100111001001110010010011100101011
Decrypted: Hello
Goldwasser–Micali (GM) cryptosystem
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.
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 he determines:
a=pseudosquare(p,q)
We pick a value of a, so that there is then no solution for this:
u² ≡ a (mod N)
This is defined a having 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 (a/p) = (a/q) = -1. This is a Jacobi symbol calculation.
Bob publishes N and a.
Encryption
To encrypt for Bob. Alice selects m, and which is a bit to encrypt m∈0,1.
Alice then uses Bob’s values of (N,a) to compute:
c=r² (mod N) if m=0
c=a r² (mod 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 the cipher bit (c ) to Bob.
Decryption
Bob then computes the Jacobi symbol (c/p) and gets:
m=0 if c/p=1
m=1 if c/p=−1
A demonstration of the method here.
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': (810571289346697L, 417803374284193L), 'priv': (16117253, 50292149)}Message: hello Encoded: 805121215
Encrypted: [102605923461178L, 143126886286230L, 745770432842022L, 168824391145739L, 261618935651655L, 460849071043598L, 798955941491864L, 487047472970991L, 397987844446930L, 743669716499309L, 669942878308283L, 178548007880797L, 645225183019810L, 779540939053212L, 384395411075108L, 782842239347547L, 691841667554224L, 181138769678461L, 779305447143669L, 451333672269645L, 32858488530236L, 678286539525029L, 51434079116117L, 281928894615544L, 156989394653382L, 31002122426343L, 334583216645061L, 216935340466474L, 38608665591955L, 332742987467921L]
Decrypted: 805121215
Conclusions
The Goldwasser–Micali (GM) cryptosystem is a public key method which has been around for a while (1982), and was the first to outline the usage of probabilistic methods for encryption. By today’s standards it is not efficient, but its methods are now being used in the implementation of homomorphic encryption, such as with [paper]. For Safi, she still co-leads the Cryptography and Information Security (CIS) at MIT, and which contains some of the most amazing people in the history of cryptography:
And here is a recent talk:
References
[1] Goldwasser, S., & Micali, S. (1982, May). Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the fourteenth annual ACM symposium on Theory of computing (pp. 365–377).
[2] Goldwasser, S., Micali, S., & Rackoff, C. (2019). The knowledge complexity of interactive proof-systems. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (pp. 203–225).