[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
Another option is to use single int variable. In this case, the length of your register will be limited to at most 32 bits, and you will need to use the bit-whacking operators & (bitwise and) and | (bitwise or), and the bit-shifting operators << and >> described in Section 5.1 of the booksite. We will use this approach in the next assignment, after we have covered it in class.
Until init() has been called, your seed and tap should be set in such a way that LFSR.step() will always return 0.
It is good style to give class variables names somewhat longer, more descriptive names. There are two reasons for this. First, they are often declared far away from the place you are using them so it is important to know from the name what the variable's purpose is. Second, using descriptive names for class variables makes it less likely you will accidentally declare a local variable within a function with the same name (you are actually allowed to do this, but it rarely results in the behavior you intended and can be a very difficult bug to find).public class LFSR { // Create an array of chars for the lfsr seed as a // class variable so it can be accessed by every // function in LFSR. Do the same for the tap position. // // Depending on how you choose to implement your own // LFSR, your class variables may well differ in type // and number from these ones. private static char[] seedArray = { '0' }; private static int tapPosition = 0; public static int step() { // you can access the variables seedArray and tapPosition here } public static int generate(int k) { // you can also access seedArray and tapPosition here } }
You will find the String.length() and String.charAt() methods helpful for converting the seed argument to your preferred internal representation. For example, the following code:LFSR.init("01101000010", 8);
would print:String seed = "01101000010"; System.out.println("The first character of seed is " + seed.charAt(0)); // print the *leftmost* character of seed System.out.println("The second character of seed is " + seed.charAt(1)); // print the second character from the left of seed System.out.println("The last character of seed is " + seed.charAt(seed.length() - 1)); // print the *rightmost* character of seed
The first character of seed is 0 The second character of seed is 1 The last character of seed is 0
should outputLFSR.init("01101000010", 8); StdOut.println(lfsr.string());
01101000010
should outputLFSR.init("01101000010", 8); for (int i = 0; i < 10; i++) { int bit = LFSR.step(); StdOut.println(LFSR.string() + " " + bit); }
11010000101 1 10100001011 1 01000010110 0 10000101100 0 00001011001 1 00010110010 0 00101100100 0 01011001001 1 10110010010 0 01100100100 0
should outputLFSR.init("01101000010", 8); for (int i = 0; i < 10; i++) { int r = LFSR.generate(5); StdOut.println(LFSR.string() + " " + r); }
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 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:
PhotoMagic must implement the following API: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
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
% 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.
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:
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().String base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
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.