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 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 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.
LFSR lfsr = new LFSR("01101000010", 8);
should outputLFSR lfsr = new LFSR("01101000010", 8); StdOut.println(lfsr);
01101000010
should outputLFSR lfsr = new LFSR("01101000010", 8); for (int i = 0; i < 10; i++) { int bit = lfsr.step(); StdOut.println(lfsr + " " + bit); }
11010000101 1 10100001011 1 01000010110 0 10000101100 0 00001011001 1 00010110010 0 00101100100 0 01011001001 1 10110010010 0 01100100100 0
should outputLFSR lfsr = new LFSR("01101000010", 8); for (int i = 0; i < 10; i++) { int r = lfsr.generate(5); StdOut.println(lfsr + " " + 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 pictures, by implementing the following API:
Thepublic 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
Picture
class should already be available on your system.
It is part of the stdlib.jar
file that was required to use
the Std*
classes from previous weeks.
Picture
(see pp. 324–337 in the textbook)
and an LFSR as arguments and returns a new picture that is the result
of transforming the argument picture using the linear feadback shift register as follows:
For each pixel (x, y), 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 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.
Picture
and don't modify the original one.
% 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.
Useful files.
Download the contents of the directory
lfsr to your system, or this
.zip
of the directory.
It contains a template LFSR.java file, which you can either use to get started (see
the checklist), or you can delete it and start from scratch.
It also contains
pipe.png, the readme.txt file,
and some other encrypted images.
Submission. Submit LFSR.java and PhotoMagic.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.String base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
To earn extra credit, you must 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.