Programming Assignment 3: Cryptography

Initial Due Date: 2025-10-02 8:00AM
Final Due Date: 2025-10-16 4:15PM

Goals

In this assignment you will:

Practice with string methods, slicing and writing for loops.
Practice adding code to an existing code base.
Encrypt/decrypt secret messages!

Background

For this assignment, we’re going to be experimenting with basic cryptography. Cryptography is a field at the intersection of math and computer science that studies ways of securely communicating information. The two main functions are encryption, where we take a plaintext message and encrypt it into the cyphertext, and decryption, where we take the encrypted cyphertext and extract the original plaintext message. In this assignment, we’ll experiment with a few different ways of doing both of these operations.

One way to communicate securely with someone is to first decide (beforehand) on a secret key that you both know. Then, when you want to send a message, you encrypt it using the secret key and send the encrypted message to the other person. The other person can then use that same key to decrypt the message.

For this assignment, you will be provided some code to get you started. This code has some variables and functions already written for you, and you will be filling in some of the details. An important skill for any programmer is the ability to utilize and extend previously written code.

Download the starter code

Right-click on the above link, select “Save as…” or “Download as…”, and save the file for this assignment to your cs146 folder. Then open your cs146 folder in VS Code and open the pa3_enryption.py file. This file does not have any syntax errors, however, until you fill in some of the details not all of the functions will run (i.e. the keygen function will throw an error).

Guide

Warming up

As a warm-up, we’re going to try a very simple method for encryption. You have a friend who says they have a great idea for encrypting a message. To encrypt a string, you repeat each letter 3 times. To decrypt it, you reverse the process. For example: “secret message” would become “ssseeecccrrreeettt mmmeeessssssaaagggeee”

Write a function called fools_encrypt that takes a message as a parameter and returns the message encrypted using this scheme.

If you want a challenge (not required), try to write a function named fools_decrypt that decrypts this. For example, you could execute:

fools_decrypt("ssseeecccrrreeettt   mmmeeessssssaaagggeee")

'secret message'

secret = fools_encrypt("secret message")
secret

'ssseeecccrrreeettt   mmmeeessssssaaagggeee'

fools_decrypt(secret)

'secret message'

Show a possible solution

FOOLS_EXPANSION = 3

def fools_decrypt(message):
    """
    Decrypts the encrypted message which was encrypted using fools_encrypt
    
    Args:
        message: String to decrypt

    Return:
        Decrypted message string
    """
    decrypted = ""
    for i in range(0, len(message), FOOLS_EXPANSION):
        decrypted += message[i]   
    return decrypted

Show another possible solution

FOOLS_EXPANSION = 3

def fools_decrypt(message):
    """
    A more concise approach to decrypt a message encrypted using fools_encrypt

    Args:
        message: String to decrypt

    Return:
        Decrypted message string
    """
    return message[::FOOLS_EXPANSION]

Caesar’s method

One of the simpler and more famous encryption schemes is credited to Julius Caesar. This scheme is representative of “substitution ciphers” in that each character is substituted for a different character. To specify a substitution cipher we need to specify the alphabet of characters that our message can contain and then for each of these characters we specify a corresponding substitution character. Caesar’s approach was to substitute a letter in the original alphabet with the letter that was at some fixed offset in the alphabet. For example, if you chose 2 as your fixed number:

alphabet: a b c d e f g h i j k l m n o p q r s t u v w x  y  z ' '
key:      c d e f g h i j k l m n o p q r s t u v w x y z ' ' a  b

i..e, all ’a’s would be replaced with ’c’s, all ’d’s with ’f’s, etc. or if we chose 4

alphabet: a b c d e f g h i j k l m n o p q r s t u v  w  x y z ' '
key:      e f g h i j k l m n o p q r s t u v w x y z ' ' a b c  d

Notice that we include the space as a character (written as ' ') and that we wrap around when we reach the end of the alphabet. When encrypting, you simply replace each character in your message with the encrypted character (i.e., the character as a fixed offset in the alphabet) and to decrypt it you reverse the process.

Now, let’s try to implement Caesar’s encryption scheme. Note that the starter code has a function named shift_letter. Play with this function and try some different letters (lowercase letters only) and different number offsets to make sure you understand how it works. Notice that you can also pass it negative numbers to shift the other direction.

Encryption

Once you’re comfortable with how shift_letter works, write a function called caesar_encrypt that takes two parameters: the message to be encrypted and the size of the shift for the encryption. You will very likely want to utilize the shift_letter function.

Decryption

One of the nice things about this encryption scheme is that we can use the same function for encrypting and decrypting a message. Before continuing, think about how we could do this!

To decrypt a message, we can use our caesar_encrypt function, but now, give it a negative number. Encrypt a message or two and make sure that you can decrypt them. Decrypt the following message with number offset 5:

htruzyjwexhnjshjenxestertwjefgtzyehtruzyjwxeymfsefxywtstrcenxefgtzyeyjqjxhtujx

It’s a quote from a famous computer scientist (Dijkstra). You don’t have to write it down, but it’s a good check to make sure you’ve got things working.

Warning: our encryption schemes will only work for lowercase letters (specifically the letters a-z and space), so make sure that your message doesn’t have any other characters otherwise, it won’t work correctly.

Substitution ciphers

Caesar’s method is just an example of a more general type of encryption scheme called substitution ciphers. For a general substitution cipher, we need a key. The key has all of the same letters as the alphabet, but the order has been shuffled.

When encrypting, you encrypt one letter at a time. For each letter in the message you find that letter in the alphabet and then replace it with the corresponding letter in the key. For example, say you have following alphabet and key (the indices are labelled for clarity):

alphabet: a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z  ' '
          0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
key:      h  v  i  e  k  s  y  r  b  d  a  j  q  w  n  c  x  m  g  u  f  l  t  p ' ' o  z

and you want to encrypt the character ‘k’. You look that up in the alphabet and notice that it is at index 10. You then use this index in the key to get ‘a’ as the letter. This process is repeated for each letter in the message until you have encrypted the entire message. Make sure you understand this process before moving on to the coding.

Key generation

Before we can actually encrypt anything, we first need to generate a key. The starter code has a helper function named keygen for generating the kind of keys needed by your substitution encryption and decryption functions. This function takes any string as a parameter and generates a random key based on that input string (think of it like a password). The keygen function is complete, except it relies on the splice function, which needs to be implemented. Fill in the details of the splice function (see the docstring for what this function should do).

When you’re done, you should be able to generate random keys using the keygen function. Try out a few examples and make sure that it is a permutation of all of the letters in the alphabet and that you get the same thing back if you give it the same password. For example:

keygen("doglover")

'rviohn pwdgulmqezsabktycjxf'

keygen("doglover")

'rviohn pwdgulmqezsabktycjxf'

Note: due to various computer-specific factors you may not get the exact same keys as included above. However, calling keygen twice with the same string should return the same key.

Encryption

Now that you can generate random keys, you’re ready to encrypt messages. Write a function named subst_encrypt that takes two parameters: the message to be encrypted and the key (not the password). The function should return the message encrypted using the key. Notice that there is a constant named ALPHABET which has all of the letters and space in order. You’ll likely need (want) to use this.

Decryption

For a general substitution cipher we also need to write a decryption method. Write a function called subst_decrypt that takes two parameters: the encrypted message and the key (not the password). The function should return the message decrypted using the key (i.e. the original message before encryption). This function should be very similar to the encryption function with just one or two minor changes (it’s the same basic idea, but in the other direction). When you’re done, you can generate a new key, then encrypt and decrypt messages. For example:

key = keygen("mypassword")
key

'stpmzrxhlabeqog jnvydkucfwi'

encrypted = subst_encrypt("this is a secret message", key)
encrypted

'yhlvilvisivzpnzyiqzvvsxz'

subst_decrypt(encrypted, key)

'this is a secret message'

As before, keygen might work differently on your machine, so your encrypted text might look different (but the decrypted message should be the same as the original message).

Decrypt the following message using the password “i like cs”

virofrhvovin aoufzbvouofzzdru onhortr onyowzboueropez aowzboueroz dwozyyofwouofnv

Note: If it doesn’t work, check to see if you random key is 'ufclryainmjds zxgehvbtpqwko'. If it’s not, it’s most likely just a difference in computers. Try your decrypt message function with this key then to make sure it works.

Again, you don’t have to write it down, but it’s a good check to make sure you’ve got things working.

Specification

At a minimum your submission should have:

A function named fools_encrypt that takes a message as a parameter and returns the message encrypted using the scheme described in the Guide section.
A function named caesar_encrypt that takes two parameters, the message to be encrypted and the size of the shift for the encryption, and implements Caesar’s encryption method.
A fully implemented splice function.
A function named subst_encrypt that takes two parameters, the message to be encrypted and the key, and performs substitution encryption.
A function named subst_decrypt that takes two parameters, the encrypted message and the key, and performs substitution decryption.

Creativity Suggestions

[1 point] Write two new methods called encrypt_text_with_emoji and decrypt_text_with_emoji which both take in (1) a message to encrypt/decrypt, (2) a text_key to use for the text encryption/decryption and (3) an emoji_key to use for the emoji encryption/decryption. For simplicity, assume that the last character in message is an emoji from the possible list of emojis below (from here):

EMOJIS = "😀😁😂😃😄😅😆😇😈😉😊😋😌😍😎😏😐😑😒😓😔😕😖😗😘😙😚😛😜😝😞😟😠😡😢😣😤😥😦😧😨😩😪😫😬😭😮😯😰😱😲😳😴😵😶😷😸😹😺😻😼😽😾😿🙀🙁🙂🙃🙄🙅🙆🙇🙈🙉🙊🙋🙌🙍🙎🙏"

The key you use for the text encryption/decryption (text_key) can be generated similar to what you used earlier. However, the key you generate for the emoji encryption/decryption (emoji_key) needs to contain the emojis above, so now you should use the keygen function as keygen("some password", EMOJIS) to generate emoji_key (but replace "some password" with a passphrase of your choice). For example:

>>> text_key = keygen("i like cs") # uses the default ALPHABET to generate the key
>>> emoji_key = keygen("cs is fun", EMOJIS) # uses EMOJIS to generate the key
>>> encrypted_message = encrypt_text_with_emoji("hello 😎", text_key, emoji_key)
>>> encrypted_message
irddzo😕
>>> original_message = decrypt_text_with_emoji(encrypted_message, text_key, emoji_key)
"hello 😎"

[1 point] Caesar’s method can actually be written using our code for the general substitution cipher. Write a function named shift that takes in an integer as an argument. The function should return a key that is the in-order alphabet shifted up by the number input. For example:
```
shift(3)
```
```
'defghijklmnopqrstuvwxyz abc'
```
If you then use this key with your subst_encrypt function you should get the same answer as if you’d used your caesar_encrypt method with the number offset.
Write a pair of functions my_encrypt and my_decrypt that implement your own encryption algorithm! You may rely on whatever input you would like, but make it clear in the documentation how they should be run. Points will be awarded based on difficulty and creativity. For example, a better (more secure) version of our substitution would evolve the key with each letter (termed a polyalphabetic cipher). Think about how you could deterministically evolve your substitution key.

When you’re done

When you’re done you should have three different encryption/decryption methods and a working function for generating random keys. Make sure that your program is properly commented:

You should have a comment at the very beginning of the file with your name, and a listing of your creativity additions.
Each function should have an appropriate docstring (including arguments and return value if applicable).
Other miscellaneous inline/block comments if the code might otherwise be unclear.

In addition, make sure that you’ve used good coding style (including meaningful variable names, constants where relevant, vertical white space, removing “dead code” that doesn’t do anything, removing testing code, etc.).

Submit your program via Gradescope. Your program program file must be named pa3_encryption.py. You can submit multiple times, with only the most recent submission (before the due date) graded. Note that the tests performed by Gradescope are limited. Passing all of the visible tests does not guarantee that your submission correctly satisfies all of the requirements of the assignment.

Grading

Assessment	Requirements
Revision needed	Some but not all tests are passing.
Meets Expectations	All tests pass, the required functions are implemented correctly and your implementation uses satisfactory style.
Exemplary	All requirements for Meets Expectations, 2 creativity points, and your implementation is clear, concise, readily understood, and maintainable (e.g. relevant constants are used appropriately).

FAQ

How do I use keygen?

Note that keygen is a helper function for generating valid keys for your subst_encrypt and subst_decrypt functions. You should not use keygen within the subst_encrypt and subst_decrypt functions. Instead, as shown in the examples, both of those functions take the key, generated previously by keygen, as a parameter. For example:

key = keygen("mypassword")
encrypted = subst_encrypt("this is a secret message", key)
decrypted = subst_decrypt(encrypted, key)
print(decrypted)

Notice that the key produced by keygen is used as the second parameter to both subst_encrypt and subst_decrypt. More specifically, your code should produce the exact same output as below, that is given a string and a key, your function should be able to encrypt or decrypt the message (without using keygen):

subst_encrypt("this is a secret message", "jf rdesquztkwhoipcbamlvxgny")

'aqubyubyjybd cdaywdbbjsd'

subst_decrypt("aqubyubyjybd cdaywdbbjsd", "jf rdesquztkwhoipcbamlvxgny")

'this is a secret message'