Overview / Logistics
The purpose of this assignment is to get you practice with binary and bitwise operators in Java in a fun application involving cryptography. Not only will you learn more about how pseudorandom number generators, like
java.util.Random, actually work behind the scenes, but you will also implement an operation which is at the heart of many digital encryption schemes: "XOR Encryption."
Click here to download the skeleton code for this assignment. You will be editing
When you are finished, you should submit
LFSR.java to Canvas, as well as your encrypted text file from part 4. Please also submit answers to the following questions: (you can simply number your answers from 1 to 7 as a comment on Canvas)
- What is the initial state for your example in part 4, and which hex string did you use for your taps? If you do not provide this information, you will not receive full credit for part 4
- Did you work with a buddy on this assignment? If so, who?
- Did you use any resources outside of the class textbook and provided links to help you complete the assignment? Please list them here.
- Are you using up any grace points to buy lateness days? If so, how many?
- Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)
- Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
- Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (fine to leave this blank)
A linear feedback shift register (LFSR) is a data structure for generating pseudorandom binary bits. One can think of it as a scheme for generating coin flips which look totally random, but which are perfectly repeatable given an initial state and a set of "taps." Together, these bits of information can be thought of as the password that we use to hide data. In particular, we will use the sequence of pseudorandom bits generated by this password to hide a message.
A linear feedback shift register is specified by a binary string and a set of taps, which are locations of particular bits of the register numbered at 1 starting on the right. To generate a new bit, the LFSR takes the XOR of the bits at all of the tap positions. Then, the bit string of the LFSR is updated by deleting the leftmost bit, shifting the whole bit string by one to the left, and putting the new bit in the rightmost position. The animation below shows this in more detail. Please play with this until the concept is clear
Once you have implemented the LFSR, you can use it to encrypt data. All data in a computer is represented in binary, but we will focus on text data in this assignment since it is easy to output. We will use a binary representation of text called UTF-8, which is the most encoding for text on the world wide web. In UTF-8, each character can be from 1 to 4 bytes long. To keep things simple, though, we will assume that text uses an "ASCII subset" of UTF-8, in which each character is only 7 bits packed into a single byte. For example, the capital letter A is
0x41. This way, we will ensure that each character is a single byte.
By default, bitwise operators in Java are performed on the 32-bit
int type, so code has been provided to convert an array of bytes corresponding to an ASCII Unicode string into an array of ints in "little endian order"; that is, each group of contiguous 4 character bytes is packed into a single int, with the first byte on the right and the last byte on the left. Below you can see illustrations of a few examples of the conversion, which is done for you. For those interested, you can refer to the ASCII table here to see the hex codes for all ASCII characters. You will see, among other things, that numbers come before uppercase letters, which come before lowercase letters.
Little Endian ints
Little Endian ints
0x1234 ^ 0xFACE = 0xE8FA
0xE8FA ^ 0xFACE = 0x1234
In this assignment, you will create a pseudorandom array of ints using the LFSR, and you will xor the ints representing your message with this random sequence of ints to obtain your cipher text.
Part 1: (8 pts)
public static int getLFSRBit(int lfsr, int taps)
The first step is to implement a method which computes the next bit that will come out of a 32-bit LFSR (represented by an
int) with a particular set of taps. For example, if you test it with the taps in the LFSR example, you should obtain bits 0, 0, 1, 1, from the first 4 LFSR states
0xD761, respectively. The code below will do this if your method is working properly, though you should test it on more of your own examples before moving on (and you can use the LFSR simulator above to help).
- By convention, a tap at the first position is at a 1, not a 0. So you should be careful how much you choose to left shift or right shift. For instance, right shifting by 1 will place the bit in position 2 at position 1.
Part 2: (8 pts)
public static int cycleLFSRBy32Bits(int initial, int taps)
Once you are able to compute the next bit in an LFSR using your
getLFSRBit method, you should use to cycle through the LFSR 32 times. After 32 cycles, the LFSR will contain a new random integer. You will the XOR a sequence of such integers with the ints representing your data in the next section
First, devise code to perform one full step of the LFSR. Use
getLFSRto compute the bit, then shift by 1 to the left, and place that bit in the rightmost position. Once you've done this, simply place that code in a loop that loops 32 times.
- For an example, set the app above to use some initial state and taps with 32 bits, and then hit "turbo" 32 times. The bit string that you get is the number that you should end up with. You can use code from the lab 8 code roundup to print the result out as a bit string.
Part 3 (8 pts)
public static int encryptDecryptIntArray(int initial, int taps, int input)
We are now finally ready to put all of the pieces together! In this method, you should generate a sequence of random ints using your
cycleLFSRBy32Bits over and over again, and you will XOR each element in the
input array with each one of these ints. The initial state is passed in as the variable
initial, and the first int you XOR with should be the result of a 32-bit cycle. All subsequent ints should be the result of performing a cycle starting with the int from the last loop iteration.
Some examples have been provided with the code in the
Examples/ directory at the root of your project, and you should test all of them.
Example 1:As a first example, I encrypted the string "Welcome To CS 173!" with the following code:
We use 173 and the taps 32, 22, 2, and 1 as our "password." We will not be able to decrypt
Examples/welcome.txt if we do not use these. These taps were obtained from this document to ensure that the LFSR will be "as random as possible," which means that the register will shift through all possible 32-bit states before returning to the initial state.
Click here to see the encrypted string that the above code generated in a working implementation. You'll notice that it doesn't look at anything like the original text, which is good, since we were trying to hide it. If you use the correct "password" (intial state and taps), though, you should be able to decrypt it. Once you finish your implementation, run the code below and make sure you can get the message back. Also, see what happens if you use an initial state other than
Let's now encrypt the text "I can't feel my face when I'm with you" using the initial state
0xFACE and the taps 31, 6, 5, and 1 as our password. These taps were obtained from this paper. The encrypted file
Examples/face.txt was created this way with a working implementation using the code below
Click here to see the encrypted string that the above code generated in a working implementation. Try to decrypt it using the code below. Notice what happens if you use the wrong taps or the wrong initial state.
Finally, I have encrypted an English translation of The Ilyad using the initial state of 24 (since there are 24 books in The Ilyad), along with the taps 32, 11, 8, 7, 5, 3. Click here to see the encrypted text. Verify that you are able to decrypt the text in
Examples/Ilyad.txt using that initial state and those taps. (NOTE: You need not read The Ilyad in your console! Simply verify that the output is sensible)
Dr. Philip Koopman at Carnegie Mellon has generated a text file with some taps which are optimal for 32-bit LFSRs, which means that the LFSR starting with a nonzero initial state will visit all possible nonzero 32 bit states before cycling back. Click here to see a text file with the first 32 of these. The taps are described in hex. A 1 in a particular position means that position is a tap. For instance, in the Ilyad text above, I used the hex string
0x800004D4 from his table, which has taps at positions 3, 5, 7, 8, 11, and 32.
In this part of the assignment, you must use your program to encrypt a string that says your name and your section, using the taps from a different example in Dr. Koopman's list. Choose your favorite number or some interesting number as your initial state, and create an encrypted text file using the
encryptDecryptStringAndSave method. Please indicate on Canvas the initial state you used and the hext string you used for your taps.
Part 5: Style (2 Points)
You must adhere to the style guide to receive full credit here.