CIS 110 Spring 2013 - Introduction to Computer Programming

upenn.edu | directories | van pelt library
seas.upenn.edu | CETS | engineering library
computer graphics & game dev (SIGGRAPH @ Penn) | dining philosophers (DP) | science & tech wing (STWING) | women in cs (WICS)
CETS Answers

Homework 4: LFSR and Encryption

Goals

  • Learn about linear feedback shift registers and encryption.
  • Learn about static class variables.
  • Get an introduction to bit manipulation.
  • Learn to use the ImageData API to interact with image files.
  • Learn about two-dimensional arrays.

Submission

Submit LFSR.java, PhotoMagic.java, a completed readme_lfsr.txt file, and, optionally, PhotoMagicDeluxe.java using the submission link in the sidebar.

Background

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

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

LFSR

This allows you to generate pseudo-random bits. The generation of bits is entirely predetermined by the initialized seed and tap, but without knowing what those are, the input encrypted by an LFSR cannot be easily decrypted by hand.

For more detail on LFSRs and excryption, consult the slides for Lecture 7.

Your program. First, you will write a library LFSR.java that will simulate an LFSR using 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

Then, you will use this LFSR class in order to write a program PhotoMagic.java that can encrypt and decrypt images using randomly generated bit sequences.

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

Part I: Setting Up Your Code

  • Data representation. There are several ways to represent a shift register (which is fundamentally a sequence of bits), and we will accept any reasonable (and functional) approach. For this assignment, we suggest storing the shift register as one of:

    • An array of ints that are 0 or 1;
    • An array of chars that are '0' and '1';
    • An array of booleans that are true or false;
    • If you want to jump ahead a bit, a single int. 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. There is no advantage in this assignment to this approach.

    Until init() has been called, your seed and tap should be set in such a way that LFSR.step() will always return 0.

  • Class variables. Unlike previous assignments, the functions in LFSR all need shared access to the seed and tap position. Java supports this using class variables, which are variables declared inside a class, but outside of any functions. Similar to functions, the type of variable should be preceded by private static. Every function declared in the class has access to these variables, and every function that assigns a new value to these variables changes the value for every function as well. Because the variables are declared private static rather than public static, functions in other classes to not have access to them. For example:
        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 int[] seedArray   = { 0 };
            private static int   tapPosition = 0;
    
            public static boolean init(String seed, int tap) {
                // you can access the variables seedArray and tapPosition here
            }
    
            public static String string() {
                // you can also access seedArray and tapPosition here
            }
        }
      

    It is good style to give class variables 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 the variable's purpose is by looking only at the name. 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).

Part II: Initialize the LFSR

  • Initialization. The init function takes the initial seed as a String argument whose characters are a sequence of 0s and 1s. The length of the register is the length of the seed. The tap bit is the position of the bit that will be used (along with the highest order bit) in order to generate the next bit in the step() function.

    It is important to decide how to interpret the seed and the tap position at this point. The tap position is passed in as an int argument to the function. It is zero-indexed from the right side of the seed, as shown in the image below. The seed, if converted directly from a String into an array of bits and kept in order, will be zero-indexed from the left side. As such, the seed and the tap position are indexed in conflicting ways, and your initialization function must compensate for this. There is more than one good way to do this: remember, all that matters is that the functions defined above all behave exactly according to the specifications.

  • Error checking. The seed or tap arguments may be invalid for a number of reasons:

    • The seed is not composed entirely of 0s and 1s.
    • The tap position is negative.
    • The tap position is greater than or equal to the seed length.

    If this is the case, the LFSR's internal state should not be updated, and init() should return false. Otherwise, init() should return true. Keep in mind that your LFSR class should start out in a state in which step and generate should produce a steady stream of 0s, and a failed call of the init() function should not change that.

  • Testing. The following code should initialize the LFSR class to the state shown in the picture above.

        LFSR.init("01101000010", 8);
        

  • String manipulation. 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:
        String seed = "01101000010";
        System.out.println("The first character of the seed is " + seed.charAt(0));   // print the *leftmost* character of seed
        System.out.println("The second character of the seed is " + seed.charAt(1));  // print the second character from the left of seed
        System.out.println("The last character of the seed is " + seed.charAt(seed.length() - 1)); // print the *rightmost* character of seed
        
    would print:
        The first character of the seed is 0
        The second character of the seed is 1
        The last character of the seed is 0
        
  • String representation. The string() function returns a string representation of the LFSR by iterating through the array and concatenating the values in the registers. For example,

      LFSR.init("01101000010", 8);
      StdOut.println(LFSR.string());
      
    should output
      01101000010
      

Part III: Simulating Steps

  • Simulate one step. The step() method simulates one step of the LFSR, updates the state, and returns the newly generated least significant (i.e. rightmost) bit as an integer (0 or 1). In order to execute the step:

    1. Take the most significant bit and the bit in the tap position, XOR them, and store the result in a temporary variable.
    2. Shift all of the bits in the sequence one position to the left, thus pushing the old most significant bit out entirely.
    3. Put the newly generated bit (currently stored in the temporary variable) and put it into the newly vacated least significant bit position.

    To xor two int values, use the ^ character. Hint: If you use an array of characters, make sure to convert them to integers first. You can do this by subtracting the character '0'. This trick works because characters as stored as numbers according to the ASCII standard (and the Unicode standard for foreign characters). The character 'A' is stored as 65, 'B' as 66, and so on. '0' is stored as 48, '1' as 49, etc. You can carry out arithmetic on character codes just like any other integers. In particular:

    char c0 = '0';
    int x = c0 - '0'; // the value of x is now 0
    char c1 = '1';
    int y = c1 - '0'; // the value of y is now 1

  • Extracting multiple bits. The generate() function takes in 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 int 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 value of the binary number 11001.

  • Testing. LFSR is a library for other programs to use, not a program unto itself. You should use the main() function to test that the LFSR works correctly. Since main() is not part of the API, you can decide what arguments it will take and what it will print out. The only requirement is that it do a reasonable job testing LFSR's API functions. Your submitted LFSR must contain a main() function. You should leave any testing and debugging code in main() in place; remove testing and debugging code in other functions.

    The following code does some basic testing of step() generate(). You can cut and paste it into your main(). We encourage you to add additional tests as well, but it is not required. Think about cases and sequence of cases that might behave oddly, error cases, and sequences of calls to init(), step(), and generate() that might interact in unexpected ways.

    Testing step()

          LFSR.init("01101000010", 8);
          for (int i = 0; i < 10; i++) {
              int bit = LFSR.step();
              StdOut.println(LFSR.string() + " " + bit);
          }
      
    should output
         11010000101 1
         10100001011 1
         01000010110 0
         10000101100 0
         00001011001 1
         00010110010 0
         00101100100 0
         01011001001 1
         10110010010 0
         01100100100 0
      

    Testing generate()

          LFSR.init("01101000010", 8);
          for (int i = 0; i < 10; i++) {
              int r = LFSR.generate(5);
              StdOut.println(LFSR.string() + " " + r);
          }
      
    should output
          00001011001 25
          01100100100 4
          10010011110 30
          01111011011 27
          01101110010 18
          11001011010 26
          01101011100 28
          01110011000 24
          01100010111 23
          01011111101 29
      

    Try to test your code with multiple inputs. Here is another test for generate()

          LFSR.init("01101000010100010000", 16);
          for (int i = 0; i < 10; i++) {
              int r = LFSR.generate(8);
              StdOut.println(LFSR.string() + " " + r);
          }
          
    It should output:
          01010001000000101010 42
          00000010101011011001 217
          10101101100100010111 23
          10010001011111000001 193
          01111100000100011010 26
          00010001101010011100 156
          10101001110010011100 156
          11001001110011100111 231
          11001110011110000111 135
          01111000011110111101 189
        
  • Possible errors:
    • I got an ArrayOutOfBounds or NullPointerException error. What would cause this? Do you 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, thereby hiding the instance variable with the same name?

    • My generate() works with the 11 bit seed and the tap position 8, but when I try generate() with the 20 bit seed and the tap 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.init() arguments should set the size of the register and the tap position.

Part IV: Encrypting and Decrypting 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 class into the same folder as your assignment. If you are working on the lab computers, you may need to download the Picture class as well (the introcs installer normally sets this class up for you).

    ImageData provides the following API that you can use to load, save, and display images:

    public class ImageData
    ----------------------------------------------------------------------------------------------------------------
    public static int[][] load(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
    
  • PhotoMagic must contain two functions:

    • Transform function. The transform() function takes a 2-D array of integers, and the seed and tap to use for the LFSR as arguments and returns a new 2-D array of integers that is the result of transforming the argument picture using the linear feadback shift register as follows: Update each pixel (x, y) raster-scan order — (0, 0), (0, 1), (0, 2), ..., where the first coordinate is the row, and the second coordinate is the column — by XOR-ing it with a different, newly-generated, random 32-bit integer returned by LFSR.generate(32) (you can read more about raster-scan order here). You may assume that transform will only be called on arrays of valid image data. transform should have the following header:
      public static int[][] transform(int[][] picture, String seed, int tap)  //  transform picture using lfsr

      The returned 2-D array must be created without modifying the picture array. Remember that array variables store the location in memory where the array is stored, not the actual data. So when you pass an array variable as a function argument, the function gets a copy of this pointer; in other words, you get two names for the same piece of memory, not two copies of your data. Part of the contract that PhotoMagic makes with the clients is that it will not clobber their image data. We will be calling your PhotoMagic.transform() function directly, not just running your program. It must behave exactly as specified.

    • Main. 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() function in the ImageData 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. Do not use ImageData.save() to save your image.

      Magritte pipe Noise

      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.

      Noise Magritte pipe
      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.
  • More testing. Here are three more encrypted images. The filename of each gives the seed and the tap position that should be used to decrypt them. Try it out!

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. Use base64.indexOf(c) method to find out the index of character c in the string base64. This index is the Base64 code for the character. (indexOf() is essentially the opposite of charAt()). 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 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.

This image was encrypted using a seed of at most 16 bits. Can you decrypt it? If you're still bored, try and figure out what it's a picture of.

Enrichment

Read more about Linear Feedback Shift Registers.