# The Blum-Goldwasser cryptosystem

Mike Hogan1

### Abstract:

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

# Introduction

The need for information security has been a paramount concern for military operations dating back to the Roman Empire and the rule of Julius Caesar. According to his biographer, Suetonius, Caesar kept messages confidential by using a simple shift cipher. The Japanese code, known as JN-25 to the Americans, was broken in 1942 to allow advanced knowledge of the impending invasion of Midway, and contributed to the American victory in the same battle. However, since the beginning of the information age, the need for cryptographic security has expanded to include encryption of bank information for everyday consumers making online purchases or even everyday communications by all people.

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.

# Background

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.

## Complexity

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.

Definition 1 (Algorithm)   An algorithm is a well-defined computational process that receives an input and, after a finite number of steps, yields an output.

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

1. Initialize
2. While ,
1. Set floor
2. Set
3. Set , and return

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.

Definition 2 (O-notation)   Let be positive functions on the natural numbers. Then we say

if there exists a constant and an such that for all .

An example of O-notation is . This is true because , for all , after taking .

Definition 3 (-notation)   Let be positive functions on the natural numbers. Then we say

if there exists a constant and an such that for all .

To further clarify these definitions, let us look at the complexity of the Extended Euclidean Algorithm defined above.

Remark 1   Let be the Extended Euclidean Algorithm. Then . Also, since can be found in any number of steps, there is no lower bound to it, thus does not exist for this algorithm.

## Kerckhoff's Principles of Cryptographic Security

Auguste Kerckhoff articulated six rules for cryptographic security in his 1883 article, La cryptographie militaire,'' part of Journal des sciences militaires.

### The system should be unbreakable in practice

While a system that is mathematically unbreakable is ideal, a fundamentally secure cryptosystem needs only to be unbreakable in practice. The Blum-Goldwasser cryptosystem is breakable only through factoring , a problem that is believed practically impossible if is 1000 bits.

### Security through obscurity is bad

An adversary who knows what system is being used should not have any advantage in breaking it. The Blum-Goldwasser system is public-key, therefore it will be widely known by any adversary. In our application, an extra step is being taken to ensure against chosen ciphertext attacks, making it not quite a public-key system. However, adversaries will still have the same trouble in breaking the system even if they know the method of encryption.

### The public key is easily communicable and changeable

The public-key is easily changed (as will be seen in the simple Python code below) and can be transferred from party to party without compromising the integrity of the system.

### Cryptogram should be transmissible digitally

Since the only transmission is a -length binary string, it is easily transferrable through digital means, including telegraph, the original apparatus used for Kerckhoff's theories.

### Encryption apparatus is portable and operable by a single person

The apparatus is a computer with a Python compiler.

### The system is easy to use

There is no need for knowledge of the system in order to use our implementation. The user needs only enter the message he or she wishes to encrypt. The implementation calculates everything for the user.

## Number theory

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.

Example 1   , so

Definition 4 (Quadratic residue)   Let be an integer. We say is a quadratic residue if the congruence is solvable. The set of all quadratic residues , , is denoted by .

The order of is important for security. The larger the group, the harder it will be to randomly stumble across our quadratic residues.

Lemma 1   Let be a prime number, . is a subgroup of of index 2. In other words,

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 .

Lemma 2   Let be odd primes with . Then the order of the group of quadratic residues mod is given by:

Example 2

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


We can prove this formally as well:

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

Example 3   Here are a couple of examples of the above proof entered into Sage. You will see that 4 solutions is only reached when has 2 solutions each mod and mod .
[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


Theorem 1 (Chinese Remainder Theorem)   Suppose are positive integers which are pairwise coprime. Then, for any given integers , there exists an integer solving the system of simultaneous congruences

Furthermore, all solutions to this system are congruent modulo the product .

The unique solution to the Chinese Remainder Theorem is given by Gauss' Formula.

Theorem 2 (Gauss' Formula)   In the Chinese Remainder Theorem, the solution is given by

where

In our case, if

then

Theorem 3 (Euler's theorem)   For any modulus and any integer coprime to , we have

where denotes Euler's totient function counting the integers between and that are coprime to .

Theorem 3 is a generalization of Fermat's Little Theorem, because if is a prime number, then .

Definition 5 (Carmichael's -function)   Let , where are distinct odd primes. Carmichael's -function is defined by

and

Remark 2   When , with distinct odd primes, then We will be using this later.

Theorem 4 (Carmichael's Theorem)   Let be integers such that is coprime to . Then,

Remark 3   Let be the product of two primes. By Theorems 3 and 4, This shows that is an upper bound for the period of the sequence . It is also possible that the "true period" is a proper factor of .

# Pseudo-random Binary Sequences

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 .

Definition 6 (Autocorrelation)   Let , be a sequence of numbers considered random.'' We say the autocorrelation of is

If is periodic with period , then the autocorrelation is reduced to

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.

Definition 7 (Pseudo-random binary sequence)   Let , , be a binary sequence with period . We say this sequence is pseudo-random provided the following conditions hold (Golomb's Principles) [Gol]:
1. balance: .

In order to satisfy this condition, a sequence with 0's will have 1's, .

2. low autocorrelation:

for some "small" . For sequences satisfying these first two properties, it can be seen that must hold.
3. Proportional Runs Property: In each period, half the runs are length , one-fourth are length , one-eighth are length , etc. Moreover, there are as many runs of 1's as there are of 0's.

## Generalities

Now that a pseudo-random binary sequence is defined, it is important to know how this pertains to a cryptosystem. Let be a message in binary, and let be a pseudo-random binary sequence. If you add and component wise with a modulo of , you will receive a new message that is completely different from the other two. However, if you want to retrieve again, simply add and in the same manner, and the result yielded is . This is called a stream cipher. The Blum-Goldwasser cryptosystem relies heavily on a stream cipher known as the Blum-Blum-Shub stream cipher.

## BBS stream cipher

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.

Definition 8 (Blum-Blum-Shub streamcipher)   Let be two distinct prime numbers such that and . Let and let be a random number. We define , the first number of the Blum-Blum-Shub pseudorandom number generator as

Each proceeding seed can be defined as

or, more generally by Theorem 3,

The streamcipher, , is created by setting , thus yielding a pseudorandom string of 0's and 1's.

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 .

Theorem 5 (Period of )   Let be a number as described above and let be a quadratic residue of it. Let be the period of the BBS sequence, . If and then .

In order to prove the equality of the statements, it is enough to show that and .

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,

By definition of , since . Therefore,

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.

Definition 9 (Special Blum Prime)   Let be a prime number. We say is a special Blum prime if and only if , and with prime numbers. A number is special if and only if are distinct special Blum primes.

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.

Example 4   Here is an example, using Sage, plotting the multiplicative order of each quadratic residue of . In this specific example, we use two special Blum primes. Note that
[frame = single, label = \Sage, fontsize = \small]
sage: p = 2*11+1; q = 2*23+1; n = p*q
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)]


Example 5   Here is larger example using . As you can see, almost all multiplicative orders are . In fact, only of the quadratic residues are not of the desired order.
[frame = single, label = \Sage, fontsize = \small]
sage: p = 263; p1 = 131
sage: q = 347; q1 = 173
sage: n = p*q; n
91261
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

Theorem 6 (Period of a special number)   Let be a special number and be a quadratic residue satisfying the conditions of Theorem 5. Then, can be estimated asymptotically from below by , as .

Remark 4   This improves on the estimate given in [BBS].

proof: Let the above assumptions hold. Then,

Thus, continuing with Carmichael's function,

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.

Theorem 7 (Blum-Blum-Shub as a LFSR)   Let be a given BBS sequence with period . Define . Then, the BBS sequence can be considered a LFSR with a key length of , approximated by .

Sketch of proof: The shortest LFSR of a sequence can be defined by the connection polynomial as described in [Bro]. With a small key, the Berlekamp-Massey method is efficient to define this connection polynomial and break the sequence. However, with a long key, specifically of length , this is just as inefficient as trying to calculate the quadratic residues.

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].

Definition 10 (Quadratic residuosity assumption)   The quadratic residuosity assumption states that it is "hard on average" to compute the quadratic residue of a number in . More formally, for each polynomial , the complexity is , so there is no polynomial time algorithm to determine the quadratic residue of a number.

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.

# BG cryptosystem

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.

## Encryption

Definition 11 (XOR operation)   Let and be binary sequences. We define as

for all .

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

Remark 5   Note: If we were to take again, it will yield the original message

## Decryption

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.

Theorem 8 (Decryption algorithm works)

proof: Let be the transmitted cipher, where . Since
by the Chinese Remainder Theorem, see theorem 1, for each ,

has a unique solution , given by

We know that satisfies

So,

 (1)

Recall that is a quadratic residue, and is therefore equal to for some . Therefore, when ,

because of Fermat's Last Theorem. It follows, for any

where . Repeat this method for replaced by :

We can inductively repeat this until the process yields

Similarly,

Therefore, by the uniqueness of the Chinese Remainder Theorem solution and (1), we have

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.

Example 6   Here is an example of the encryption and decryption of a string of 's and 0's implemented in Sage version 4.3.4. We will be using a private key and to keep it simple.

[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


## Complexity

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].

## Security

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.

# Conclusion

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.

# Appendix: Sage code

This is the initial code on Python implemented by Prof Joyner and me. The code has since been cleaned and added to Sage 4.3.4 by Minh Van Nguyen. A special thanks to Minh for his hard work in the implementation.
[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)

"""

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()):
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


## Bibliography

BBS
L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo random number generator. SIAM Journal on Computing, Volume 15, Issue 2, pp. 364-383. Society for Industrial and Applied Mathematics, Philadelphia, 1986.

BG
M. Blum and S. Goldwasser. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. In Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 289-299, Springer, 1985. the decry

Bro
T. Brock. Linear Feedback Shift Registers and Cyclic Codes in SAGE. Rose-Hulman Undergraduate Mathematics Journal, Vol. 7, Issue 2, 2006.

GM
S. Goldwasser and S. Micali. Probabilistic Encryption and 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, ACM, New York, 1982.

Gol
S. Golomb, Shift register sequences. Aegean Park Press, Laguna Hills, Ca, 1967

Men
A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

S
W. Stein, Sage: Open-source Mathematical Software, version 4.3.4, 2010.

The Blum-Goldwasser cryptosystem

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

#### Footnotes

... Hogan1
Department of Mathematics, United States Naval Academy, Honors Thesis 2009-2010, Advisor Prof. Joyner, wdj@usna.edu
david joyner 2010-05-05