Homework 4: Encryption and Steganography

Extended Deadline: The deadline for this assignment has been extended to Tuesday, 29 October 9:00 PM. You may still use a three hour grace period (until 11:59 PM), but you may not use any late days. Since many of you have been working very hard on this and are finished or close to finishing, we will also give an additional point of extra credit to submissions received prior to the original deadline (Thursday, 24 October 9:00 PM). Any assignment submitted by the extended deadline (Tuesday) will be eligible for the extra credit options at the end of the assignment.

Table of Contents


Mid-Semester Feedback

Please fill out the mid-semester feedback form as a way of letting us know how we're doing and how we can make the course even better for the second half of the term and beyond. Your feedback is anonymous and will only take a few minutes. You are welcome to wait until you are done with the assignment to fill it out.


Submit ASCII.java, Encrypt.java, RetrieveMessage.java, HideMessage.java, a completed readme_steganography.txt file, and, optionally, an extra.zip file containing images with hidden messages file and/or PhotoMagic.java.

Background: Image Steganography

Image steganography is the science of hiding secret messages inside of images. Think of it as 21st century disappearing ink. The casual observer simply sees an ordinary image; only someone who knows how to look for it will notice or find the message.

You will implement a simple, but very effective form of image steganography. The idea is to fiddle with each pixel's color in a way that isn't perceivable to the human eye, but that the computer can interpret. Since the human eye is least sensitive to blue wavelengths, we'll slightly adjust the amount of blue in each pixel in a way that encodes a single bit of information.

As far as the computer is concerned, an image is just a 2-D array of pixels. The color of each pixel is encoded an integer between 0 and 16.8 million (224 - 1 to be precise), with 8 bits dedicated to each of the red, green, and blue primaries.

Flipping the ones bit of this number (i.e. subtracting 1 from an odd number or adding 1 to an even number) changes the amount of blue in the color by a minute amount that is indistinguishable to the human eye.

Hiding information: As we discussed in class, image steganography will represent the information to be hidden as a sequence of bits, and then hide that sequence of bits in the image. We will assume the information to be hidden is made up of (English) letters, digits, and punctuation marks, represented as bits according to the ASCII character set. Then, we will simply set the least significant bit (LSB) of each successive pixel to 0 or 1 to match the values of each bit in your message. This will cause the blue value of each pixel to change by at most one step, which won't be noticeable; but now each pixel in the image carries one bit of your message. Since ASCII requires 7 bits to represent a single character, each character of your message will be spread across 7 pixels in the image.

Retrieving information: Someone else (or you) can then retrieve the hidden message by reading in the ones bits of each pixel. Every seven bits that you retrieve represents a single character in ASCII.

The Structure of Your Program and the API

Because this is a more complex assignment, instead of implementing it as a single Java class, we will break it into multiple manageable pieces, each of which will implement a single component of the larger assignment. These pieces will be placed into separate library classes. Your program will consist of libraries that implement the following aspects of the assignment: ASCII conversion, the LFSR, and encryption/decryption.

Also, since we need to be able to both hide and retrieve messages from images, we will actually write two programs, one for hiding (and encrypting) messages in images, and a program for retrieving (and decrypting) messages from images.

Each of these pieces (the libraries and the two programs) must conform exactly to the APIs listed below. In addition, you may add any private helper functions and class variables you need.

The steps of the assignment describe how to implement these APIs, and give additional information about their expected behavior. Use these tables as a reference while you write your code, but make sure you follow all the assignment's steps carefully.

public class ASCII
public static boolean[] encode(String msg)       // encode msg to an array of bits using ASCII encoding
public static String    decode(boolean[] bits)   // decode bits to a String using ASCII encoding

public static void      main(String[] args)      // unit testing function

public class Encrypt
public static boolean[] encrypt(boolean[] bits, String seed, int tap) // encrypt/decrypt bits

public static void    main(String[] args)                             // unit testing function

public class HideMessage
public static void main(String[] args)                // hide an (optionally encrypted) message in an image

public class RetrieveMessage
public static void main(String[] args)                // retrieve an (optionally encrypted) message in an image

In addition, we provide the LFSR library that implements a linear feedback shift register that you should use for encrypting and decrypting messages. Download this to the same folder as your own code. Note: We only provide a compiled .class file for the LFSR library; we do not provide the source code. Error messages that refer to the LFSR library are likely to be gibberish. You will need to look at the error message's stack trace to find the line in your own code that triggered it.

public class LFSR
public static boolean init(String seed, int tap)  //  create LFSR with the given initial password and tap
public static boolean step()                      //  simulate one step and return the least significant (rightmost) bit
public static String  string()                    //  return a string representation of the LFSR

public static void    main(String[] args)         // unit testing function

We also provide the ImageData library for reading and writing images as 2-D integer arrays. Save it to the same folder as your own code. Only if you have any trouble compiling and using this library on your computer, try downloading the Picture library and saving it to the same folder as well. The Picture library should have been installed already by the introcs installer.

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

Part I: ASCII Conversion

Our first step will be to implement the library class that can encode the text message (in ASCII) as binary sequence, and can also decode a binary sequence back into the ASCII text message.

The ASCII (American Standard Code for Information Interchange) Character Set maps all English letters, digits, and punctuation to numbers between 0 and 127. For example, "A" is encoded as the number 65, "z" is encoded as 122, and the space character is encoded as the number 32. Java stores all English characters internally using ASCII already; if you cast a character to an integer in Java (either explicitly or implicitly), you get the ASCII code for that character. So "(int) 'A'" give the value 65. The reverse is also true: "(char) 65" gives the value 'A'. (Recall that 'A' with single quotes is the character A, which Java stores internally as the number 65; "A" with double quotes is the String A, which Java stores internally as something terrifically complicated so that programs that manipulate lots and lots of strings will run slightly faster and use slightly less memory.)

Below, we provide details on each of the encode() and decode() functions in the ASCII library. In addition, you should also write a main() function that performs unit testing of these functions. Recall that the basic idea behind unit testing is that we will write a main() method in each library class that will test the code we write. As we write each function, we can test as we go by running that main() method, ensuring that our code is correct before moving on to the next part of the assignment.

We now describe the encode() and decode() functions that you will write.

encode() Encode should accept a string, and return an array of booleans containing the bits representing that string in ASCII.

decode() Decode should accept an array of boolean values representing a message in ASCII, and return the message as a string.

Part II: Understanding the LFSR Library

In order to encrypt and decrypt messages, you will need to use the LFSR library we provide. The API is included above, but this section gives you more detailed information on how it behaves.

You don't need to implement anything in this part, just read this section thoroughly to understand the LFSR library's API.

Part III: Encrypting/Decrypting Message

Warning: Do not even think about starting this part until you have completed and tested your ASCII library!

The next task is to write an Encrypt library to encrypt and decrypt messages using a one-time pad generated using the LFSR, using the process we discussed in class. Since one-time pad is symmetric (i.e. encryption and decryption are identical), Encrypt only needs to provide a single encrypt() function.

Part IV: Hiding and Retrieving Messages

Warning: Do not even think about starting this part until you have completed and tested your ASCII and Encrypt libraries!

Your final task is to write two programs, HideMessage and RetrieveMessage that use your ASCII and Encrypt libraries to hide and retrieve encrypted messages.




Extra Credit 1: Silly Secrets

Submit at least two images in a zip file name extra.zip that contain messages you encrypted and embeeded with your own program. Include the seed an tap position in the images' filenames and in your readme. Be creative with both the images and the secret message. We'll show a selection of them in class.

Extra Credit 2: Encrypting and Decrypting Images

Images are just bits, like any other digital data, and there is no reason they can't be encrypted too. Write a program, PhotoMagic.java, that takes an image name, seed, and tap position as arguments, encrypts the image using the specified seed and tap, and displays it.