Monday, February 27, 2012

Project: Caesar Cipher

Hello and welcome to the first project of 2012 at Fun with Scratch! Ever wanted to send secret coded message to your friends? This project is a simple code machine that encrypts your message into a cipher text with a technique called the Caesar Cipher. You can send the encrypted text to your friend - via some means like e-mail or phone, etc - and with this same program your buddy can decrypt and read your secret message!

In the past I usually explain from start to end all the scripts in a project. If you have been following them all, I trust that by now you would be able to understand the use of broadcast and when I receive blocks to control scene transitions in this project.

What I want to focus on this time is the concept of Caesar Cipher, how we devise an algorithm for it, and how we translate this algorithm into Scratch scripts.

Let's begin.

The Caesar cipher

The idea is simple. Given a message, we change it into a code (or cipher) by replacing each letter in the message with another letter in the alphabet. The letter we use for replacement is determined by the shift.

A shift of 1 means that we replace the letters in our message with the first letter after it. So A is replaced with B, B with C, and so forth. At the end of the alphabet, we restart at the beginning. So, Z is replaced by A.

Here is another example. When the shift is 3, A is replaced with D, B with E, Y with B, Z with C, etc. The message "I LOVE APPLES" will be encrypted as "L ORYH DSSOHV".

Caesar cipher with shift of 3 e.g. B is replaced with E
(image from Wikipedia)

Decryption is the reverse of encryption. So given the cipher text "L ORYH DSSOHV" with a shift of 3, we would replace each letter in the cipher with the third letter before it in the alphabet, yielding "I LOVE APPLES".

Caesar cipher algorithm

First off, if you are new to the word "algorithm": it simply means a set of step-by-step instructions. A recipe is an example of an algorithm. A recipe specifies ingredients needed and contains step-by-step instructions to make something with the ingredients.

Now, when we are given a plain text like "I LOVE APPLES", what step-by-step instructions can we create to convert it into a Caesar cipher?

Here is one way we could do it.

Before we start any encryption we:
  • List the entire alphabet on paper, in order.
  • Ask someone to give us a message to encrypt.
  • Also ask that person to tell us the shift that they want to encrypt with.
So let's say the message is "HELLO", and the shift is 3. To help us remember, we will write them somewhere like so:

shift      : 3
plainText  : HELLO
cipherText :

We leave cipherText blank for now. We will fill cipherText as we go along our algorithm.

This is how we can proceed to encrypt it:
  1. Point the left index finger at the first letter of plainText (which is "H").
  2. Point my right index finger at the first letter in the list of alphabets (which is "A").
  3. Compare the letter that the left index finger is pointing at, to the one the right index is pointing. If they are different, shift the right index to the next letter. Continue to do so until the letter the right index is pointing at is the same as the one on the left. Once that happens, move the right index 3 letters down (because the shift is 3). We would reach the cipher letter (in this case, once we reach "H", we move 3 letters down to reach "K", its cipher). So we write it down:

    cipherText: K

Now we redo Steps 1-3. However at step 1, move the left index to the next plainText letter (which is "E"). At Step 3, we stop only when the right index reaches "E", then move down 3 letters and to reach "H". That's the cipher for "E". So we write it down:

cipherText: KH

All we do is that we would repeat Steps 1-3, moving the left index to the next letter until all of plainText has been encrypted, resulting in:

cipherText: KHOOS

Caesar cipher encryption in Scratch

One of the nicest things with Scratch is that we can almost always translate our algorithm into Scratch blocks directly. We actually have six "ingredients" in our algorithm, and we will translate these into variables in Scratch:

"Ingredients":Scratch Variables
left index finger:idx
right index finger:aIdx

Let's look at the algorithm in Scratch script:

Full Caesar cipher script for encryption

This script is run when the sprite receives an "encryptCaesar" message. It does two things. First, set idx to 0,  which is like saying that we move the left index finger to the beginning of the plain text, not pointing at the first letter, but resting just to the left of it. Second,  set cipherText to blank, and that is akin to getting ourselves a blank sheet of paper to write our cipher on.

When we have done that, we are ready to repeat Steps 1-3 of the algorithm for the entire length of the plainText.

Repeat algorithm for all letters in the plain text

The two blocks below represent Steps 1 and 2:

Steps 1 and 2

Remember that idx is the Scratch representation of the left index finger. Changing it by 1 moves the left finger to the next letter. Since we first rest the index before the first letter, this change by 1 just moves it to point at the first letter.

Step 2 points the right index at the first letter of the alphabet, that is equivalent in Scratch to setting aIdx to 1. We ignore the encrypted? variable for now.

The next does Step 3, which compares the letters pointed at by the two indexes. If it is the same, we append the letter shift numbers down it to the cipherText. If not, we move on to compare the next letter in the alphabet.

Step 3

The encrypted? variable is there to tell us whether we have encrypted the current plainText letter (i.e. the pointed by the left index, or idx in Scratch). Once we find a match in the alphabet, we can set encrypted? to true, so that we needn't compare the rest of the letters in the alphabet and can move on to the next plainText letter.

If we have traversed down the entire alphabet, and encrypted? remains false, then we know that the character we are pointing at in the plainText is not a letter, but some symbol not in the alphabet. In this case, we simply use back the same symbol in cipherText. This is what the following block does:

When there is no match in the alphabet, simply append the plain text symbol to the cipher

Final message

This is definitely a tad more advanced than the projects we have had here before. You would at least need to know modular arithmetic, and reason out the range transition of the indexes. Post a comment here if you need help with it. If you are a Scratch teacher you may want to introduce these concepts to the student first before embarking on the project.