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

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

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

To do so, you need to choose the internal representation (instance variables), implement the constructor, and implement the three instance methods. These are interrelated activities and there are several viable approaches.

A client to encrypt and decrypt images.  Your final task is write a LFSR client PhotoMagic.java that can encrypt and decrypt pictures, by implementing the following API:

public class PhotoMagic
-----------------------------------------------------------------------------------------------------------------------------
public static Picture transform(Picture picture, LFSR lfsr)  // return a transformed copy of picture using lfsr

public static    void main(String[] args)                    // read in the filename of a picture and the description of an
                                                             // LFSR from the command line and display an encrypted copy of 
                                                             // the picture.  Use the LFSR to do the encryption.
For most people the Picture class we're using is already installed on your system. See pp. 324–337 in the textbook and the checklist for more information.

Files for this assignment. Here is the readme.txt template for this week. There are additional optional files described in the checklist: a template for LFSR.java giving one way of getting started, and sample pictures for testing.

Style.   When implementing a class, include a comment next to each instance variable (field) indicating its purpose, and one above each method (function) documenting what it does.

Submission.   Submit LFSR.java, PhotoMagic.java, and a completed readme.txt file.

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.

To earn extra credit, you must work modularly. Do not copy huge chunks of code from PhotoMagic.java to PhotoMagicDeluxe.java. Instead, call PhotoMagic.transform(). Optionally, as an alternative, read about inheritance which is not a topic for this course, then inherit your extra credit class from PhotoMagic while overriding only main. (If you use inheritance, ignore the two API warnings for PhotoMagicDeluxe about superclasses not matching and transform missing.)

Challenge for the bored.  Write a program BreakPhotoMagic.java that takes the filename 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.
Copyright © 2008.