COS 126

Linear Feedback Shift Register
Programming Assignment

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

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
For simplicity, we pass the initial seed to the constructor as a Java String whose characters are all 0 or 1. The length of the register is the length of the string. We will generate each new bit by xoring the most significant (leftmost) bit and the tap bit. The position of the tap bit comes from the constructor argument. For example, the following code creates the LFSR described above.
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 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
   Magritte pipe Noise

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 (Program 3.1.4 of the book), which relies on the 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
   Noise Magritte pipe
Anyone knowing this password and tap can get the original picture back, but another password won't work. (If you're not convinced, try it.) Thus, for example, you could post an encrypted picture on the web, but only friends who have the password (and your program) can see the original.

Getting started. The subdirectory lfsr from the COS126 ftp site contains a template file to get you started. It also contains, 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 and 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 implementation to take an alphanumeric password. To avoid problems with special characters, use a six-bit code where the ith character in the string

is encoded with the binary representation of i (this is the base-64 encoding from Lecture 1).

Your PhotoMagicDeluxe program should take three command-line arguments: an image name, an alphanumeric password, a tap number. Like, 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 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).

This assignment was created by Robert Sedgewick.
Copyright © 2008.