SOURCE Lesson Plans Detail

Cracking Codes

Topic Cryptography Brown Science Prep Priya Patel Undergraduate students

Overview / Purpose / Essential Questions

In what ways can Alice send a message to Bob without someone else knowing what she says?

Performance / Lesson Objective(s)

To learn a few methods of encoding (scytale, ciphers)

To briefly introduce modular arithmetic

To see how modular arithmetic applies to other coding methods

Lesson Materials

4-5 cylinders of uniform size (soda cans or thinner)

about a yard of ribbon for each group

A prize at the end of the lesson

Lesson Motivation

Sending secret messages has been a part of war strategy since ancient times. Encoding things has gotten more difficult as computers have become more powerful, and certain systems no longer are useful for encoding.

Lesson Activities

A code-based scavenger hunt at the end, where each group will get 3 encoded messages that they must decode in order to proceed.

Procedure

Scytale-

One of the oldest coding methods is called a “scytale.”

It looks like just a series of letters, but generals in Roman and Greek armies would wrap it around their standards to read what it said.

-Wrap the ribbon around the soda can and read what it says.

The scytale can also be decrypted mathematically. Say you have a string of letters. Instead of wrapping the string around a can or something, you can arrange the letters into a specific number of rows and decode the message. Example :

To decode, try arranging the letters into three columns, starting from the leftmost column and working your across.  *this is the same one as the can, so I will determine it. *

The trick to decoding a scytale is finding the right sized “stick.” However, it can just as easily be decoded by figuring out how many columns to divide the message into.

Try this one.

I U A A A T M L M A L A C Y N T B.

Ciphers

Another way to encode things is via ciphers. A simple cipher is a translation of the alphabet. Example:

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

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

The second row is the code alphabet- this is what would be given. The job is to determine what the bottom row letters correspond to. In a simple cipher, there is no rearranging of the alphabet,  just a shifting.

___      ___  __  __  __            ___  __           __  __  __  __         __  __  __  __

M         A     I    R     X           X    S            Q   E   X    L              G  E   Q    T

If the top row were not given, then one would have to figure out how to arrange the alphabet. You could do this by seeing that M is a word, and in English, the only words that are single letters are A and I. That would allow you to know that M is either A or I, arrange the alphabet and guess and check. This can also be done with numbers, but instead of writing out the letters a-z on the top, there could be numbers 1-26, with 1=a, 26=z, etc.

A different kind of cipher would be more complex, in which letters could randomly be assigned to other letters, and the order of the alphabet would not be maintained. Example:

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

o

y

x

w

v

u

b

a

p

z

t

s

d

c

j

f

q

l

e

k

i

m

h

n

r

g

The same message as before would be encoded as

__      __ __ ___ ___            ___ ___           ___ ___ ___ ___         ___ ___ ___ __

P          H  V    C   K                 K     J                D    O   K     A           X    O   D     F

These are much harder to decrypt, because with a simple cipher, if you know what one letter is, you have the entire code, but for this cipher, you need to individually determine each letter (especially hard with a short message).

This is sometimes done by analyzing frequency. In English, E, R, S, T and A are some of the most common letters used (E being the most common). So if you have a long encoded message that has a lot of G’s, then you can infer that G=E.  The rest, you need to figure out based on your knowledge of what letters go together (C and K are commonly found together), and what letters can show up in pairs (OO, LL, SS, EE).

Mod

Introduction to Modular Arithmetic- Modular arithmetic is integral in many systems of coding.

Think of a clock. If it’s 2, and I want to know what time it will be in 14 hours, I have just performed arithmetic in mod 12.

P mod Q is equal to the remainder of Q divided into P.

So in 14 hours, if it is two, I add 14 to 2 and perform

16 mod 12 = 4.

What would 145 mod 13 be?

There is an “unbreakable” code that combines ciphers, randomness and modular arithmetic, called the “one time pad.”

The one time pad is a series of random letters that both Alice and Bob have. Each letter is assigned a number (usually, A=0, B=1..etc). If the message they want to send is “HELLO,” the numbers for that would be “7- 4- 11- 11- 14”

If the first 5 letters on the one time pad are AFRTP, the numbers would be “0-5-17- 19-15-” To encode the message, Alice would simply add the numbers from her plaintext to her cipher. if the total is over 26, one would use mod26 to figure out how to encode it. She’d get  23-12-2-10-11, or (X M C K L) and then would transfer those numbers into letters (EQNVZ).

Bob would merely do the same thing, changing the encrypted text to numbers, and would subtract the values from his identical pad, (X M C K L, or 23-12-2-10-11) and subtract XMCKL from EQNVZ to get “HELLO”

*Do the subtraction.

For this code to work, the one-time pads must be secure and random, and once they are used, they must be destroyed. The KGB used them for a time, and wrote their ciphers on flash paper, which could combust.

RSA

The problem with most systems of encoding and decoding is that if Eve is always listening, then Alice can’t tell Bob how to decode it, meaning that if she sends him her key, Eve has it too. (My solution at math camp was to just kill Eve, but I don’t think it works that way). The answer to this- Bob and Alice each have their own keys.  Here’s how it works-

Play video – start at 2:26

Wrap up / Conclusion

Scavenger hunt-
Each group will have one scytale, one simple cipher, and one simple cipher with numbers.

EACH Scytale will say something to the effect of - go to the Barus and Holley lobby

(On the lobby table each group will have an envelope with a simple cipher in it)

One  simple cipher will say something like “go down the stairs and to the left”

one will say “go to the barus and holley computer lab”

etc. etc.

These ciphers will all lead to the auditorium, where there will *hopefully* be a cake and each group will have 3-4 letters that they have to decode. *This will force them to keep busy while all the groups must finish. The final message will need to be unscrambled to say

Yay- now eat cake.

Briefly review each type of code in the lobby before leaving.

Pre Assessment Plan

Discuss with students what codes they have heard of and in what contexts.

Post Assessment Plan

Scavenger hunt to test students' understanding of the various codes.

Supplies List

QtyUnitItem
1RollYarn
5EachEmpty film canisters

Alignment Info

Audience(s) High school students Applied Math Math (Common Core) 1.OA.1Use addition and subtraction within 20 to solve word problems involving situations of adding to, taking from, putting together, taking apart, and comparing, with unknowns in all positions, e.g., by using objects, drawings, and equations with a symbol for the unknown number to represent the problem. Hands-on High School 1 05/29/2013 12:55 PM 12/20/2018 11:02 AM