Overview

Today, we are going to explore string operations and how they can be applied to cryptography.

Objectives for today's lab:

Obtain experience using strings in Python, including looping over characters in strings and conversion to/from ASCII
Create a program that uses string operations to encrypt and decrypt a string using a simple substitution cipher

Caesar Cipher

The Caesar cipher is a specific kind of simple substitution cipher where each letter in the input is shifted by a certain number of letters to obtain the output. This is called a 'rotation', like with old-fashioned decoder rings. To get a key, you can take an alphabet and line it up with a shifted one:

Rotate by three to the left (encrypt):
ABCDEFGHIJKLMNOPQRSTUVWXYZ -> DEFGHIJKLMNOPQRSTUVWXYZABC

So the string 'COMPUTER' would be encrypted into 'FRPSXWHU'

Notice now how 'rotate' is actually different from 'shift' because the letters towards the end of the alphabet are wrapped around. Decryption is done the same way, but by rotating in the opposite direction:

Rotate by three to the right (decrypt):
ABCDEFGHIJKLMNOPQRSTUVWXYZ -> XYZABCDEFGHIJKLMNOPQRSTUVW

And 'FRPSXWHU' would be decrypted into 'COMPUTER'

Program Outline

Your program is going to read in some plaintext from the user as a string, loop over each of the characters in the string and print out their encryption value. For simplicity, our program will convert all of the characters in the input to uppercase characters. Spaces should be ignored. You may assume that the input contains no characters other than letters and spaces.

The psuedocode will look like the following:

read input <string> from user
convert <string> to all uppercase
for each <char>acter in <string>
    if <char> is not a space
        convert <char> to its ASCII <value>
        rotate <value> by a given amount
        convert <value> back to a character, <char>
        print out <char>

Step 0: Setup

The first step is to create a lab3 folder in your cs201/labs directory and make a lab3.py file to start programming.

From your home directory:

cd 201/labs
mkdir lab3
cd lab3
emacs lab3.py &

Edit the lab3.py to look like the following:

# File:        lab3.py
# Written by:  YOUR NAME HERE
# Date:        DATE HERE
# Section:     ?
# Email:       ?@umbc.edu 
# Description: Lab 3, Cipher. Encoding/Decoding a string. 
#              Use this as example for our Homework in a few weeks!!

import string

def main():

	#read input <string> from user

	#convert <string> to all uppercase

	#for each <char>acter in <string>
    
		#if <char> is not a space
			
			#convert <char> to its ASCII <value>
		
			#rotate <value> by a given amount
        
			#convert <value> back to a character, <char>
        
			#print out <char>


main()

Step 1: Getting Started

Your program is going to read input from the user and encrypt/decrypt the results, so the first thing it needs to do is read input from the user into a variable. Remember that raw_input() is needed when dealing with strings. For reference, input works as follows:

>>> user_string = raw_input("Please input a string: ")
Please input a string: Hello
>>> user_string
'Hello'

Step 2: Convert to All Uppercase

To make things easier, before starting to convert to ASCII, we'll use the string.upper() function to convert your string to all uppercase letters. This will make the rotation easy because all of the letters will now have their ASCII values between 65 and 90.

Here's an example (that you should not copy directly into your code) of using the string.upper() function. You must import string before calling the function.

>>> import string
>>> original = 'This is the message'
>>> allCaps = string.upper(original)
>>> print allCaps
THIS IS THE MESSAGE
>>> print original
This is the message
>>>

Step 3: Looping Over Characters

In order to loop over each character in the string, you must use a for loop.
For loops are of the format for <loop variable> in <string variable>:

Your loop variable can be named anything you want, but make sure that the
<string variable> is the variable that you've read your input into.

Inside the for loop, you'll have to do a check to make sure the character is not a space. For this task, you'll use an if statement.

If your loop variable is called 'char' then it would look like this:

if char != ' ':
    #Code here for doing something with a char that isn't a space

Step 4: Rotating Characters

The first step in rotating the characters is to convert them to ASCII using the ord() function. Once we have the ASCII value, how are we going to do the rotation?

You can refer to this ASCII chart as a reference.

Convert the character to ASCII and store its value in a variable.
Next, you should rotate the ASCII value by adding the rotation amount. In this case, the rotation amount is 13.
Now comes the tricky part. How can you make sure that letters won't be shifted off the end of your alphabet instead of wrapped around?
You can ensure this by comparing the rotated character to the capital 'Z' character. If the ASCII value of the rotated character is greater than ord('Z'), then you should subtract 26 from the rotated value.
Finally, convert back to a character with the chr() function and print out the newly encrypted value.

Sample Output

travis-laptop-2% python lab3.py         
Input your plaintext: hello
U R Y Y B
travis-laptop-2% python lab3.py
Input your plaintext: uryyb
H E L L O

Bonus Step: Encryption/Decryption

If you are attempting the bonus step, make a copy of your lab3.py file called bonus3.py. Make the modifications as described below to your program in your bonus3.py file. Don't forget to change the name of the file and the description in the file header comment too.

Right now, your program only shifts 13 characters, which is conveniently its own inverse so it can both encrypt and decrypt. (13 encrypts, -13 would decrypt) However, it would be useful to have the user be able to input a key (the number of characters to shift) to encrypt (key), or the inverse of the key to decrypt (-key).

Hint: The modulus operator can be useful and negative numbers can be used with the modulus operator:

>>> -3 % 26
23

Sample Bonus Output

travis-laptop-2% python bonus3.py
Input your plaintext: hello
Input shift distance: 4
L I P P S
travis-laptop-2% python bonus3.py
Input your plaintext: lipps
Input shift distance: -4
H E L L O

Challenge Step: Variable Rotation

As before, if you are attempting this step, make a copy of bonus3.py named challenge3.py and make your modifications to this new file.

Now that we have created our simple substitution cipher, we can try to make it more secure. Right now, each letter is always encrypted to the same value. This is a disadvantage because someone could use that information to break our cipher through a frequency analysis (noting that certain letters occur more often than others).

One way of making it more secure is to vary the shift amount. If your shift amount is completely random, this is known as a one-time pad and is perfectly secure, because no information can be gained from just having the ciphertext.

It is difficult to make something completely random, but there are ways to approximate it. The way you'll use is called a linear congruential generator. It creates a series of almost-random numbers by taking the previous number, multiplying it by a constant, adding another constant and applying a modulus.

For your program, you will read in a starting number and for each character that you encrypt you will get it's shift by taking the previous number, multiplying it by 7, adding 11 and applying a modulus of 26.

Sample Challenge Output

travis-laptop-2% python challenge3.py
Input your plaintext: hello
Input 'E' for encrypt or 'D' for decrypt: e
Input random seed: 13
F B B E C
travis-laptop-2% python challenge3.py
Input your plaintext: fbbec
Input 'E' for encrypt or 'D' for decrypt: d
Input random seed: 13
H E L L O

Lab 3 - Strings