Blum-Goldwasser Probabilistic EncryptionWith 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. |
Outline
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.
Key generation
In the key generation we generate two prime numbers \(p\) and \(q\) so that:
\(p \equiv 3 \pmod 4\)
and:
\(q \equiv 3 \pmod 4\)
These are our private key elements \((p,q\)). Next we compute the public key with:
\(n = p.q\)
Encryption
To encrypt, we split into blocks which have the same number of bits as \(n\). We then generate a random number (\r\) and compute:
\(x_0=r^2 \pmod n\)
This is the starting seed value for the Blum-Blum-Shub (BBS) random number generator. Each block key is then computed as:
\(x_i = {x_{i-1}^2} \pmod n \)
For each cipher block we can then simple Ex-OR these block keys with the message block:
\(c_i = m_i \oplus x_i\)
The final cipher is all the cipher values (\(c_i\)) and the final state (\(x_t\)):
\(x_{t+1} = x_t^2 \bmod{n}\)
Blum and Goldwasser then created a method which then only needs \(p\), \(q\) and \(x_t\) to be able to regenerate \(x_0\). With the value of \(x_0\), 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:
\(m_i = c_i \oplus x_i\)
Decryption
To decrypted we take the encrypted cipher of \((c_1, c_2, \dots, c_t, x_{t+1})\) and then use the private key \((p,q)\) to determine:
\(d_p = ((p+1)/4)^{t+1} \bmod{(p-1)}\)
\(d_q = ((q+1)/4)^{t+1} \bmod{(q-1)}\)
\(u_p = x^{d_p} \bmod{p}\)
\(u_q = x^{d_q} \bmod{q}\)
We then use the Extended Euclidean Algorithm to determine \(r_p\) and \(r_q\) so that \(r_p p + r_q q = 1\)). Then we recover the seed for the Blum Blum Shub method with:
\(x_0 = u_q r_p p + u_p r_q q \bmod{n}\)
This will be the same value which was used in encryption (see proof below). \(x_0\) can then used to compute the same sequence of \(x_i\) values as were used in encryption to decrypt the message, as follows.For \(i\) from 1 to \(t\):
- \(x_i = x_{i-1}^2 \bmod{n}\)
- \(p_i =\) the least significant \(h\) bits of \(x_i\)
- \(m_i = c_i \oplus p_i\)
We can then reassemble the message values of \((m_1, m_2, \dots, m_t)\) to reconstruct the message \(M\).
Outline
The code is as follows:
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:
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
Reference
[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.