Cryptography In The Family: Blum, Blum and Blum

Cryptography In The Family: Blum, Blum and Blum

Behind that smartphone in our pocket are decades of solid research advancement. And behind this research are people. And, these are people with a passion to solve real problems and share their knowledge. And, sometimes this work is in-the-family.

So, yesterday, I published an article on the contribution that the Lenstra brothers had made to mathematics and cryptography [here], so let’s look at another family: The Blum’s.

The husband and wife team of Manuel Blum and Lenore Blum were professors at Carnegie Mellon University. But, both of them resigned in 2018 as a protest against sexist treatment within a research project. Avrim (their son and included in the photo at the top of this article), too, followed the family route and also become a Professor of Computer Science at Carnegie Mellon University. In fact, his PhD mentor was the cryptographic genius that is Ron Rivest.

Like his parents, Avrim advanced in many areas of complexity theory, and around machine learning [here]:

Just like their son, Manuel and Lenore provided so many great things to the world of research. Among these were the Blum integers, the Blum-Blum Shub random number generator, the Blum-Goldwasser public key encryption system and the invention of CAPTCHA. And, Manuel, too, was an amazing mentor to many PhD students, including Len Adleman, Shafi Goldwasser and Silvio Micali. Here is one classic paper that Silvio and Manual wrote together:

He was an inspirational PhD supervisor, and you can tell he cared greatly about his students [here]:

When working on a PhD, you must focus on a topic so narrow that you can understand it completely. It will seem at first that you're working on the proverbial needle, a tiny fragment of the world, a minute crystal, beautiful but in the scheme of things, microscopic. Work with it. And the more you work with it, the more you penetrate it,he more you will come to see that your work, your subject, encompasses the world.  In time, you will come to see the world in your grain of sand.

To see a world in a grain of sand
Or a heaven in a wild flower,
Hold infinity in the palm of your hand
And eternity in an hour.
WILLIAM BLAKE (1757-1827)"

and on the importance of continually writing (and learning):

I remember a professor of Mathematics at MIT, 
name of BERTRAM KOSTANT, 
who would keep his door open whenever he was in his office, and he would always be at his desk writing. 
Writing. Always writing. 
Was he writing up his research? Maybe. 
Writing up his ideas? Maybe. 
I personally think he was reading, and writing what he was reading. 
At least for me, writing what I read is one of the most enjoyable and profitable ways to learn hard material.

I personally believe this to be great advice, as I wrote books and my website, because I was learning about the topics.

Blum and Blum

One of Manuel and Lenore’s first papers together appeared in 1975 [here][1]:

But, it was in 1986, Lenore and Manuel outlined one of the best provable pseudo-random number generators around … the Blum Blum Shub (BBS) method [here]:

It uses the form of:

and where x_0 is a random seed. The value of M is equal to pq, and where p and q are prime numbers. These values of p and q are both congruent to 3 mod 4 (p=q=3 (mod4) ). What does that mean? Well when I take the values of p or q and divide them by 4, I will get a remainder of 3.

So, p=7 is possible (as 7 divided by 4 is 1, remainder 3), and p=11 is also possible (as 11 divided by 4 is 2, remainder 3). A value of 13 is not possible as it will be 3, remainder 1. Let’s try a simple example in Python [here]:

>>> p=7
>>> q=11
>>> M=p*q
>>> x0=5
>>> x1=(x0**2)%M
>>> x2=(x1**2)%M
>>> x3=(x2**2)%M
>>> x4=(x3**2)%M
>>> print (x1,x2,x3,x4)
25 9 4 16

In this case, we are using p=7 and q=11, and then a seed of x_0=5, and the random sequence is 25, 9, 4 and 16. We normally just take the least significant bit, so the output would be ‘1100’.

The security of the method involves the difficulty in factorizing M. Overall it is slow but is the strongest proven random number generator. For each step, we extract some of the information from x_n+1, and which is typically the least significant bit. It would not be used within a cipher application but could be used in key generation.

The code used is [here]:

import sympy
import random
import re 
import sys
x = 3*10**10
y = 4*10**10
seed = random.randint(1,1e10)

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
def next_usable_prime(x):
        p = sympy.nextprime(x)
        while (p % 4 != 3):
            p = sympy.nextprime(p)
        return p
p = next_usable_prime(x)
q = next_usable_prime(y)
M = p*q
N = 1000 

if (len(sys.argv)>1):
    N=int(sys.argv[1])

print "\np:\t",p
print "q:\t",q
print "M:\t",M
print "Seed:\t",seed
x = seed
bit_output = ""
for _ in range(N):
    x = x*x % M
    b = x % 2
    bit_output += str(b)
print bit_output
print "\nNumber of zeros:\t",bit_output.count("0")
print "Number of ones:\t\t",bit_output.count("1")
xi=''
print "\nPredicting 1st 10 with Euler's Theorem:"
for i in range(10):
    xi += str((seed ** (2**i % lcm((p-1),(p-1))) % M) %2)
print xi

A sample run is [here]:

p:  30000000091
q:  40000000003
M:  1200000003730000000273
Seed:   2188162291
1011001011011110101101110001011000110001000010110110010100011110011010011100000001011111101100100101Number of zeros:    49
Number of ones:     51

Here is my explanation:

Blum integers

Let’s look at the magic of Blum integers — and which were named after Manuel. These related to the solving of the form:

y = x² mod n

and where we need to find values of y for different values of x, and for a given modulus (n). The example if we have:

4 = x² (mod 15)

The valid values of x are 2, 7, 8 and 13. Sometimes, though there is no solution, such as for x=3.

A Blum integer is created by multiplying up two prime numbers (p and q) and where p=3 (mod 4) and q = 3 (mod 4):

n=p * q

Thus we take the prime numbers (p and q) and divide them by four, and if we get an answer of 3, we have the required value. For example, 7 is a possible value, as when we divide by four, we get 3. The possible prime numbers are then: 3, 7, 11, 19, and so on. The Blum integers then become: 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, ….

Now, these have interesting properties. The first is that when we determine the modular square root of a value we get four square roots. Let me example this with an example. Let’s say I have p=47 and q=43:

47 = 3 (mod 4) [as this is 15 r 3]

43 = 3 (mod 4) [as this is 14 r 3]

We find N as:

N = 47*43 = 2,021

Next, we find that there are four square root values for each value between 0 and N. Let’s pick a value of y=4. For this, the solutions for x in 4=x² (mod 2021) are:

1976^2=4 (mod 2021)
  2^2=4 (mod 2021)
  2019^2=4 (mod 2021)
  45^2=4 (mod 2021)

For example 1,972²² = 3,904,576 and then if we take (mod 2,021) we get 4. Thus our Blum integer always gives us four modulo square roots. Here is a little program to compute a few of these [here]:

import sys
import libnum

p=0
q=0
bitsize=8
if (len(sys.argv)>1):
        bitsize=int(sys.argv[1])

while ((p%4)!=3):
  p=libnum.generate_prime(bitsize)
while ((q%4)!=3):
  q=libnum.generate_prime(bitsize)
print ("\nPrime (p): %d. Length: %d bits, Digits: %d" % (p,libnum.len_in_bits(p), len(str(p)) ))  
print ("\nPrime (q): %d. Length: %d bits, Digits: %d" % (q,libnum.len_in_bits(q), len(str(q)) )) 

n=p*q
print ("N=",n)
print ("The first few values:")
for x in range(2,12):
  if (libnum.has_sqrtmod(x,{p: 1,q:1})):
    res=libnum.sqrtmod(x,{p: 1,q:1})
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))  
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    print ()

Here is the code:

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][2]:

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%4
3
>>> q%4
3

The basic method, as defined by Wikipedia, is:

The code is as follows [here]:

import numpy as np
import binascii
import Crypto.Util.number
from Crypto import Random
import sys
import 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-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 = (((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 = 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): breakwhile True:
 q=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
 if (q%4==3): breakm=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:", 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 16
p= 65447
q= 34231
a= -7482
b= 14305
r= 37115
x0= 1908144401
ap+bq: 1Ciphertext: 0011100101011111010000110011100011010010
Decrypted: Hello

CAPTCHA

Of course, finally, we reach the online system that aims to tell a human from a robot [3]:

It was one of the first papers to bring together the fields of cryptography and AI, and which would be followed on by Avrim.

Conclusions

The research world has much to thank Manuel, Lenore and Avrim for. Without them, our world would be a good deal more complex and less trustworthy. Sometimes, cryptography is in the blood. And, for research? It is in their DNA:

and:

References

[1] Blum, L., & Blum, M. (1975). Toward a mathematical theory of inductive inference. Information and control, 28(2), 125–155.

[2] Blum, M., & Goldwasser, S. (1984, August). An efficient probabilistic public-key encryption scheme which hides all partial information. In Workshop on the theory and application of cryptographic techniques (pp. 289–299). Springer, Berlin, Heidelberg.

[3] Ahn, L. V., Blum, M., Hopper, N. J., & Langford, J. (2003, May). CAPTCHA: Using hard AI problems for security. In International conference on the theory and applications of cryptographic techniques (pp. 294–311). Springer, Berlin, Heidelberg.