The Encryption Algorithm The encryption algorithm carries ou

The Encryption Algorithm

The encryption algorithm carries out encryption and decryption using a deck of cards^[1]. However, we\'re going to make two simplifications to a regular card deck. First, rather than use a standard deck of 52 cards, we\'re going to use 28 cards. Second, rather than use actual card ranks and suits, we\'re going to use the numbers from 1 to 28. We will call 27 and 28 the jokers. We\'re doing this because it\'s not necessary to know anything about playing cards to understand this algorithm, so we might as well use integers rather than card names.

We\'ll be doing lots of rounds, one for each letter in a message, and so we decided to have a function that does all the steps in a round.

Each of the steps in a round is independent, and so we decided to have a separate function for each step.

The algorithm is an example of a stream cipher. What that means is that every time you complete a round of the algorithm, you get one keystream value. This stream of values is then used, in combination with plaintext or ciphertext, to encrypt or decrypt, respectively. You will complete one round of the algorithm for each letter in the text to be encrypted or decrypted.

Each round of the algorithm consists of (one or more repetitions of) five steps; once all steps in a round are complete, one keystream value is available and the next round of keystream generation can begin.

Here is the algorithm; an example follows.

Begin with a deck of cards, which is really just a permutation of the integers from 1 to 28. The steps for one round are as follows:

Steps 1 and 2 involve swapping cards, so we\'ll have a helper function that does that; both step 1 and step 2 will call that function.

Find the card with value 27. Swap this card with the following card (so that it moves down one position). If the card with value 27 is at the bottom end of the deck, then swap the 27 with the top card. That is, think of the deck as circular, so that the card following the bottom card is the top card.

Find the card with value 28. Move it two cards down by performing two swaps, again treating the deck as circular.

Recall that the two cards with values 27 and 28 are the two jokers. Swap the cards above the first joker (the joker closest to the top of the deck) with the cards below the second joker. This is called a triple cut. Think about what happens if a joker is at the top or bottom of the deck? What if the jokers are next to each other? Is this a problem?

Look at the bottom card from the deck. That card will have some value v. If v is 28, use a value v of 27 in this step. Then, take v cards from the top of the deck, and put them above the bottom-most card in the deck.

If we get a joker as a potential keystream value, we might have to repeat all these steps. We decided to have a function that generates the next potential keystream value, and a separate function that calls that one until a non-joker is produced.

Look at the top card from the deck. That card will have some value v. If v is 28, use a value v of 27 in this step. Starting from the top, find the card that is at position v in the deck (the topmost card is at position 0). If the card on which you land is a joker, continue the current round at step 1. Otherwise, remember the value of the card on which you landed; this is the keystream value generated for the current round. This keystream value will be in the range 1-26 inclusive. (Thought question: why can\'t it be a 27 or a 28?)

To generate another keystream value, we take the deck as it is after step 5 and run another round of the algorithm. We need to generate one keystream value for each character in the text to be encrypted or decrypted.

Example: Completing one Round

Let\'s go through an example of how the algorithm generates keystream values. Consult the descriptions of the steps given above as you follow along with this example. We\'ll illustrate the first round of the algorithm, but encourage you to do another round by-hand so you really understand what\'s happening.

Consider the following deck. The top card has value 1. The bottom card has value 26.

Step 1: Swap 27 with the value following it. So, we swap 27 and 2:

Step 2: Move 28 two places down the list. It ends up between 6 and 9:

Step 3: Do the triple cut. Everything above the first joker (28 in this case) goes to the bottom of the deck, and everything below the second (27) goes to the top:

Step 4: The bottom card is 6. The first 6 cards of the deck are 5, 8, 11, 14, 17, and 20. They go just ahead of 6 at the bottom end of the deck:

Step 5: The top card is 23. Thus, our generated keystream value is the card at position 23. This card has value 11. Since this value 11 isn\'t 27 or 28, we are done with the round.

As a self-test, you should carry out the next round of the algorithm to find the second keystream value. Its value is 9; be sure you get the same value to convince yourself that you understand the five steps.

Solution

Solution:

Consider the following deck. The top card has value 1. The bottom card has value 26.

Step 1: Swap 27 with the value following it. So, we swap 27 and 2:

Step 2: Move 28 two places down the list. It ends up between 6 and 9:

Step 3: Do the triple cut. Everything above the first joker (28 in this case) goes to the bottom of the deck, and everything below the second (27) goes to the top:

Step 4: The bottom card is 6. The first 6 cards of the deck are 5, 8, 11, 14, 17, and 20. They go just ahead of 6 at the bottom end of the deck:

Step 5: The top card is 23. Thus, our generated keystream value is the card at position 23. This card has value 11. Since this value 11 isn\'t 27 or 28, we are done with the round. The generated keystream value is 11.

Encrypting And Decrypting

To encrypt a message, remove all non-letters from the message and convert any lowercase letters to uppercase. Next, convert the letters to numbers (A becomes 0, B becomes 1, ..., Y becomes 24, and Z becomes 25). Then, use the algorithm to generate the same number of values as there are letters in the message. Add the corresponding pairs of numbers, modulo 26. Finally, convert the resulting numbers back to letters.

Decryption is just the reverse of encryption. Start by converting the message to be decoded to numbers. Using the same card ordering as was used to encrypt the message, generate one keystream value for each character in the message. (Because the same starting deck of cards was used, the same keystream will be generated.) Subtract the keystream values from the message numbers, again modulo 26. Finally, convert the numbers to letters to recover the message.

Encrypting and Decrypting

Let\'s say we want to encrypt the plaintext message Lake Hylia. We start by cleaning the message by removing non-letters and capitalizing the letters, which gives us LAKEHYLIA. Next, we convert these letters to numbers:

Since we have nine letters, nine keystream values are required. Rather than go through nine rounds of the algorithm here, let\'s just assume that the nine generated keystream values are as follows:

Now add the numbers from the letters and the generated keystream values together pairwise, modulo 26. (If the letters were not from English, the 26 would be replaced by the number of letters in the alphabet.) The ``modulo 26\'\' part means that if the sum of the pair of numbers is greater than 25, then subtract 26 from the sum. (For example, 1 + 8 = 9, which is not greater than 25, so (1 + 8) modulo 26 is 9. But, 11 + 17 = 28, which is greater than 25, so we compute 28 - 26 = 2, and (11 + 17) modulo 26 is 2.) Then, convert the resulting sums to letters to produce the encrypted message (the ciphertext):

To decrypt this message, the recipient would start with the same deck with which the encryption was started, and generate the same nine-number keystream. They would then convert the ciphertext to numbers. Then, instead of adding corresponding numbers from the keystream and ciphertext, they would pairwise-subtract the keystream from the ciphertext, modulo 26. (Again, if the letters were not from English, the 26 would be replaced by the number of letters in the alphabet.) That is, if the subtraction gives you a negative number, add 26 to the result. (For example, 9 - 8 = 1, which is not negative, so (9 - 8) modulo 26 is 1. But 2 - 17 = -15, which is negative, so add 26 to get 11, and then (2 - 17) modulo 26 is 11.) The decryption back to LAKEHYLIA looks like this:

MAIN PROGRAM IN PYTHON CODE:

\"\"\"

Encrypt or decrypt the contents of a message file using a deck of cards.
\"\"\"

import cipher_functions
import os.path

def get_valid_filename(msg):
\"\"\" (str) -> str

Prompt the user, using msg, to type the name of a file. This file should
exist in the same directory as the starter code. If the file does not
exist, keep re-prompting until they give a valid filename.
Return the name of that file.
\"\"\"

filename = input(msg)
while not os.path.exists(filename):
print(\"That file does not exist.\")
filename = input(msg)
return filename

def get_encryption_mode():
\"\"\" () -> str

Prompt the user to enter the encryption mode. If the user enters an invalid
mode, keep re-prompting until they give a valid mode.
\"\"\"

msg = \'Do you want to encrypt ({0}) or decrypt ({1})? \'.format(
cipher_functions.ENCRYPT, cipher_functions.DECRYPT)
mode = input(msg)
while not (mode == cipher_functions.ENCRYPT or
mode == cipher_functions.DECRYPT):
print(\'Invalid mode.\')
mode = input(msg)
return mode

def main():
\"\"\" () -> NoneType

Perform the encryption using the deck from file named DECK_FILENAME and
the message from file named MSG_FILENAME. If MODE is \'e\', encrypt;
otherwise, decrypt.
\"\"\"

prompt = \'Enter the name of the file that contains the card deck: \'
deck_file = open(get_valid_filename(prompt), \'r\')
deck = cipher_functions.read_deck(deck_file)
deck_file.close()
if not (cipher_functions.is_valid_deck(deck)):
print(\'The supplied card deck is not a valid deck.\')
print(\'Encryption process stopping.\')
return

prompt = \'Enter the name of the file that contains the message: \'
msg_file = open(get_valid_filename(prompt), \'r\')
messages = cipher_functions.read_messages(msg_file)
msg_file.close()

mode = get_encryption_mode()

for msg in cipher_functions.process_messages(deck, messages, mode):
print(msg)

if __name__ == \"__main__\":
main()

CIPHER FUNCTIONS USED

# Functions for running an encryption or decryption algorithm

ENCRYPT = \'e\'
DECRYPT = \'d\'

TYPE CHECKER And Use of Functions

\'\'\'This module should be used to test the parameter and return types of your

functions. Before submitting your assignment, run this type-checker. This
typechecker expects to find files cipher_functions.py, secret1.txt, and
deck1.txt in the same folder.

If errors occur when you run this typechecker, fix them before you submit
your assignment.

If no errors occur when you run this typechecker, then the type checks passed.
This means that the function parameters and return types match the assignment
specification, but it does not mean that your code works correctly in all
situations. Be sure to test your code thoroughly before submitting.
\'\'\'

import builtins

# Check for use of functions print and input.

our_print = print

def disable_print(*args):
raise Exception(\"You must not call built-in function print!\")

def disable_input(*args):
raise Exception(\"You must not call built-in function input!\")

builtins.print = disable_print
builtins.input = disable_input

import cipher_functions

sample_deck = [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 3, 6, 9, 12, 15,
18, 21, 24, 27, 2, 5, 8, 11, 14, 17, 20, 23, 26]

# typecheck the cipher_functions.py functions

# Type check cipher_functions.clean_message
result = cipher_functions.clean_message(\'abc\')
assert isinstance(result, str), \\
\'\'\'clean_message should return a str, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.encrypt_letter
result = cipher_functions.encrypt_letter(\'A\', 1)
assert isinstance(result, str) and len(result) == 1, \\
\'\'\'encrypt_letter should return a single character, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.decrypt_letter
result = cipher_functions.decrypt_letter(\'B\', 1)
assert isinstance(result, str) and len(result) == 1, \\
\'\'\'decrypt_letter should return a single character, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.swap_cards
result = cipher_functions.swap_cards(sample_deck, 1)
assert result is None, \\
\'\'\'swap_cards should return None, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.get_small_joker_value
result = cipher_functions.get_small_joker_value(sample_deck)
assert isinstance(result, int), \\
\'\'\'get_small_joker_value should return int, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.get_big_joker_value
result = cipher_functions.get_big_joker_value(sample_deck)
assert isinstance(result, int), \\
\'\'\'get_big_joker_value should return int, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.move_small_joker
result = cipher_functions.move_small_joker(sample_deck)
assert result is None, \\
\'\'\'move_small_joker should return None, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.move_big_joker
result = cipher_functions.move_big_joker(sample_deck)
assert result is None, \\
\'\'\'move_big_joker should return None, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.triple_cut
result = cipher_functions.triple_cut(sample_deck)
assert result is None, \\
\'\'\'triple_cut should return None, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.insert_top_to_bottom
result = cipher_functions.insert_top_to_bottom(sample_deck)
assert result is None, \\
\'\'\'insert_top_to_bottom should return None, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.get_card_at_top_index
result = cipher_functions.get_card_at_top_index(sample_deck)
assert isinstance(result, int), \\
\'\'\'get_card_at_top_index should return an int, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.get_next_keystream_value
result = cipher_functions.get_next_keystream_value(sample_deck)
assert isinstance(result, int), \\
\'\'\'get_next_keystream_value should return an int, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.process_messages
result = cipher_functions.process_messages(sample_deck, [\'A\', \'B\', \'C\'], \'d\')
assert isinstance(result, list), \\
\'\'\'process_messages should return a list, but returned {0}\'\'\' \\
.format(type(result))
for item in result:
assert isinstance(item, str), \\
\'\'\'process_messages should return a list of str, but returned a list of {0}\'\'\'\\
.format(type(item))

# Type check cipher_functions.read_messages
result = cipher_functions.read_messages(open(\'secret1.txt\'))
assert isinstance(result, list), \\
\'\'\'read_messages should return a list, but returned {0}\'\'\' \\
.format(type(result))
for item in result:
assert isinstance(item, str), \\
\'\'\'read_messages should return a list of str, but returned a list of {0}\'\'\'\\
.format(type(item))

# Type check cipher_functions.is_valid_deck
result = cipher_functions.is_valid_deck([1, 2, 3])
assert isinstance(result, bool), \\
\'\'\'is_valid_deck should return a bool, but returned {0}\'\'\' \\
.format(type(result))

# Type check cipher_functions.read_deck
result = cipher_functions.read_deck(open(\'deck1.txt\'))
assert isinstance(result, list), \\
\'\'\'read_deck should return a list, but returned {0}\'\'\' \\
.format(type(result))
for item in result:
assert isinstance(item, int), \\
\'\'\'read_deck should return a list of int, but returned a list of {0}\'\'\'\\
.format(type(item))

our_print(\"\"\"

Yippee! The type checker program completed without error.\"\"\")