Mike Hogan^{1}
In this project we will investigate the Blum-Goldwasser Cryptosystem, a public-key, probabilistic cryptosystem. We will implement the cryptosystem on a computer using the Python programming language. In addition, we will analyze the security and computational complexity of the cryptosystem. Along the way, we will also investigate the Blum-Blum-Shub streamcipher, an essential component of the cryptosystem. In addition, we will explore the number-theoretic background (Chinese remainder theorem, Fermat's little theorem, quadratic residues, and so on) needed for the analysis of these topics. Finally, we will improve upon the estimate for the period of the Blum-Blum-Shub sequence.
In addition to the need for security in everyday communications, the need for security in military communications has never been higher. Engaged in wars on two fronts with an evolving enemy and having forward deployed assets in locations all over the world, we cannot afford to have communications intercepted and used against us. I hope that my research can increase the knowledge of the basics behind current cryptosystems and lead to new thinking on improving our current methods.
In this paper, I will be taking an in depth look at the Blum-Goldwasser crypstosystem, a probabilistic, public-key cipher with minimal, if any, usage in applications today. I will discuss the math behind the cryptosystem, as well as the complexity, efficiency, and security. Through the Blum-Goldwasser system, I will also explore the Blum-Blum-Shub stream cipher, a key component of the system. Using special Blum primes, I will establish a better estimation for the period of the pseudorandom sequence than that given in [BBS] (see p. 378). Finally, I will implement the Blum-Goldwasser cryptosystem in Sage with the Python coding language.
Cryptosystems are used to ensure that your messages are not intercepted and read by an adversary you don't want to gain knowledge of your correspondances. There are two things that distinguish cryptosystems from one another: the complexity, or efficiency, of the system and the security behind the system. In this section, [Men] is used as a general reference.
In order to discuss the complexity of the cryptosystem, we first need to define an algorithm as well as two measures of complexity, O-notation and -notation.
An example of a well-known algorithm, and one that will be used for the
decryption of the Blum-Goldwasser
cryptosystem, is the Extended Euclidean Algorithm.
Algorithm:
INPUT:: integers, ,
OUTPUT: : where
and integers which satisfy
The following notations are two of the methods to measure the complexity of an algorithm. O-notation will give us an upper bound of complexity, while -notation will yield a lower bound.
An example of O-notation is . This is true because , for all , after taking .
To further clarify these definitions, let us look at the complexity of the Extended Euclidean Algorithm defined above.
The basis for the security of the Blum-Goldwasser cryptosystem, as well as the actual encryption and decryption, is in computing quadratic residues. In this section, I will discuss theorems generally and in the more specific case of , distinct odd primes, that will apply to the Blum-Goldwasser cryptosystem.
The number theory behind the Blum-Goldwasser cryptosystem uses the modulo operation. The modulo operation yields the remainder after the division of two numbers. This lends to a set of congruencies between numbers.
The order of is important for security. The larger the group, the harder it will be to randomly stumble across our quadratic residues.
proof:
Let
. Clearly,
. Let
be defined as
. Then,
since is abelian. Thus, is a homomorphism. By definition,
. Since
and
, then
.
The Blum-Goldwasser system utilizes the product of two primes, . We want to look at the order of the group .
Here is an example of Lemma 2 entered using Sage:
[frame = single, label = \Sage, fontsize = \small] sage: n = 11; QR = list(Set([x^2%n for x in range(1,n) if gcd(x,n)==1])); QR; len(QR) [1, 3, 4, 5, 9] 5 sage: n = 13; QR = list(Set([x^2%n for x in range(1,n) if gcd(x,n)==1])); QR; len(QR) [1, 3, 4, 9, 10, 12] 6 sage: n = 11*13; QR = list(Set([x^2%n for x in range(1,n) if gcd(x,n)==1])); len(QR) 30
proof: Let be distinct odd primes, and let . Suppose and for some . Then . Further, since has either 0 or 2 solutions, and has either 0 or 2 solutions, we see has either 0 or 4 solutions. In particular, if , then is a 4-1 map, so
[frame = single, label = \Sage, fontsize = \small] sage: p = 23; q = 47 sage: a = randrange(2,20); a 2 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; len(solns1) 2 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; len(solns2) 2 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; len(solns) 4 sage: a = randrange(2,20); a 13 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; solns1; len(solns1) [6, 17] 2 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; solns2; len(solns2) [] 0 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; solns; len(solns) [] 0 sage: a = randrange(2,20); a 5 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; solns1; len(solns1) [] 0 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; solns2; len(solns2) [] 0 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; solns; len(solns) [] 0 sage: a = randrange(2,20); a 16 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; solns1; len(solns1) [4, 19] 2 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; solns2; len(solns2) [4, 43] 2 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; solns; len(solns) [4, 372, 709, 1077] 4 sage: a = randrange(2,20); a 7 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; solns1; len(solns1) [] 0 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; solns2; len(solns2) [17, 30] 2 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; solns; len(solns) [] 0 sage: a = randrange(2,20); a 2 sage: solns1 = [x for x in range(p) if (x2-a)%p == 0]; solns1; len(solns1) [5, 18] 2 sage: solns2 = [x for x in range(q) if (x2-a)%q == 0]; solns2; len(solns2) [7, 40] 2 sage: solns = [x for x in range(p*q) if (x2-a)%(p*q) == 0]; solns; len(solns) [87, 524, 557, 994] 4
Furthermore, all solutions to this system are congruent modulo the product .
The unique solution to the Chinese Remainder Theorem is given by Gauss' Formula.
In our case, if
Theorem 3 is a generalization of Fermat's Little Theorem, because if is a prime number, then .
and
Digital communication is centered around the transmission of binary sequences, strings of 1's and 0's, that represent letters, numbers and symbols. A pseudo-random sequence is a sequence of numbers that appears random to a user, but actually repeats after some point. The length of the sequence before it repeats is referred to as the period of the sequence. In order to formally define a pseudo-random binary sequence , we must first define its autocorrelation .
We will also be examining the "runs" in a binary sequence. A run is a subsequence of all 0's or 1's. The length and frequency with which each run appears has a role in determining if the sequence is pseudo random or not.
In order to satisfy this condition, a sequence with 0's will have 1's, .
The Blum-Blum-Shub pseudorandom number generator was created in a 1986 paper by Lenore Blum, Manual Blum and Michael Shub [BBS]. It creates a streamcipher that meets all the requirements of a pseudorandom binary sequence.
Our implementation uses a pseudo-random number generator built into Sage to generate the initial seed . Many of these pseudo-random number generators are linear feedback shift registers, as discussed in [Bro]. All of these pseudo-random number generators are periodic over time. This creates a possible problem with the random seed and the Blum-Blum-Shub generator. Obviously, a short period will lead to replicated numbers, and make a message more easily decipherable. Similarly, a repeated random seed allows for easy decryption by an adversary if they have both the original message and the encrypted version . In their paper, Blum, Blum and Shub prove that in certain conditions the period, . Let us define to be the order of .
proof: Recall, since is the period of the sequence , it is the least possible integer such that . Also, note that is an odd number. Thus, by Theorem 4,
Conversely, by assumption, is the least positive integer such that So, . But, since it is also true that . Therefore, So, by assumption, , and, since , it can be seen that Therefore, when all the assumptions hold.
To examine this further, we need to define a type of prime that will have uses in our examples.
According to Theorem 5, we need an , our initial quadratic residue, with order of . Here are some Sage examples that demonstrate how often a quadratic residue has the required period.
[frame = single, label = \Sage, fontsize = \small] sage: p = 2*11+1; q = 2*23+1; n = p*q sage: QR = quadratic_residues(n) sage: QR.remove(0) sage: QR = [x for x in QR if gcd(x,n)==1] sage: R = IntegerModRing(n) sage: L = [R(x).multiplicative_order() for x in QR] sage: list_plot(L)The list_plot command is seen in Figure 1 below.
Below, we have a table of a sampling of quadratic residues with their multiplicative orders as presented in the graph above.
[frame = single, label = \Sage, fontsize = \small] sage: [(QR[i],L[i]) for i in range(10)] [(1, 1), (2, 253), (3, 253), (4, 253), (6, 253), (8, 253), (9, 253), (12, 253), (16, 253), (18, 253)] sage: [(QR[i],L[i]) for i in range(100,111)] [(404, 253), (418, 253), (426, 253), (427, 253), (430, 253), (432, 253), (439, 253), (440, 253), (441, 253), (450, 253), (455, 253)] sage: [(QR[i],L[i]) for i in range(115,125)] [(484, 23), (486, 253), (487, 253), (491, 253), (495, 253), (507, 23), (512, 253), (518, 11), (519, 253), (524, 253)]
[frame = single, label = \Sage, fontsize = \small] sage: p = 263; p1 = 131 sage: q = 347; q1 = 173 sage: n = p*q; n 91261 sage: QR = quadratic_residues(n) sage: QR.remove(0) sage: QR = [x for x in QR if gcd(x,n)==1] sage: R = IntegerModRing(n) sage: L = [R(x).multiplicative_order() for x in QR] sage: a = L[1]; a 22663 sage: odds = [i for i in range(len(L)) if L[i]!=a] sage: len(odds); len(L) 303 22663 sage: list_plot(L)The list_plot command is seen in Figure 2 below.
The above examples demonstrate that almost all quadratic residues meet the needs of Theorem 5. Looking further, at special numbers specifically, we can estimate
proof: Let the above assumptions hold. Then,
Special Blum primes only occur as ln of all primes, but a special number has the maximum approximation. In his paper, Brock discusses linear feedback shift registers and their periods. While BBS itself is not a LFSR, it can be examined in a similar manner.
The period length of this sequence is the one of the inherent security issues present in the Blum-Blum-Shub sequence. A large period makes it hard for an adversary to determine the seed by listening to the sequence and determining where it repeats, while a small period makes the sequence more susceptible to attacks. Another possible attack, however, comes from an adversary finding the initial seed computationally. The fact that is a quadratic residue ensures security here. If we examine prime for quadratic residues, we will discover there are quadratic residues. Observe that, for , numbers in are quadratic residues. If someone could determine the quadratic residuosity of a number , then the security of the system may be compromised. However, there is an assumption about the difficulty of finding quadratic residues [BBS, GM].
This means that for large enough , it is virtually impossible, by sheer time constraints, to compute the initial seed , making this number generator safe from this mathematical attack.
The Blum-Goldwasser cryptosystem [BG] makes use of the BBS streamcipher to encrypt a message. In addition, the decryption algorithm is used to determine the initial seed of BBS, , without compromising the integrity of the system.
Consider a message a binary string of length Let be a random seed Let be the Blum-Blum-Shub streamcipher of length associated to Compute where indicates the XOR operation. This defines the ciphertext output of the Blum-Goldwasser encryption algorithm. Alice sends the ciphertext along with a number
Bob receives a ciphertext and a number Let
Now, use the Extended Euclidean Algorithm (sec. 2.1) to compute such that Set
We now give the proof that the decryption is correct.
proof:
Let be the transmitted cipher, where
.
Since
by the Chinese
Remainder Theorem, see theorem 1, for each ,
Recall that is a quadratic residue, and is therefore equal to for some . Therefore, when ,
Similarly,
Since Bob has now calculated the original , he can generate the Blum-Blum-Shub streamcipher by calculating , and recreating , where . When is calculated, is the decrypted message.
[frame = single, label = \Sage, fontsize = \small] sage: from sage.crypto.public_key.blum_goldwasser sage: import BlumGoldwasser sage: bg = BlumGoldwasser(); bg The Blum-Goldwasser public-key encryption scheme. sage: p = 499; q = 547 sage: pubkey = bg.public_key(p, q); pubkey 272953 sage: prikey = bg.private_key(p, q); prikey (499, 547, -57, 52) sage: P = "10011100000100001100" sage: C = bg.encrypt(P, pubkey, seed=159201); C ([[0, 0, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]], 139680) sage: M = bg.decrypt(C, prikey); M [[1, 0, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 0, 0]] sage: flatten(M) [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0] sage: M = "".join(map(lambda x: str(x), flatten(M))); M '10011100000100001100' sage: M == P True
The Blum-Goldwasser cryptosystem is a very efficient system both for encryption and decryption, comparable to the current standard, RSA encryption. During encryption, the Blum-Goldwasser cryptosystem actually performs faster than the standard in all but a few special cases. It is in linear time and based on generating the BBS stream cipher. In decryption, the initial calculations have a fixed number of steps, with additional steps based on message size. This makes it less efficient than RSA for short messages, but a quicker decryption for long messages. Decryption is also accomplished in linear time [Men].
It has been discussed in previous papers on the subject that the Blum-Goldwasser cryptosystem is susceptible to a chosen-ciphertext attack. This attack is based on an attacker finding a ciphertext and its decryption without knowing the key. With this knowledge, the attacker may be able to determine the initial seed , thus destroying the security of the system. Our model, however, takes a few steps to correct this. Firstly, we have a random initial seed for each message we send. This means that with a chosen-ciphertext attack an adversary may gain knowledge of one initial seed, but the for a second message is one of quadratic residues. Thus, the probability of having the same seed is extremely low. Another possible way to block this attack is with an authentication challenge. This would require challenging the attacker for the private key, similar to a password to gain network access. This should also work to prevent this attack.
The Blum-Goldwasser cryptosystem is an efficient system for both encryption and decryption with slight security deficiencies to a chosen ciphertext attack. Through my research I have tried to find a possible means to cover these deficiencies. We have theorized that changing the initial seed, , in a pseudorandom method, the system may then be immune to these attacks. Based on the fact that there will be different initial seeds, for a large , the same message could be sent using each quadratic residue as the initial seed and each create a different ciphertext, . Is this enough to classify this system secure? If so, is it financially feasible in comparison to RSA? This system has no public uses currently, but based on its efficiency and security, the Blum-Goldwasser cryptosystem could replace RSA in some daily uses.
[frame = single, label = \Sage, fontsize = \small] """ Functions written to implement the Blum-Goldwasser cryptosystem, written as part of an honors math project at the USNA in 2010. As part of official government work, this is in the public domain. REFERENCES: Blum-Goldwasser cryptosystem http://en.wikipedia.org/wiki/Blum-Goldwasser_cryptosystem Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. http://www.cacr.math.uwaterloo.ca/hac/ (see chapter 8) M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985. The implementation below is a blend of these. AUTHORS: M. Hogan and D. Joyner (wdjoyner@gmail.com) Last modified: 2010-02-06 """ def num2bin(x): """ Converts integer in range (1,255) to binary. EXAMPLES: sage: num2bin(100) """ return [floor(x/2**(7-i))%2 for i in range(8)] def string2ascii(m): """ Converts a string of characters to a sequence of 0's and 1's using the Python ord command. EXAMPLES: sage: string2ascii("usna2010") """ L = [] for a in m: L.append(ord(a)) M = [num2bin(x) for x in L] return flatten(M) def ascii2string(M): """ M is a ciphertext message of 0's and 1's of length 8k. This returns a string of characters representing that list in ascii. EXAMPLES: sage: M = [0,1,0,1,0,1,0,0,0,1,0,0,0,0,1,0] sage: ascii2string(M) 'BT' """ m = len(M) k = int(m/8) S = [] for i in range(k): s = sum([2**(7-j)*M[8*i+j] for j in range(8)]) S.append(chr(s)) sumS = "" for s in S: sumS = s + sumS return sumS def carmichael(n): """ The Carmichael function of a positive integer n, denoted \lambda(n) in the literature, is defined as the smallest positive integer m such that \[ a^m \equiv a \pmod n, \] for every integer a that is both coprime to and smaller than n. In other words, in more algebraic terms, it defines the exponent of the multiplicative group of residues modulo n. EXAMPLES: sage: carmichael(4) 2 sage: euler_phi(4) 2 sage: carmichael(8) 2 sage: euler_phi(8) 4 sage: carmichael(10) 4 sage: euler_phi(10) 4 sage: carmichael(36) 6 sage: euler_phi(36) 12 sage: n = 100; a = 11; (power_mod(a,carmichael(n), n) - 1)%n 0 sage: n = 111; a = 11; (power_mod(a,carmichael(n), n) - 1)%n 0 REFERENCES: http://en.wikipedia.org/wiki/Carmichael_function """ L = factor(n) if n == 2: return 1 if n == 4: return 2 t = len(L) # the no. of dist. prime factors of n if t == 1: # n is a prime power p = L[0][0] if p == 2: # so n is a power of 2 return ZZ(n/4) if p>2: return ZZ((p-1)*n/p) powers = [L[i][0]**L[i][1] for i in range(t)] return lcm([carmichael(m) for m in powers]) def bbs(N, x0, L): """ Implements the Blum-Blum-Shub pseudo-random number generator. INPUT: N - product of two primes, each congruent to 3 (mod 4) x0 - a seed, 1<x0<N (possibly a square (mod N)?) L - the length of the sequence OUTPUT: a pseudo-random sequence of 0's and 1's NOTE: Under some reasonable hypotheses, Blum-Blum-Shub [1] sketch a proof that the period of the BBS stream cipher is equal to carmichael(carmichael(N)). This is verified below in a few examples by using the Sage function lfsr_connection_polynomial (written by Tim Brock) which computes the connection polynomial of a linear feedback shift register sequence. The degree of that polynomial is the period. EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: p%4 == 3; q%4 == 3 True True sage: bbs(p*q, 999, 10) [1, 1, 1, 1, 1, 1, 0, 0, 0, 1] sage: carmichael(carmichael(7*11)) 4 sage: bbs(7*11, 13, 16) [1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0] sage: s = [GF(2)(x) for x in bbs(7*11, 13, 60)] sage: lfsr_connection_polynomial(s) x^3 + x^2 + x + 1 sage: carmichael(carmichael(11*23)) 20 sage: s = [GF(2)(x) for x in bbs(11*23, 13, 60)] sage: lfsr_connection_polynomial(s) x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12\ + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 REFERENCES: [1] Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/61.PDF """ if L<0: return [] b = [x0%2] # = [x0**2%2] R = IntegerModRing(N) x0 = R(x0) for i in range(L-1): x1 = x0**2 b.append(ZZ(x1)%2) x0 = x1 return b class BGCryptosystem(): """ Class implementing Blum-Goldwasser cryptosystems. EXAMPLES: """ def __init__(self, public_key): self._public_key = public_key def public_key(self): """ Returns the public key of the cipher. EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: BG = BGCryptosystem(p*q) sage: BG.public_key() 1123957 """ return self._public_key def __str__(self): """ Print method. EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: BG = BGCryptosystem(p*q) sage: print BG BGCryptosystem(1123957) """ return "BGCryptosystem(%s)"%self.public_key() def __repr__(self): """ Display method. EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: BG = BGCryptosystem(p*q) sage: BG Blum-Goldwasser cryptosystem with public key 1123957. """ return "Blum-Goldwasser cryptosystem with public key %s."%self.public_key() def random_key(self): """ Returns a random key to be used by the cipher. EXAMPLES: """ N = self.public_key() return floor(rand()*N) def encrypt(self, M, r): """ Implements the Blum-Goldwasser public key encryption algorithm. INPUT: M - a cleartext string (the message) r - a random number 1 < r < N EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: p%4 == 3; q%4 == 3 True True sage: BG = BGCryptosystem(p*q) sage: c, y = BG.encrypt("Hello World", 999) sage: len(c) 88 sage: y 760299 TODO: Check if r can be defined inside the method, and removed as an input parameter. """ N = self.public_key() m = string2ascii(M) L = len(m) R = IntegerModRing(N) x0 = ZZ(R(r**2)) b = bbs(N, x0, L) return [(b[i]+m[i])%2 for i in range(L)], power_mod(x0, 2**L, N) def decrypt(self,c,y,p,q): """ Implements the Blum-Goldwasser decryption algorithm. INPUT: b - a list of 0's and 1's of length L (the ciphertext) y - a number 1 < y < N = p*q p, q - primes, each congruent to 3 (mod 4) OUTPUT: a string (the cleartext message) EXAMPLES: sage: p = next_prime(1015); q = next_prime(1100) sage: p%4 == 3; q%4 == 3 True True sage: BG = BGCryptosystem(p*q) sage: c, y = BG.encrypt("Hello World", 999) sage: BG.decrypt(c,y,p,q) 'Hello World' """ N = p*q if not(N == self.public_key()): raise ValueError("Your private key (%s,%s) are incorrect"%(p,q)) L = len(c) pqgcd, a, b = xgcd(p,q) #rp = power_mod(y, int((p+1)/4)**L, p) #rq = power_mod(y, int((q+1)/4)**L, q) #pi = power_mod(p, -1, q) #qi = power_mod(q, -1, p) #x0 = (q*qi*rp + p*pi*rq)%N d1 = power_mod(int((p+1)/4), L, p-1) d2 = power_mod(int((q+1)/4), L, q-1) u = power_mod(y, d1, p) v = power_mod(y, d2, q) R = IntegerModRing(N) x0 = ZZ(R((v*a*p+u*b*q))) b = bbs(N, x0, L) d = [(x[0]+x[1])%2 for x in zip(b,c)] s = ascii2string(d) reverse_s = s[::-1] return reverse_s
The command line arguments were:
latex2html -t 'M. Hogan Math Honors Thesis 2009-2010' -split 0 hogan-honorsthesis2009-2010.tex
The translation was initiated by david joyner on 2010-05-05