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.
The Caesar cipherThe 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 algorithmFirst 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.
alphabets : ABCDEFGHIJKLMNOPQRSTUVWZXYZ
shift : 3
plainText : HELLO
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:
- Point the left index finger at the first letter of plainText (which is "H").
- Point my right index finger at the first letter in the list of alphabets (which is "A").
- 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
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:
Caesar cipher encryption in ScratchOne 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:
|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.
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|