COS126

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

What is an LFSR? A linear-feedback shift register (LFSR) is a register of bits that performs discrete step operations that:

shifts the bits one position to the left and
replaces the vacated bit by the exclusive or(xor) of the bit shifted off and the bit previously at a given tap position in the register.

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.

Here is a live demo:

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.

Constructor. The constructor takes the initial seed as a String argument, which is composed of '0' and '1' characters. The number of bits n in the LFSR is equal to the length of the seed. We will generate each new bit by xoring the leftmost bit and the tap bit. The index of the tap bit is specified as the second constructor argument. For example, the following code creates the LFSR described above.
```
LFSR lfsr0 = new LFSR("01101000010", 9);
```
Length. The length() method returns the number of bits n in the LFSR. For example, lfsr0.length() returns 11.
Extract the ith bit. The bitAt() method returns the bit i of the LFSR. For example, lfsr0.bitAt(9) returns 1 and lfsr0.bitAt(11) returns 0.
String representation. The toString() method returns a string representation of the LFSR by concatenating the values in the registers. For example,
```
LFSR lfsr0 = new LFSR("01101000010", 9);
StdOut.println(lfsr0);
```
outputs
```
01101000010
```

Simulate one step. The step() method simulates one step of the LFSR and returns the rightmost bit as an integer (0 or 1). For example,

LFSR lfsr1 = new LFSR("01101000010", 9);
StdOut.println(lfsr1);
for (int i=0; i < 10; i++) {
    int bit=lfsr1.step();
    StdOut.println(lfsr1 + " " + bit);
}

outputs

01101000010
11010000101 1
10100001011 1
01000010110 0
10000101100 0
00001011001 1
00010110010 0
00101100100 0
01011001001 1
10110010010 0
01100100100 0

Extracting multiple bits. The method generate() takes a positive integer k as an argument and returns a k-bit integer obtained by simulating k steps of the LFSR. 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, extracting (from left to right) each bit from the sequence 1 1 0 0 1, the variable takes on the values 1, 3, 6, 12, and 25, ending with the binary representation of the bit sequence. For example,
```
LFSR lfsr2 = new LFSR("01101000010", 9);
StdOut.println(lfsr2);
for (int i = 0; i < 10; i++) {
    int r = lfsr2.generate(5);
    StdOut.println(lfsr2 + " " + r);
}
```
outputs
```
01101000010
00001011001 25
01100100100 4
10010011110 30
01111011011 27
01101110010 18
11001011010 26
01101011100 28
01110011000 24
01100010111 23
01011111101 29
```
Implement the generate() method by calling the step() method k times and performing the necessary arithmetic.
Corner cases. You may assume that the arguments to the constructor and instance methods are valid. For example, you may assume that constructor argument seed is a string comprised of only the characters '0' and '1' and that tap is an integer between 1 and seed.length(). You may also assume that the argument k to generate() is a positive integer.
Testing. Your main() must contain code that directly tests all of the methods. As you write each instance method, add a test to main() to show that the new code works properly and that you didn't break any existing functionality (e.g., by printing the return value to standard output).

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 {

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

Manipulating pictures. The Picture data type is part of stdlib.jar; the Color data type is a Java library.
The transform method. The transform() method takes a Picture and an LFSR as arguments and returns a newPicture object that is the result of transforming the argument picture using the LFSR as follows: For each pixel (col, row), in column-major 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 a newly-generated 8-bit integer. Do the same for the green (using another new 8-bit integer) and, finally, the blue. Create a new Color object using the result of the xor operations, and set the pixel in the new picture to that color.
Main method. The main() method takes three command-line arguments: the name of an image file, a binary password (the initial LFSR seed), and an integer (the tap position). It must display the transformed picture on the screen, using the show() method in the Picture data type. For example, the command
```
% java-introcs PhotoMagic pipe.png 01101000010100010000 17
```
takes as input the picture pipe.png (left) and displays as output the transformed picture Xpipe.png (right).

Now, here's the magic: running the same program with the same binary password and tap on the transformed picture recovers the original picture! For example, typing
```
% java-introcs PhotoMagic xpipe.png 01101000010100010000 17
```
takes as input the transformed picture Xpipe.png (left) and displays as output the original picture pipe.png (right).

Anyone knowing this password and tap can recover the original picture, but another password won't work. If you're not convinced, try it. Thus, for example, you can post a transformed picture on the web, but only friends who have the password (and your program) can see the original.
Corner cases. You may assume that the arguments to transform() are not null.

Files for this assignment. The file lfsr.zip contains a number of sample PNG files, including the ones used above; an optional template for getting started with LFSR.java; 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 LFSR.java, PhotoMagic.java, 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 PhotoMagic.java, 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.