Two Of The Greatest Computer Scientists, Ever! Blum and Goldwasser

Two Of The Greatest Computer Scientists, Ever! Blum and Goldwasser

Let me start with my viewpoint. To me, every child at school should learn coding, and, every child should know about the famous computer scientists/engineers, such as Claude Shannon, Richard Stallman and Daphne Koller, as much as they know about Newton and Galileo. In fact, these amazing researchers have changed our world in more ways than we can ever imagine.

Great teams in Computer Science

We all know about Gates and Allen, Jobs and Wozniak, and Bosack and Lerner. But what about Cybersecurity? Well, we have possibly the greatest with Marty Hellman and Whitfield Diffie, and with Rivest, Shamir and Adleman. But, I give you another one … Manuel Blum and Shafi Goldwasser. Both Manuel and Shafi are truly exceptional on their own:

In fact, Manuel is ranked No 11 and Shafi at No 12 in the Top Influential Computer Scientists from 2010 to 2020. They are individual two of the greatest computer scientists ever! By the way, Lenore Blum is listed at No 19.

Blum-Goldwasser Probabilistic Encryption

And, so, Manuel Blum was an exceptional teacher and mentor. He supervised some exceptional people such as Len Adleman, Silvio Micali and Shafi. Few in academia could ever get near the exceptional work that Manuel and Shafi have achieved. And, so, the talent that was Shafi first came to the work through her work with Manuel on Blum-Goldwasser Probabilistic Encryption:

We have to understand that it is probabilistic, and which means that every time we encrypt some plaintext, we get a different ciphertext. This stops Eve from linking ciphertext to plaintext, as the ciphertext will forever change for the same plaintext. The next thing about the method that is important to understand is that it is a public key encryption method — and so has a public key (to encrypt) and a private key (to decrypt). And thus, anyone who wants to send Alice a secret message uses her public key, and she keeps a private key to decrypt it.

The method that Manuel and Shafi come up with is beautifully crafted. Basically, we start with a random seed value (r) — and which will make sure that every time we encrypt the same message, we will always get the same result. We then take two random prime numbers (p and q) and compute a public modulus of:

To encrypt, we split into blocks which have the same number of bits as n. We then generate a random number (r) and compute:

This is the starting seed value for the Blum-Blum-Shub (BBS) random number generator. Each block key is then computed as:

For each cipher block, we can then simply Ex-OR these block keys with the message block:

The final cipher is all the cipher values (c_i) and the final state (x)t). Blum and Goldwasser then created a method which then only needs p, q and x_t to be able to regenerate x0. With the value of x0, we can then regenerate the same series of x_i values, and just have to EX-OR the cipher text with these values to recover the plaintext:

I have defined the full method here:

https://asecuritysite.com/principles_pub/blumgold

The great thing about the method is that it does not use the CPU expensive operation of M^e (mod n) that RSA uses, and just uses a simple EX-OR operation on the bit values. In decryption, it is the same, and rather than using C^d (mod n), we simply regenerate the same key bitstream and EX-OR the cipher text with this. This method is thus ultra-fast — compared with RSA.

Coding

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= 65447
q= 34231
a= -7482
b= 14305
r= 37115
x0= 1908144401
ap+bq: 1
Ciphertext: 0011100101011111010000110011100011010010
Decrypted: Hello

Conclusions

While mighty corporations invest massively in research and development — when it comes down to it, it is the power of the human mind that makes the greatest advancements. This can be great individuals or great teams. One thing that is for sure is that a focus on a key problem can bring great minds together — and that is the magic of research.

And, so, as I started, we need to get our kids coding, otherwise we will create another generation that we switched off coding at an early stage. Our

Postscript

Here is the ranking from [here]:

#1 Daphne Koller

#2 Tim Berners-Lee

#3 Yann LeCun

#4 Scott Aaronson

#5 Erik Demaine

#6 Donald Knuth

#7 Zvi Galil

#8 Geoffrey Hinton

#9 Nick Bostrom

#10 Nancy Lynch

#11 Manuel Blum

#12 Shafi Goldwasser

#13 Michael J. Fischer

#14 Stuart J. Russell

#15 Wendy Hall

#16 Gerald Jay Sussman

#17 Charles E. Leiserson

#19 Lenore Blum

#20 Raj Reddy

#22 Bruce Schneier

#23 Subhash Khot

#24 Adi Shamir

References

[1] Blum, M., & Goldwasser, S. (1985). An efficient probabilistic public-key encryption scheme which hides all partial information. In Advances in Cryptology: Proceedings of CRYPTO 84 4 (pp. 289–299). Springer Berlin Heidelberg.