Big Data and Privacy - Lesson 8: Encryption with Keys and Passwords
Overview
In this lesson, students learn about the relationship between cryptographic keys
and passwords. Students explore the Vigenere cipher with a widget to examine how a cryptographic
"key" can be used to encrypt and decrypt a message. Then, students use a tool that shows them about
how long it would take to crack a given password using a standard desktop computer. Students
experiment with what makes a good password and answer questions about the "human components" of
cybersecurity.
Vocabulary
Encryption algorithm: some method of doing encryption
Encryption key: a specific input that dictates how to apply the method and can also be used to decrypt the message
For example, the Caesar Cipher is an encryption algorithm that involves shifting the alphabet; the amount of alphabetic shift used to encode the message is the key
Vigenere cipher (Vee-zha-nair): a method of encrypting
text by applying a series of Caesar ciphers based on the letters of a keyword.
Computationally Hard: a "hard" problem for a computer
is one in which it cannot arrive at a solution in a reasonable amount of time.
Goals
Students will be able to:
Explain the relationship between cryptographic keys and passwords
Explain in broad terms what makes a key difficult to "crack"
Reason about strong vs. weak passwords using a tool that shows password strength
Understand that exponential growth is related to an encryption algorithm's strength
Explain how and why the Vigenere cipher is a stronger form of encryption than plain substitution
Explain properties that make for a good key when using the Vigenere Cipher
Purpose
Cryptography and encryption are important and far-reaching fields within computer
science. This lesson begins to get students' feet wet with the human side of cybersecurity: choosing
good passwords through an exploration of the classic Vigenere Cipher. We also learn that the
Vigenere cipher is actually susceptible to frequency analysis (though at first glance it is not)
and in subsequent lessons we will learn better methods that are used today. Strong encryption techniques
are typically publicly known algorithms, but have mathematical properties which ensure that the
original message cannot easily be retrieved. These techniques typically feature a secret "key" or
piece of information that is used when encrypting the message. While the algorithm can be publicly
known, the secret key is not.
The art of encryption is coming up with an algorithm that 1) makes
the message undecipherable without the key and 2) is such that the key should only be discoverable
through an exhaustive search of all possible keys, rather than through some other analytical
technique. In this lesson we focus on making a good key, while in subsequent lessons we learn more
about problems and algorithms that are computationally hard. Guessing a random sequence of 200
characters, for example, is computationally hard, because there is no known way to approach the
problem besides trying the trillions and trillions of possible character combinations.
Discussion: Are there ethical reasons to try to crack secret codes?
There are situations in which cracking a code is ethical and important.
Give students a few minutes to write down a response and discuss with a neighbor. Have students quickly share out reasons they came up with. There are a lot of different reasons that a person may want to crack a code. Some of them are more ethical (legal) than others.
Discussion: If random substitution is an algorithm for encryption, what is the key to a random subsitution cipher?
Answer: The key is the actual letter-to-letter mapping that was used to encode the message - it can also be used to decrypt.
Discussion: The Importance of a Good Key
Good
encryption algorithms are publicly known, but use secret keys as an input to the algorithm. The
task of cracking the encryption becomes not guessing the method but guessing the key. We want
guessing the key to be computationally hard. This relates to the passwords you choose to use on a
daily basis. Encryption algorithms are evaluated based upon the amount of time it would take a
computer to crack the key. The Vigenere cipher cannot be cracked using frequency analysis (at first
glance); it requires a "brute force" strategy of trying every combination.
Activity 1: Vigenere Cipher Widget
Hand out the "Exploring the Vigenere Widget" resource and have students
open the "Vigenere Encryption Widget" and "Vigenere Decryption Widget." Have students work through the activities. They will encrypt and decrypt a message with the Vigenere widgets.
The Vigenere Cipher Explanation
The Vigenere Cipher is similar to the Caesar Cipher we used in the previous lesson. However,
the substitution offset changes depending on the current character of the key. For example, consider using
the message "TEST" with a secret key of "KEY" and think through the following
steps.
The first character of the key is "K," which is the
eleventh letter of the alphabet, so our offset is 10 (since A gives a starting offset of 0).
Shifting the first character of our message, "T," 10 places gives us the
character "C" (note that underscores are considered a 27th "letter" of the alphabet in our Vigenere Cipher).
The second character of the key is "E," which is the
fifth letter of the alphabet, so our offset is 4. Shifting the second character of
our message, "E," 4 places gives us the character "I."
The third character of the key is "Y," which is the
twenty-fifth letter of the alphabet, so our offset is 24. Shifting the third character of
our message, "S," 24 places gives us the character "P."
There is no fourth character of our key, so we instead return to the first
character of the key, "K," which is the
eleventh letter of the alphabet, so our offset is 10. Shifting the fourth character of
our message, "T," 10 places gives us the character "C."
Now that we're done encrypting the original message, we simply need to
add the new characters together to get the ciphertext of "CIPC."
The process of decryption for a Vigenere Cipher is very similar to its process
of encryption. The only difference is that the shifting is done in the other direction; for example,
with a ciphertext character of "C" and a key character of "K," the deciphered character is obtained by a shift of -10, giving us "T."
Discussion: From what you've learned what are the properties of the Vigenère Cipher that make it harder to crack? In other words, if you had to crack a Vigenère cipher what would you do?
Some of the key points for discussion include:
Vigenère is strong because when reviewing the cipher text there are no discerable patterns assuming a good key was chosen.
Because the ciphertext is resistant to analysis it leaves us simply having to guess what the key is.
Even if we know the length of the key we might still have to try every possible letter combination which is a prohibitively large number of possiblities.
Activity 2: Keys and Passwords
Remind the students that:
We know that a good encryption algorithm reduces the problem of cracking it to simply guessing the key.
We want the key to be Computationally Hard to guess - in other words, hard for a computer to guess.
Computationally Hard typically means that arriving at the solution would take a computer a prohibitively long time - as in: centuries or eons.
In terms of cracking encryption, that means that the number of possible keys must be so large, that even a computer trying billions of possible keys per second is unlikely to arrive at the correct key in a reasonable amount of time.
Nowadays when you use a password for a website or device, your password is used as a cryptographic key. So, choosing a good password is meaningful because we want the key to be hard for a computer to guess.
Cryptographic Keys and Your Passwords: If you have ever joined a website where you
had to create an account to login, you also had to create a password. That password is used as a
key to do a variety of things at that site, but mostly it's used to authenticate (prove) who you
are. Open the "How Secure is my Password?" resource. Test some passwords out. Try answering
the questions in the "Keys and Passwords" worksheet.
Ask the students to try the following:
Try typing common words from the dictionary or well-known names like "apple" or "chicago"
Try typing something that's over 16 characters
Try a string of 4 random words together, like AppleChicagoBalletTree
Type a 0, then keep typing 0s and watch what happens to the statistics (actually, you might want to just hold 0 down for a while)
Watch the following video as a class, and have students answer the following questions during or after the video.
What is the difference is between "cracking" a code and "decrypting" a message?
Knowing what you know now about frequency analysis,
would you feel comfortable sending your password over the Internet using a substitution cipher?
Why or why not.
Using the Vigenere Cipher, does the length of the key
matter? For example, if one key is length 5 and another is 20, does one produce a "better" encrypted message than the other, or is it basically the same? Explain your reasoning.
Why is the Vigenere Cipher hard to crack?
Wrap Up
Before the Vigenere cipher was cracked, many governments openly used it.
That is, they made no secret about the fact that they were using the Vigenere cipher - it was
publicly known. In the modern day, it remains the case that most encryption techniques are
publicly known.
Prompt: Why might it actually be a good thing that encryption algorithms are freely shared, so that anyone who wishes can try to crack them?
Possible responses include:
If the security of an encryption technique relies solely on the method remaining a secret, it actually may not be that secure.
Ideally, a method will be so secure that even if you know which technique was used, it is difficult or impossible to crack the message.
By making encryption techniques public, we open them up to being tested by anyone who wishes to ensure there are no clever ways of cracking the encryption.
Q1: (Choose two.) Why is the Vigenere Cipher hard to crack?
A.) One cannot solve using frequency analysis directly.
B.) Long keys create exponential growth possibilities.
C.) The key is always secret to both the sender and receiver of the message.
D.) A Vigenere cipher relies upon an "alphabet shift" algorithm.
Q2: What problems exist with encryption schemes such as the Vigenere Cipher, even when strong encryption keys are used?
Q3: Why are computers better than humans at breaking encryptions such as the Vigenere?
A.) Computers are smarter than humans.
B.) Computers are faster than humans.
C.) The Vigenere was originally designed by a computer.
D.) They are not; humans are better as breaking Vigenere encryptions than computers.
Q4: Which makes for a password that is harder to crack?
A.) A word from the dictionary
B.) 8 random characters that include numbers and punctuation
C.) A 16-character password that is all letters of the alphabet
D.) A 32-character password that is all letters of the alphabet
E.) A 150-character password that is all the same character
Q5: Companies and organizations commonly require users to change their passwords frequently. Websites have password length and complexity requirements. Is it better to change your password frequently or to have a longer password? What level of security is appropriate to require of end users? Does this change, depending on the context (for example, employee or customer)?
Extended Learning
The students can learn more about different kinds of ciphers on Crypto Corner.
Assign each student a type of cipher. Students should then research the cipher, including information on its algorithm, its history, and what they would have to do to crack the cipher. They should present an example, and describe the process they follow in cracking the code.
The opening pages of Blown to Bits, Chapter 5, discuss a move the government made to try to control encryption in the aftermath of the terrorist attacks of September 11, 2001, but then dropped. Additionally, during the 1990s, the US Government was pressuring the computer industry to be allowed to have a "back door" to decryption. Why do you think they stopped urging for this?
Possible Answer: This would weaken the public's trust in the Internet as an e-commerce vehicle. Any back door could probably be exploited by others. The government believed they could eventually break cryptography without a back door.
Encryption is clearly regarded as essential to Internet commercial activity. That it will not be outlawed seems like a settled matter. But conversely, should it be required by government regulation? What about for other non-web media, such as mobile phone traffic and television?
Have students find videos demonstrating these or other advanced encryption methods; ask them to describe each algorithm and what causes it to be "hard."
Standards Alignment
Computer Science Principles: 2.3.2 (A)
Computer Science Principles: 3.1.1 (A)
Computer Science Principles: 4.2.1 (A, B, C, D)
Computer Science Principles: 6.3.1 (C, H, I, J, K)