LFSR And Encryption: TOY

[an error occurred while processing this directive]

CIS 110

LFSR and Encryption in TOY

Programming Assignment

Please take a few minutes to fill out the mid-semester evaluation. This evaluation is anonymous, and is a chance to give us specific feedback that we can use to improve the course for you as well as future students.

Write a program lfsr.toy that produces pseudo-random bits by simulating a linear feedback shift register, and encrypt data in TOY. You should store the seed in a register and use the <<, >> and & operators to manipulate it. Review Homework 4 for a description of LFSRs and encryption. Your program will read the seed, tap position, and the data from StdIn, and will print the encrypted results to StdOut. The format for this data is described in the Input Format section below. Recall that you access StdIn by loading from mem[FF] and you access StdOut by storing to mem[FF].

Using pipes and the supplied ImageToTOY and TOYToImage programs, you will be able to encrypt and decrypt images. You should be able to encrypt images using PhotoMagic, then decrypt them with you TOY program, and vice versa. Conceptually, ImageToTOY and TOYToImage serve the same purpose as the ImageData class from Homework 5, and you are writing a TOY program lfsr.toy that will encompass the functionality of LFSR and PhotoMagic.transform().

Warning Debugging machine language is extremely tricky, no matter how much experience you have. It is imperative to be able to carefully proofread your code numerous times, which means working in shorter stints over a period of days. So start early, and don't wait to come to TA office hours!

Required Files In order to develop TOY applications you will need to download and compile the command-line TOY simulator TOY.java. You may also need StdIn.java and In.java. It is essential that you use this version of the TOY simulator rather than the version on the booksite. They differ in the way they print debug information, and the booksite version will not work for this assignment.

We strongly recommend developing in Visual X-TOY 7.3. This version is newer than the version on the booksite, and includes improved auto-commenting features that will likely save you a very significant amount of time over older X-Toy versions. You will need to use TOY.java for final testing of the image encryption and decryption, but you will be able to write all your code and do nearly all your testing within X-Toy. Unless you are a masochist, do not test your program with TOY.java Until you are sure it is encrypting and decrypting test input correctly within X-Toy. To specify the standard input to use when testing in X-Toy, click Open... on the StdIn pane or enter values manually into the entry box.

For encrypting and decrypting images you will need ImageToTOY.java, TOYToImage.java, and ImageData.java. You may also need Picture.java

Finally download the lfsr.toy skeleton to get started, and the readme_lfsr_toy.txt template. zeros.in is a simple input file for lfsr.toy that you can use for tests. white-10x10.png is a 10x10 white image that is also useful for testing. In addition, you should develop your own test input files and share them with each other. TOYXpipe.png is a copy of the pipe image from Homework 5 encrypted with the seed 01101000010 and tap position 8. Be aware that encrypting and decrypting images in TOY will be very slow, so it is best to debug with very small images and test input files like zeros.in and white-10x10.png.

Input Format The TOY simulator represents data in text format. Each TOY word is 4 hex digits, with white space separating successive words. Your program should interpret the first word of standard input as the number of bits in the seed, the second word as the seed (which will be at most 16 bits long), and the third word as the tap bit. It should store these values in registers and also print them to standard output. The next two words should be printed to standard output unchanged. We will use these two numbers to store the image's width and height, so they should not get encrypted. For convenience, we'll transmit each bit of the actual data individually (as 0000 or 0001), instead of packing 16 bits per TOY word as would be done in a real application. Since TOY has no facility for detecting the end of the input, we'll mark the end of the input with the value FFFF. Your program should repeatedly read a single word (which will be 0000 or 0001) from standard input, generate one random bit using an LFSR, and print out the XOR of the input and random bits. When it reads FFFF, it should print FFFF to standard output, and halt.

For example, the input file zeros.in is a valid input to lfsr.toy specifying the 11-bit (000B in hex) seed 01101000010 (0342 in hex), tap bit 8, two arbitrary words (DEAD and BEEF in hex), and a series of 8 0-bits.:

Your program should produce a file zeros.out with the following contents:

Using the command:

% java TOY lfsr.toy < zeros.in > zeros.out

Observe that the output of lfsr.toy is itself valid input to lfsr.toy. This means that you can run the encrypted ouput back through lfsr.toy to decrypt it. You can feed the output of one program into another program as input using a pipe in the terminal:

% java TOY lfsr.toy < zeros.in | java TOY lfsr.toy > zeros.out2

uses the file zeros.in as the standard input to lfsr.toy, and feeds the output into another run of lfsr.toy. The output of the second run is saved to the file zeros.out2, which should be indentical to zeros.in if your program works correctly. The pipe character | is the same vertical bar that Java uses for the or operator (||).

Encrypting Images Unlike Java, TOY does not come with a facility for reading in Images. You could write a program to do so, but it would be unpleasant. Instead, we provide the Java programs ImageToTOY and TOYToImage to convert image files to input for lfsr.toy and convert the output back into an image. The two TOY words that are passed from input to output without modification are used to store the image width and height.

% java ImageToTOY white-10x10.png 01101000010 8 > white.in

Creates a valid input file to lfsr.toy from the 10x10 white square white-10x10.png and specifies the seed 01101000010 with tap bit 8.

% java TOYToImage < white.in

Reads the contents of white.in from standard input, converts it back to an image, and displays it. You can chain these together with the actual encryption using pipes:

% java ImageToTOY white-10x10.png 01101000010 8 | java TOY lfsr.toy | java TOYToImage

Converts the image white-10x10.png along with the seed and tap into an appropriate input file, runs it through lfsr.toy, and converts the output into an encrypted image. Although this works with any image, keep in mind that it will be very slow normal-size images. It is best to test with very small images like white-10x10.png and artifical test files like zeros.in.

Similarly, you should be able to produce the pipe image with the command:

% java ImageToTOY TOYXpipe.png 01101000010 8 | java TOY lfsr.toy | java TOYToImage

Using Debug Mode in X-Toy Unlike in Java, it is not simple to print out the values of variables in TOY to see what is going on. Instead you will need to use the debug mode in X-Toy. You can access this from the Mode menu, or by clicking the computer icon on the toolbar. (Switch back to edit mode to modify your code.) In debug mode you can step through your program one instruction at a time, and inspect the contents of every register and memory location as you go. You can load a file to use as StdIn on the StdIn pane. Stepping through your program and methodically scrutinizing these values is how you will discover errors in your instructions. Keep in mind the "Sim Mode" is much cooler than debug mode but is much less useful.

Example Program X-Toy contains many sample programs that you can access through "Open Example Program" in the File menu. You may wish to look at "Fast Multiply" and "Multiply with stdin/stdout" in particular since these use many of the same instructions that you will need for lfsr.toy.

Checklist. Don't forget to read the checklist. Pay especially close attention to the Debugging section.

Submission. Submit lfsr.toy and a readme_lfsr_toy.txt file and answer the questions.

This assignment was created by Benedict Brown.