CS112 Assignment 6 CS112 Assignment 6: Linear Feedback Shift Register The goals of this assignment are to introduce you to object-oriented programming and help you learn a simple encryption/decryption method widely used in the real world. On this assignment, you are encouraged (but not required) to work with a partner provided you practice pair programming. Pair programming "is a practice in which two programmers work side-by-side at one computer, continuously collaborating on the same design, algorithm, code, or test." One partner is driving (designing and typing the code) while the other is navigating (reviewing the work, identifying bugs, and asking questions). The two partners switch roles every 30-40 minutes, and on demand, brainstorm. Before pair programming, you must read the article All I really need to know about pair programming I learned in kindergarten. You and your partner will turn in one copy of the assignment code. However, you must each submit a README.txt file for the assignment. The code and README.txt files must list the names of both partners and the README.txt file should detail your experience. Due: 11:00 p.m., EST, March 1, Thursday. Part 1. Understanding the Problem 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 Shift all of the bits one position to the left and Replaces the vacated bit by the exclusive or of the bit shifted off and the bit 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 the tap position tap. As in the example in Lecture 20 (see demo slides in pdf), the following illustrates one step of an 11-bit LFSR with initial seed 01101000010 and tap position 8. 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 tap) // create LFSR with the given initial seed and tap
public int step() // simulate one step and return the least significant (rightmost) 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. Constructor. The constructor takes the initial seed as a String argument whose characters are a sequence of 0's and 1's. The length of the register is the length of the seed. We will generate each new bit by xor-ing the most significant (leftmost) bit and the tap bit. The position of the tap bit comes from the constructor argument. For example, the following code should create the LFSR described above.
LFSR lfsr = new LFSR("01101000010", 8);
String representation. The toString() method returns a string representation of the LFSR by concatenating the values in the registers. For example,
LFSR lfsr = new LFSR("01101000010", 8);
StdOut.println(lfsr);
should output
01101000010
Simulate one step. The step() method simulates one step of the LFSR and returns the least significant (rightmost) bit as an integer (0 or 1). For example,
LFSR lfsr = new LFSR("01101000010", 8);
for (int i = 0; i < 10; i++) {
int bit = lfsr.step();
StdOut.println(lfsr + " " + bit);
}
should output
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 an 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, given the bit sequence 1 1 0 0 1 the variable takes the values 1, 3, 6, 12, 25, ending with the binary representation of the bit sequence. For example,
LFSR lfsr = new LFSR("01101000010", 8);
for (int i = 0; i < 10; i++) {
int r = lfsr.generate(5);
StdOut.println(lfsr + " " + r);
}
should output
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. 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) // 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
// display the encrypted version of the picture
Transform method. The transform() method takes a Picture (see pp. 324–337 in the SW textbook) and an LFSR as arguments and returns a new picture that is the result of transforming the argument picture using the linear feedback shift register as follows: For each pixel (x, y), in raster-scan 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 in the new picture to that color. Main method. The main() method takes three command-line arguments, a picture name, a binary password (the initial LFSR seed), and an integer (the tap number). It should display the transformed picture on the screen (using the show() method in the Picture class). For example, typing
% java PhotoMagic pipe.png 01101000010100010000 16
takes as input the picture pipe.png (left) and displays as output the picture on the right. You can save the right-hand picture as Xpipe.png by selecting File -> Save -> Xpipe.png from the menu in the window where the image is displayed. 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 PhotoMagic Xpipe.png 01101000010100010000 16
takes as input the picture Xpipe.png (left) and displays as output the picture on the right. 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 can post the transformed picture on the web, but only friends who have the password (and your program) can see the original. Part 2. Carrying Out the Actual Work These are purely suggestions for how you might make progress. You do not have to follow these steps. Download the lfsr subdirectory to your computer. You can either download this lfsr.zip file (and then unzip it) or visit this http site. This subdirecctory contains a template LFSR.java file to get you started. It also contains Picture.java, and pipe.png along with some other encrypted images. Reread the slides for Lecture 20 (to reacquaint yourself with the basic ideas behind LFSRs), the lecture slides for "Using Data Types" and "Creating Data Types", and pages 316–335 and 370–77 in the SW textbook (to learn the basics of object-oriented programming). The design of your program should look like the template LFSR.java, except that you will need to fill in all of the constructors and methods. We recommend defining the instance variables as follows:
public class LFSR {
private int N; // number of registers in the LFSR
private int[] reg; // reg[i] = ith least significant (rightmost) bit of the LFSR
private int tap; // index of the tap bit
}
Make the constructor. Your constructor for LFSR will initialize all the instance variables. Use new to allocate memory for the int[] array. Observe that you must do this in the constructor (and not when you declare the instance variables) since otherwise you wouldn't know how big to make the array. Write the toString() method. As you fill in the methods for LFSR, use the test code described in the assignment. Write the step() method. Test. Write the generate() method. Test. PhotoMagic. Your PhotoMagic class is a client of the Picture, Color, and LFSR classes. By placing the line import java.awt.Color; above the line where you declare public class PhotoMagic, the compiler will know that you are going to use the Color class. Place Picture.java and LFSR.java in the same directory with PhotoMagic.java, so the compiler will be able to find both of them. Testing: Be sure to thoroughly test each piece of your code as you write it. We offer some suggestions in the assignment specification. You should also test your data type with other parameters. Use the following code to test generate() with a 20-bit fill and a tap of 16.
LFSR lfsr3 = new LFSR("01101000010100010000", 16);
for (int i = 0; i < 10; i++) {
int r = lfsr3.generate(8);
StdOut.println(lfsr3 + " " + r);
}
It should output:
01010001000000101010 42
00000010101011011001 217
10101101100100010111 23
10010001011111000001 193
01111100000100011010 26
00010001101010011100 156
10101001110010011100 156
11001001110011100111 231
11001110011110000111 135
01111000011110111101 189
PhotoMagic. Here are a few sample executions of PhotoMagic.java along with the desired output.
% java PhotoMagic pipe.png 01101000010100010000 16
[ compare against the picture on the assignment ]
% java PhotoMagic Xpipe.png 01101000010100010000 16
[ Magritte's painting of a pipe ]
% java PhotoMagic Xbaboon-red.png 01101000010100010000 16
% java PhotoMagic Xbaboon-green.png 01101000010100010000 16
% java PhotoMagic Xbaboon-blue.png 01101000010100010000 16
[ the red, green, and blue components of a baboon ]
% java PhotoMagic Xscarpet-cookies.png 01101000010100010000 16
[ a Sierpinski carpet design in vanilla and chocolate ]
% java PhotoMagic Xjava.png 001110001111000100001101010010000100010010000000001100000100 58
[ Java logo ]
PhotoMagicDeluxe. Here is a sample execution of PhotoMagicDeluxe.java along with the desired output.
% java PhotoMagicDeluxe Xjava.png OPENSESAME 58
[ Java logo ]
Part 3. Frequently Asked Questions What preparations do I need to do before beginning this assignment? Review the Lecture 20 slides and LFSR demo slides to reacquaint yourself with the basic ideas behind LFSRs. Also read Sections 3.1 and 3.2 of the textbook (to learn the basics of object-oriented programming). Do I need to follow the prescribed API? Yes, we will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points. How should I represent the LFSR? There are several possible approaches. We recommend that you use an int[] array of size N, each entry of which is either 0 or 1. If you follow this approach, the constructor amounts to creating the array and converting the char values in the string to int values for the array (and initializing your other instance variables). How do I create an instance variable which is an array if I don't know its length at compile time? Declare it as an instance variable, but initialize it in constructor (where you will know its length). For example, see Program 3.2.3 (page 381) in the SW textbook. What extra comments should I include when writing object-oriented programs? You must comment the purpose of every method, using the names of the argument variables in your description, as below.
// simulate k steps of the LFSR and return corresponding k-bit integer
public int generate(int k)
Additionally, you must comment the purpose of each instance variable, as below.
private int N; // number of registers in the LFSR
private int[] reg; // reg[i] = ith least significant (rightmost) bit of the LFSR
private int tap; // index of the tap bit
In the seed string, seed.charAt(0) is the leftmost bit. But in the Lecture 20 slides and the assignment page, bit 0 is the rightmost bit. Do I have to arrange the bits in my register array that way? Strings are always indexed from left to right (the way we read English). Traditionally, binary digits are indexed from right to left, with bit 0 as the lowest order or rightmost bit. You are welcome to use either approach here --- just be careful to do it correctly and consistently. How do I convert the char values in the string to int values for the array? The number zero is represented by the char value '0'. The char data type is a Java primitive type, so you can compare two of them with if (c == '0'). My step() method is producing 19 for the binary number 11001. What am I doing wrong? You are calculating the bits in reverse order. 19 is the decimal value of the binary number 10011. My generate() works with the 11 bit fill and the tap at position 8, but when I try generate()with the 20 bit fill and the tap at position 16, I get a different answer from the one shown in the example. What am I doing wrong? Make sure you are not hardwiring 11 or 8 in your LFSR code. The LFSR constructor arguments should set the size of the register and the tap position. The toString() is not explicitly called in the test client code, but it still gets called. How does this work?
LFSR lfsr = new LFSR("01101000010", 8);
StdOut.println(lfsr);
When a Java object is passed to any of the print methods, a call is automatically made to that object's toString() method. I get an ArrayOutOfBounds or NullPointerException error. What could cause this? Do your constructors initialize all of the instance variables (e.g., N, reg, and tap)? Did you allocate memory for your array with new? Did you inadvertently redeclare int N or int[] reg in a method or constructor, thereby hiding the instance variable with the same name? How do I do exclusive or (XOR) in Java? Use the ^ Java symbol. The operation a ^ b, where a and b are int values, does a bit-by-bit exclusive or of the values. Why are we using the .png format isntead of .jpg? It is a lossless format that preserves the precise bits in the colors. How do I read in the .png files? Use our Picture.java data type, described in Section 3.1 of the textbook. You will only need the constructors and methods of the Picture API summarized on page 330. To see it in action, look at the program Grayscale.java which takes the name of a picture file as a command line argument, converts all pixels to gray, and displays all those pixels. See Luminance.java to see how to retrieve the r, g, and b values for the Color. Sometimes my encrypted picture looks like a shadowy version of the original. How do I pick a good tap number? Here are suggested tap numbers for maximizing the cycle of different size linear feedback shift registers: 5-bit (tap 2), 6-bit (tap 4), 9-bit (tap 4), 10-bit (tap 6), 11-bits (tap 8), 20-bit (tap 16), 30-bit (tap 22), 36-bit (tap 24), 48-bit (tap 42), 60 bits (tap 58), 100 bits (tap 62), and 150 bits (tap 96). Part 4. Editing a README.txt File Using any plain text editor (e.g., Dr. Java, emacs, or notepad) to create a text file named README.txt. We provide a README.txt file that you must use as a template. Download this file and answer all questions in the space provided. Note: the template we provide for each assignment is different from each other. Once again, this README.txt file must be a plain text file; Microsoft Word .doc or .docx formats or Mac TextEdit .rtf formats are unacceptable. Part 5. Submitting Your Assignment All you need to submit electronically for Assignment 6 are the LFSR.java file, the PhotoMagic.java file, and the README.txt file. If you follow pair programming, you and your partner will turn in one copy of the LFSR.java and PhotoMagic.java files only. However, you must each submit a README.txt file for the assignment. The code and README.txt files must list the names of both partners and the README.txt file should detail your experience. To submit, just upload these files from the Assignment submission page (Navigation Tools/Assignments) on the Yale classes*v2 server. Clarification: In the Honor Pledge the word 'aid' shall be defined to mean any aid that has knowingly violated the rules defined in class. In no circumstances should 'aid' refer to discussions with TAs and the Instructor or sanctioned discussions on Piazza. If you are unable to sign the pledge for any reason, please post a private message on Piazza explaining why. Good luck and enjoy! Enrichment Read more about Linear Feedback Shift Registers. 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 takes 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. Copyright © 1999–2012, Robert Sedgewick and Kevin Wayne. [Adapted and modified by Zhong Shao for use in CPSC 112]
