[an error occurred while processing this directive]
CIS 110

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 form of encryption for digital pictures.

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 initial seed (the sequence of bits that initializes the register), and the the tap position tap. As in the example in Lecture 1, the following illustrates one step of an 11-bit LFSR with initial seed 01101000010 and tap position 8.


LFSR class.  Your first task is to write a class that simulates the operation of a LFSR by implementing the following API:

public class LFSR
public static boolean init(String seed, int tap) //  create LFSR with the given initial seed and tap
public static int     step()                     //  simulate one step and return the least significant (rightmost) bit as 0 or 1
public static int     generate(int k)            //  simulate k steps and return k-bit integer
public static String  string()                   //  return a string representation of the LFSR
public static void    main(String[] args)        //  test all of the methods in LFSR

A client to encrypt and decrypt images.  Your final task is write a LFSR client PhotoMagic.java that can encrypt and decrypt imgages. Java provides a variety of ways to work with images, all of them extremely clunky. Instead, we will treat images as a 2-D array of integers, where each integer encodes a pixel color and transparency. The first dimension of the array is the row, and the second dimension is the column. To access a specific pixel, you therefore write array[row][col]. If you prefer to think in terms of (x,y) coordinates, then the equivelant statement is array[y][x] (note the inversion of y and x). In order to work with images as integer arrays, you should download the ImageData and Picture classes into the same folder as your assignment. ImageData provides the following API that you can use to load, save, and display images:

public class ImageData
public static int[][] imageData(String filename) // load image filename and return it as a 2-D array of integers
public static void    show(int[][] img)          // display img in a window
public static void    save(int[][] img, String filename) // save img to filename
PhotoMagic must implement the following API:
public class PhotoMagic
public static int[][] transform(int[][] picture, String seed, int tap)  //  transform picture using lfsr
public static  void main(String[] args)         //  read in the name of a picture and the description of an LFSR
                                                //  from the command-line and encrypt the picture with the LFSR

Commenting and coding style.   We are getting stricter about deducting points for bad style and not following directions in the assignment. Make sure you adhere to the style guide on the book site. This includes commenting your code. In addition to the file header, each function should have a comment indicating its purpose, the meaning of its arguments, and what it returns. Also, each section of code or variable declarations whose purpose is not completely obvious should have a brief comment describing its purpose. By convention, comments are either placed on the same line as the statement they are commenting, or on the line(s) above the code they refer to. See the style guide for more description of good commenting practice. Remember, comments are signposts to help you (and others) understand what code is doing and why it's structured the way it is. They don't need to be voluminous, nor do they need to be great works of literature.

Checklist.   Don't forget to read the checklist.

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

Extra credit.  Using a short binary password is weak protection and using a long one is inconvenient. For extra credit, write a client PhotoMagicDeluxe.java with the same API as PhotoMagic.java, but use an alphanumeric password instead of a binary one. Assume that the password contains only characters from the 64-character alphabet:

String base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
Interpret an N-character alphanumeric password as a 6N-character binary password, where the ith character in the 64-character alphabet is expanded to the 6-bit binary representation of i. For example, the 10-character alphanumeric password OPENSESAME corresponds to the 60-character binary password 001110001111000100001101010010000100010010000000001100000100. For full credit, work modularly: do not copy huge chunks of code from PhotoMagic.java to PhotoMagicDeluxe.java; instead call PhotoMagic.transform().

Challenge for the bored.  Write a program BreakPhotoMagic.java that the name of an encrypted picture and the number of bits N in the password as command-line arguments, tries all possible binary passwords of length N and all possible taps, and decrypts 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; we recommend debugging it using pictures transformed with binary passwords of length 5 or 6.

This assignment was created by Robert Sedgewick and adapted by Benedict Brown.
Copyright © 2008-2012.