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

• Goals
• Mid-Semester Feedback
• Files to Submit
• Background: Image Steganography
• Program Structure and API
• Part I: ASCII Conversion
• Part II: LFSR Library
• Part III: Encryption/Decryption
• Part IV: Hiding and Retrieving Messages
• Extra Credit

Goals

• Learn about encryption and hiding information (steganography)
• Get an introduction to bit manipulation.
• Learn to use the ImageData API to interact with image files.
• Learn about two-dimensional arrays.
• Give us feedback on how we're doing.

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.

Submission

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 (2²⁴ - 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.

• If the string to encode has n characters, the encoded boolean array should have 7n bits. For example, the "z" is encoded as 122, which is 1111010 in binary. So encode("z") should return the array

  
  
  { true, true, true, true, false, true, false }
  
  

  The space character is encoded as 32, which is 0100000 in binary, so encode(" ") should return the array

  
  
  { false, true, false, false, false, false, false }
  
  

• If the string to encode is null, encode() should return null.
• You may assume that every character in the string is a valid ASCII character. Java supports a much larger set of characters, including accented characters and thousands of Chinese characters. You do not need to check for this: if the string contains any of these characters, encode() is allowed to fail or compute the wrong sequence of bits.
• To find out the length of a String str, use the method

  
  
  str.length()
  
  

  Note the parentheses after length(). This is different from arrays.
• To access character i of a String str, use the method

  
  
  str.charAt(i)
  
  

• Extracting bits from a number: Use either standard arithmetic operators or bit-level operators to extract the individual bits of a number's binary representation. You'll need to think about how to do this but here are some hints:
  • Think of an arithmetic operation that would tell you the ones digit of a number written in base 10. (For example, the ones digit of 1234 is 4. What arithmetic operation would tell you that?) Change your operation slightly so it gives you the ones bit of the number written in base 2.
  • Next, think of an arithmetic operation will shift a number written in base 10 one digit to the right. (For example, shifting 1234 one digit to the right will give the number 123. What arithmetic operation will do that for you?) Change your operation slightly so it shifts a number written in binary one bit to the right.
  • To get all seven bits you need, check the character's ones bit, shift it to the right, check its ones bit again, etc.
  You are required to extract the bits from the number yourself in this assignment for full credit. However, if you cannot get this aspect working, you can move on to the next part of the assignment by using the Integer.toBinaryString(int i) function, and then separating the characters of the string to create a boolean array. If you do use the Integer.toBinaryString() function in your implementation to extract the bits from the number, be sure to come back later to replace it with your own code for full credit.

• Testing: Add the following code to your main() function to take a single program argument, encode it as an ASCII bit sequence using encode(), then print out the result:

  
  
  // print an array of booleans as 1s and 0s
  private static void printBooleanArray(boolean[] bits) {
      for (int i = 0; i < bits.length; i++) {
          // print a 1 for true or 0 for false
          if (bits[i]) System.out.print("1");
          else         System.out.print("0");
      }
  
      System.out.println(); // add a newline
  }
  
  public static void main(String[] args) {
      // convert command-line argument to bits
      boolean[] bits = encode(args[0]);
      printBooleanArray(bits);
  
      // convert the bits back to a string
      // uncomment these lines once you have
      //    implemented decode
      // String s = decode(bits);
      // System.out.println(s);
  }
  
   

  • Test with single-letter arguments, like "A", whose output are easy to verify. You can find a table of ASCII characters, including their binary codes here. Note that this table gives the binary code as 8 bits, starting with a 0. Ignore the first zero, and only use the last 7 bits of the binary code. For example, the output of running "java ASCII A" with the sample main function should be

    
    
    1000001
    
    

  • When you're confident that encode() works for single-letter arguments, try testing multi-letter arguments. The bit sequences will become long very quickly, so stick to short strings whose output you can verify manually.
  • Testing is a great group activity: you can all run the same test cases and compare your output. Remember not to share your code, and to note who you worked on testing with in your readme file.
  • Think about special cases that might trip up encode() and are hard to test using command-line arguments. Add these test cases directly in your main().

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

• If the boolean array has 7n bits, decode() should return an n-character string.
• For example, decode() should convert the boolean array

  
  
  { true, true, true, true, false, true, false }
  
  

  into the string "z".
• If the length of the boolean array is not a multiple of 7, decode() should convert as many bits as possible into characters, and discarding the remaining bits at the end. For example, encode() should convert the array

  
  
  { true, true, true, true, false, true, false, false, true, true }
  
  

  into the string "z" and discard the last three bits in the array.
• If the boolean array is null, decode() should return null.
• Combining bits into a number: This is the opposite process of extracting them from a number. Starting with the value zero, what arithmetic operation would add a ones bit? What arithmetic operation would have the effect of shifting the number left by one bit. Combine these, and you can build up the number bit by bit.
• Don't forget to cast the number you build up to a char before adding it to the end of the message.

• Testing: Uncomment the last two lines of the sample main function to convert your encoded bits back to a string. Now it should print out the encoded version of your argument, followed by the original argument. For example, "java ASCII A" should now print

  
  
  1000001
  A
  
  

• Think about cases that you might not be able to test with a command-line argument. Add code to your main function to test these cases specifically.

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.

• init()
  • The init() function accepts a string representing the initial seed, and integer representing the tap position. The seed should contain only 1s and 0s.
  • Tap position 0 is the ones bit, i.e.  the rightmost bit of the seed. If the seed has n bits, tap position n - 1 is the most significant bit, i.e. the leftmost bit.
  • If the seed is not valid (only 1s and 0s), or the tap is negative or >n - 1, init() will not update the contents of the shift register and will return false.
  • If the seed and tap are both valid, init() will reset the LFSR's shift register and tap position to the seed, and return true.
  • Until init() is called with valid seed and tap values, the LFSR is configured to generate all 0s. This ensures that the LFSR is always in a valid state.
• step() will advance the LFSR one step, and return the bit that is calculated. true corresponds to the bit value 1, and false corresponds to the bit value 0.
• string() will print out the contents of the LFSR's shift register. This is useful for debugging.
• main() is useful for testing and experimenting with the LFSR library. It accepts two arguments, the seed and tap position. It prints out the original seed and tap position (which should match your command-line arguments, then it generates 8 random bits by stepping through the LFSR. It prints out the shift register contents and the new bit after each step.
• Error Messages: In some semesters, we use LFSR as a homework assignment, so we do not supply you the .java file. Instead, we supply a compiled .class file that you can use but not inspect. If you use it incorrectly, Java is likely to report a run-time error with an incomprehensible error in LFSR.java. This is normal. You will need to look farther down the error's stack trace to find the line in your own code where you called the LFSR function. The bug is almost certainly in your own code (for example, passing the wrong types of arguments).

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.

• encrypt() should accept three arguments:
  • A boolean array of bits to encrypt;
  • The LFSR seed;
  • The LFSR tap position.
• encrypt() should xor the bits in the boolean array with bits produced by the LFSR initialized with the provided seed and tap position, as described in lecture, and return the result.
• If the array of bits is null, encrypt() should return null.
• If the seed or tap position is invalid, encrypt() should return null.
• encrypt() must not modify the array of bits it is encrypting. It must generate a new array of encrypted bits.
  

• Testing:

  • Add the following code to your class to test encrypting and decrypting with a simple test case:

    
    
    // print an array of booleans as 1s and 0s
    private static void printBooleanArray(boolean[] bits) {
        for (int i = 0; i < bits.length; i++) {
            // print a 1 for true or 0 for false
            if (bits[i]) System.out.print("1");
            else         System.out.print("0");
        }
    
        System.out.println(); // add a newline
    }
    
    public static void main(String[] args) {
      // sample array for testing encrypt()
      boolean[] test = { true,  true,  true,  true,  true  };
    
      // sample seed and tap position
      String seed = "01101000010";
      int    tap  = 8;
    
      boolean[] encrypted = encrypt(test, seed, tap);
      System.out.print("test encrypted: ");
      printBooleanArray(encrypted);
      boolean[] decrypted = encrypt(encrypted, seed, tap);
      System.out.print("test decrypted: ");
      printBooleanArray(decrypted);
    }
    
    

    
    The output of running encrypt should be:

    
    
    test encrypted: 00110
    test decrypted: 11111
    
    

  • Modify your main function to accept the seed and tap as program arguments. Test with various seeds and tap positions.
  • Modify your main function to accept the message to encrypt as a string of 0s and 1s (you will need to convert this to an array of booleans). Test a variety of messages with different seeds and taps.
  • Compare your results with those of classmates and make sure they match. Remember not to look at each others' code, and to credit each other in your readme files.
  • Think about cases that are not possible to test using command-line arguments, and add code to main to test these directly.

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.

RetrieveMessage:

• Reread the background on image steganography at the top of the page. Pay particular attention to how image steganography hides a binary sequence in the pixels of the image. You will need to be familiar with this to write these programs.
• RetrieveMessage should accept three arguments:
  • The name of an image file (in PNG format only!);
  • The seed for the LFSR number generator as a string of 0s and 1s;
  • The tap position for the LFSR.
• RetrieveMessage must load the specified image, extract the message embedded in it, decrypt it using the specified seed and tap, and print out the decrypted message using System.out.println().
• If the seed and tap are not specified, assume the message is not encrypted.
• If the seed or tap is invalid, print an error message and exit the program.
• If the number of command-line arguments is not 1 or 3, print out an error message and exit the program.
• You may assume the image file is valid.
• Read bits from the image from left-to-right, top-to-bottom, just like English text. In other words, start with the upper-left pixel, and work across rows, one by one.
• If the number of pixels in the image is not a multiple of 7, ignore the extra pixels at the end.
• If the decrypted message contains a character who's numeric code is 0, only print out the characters up to, but not including that character.
  • This character is called the NULL character or ASCII NULL.
  • You can write the NULL character in Java as '\0'. You won't be able to add this character directly to the file containing your message. Instead, read the message into a string in Java, then add the NULL character to the end of the string.
  • Do not confuse the NULL character with the character '0', which corresponds to the ASCII code 48 and represents the digit zero.
• You may decode and decrypt characters one by one until your reach the NULL character, or you may decode and decrypt all possible characters, then search for a NULL in the result.
  • str.indexOf('\0') will return the index of the first occurenct of the NULL character in the String variable str. It will return -1 if str does not contain a NULL character.
  • str.substring(0, n) will return the first n characters of str.

• You may add any private helper functions and class variables that you need.

• Any behavior not included in the list above will violate the program's specification and result in point deductions.

• Testing: The following image, named stegosaur_embedded.png, contains a hidden message that is not encrypted (image source).

  • If you correctly retrieve the message, you will know it.
  • You should see a blank line at the end of the message. This is normal.
  • If you see garbage, try extracting a single character from the first 7 pixels of the image. Print the seven bits you recover as well as the decoded character. (The first characters of the secret message in the image below are a newline character followed by an 'S'.
  • If you got the first character working, but you still see garbage, try printing only the first 100 characters. If you see a message followed by garbage, make sure you are checking for a NULL character properly.
  • Think about a variety of possible scenarios, including both valid and invalid input, and test as many of them as you can now. You will be able to do more testing after you've written HideMessage.

  

  The image below, named stegosaur_encrypted.png contains the same hidden message, but this time it is encrypted with the seed 01101000010 and tap position 8. Remember, the message is encrypted, not the image; to the naked eye, these two images look identical.

  

HideMessage:

• HideMessage should accept four arguments:
  • The name of an image file (in JPEG or PNG format);
  • The name of a text file containing your message;
  • The seed for the LFSR number generator as a string of 0s and 1s;
  • The tap position for the LFSR.
• HideMessage must load the specified image and message file, encrypt the message using the specified seed and tap position, embed the encrypted message in the image, and display the result.
• If only two arguments are specified, embed the message without encrypting it.
• If the seed or tap is invalid, print an error message and exit the program.
• If any other number of arguments than 2 or 4 is specified, print an error message and exit the program.
• You may assume that both the image file and text file are valid and readable by your program.
• Use the ImageData library to load and display images.
• Read in the message using In's readAll() method. (Remember to create the text file with your message in Dr. Java, just like your readme files,not in TextEdit, Notepad, Write, or Word.)
• Add a NULL character to the end of the message.
• If the message is too long to fit in the image, truncate it to the portion that will fit in the image. You do not need to end your message with a NULL character if it takes up the entire image. (Recall that each character requires 7 pixels to encode.)
• Store bits in the image from left-to-right, top-to-bottom, just like English text.

• You may add any private helper functions and class variables that you need.

• Any behavior not included in the list above will violate the program's specification and result in point deductions.

Testing:

• Try embedding a short message with no encryption in a small image.
• Use the "Save..." option in the image window's File menu to save the image. Save the image in PNG format by entering a filename than ends in ".png". Never save your image as a JPEG or in any format except PNG! JPEG images get their compression by discarding information that is imperceptible to the human eye, including your message!
• You should be able to extract your message using RetrieveMessage.
• Try sharing images with classmates. You should be able to retrieve messages your classmates hid with their own versions of HideMessage and vice versa. Remember not to share code, and to credit anyone you share images with in your readme file.
• If you can retrieve your own messages, but not a classmate's messages, either you or your classmate may be hiding and retrieving the bits in the image in the wrong order (e.g. by working down the columns instead of across the rows).

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.

• To encrypt a single pixel, generate 24 random bits using your LFSR, pack them into a single integer, and XOR the result with the image pixel. (Recall that each pixel contains only 24, because the first 8 bits are all 0.)
• Look back over your ASCII.decode() function if you're unsure how to pack bits into an integer.
• Encrypt pixels left to right, top to bottom.
• You may assume the input image, seed, and tap position are all valid. You do not need to perform any error chacking.
• Include at least on image encrypted with your program in your extra.zip file. Include the seed and tap position in the image's filename, and also in your readme. Feel free to hide a message (even an encrypted message) in the image. Have fun!
• Here is a sample image, both unencrypted, and encrypted using the seed 01101000010100010000 and tap position 16. You should be able to run your PhotoMagic program on the encrypted image, using the specified seed and tap, to decrypt it.