Write a program that produces pseudo-random bits by simulating a linear feedback shift register (see Lecture 1), and then use it to implement a simple encode/decode facility for photographs. The purpose of this program is to introduce you to object-oriented programming and to reinforce the message of Lecture 1.

To prepare for doing this program, reread the slides for Lecture 1 (to reacquaint yourself with the basic ideas behind LFSRs), the lecture slides for "Using Data Types" and "Creating Data Types", and pages 316-335 and 370-377 in the text (to learn the basics of object-oriented programming).

LFSR review.  A linear feedback shift register is a register of bits that performs discrete step operations that

• shift all the bits one position to the left and
• replace the vacated bit by the exclusive or of the bit shifted off and the bit at a given tap position in the register.

Our LFSR has two parameters: its number of bits N and the tap position tap. These two, plus the initial seed (the sequence of bits that initializes the register) determine the sequence of bits it produces. As in the example in Lecture 1, the following gives the contents of the LFSR with initial seed 01101000010 and tap position 8 after one step.

Simulate a LFSR.  Your first task is to implement a class that simulates the operation of a linear feedback shift register. Your class should implement the following API:

public LFSR(String seed, int tap)  // Create LFSR with the given initial seed and tap
public int step()                  // Step one position and return the least significant (rightmost) bit
public int generate(int k)         // Return a new k-bit pseudo-random integer
public String toString()           // Return a String representation of the LFSR

LFSR test1 = new LFSR("01101000010", 8);

To implement LFSR you need to choose the internal representation (instance variables) and to implement the constructor and three methods in the API. These are all interrelated, and there are several possible approaches. For this assignment, we require that you represent the LFSR as an array of int variables, all of which are either 0 or 1. Therefore, the constructor amounts to creating the array and converting the char values in the string to int values for the array (and initializing your other instance variables). The toString() method amounts to building a string by going through the array. The step() method simulates one step of the LFSR.

Extracting multiple bits.  Once you have thoroughly tested the step() method, you are ready to address your second major task: add a method generate() that takes an integer k as argument and returns a k-bit int value obtained by extracting k bits from the LFSR and converting from binary to integer. This task is easy to accomplish with a little arithmetic: initialize a variable to zero and, for each bit extracted, double the variable and add the bit returned by step(). For example, given the bit sequence 1 1 0 0 1 the variable takes the values 1, 3, 6, 12, 25, ending with the binary representation of the bit sequence.

(Note: The generate() method extracts bits from the LFSR by calling the step() method k times.)

A client to encrypt and decrypt images.  Your next task is write a LFSR client PhotoMagic.java that can encrypt images. PhotoMagic should take three command-line arguments, an image name, a binary password (an initial LFSR seed), and a tap number. It should save an encrypted image in a file named by prepending an X to the given file name (use the save() method in the Picture class). It should also show the encrypted image on the screen (use the show() method, also in the Picture class). For example, typing

% java PhotoMagic pipe.png 01101000010100010000 16

takes as input the image on the left below and produces the image (in a file) on the right below.

	pipe.png	Xpipe.png

Important notes: We use the .png format because it is a lossless format that preserves the precise bits in the colors. Also, it is best to use a password (and LFSR) that is longer than 12 bits because images have a large number of bits and also because our use of fixed tap position (such as 8) per run does not guarantee that the register will cycle through all values for all lengths. You might enjoy experimenting with violating these rules.

Implementing PhotoMagic is the easiest part of this assignment. It can be accomplished by a few additions and changes to Grayscale.java (Program 3.1.4 of the book), which relies on the Picture.java data type (Section 3.1). For each pixel (x, y), in the order (0, 0), (0, 1), (0, 2), ..., extract the red, green, and blue components of the color (an integer between 0 and 255), in that order. Then, xor each component with 8 new generated bits, create a new color using the result of the xor operations, and set the pixel to that color.

Now, here's the magic: If you understood Lecture 1, you know that running the same program with the same password on this picture recovers the original image!

% java PhotoMagic Xpipe.png 01101000010100010000 16

will produce the following result.

	Xpipe.png	XXpipe.png

Getting started. The subdirectory lfsr from the COS126 ftp site contains a template LFSR.java file to get you started. It also contains Picture.java, pipe.png and this assignment's readme.txt file.

Picking a good tap number. Here are suggested tap numbers for maximizing the cycle of different size binary registers: 5 bits, tap 2; 6 bits, tap 4; 9 bits, tap 4; 10 bits, tap 6; 11 bits, tap 8; 20 bits, tap 16; 30 bits, tap 22; 36 bits, tap 24; 48 bits, tap 42.

Submission.   Submit LFSR.java and PhotoMagic.java. Also, submit a readme.txt file and answer the questions.

Midterm Evaluation.  Please fill out the following anonymous questionnaire to provide us with feedback to help us improve this course.

Extra Credit 1.  Using a binary password is weak protection (see Extra Credit 2) and inconvenient, so create a PhotoMagicDeluxe.java implementation to take an alphanumeric password. To avoid problems with special characters, use a six-bit code where the ith character in the string

"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" 

Your PhotoMagicDeluxe program should take three command-line arguments: an image name, an alphanumeric password, a tap number. Like PhotoMagic.java, it should show the encrypted image and save that image in a file named by prepending an X to the input file name.

Note for Extra Credit 1.  Work modularly. Don't just copy huge sections of your homework code into your extra credit program. Have your Extra Credit client call any methods it needs to use. Yes, you can call any public method from another class.

Extra Credit 2.  Assume that you know the password has N bits (where N is the second command-line argument). Write a program BreakPhotoMagic.java that tries all possible seeds and all possible taps and finds the picture. Hint: all but the correct seed and tap will produce pseudo-random colors, so you can track the frequencies of each 8-bit value and pick the seed and tap that results in the frequencies that deviate the most from 128.

Warning: this program can take a very long time to run, so you want to debug it using small passwords with only 5 or 6 bits (even though 5 or 6 bits is not long enough to generate a very good encryption).

Your BreakPhotoMagic program should take two command-line arguments: the name of an encrypted image file, the number of bits in the password. It should print out the password and the tap, show the decrypted picture, and save the decrypted picture in a file (whose name is the name of the input file prepended with an X).