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 (LFSR) 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 tap position tap. As in the example in Lecture 0, the following illustrates one step of an 11-bit LFSR with initial seed 01101000010 and tap positions 9.

one step of an LFSR one step of an 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 {

   // creates an LFSR with the specified seed and tap
   public LFSR(String seed, int tap)

   // returns the number of bits in the LFSR.
   public int length()

   // returns bit i as 0 or 1.
   public int bitAt(int i)

   // returns a string representation of this LFSR
   public String toString()

   // simulates one step of this LFSR and return the new bit as 0 or 1
   public int step()

   // simulates k steps of this LFSR and return the k bits as a k-bit integer
   public int generate(int k)

   // tests this class by directly calling all instance methods
   public static void main(String[] args)

To do so, you need to choose the internal representation (instance variables), implement the constructor, and implement the 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 that can encrypt and decrypt pictures, by implementing the following API:

public class PhotoMagic {

   // Returns a transformed copy of the specified picture, using the specified LFSR.
   public static Picture transform(Picture picture, LFSR lfsr)

   // Takes the name of an image file and
   // a description of an LFSR as command-line arguments;
   // displays a copy of the image that is "encrypted" using the LFSR.
   public static void main(String[] args)
Here are a few more details about the API.

Files for this assignment. The file contains a number of sample PNG files, including the ones used above; an optional template for getting started with; and this week's readme.txt template.

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

Submission.   Submit,, and a completed readme.txt file.

Challenge for the bored 1.  Using a short binary password is weak protection and using a long one is inconvenient. Write a client with the same API as, but use a short alphanumeric password instead of a long binary one. For example, if your password works over a 64-character alphabet

String base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
then a length n alphanumeric will provide as much security as a length-6n binary one.

Challenge for the bored 2.  Write a program 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. 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.

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