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 src/LFSR.java.

What to submit:

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)

1. 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
2. Did you work with a buddy on this assignment? If so, who?
3. Did you use any resources outside of the class textbook and provided links to help you complete the assignment? Please list them here.
4. Are you using up any grace points to buy lateness days? If so, how many?
5. 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)
6. 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.
7. 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)

Background: Linear Feedback Shift Registers

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

Background: Unicode/ASCII Binary Encoding for Text

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.

String

L

e

t

'

s

s

e

n

d

s

e

c

r

e

t

s

Unicode

0x4c

0x65

0x74

0x27

0x73

0x20

0x73

0x65

0x6e

0x64

0x20

0x73

0x65

0x63

0x72

0x65

0x74

0x73

Little Endian ints

0x2774654c

0x65732073

0x7320646e

0x65726365

0x7374

Background: XOR Encryption

Recall in the video module and in our lectures (section A and section B) that if you XOR a bit string with the same bit string twice, you get back to where you started. For example

0x1234 ^ 0xFACE = 0xE8FA

and then

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.

Code To Write

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 0xFACE, 0xF59C, 0xEB38, and 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).

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

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 173

Example 2:

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.

Example 3:

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)

Part 4: Encrypting your own message (4 Pts)

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.