CS 110 Challenge Problem

HIGHLY CONFIDENTIAL: I have been approached by a CIA agent who needs help deciphering encoded messages that are being passed covertly to a terrorist sleeper cell in the United States. The agent needs our help deciphering these messages. This is what the agent knows so far.

• Messages are transmitted in the form of black and white images that are "hidden" inside pictures posted to Facebook.
• Hidden images are encoded into a picture using the right-most bit of each pixel color.
• A hidden image revealing the message can be constructed starting with the encoded picture as follows.
  1. Create a blank sketch with the same dimensions as the encoded picture.
  2. Loop over all pixels of the encoded picture and extract the right-most bit of each pixel color.
  3. If the bit is 0, set the color of the corresponding pixel in the new sketch to black. If the bit is 1, set the color to white.
• Update the pixels of the sketch to reveal the hidden message.

Here is the picture containing the latest secret message that needs to be decoded.

Unfortunately, the agent disappeared suddenly before completing the entire program for extracting  the hidden message in an ecoded picture, but not before telling me what has already been discovered.

Following is the incomplete program for extracting the hidden image from the encoded image. Your job is to complete the five numbered statements below and decipher the hidden message.

What to Hand in:

• Copy the entire sketch folder to your Dropbox folder.
• Make sure to name the sketch file/folder properly.
• Include the standard header in your source code.
• Write a paragraph/description and include it in the header of the main source code file for your sketch. Also include the deciphered message.
• Comment your code liberally with meaningful statements that help explain what your code is doing.

Incomplete program to decipher the hidden message:

// decode.pde

// Decode the hidden black and white image in the picture named encoded.png.
// Display the hidden image in the sketch.

PImage img;

// Used to bitwise-and with pixel color to read last bit
color readBit = color(0,0,1,0);

void setup() {
  // Load encoded image
  img = loadImage("encoded.png");
  
  // Display encoded image on the sketch
  size(img.width, img.height);
  image(img, 0, 0);
}

void draw() { }

// When the mouse is pressed, decode the secret message and display.
void mousePressed() {
  
  // Load the sketch pixels into the pixel's array
  loadPixels();
  
  // Load pixels of encoded image into the image's pixels[] array.
  img.loadPixels();
  
  // Loop over all pixels in encoded image.
  for (int i=0; ...       // 1. Complete the for-loop so that it accesses all image pixels

    // Copy ith pixel color from the image to pixVal.
    color pixVal = ...    // 2. How does one access the ith pixel from an image?
    
    // Extract the encoding bit using a bitwise-and (&) of pixVal and readBit.
    int encodingBit = ... // 3. How does one do a bitwise-and to extract a bit from the pixel
    
    // If value of the encodingBit is greater than 0, set pixVal to white (color(255))
    // Otherwise, set pixVal to black (color(0)).
    if (...               // 4. How does one build this if-else statement to properly set pixVal?
      pixVal = ...
    } else {
      pixVal = ...
    }

    // Reset the ith pixel in the sketch to pixVal.
    pixels[i] = ...       // 5. How does one set the ith pixel in a sketch?
  }
  
  // Update the pixels in the sketch to reveal the secret message.
  updatePixels();
  
}

---

Following are related complete programs for your reference.

This is the program used to create a black and white image to be hidden in a picture. Note that the size of the created image must match the size of the picture into which it will be encoded.

// createMessage.pde

// This program can be used to generate an image containing
// a hidden message to be encoded within another picture.

void setup() {
  size(604, 446);	// The size of the generated image must exactly match the picture into which the image will be encoded.
  background(0);	// Black background
  fill(255);	// White lettering
  textSize(48);
  text("The encoded message goes here", 100, 200);
  save("msg.png");
}

Here is the program used to encode a black and white image (msg.png) into a picture (bms.png) and save it as a new image (encoded.png).

// encode.pde

// Encode the image 'msg.png' into the picture 'bmc.png'
// The two images must be the exact same size.

PImage img;  // To hold unencoded picture
PImage msg;  // To hold image to be encoded into the picture

color delBit = color(255,255,254);  // Used to bitwise-or with color to remove last bit
color addBit = color(0,0,1,0);      // Used to bitwise-and with color to add last bit

void setup() {
  img = loadImage("bmc.png");   // Load the unencoded picture
  msg = loadImage("msg.png");   // Load the image toencode into the picture
  size(img.width, img.height);  // Size the sketch to be the same size as the picture
  image(img, 0, 0);             // Display the picture
}

void draw() {}

// When the mouse is clicked, encode the black and white image
// with the secret message into the picture, display it and save.
void mousePressed() {
  
  img.loadPixels();  // Load pixels for the picture
  msg.loadPixels();  // Load pixels for the b&w image to be encoded

  // Loop over all pixels in the picture
  for (int i=0; i<img.pixels.length; i++) {

    // Get pixel color in both the picture and the b&w message to be hidden
    color ip = img.pixels[i];
    color mp = msg.pixels[i];
    
    // Strip right-most bit from picture pixel
    ip = ip & delBit;
    
    // Add the bit from the hidden message to picture pixel color's right-most bit
    ip = ip | (mp & addBit);
    
    // Replace the encoded pixel back into the picture
    img.pixels[i] = ip;
  }
  
  // Update pixels and save the encoded picture to a new file
  img.updatePixels();
  image(img, 0, 0);
  img.save("encoded.png");
}