COS 126

Linear Feedback Shift Register
Programming Assignment

Write a program that produces pseudo-random bits by simulating a linear feedback shift register, and then use it to implement a simple encode/decode facility for photographs.

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

A LFSR has three parameters that characterize the sequence of bits it produces: the number of bits N, the tap position tap, and the initial seed (the sequence of bits that initializes the register). 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 write a class that simulates the operation of a LFSR by implementing the following API:

public class LFSR
       LFSR(String seed, int tap)  //  create LFSR with the given initial seed and tap
   int step()                      //  simulate one step and return the least significant (rightmost) bit as 0 or 1
   int generate(int k)             //  simulate k steps and return k-bit integer
String toString()                  //  return a string representation of the LFSR

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.

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 (each component is an integer between 0 and 255). Then, xor the red component with 8 newly generated bits. Do the same for the green (using another 8 newly generated bits) and, finally, the blue. 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, Xbaboon-red.png, Xscarpet-cookies.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.  Using a binary password is weak protection (see Challenge for the Bored) 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.  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.

Challenge for the bored.  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).

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