Unit4
Ch. 1
1
2
3
4
5
6
7
8
9
10

Lesson 8: Encryption with Keys and Passwords

Widget

Overview

In this lesson, students learn about the relationship between cryptographic keys and passwords. Students explore the Vigenère 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.

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 Vigenère Cipher. We also learn that the Vigenère cipher is actually susceptible to frequency analysis (though at first glance it is not) and in subsequent lessons we learn that better methods 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.

Agenda

Getting Started (10 mins)

Activity 1 (30 mins)

Activity 2 (20 mins)

Wrap-up (10-15 mins)

Assessment

Extended Learning

View on Code Studio

Objectives

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 Vigenère cipher is a stronger form of encryption than plain substitution.
  • Explain properties that make for a good key when using the Vigenère Cipher.

Preparation

  • Explore the Vigenere Cipher Widget in Code Studio
  • Familiarize yourself with the "howsecureismypassword.net" site.
  • (Optional) Print out worksheets (links in Code Studio)

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Teacher

For the Students

Vocabulary

  • Computationally Hard - a "hard' problem for a computer is one in which it cannot arrive at a solution in a reasonable amount of time.

Support

Lesson Forum

Report a Bug

Differentiation and accommodations for this lesson

Teaching Guide

Getting Started (10 mins)

Discussion Goal

Provide a quick (about 5 minutes) justification for the practice of cracking ciphers, while reviewing relevant vocabulary. At the conclusion of the lesson, students will discuss other reasons we might try to crack a cipher, namely to ensure that it is difficult to do!

Here are some other points that might come out:

  • People in the field of counterterrorism make a living by trying to crack the codes of other nations. Many attribute the success of the Allies in WWII to our ability to crack the Enigma code and uncover the plans of the Germans.
  • Others may try to crack more abstract codes that are not written by humans, searching for patterns within DNA models in order to understand their nature and be able to describe the nature of humanity.
  • It’s useful to try to crack your own codes to see how strong they really are.
  • There are many other reasons related to mathematical exploration, pattern recognition, etc.

Misconception Alert

There’s a common misconception that “cracking” and “decrypting” are interchangeable terms.

  • Decrypting is just using an algorithm to undo the encryption. It's like using a key to unlock a lock. It’s what the sender is expecting the intended recipient to do to recover the original message.
  • Cracking is more like detective work - it's like trying to pick a lock - using various methods to try to figure out what the secret message is without having or knowing the decryption "key" ahead of time.

Remarks

In the previous lesson you saw how relatively easy it was to crack a substitution cipher with a computational tool.

Today we’ll try to crack a different code to see what it’s like. Beforehand, however, we should consider why someone might want to crack a cipher in the first place.

Think - Pair - Share

Prompt:

  • "Are there ethical reasons to try to crack secret codes?"

Give students a few minutes to write down a response and discuss with a neighbor.

Discussion

  • 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.

Encryption: Algorithms v. Keys

Today, we will attempt to crack codes, paying particular attention to the processes and algorithms that we use to do so.

So, before starting today we want to make sure that we distinguish between an encryption algorithm and an encryption key

  • An Encryption algorithm is some method of doing encryption.
  • The Encryption key is a specific input that dictates how to apply the method and can also be used to decrypt the message. Some people might say "What is the key to unlocking this 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
  • When you are cracking the Caesar Cipher you are trying to figure out how much the alphabet was shifted - you are trying to discover the key.

Discussion Goal

Quickly review what a “key” is in a cryptographic method and distinguish it from the Algorithm

Prompt:

  • "If random substitution is an algorithm for encryption, what is the key to a random subsitution cipher?"

    • A: The key is the actual letter-to-letter mapping that was used to encode the message - it can also be used to decrypt.

Content Corner

Perhaps counter-intuitively, publicly known encryption algorithms are often more secure, since they have been exposed to a much more rigorous review by the computer science community. Making an encryption algorithm public allows computer scientists to verify the security of the technique either through mathematical proof, or by trying to crack it themselves.

Transitional Remarks

So, There is a difference between the algorithm (how to execute the encryption and decryption) and key (the secret piece of information).

  • In encryption you should always assume that your 'enemy' knows the encryption algorithm and has access to the same tools that you do.
  • What makes encryption REALLY strong is making it hard to guess or crack the “key,” even if the “enemy” knows the encryption technique you're using.

Today we’ll learn a little more about it and about keys and their relationship to passwords you use every day.

Activity 1 (30 mins)

Explore the Vigenère Cipher Widget

Teaching Tips

  • The Vigenere Cipher Widget is another fun tool to mess around with.
  • The key take-aways for students are:
    • A well-chosen key makes a difference - there are certain keys that don’t produce good results.
    • We’re approaching much stronger encryption because we don’t need to keep the encryption method a secret.
    • For example, if I told my enemy that I encrypted a message with the Vigenère cipher, my enemy would still have to do a virtually impossible amount of work to crack the code.
    • Even if I told my enemy the length of the key I used, as long as that length is sufficiently large, it would still leave my enemy basically randomly guessing the key. (Even for this simplified tool, if the key is 10 letters, then there are 26^10 possible keys, ~141 trillion.)
  • Try to keep students’ focus on the properties and relationships of the keys to the strength of the encryption.

Go to Code Studio

The goals of this activity are:

  • Understand how the Vigenère Cipher Algorithm works
  • Understand why simple frequency analysis doesn’t work against this cipher
  • Figure out what makes for a good v. bad secret key

The activity guide asks students to:

Part 1: Explore the Widget

Students are asked to:

  • Jump into the tool and poke around
  • Figure out what it's doing

The worksheet gives a few directed tasks:

  • Encrypt a few different messages using different secret keys
  • Decrypt a message
  • Find a “bad” secret key
  • Find a “good” secret key
  • Try to decrypt without knowing the key

Part 2: Answer Questions

Students are given space to write answers to these questions.
You can find sample responses in the KEY - Exploring the Vigenere Cipher Widget - Answer Key

  • Describe in your own words what the Vigenère Cipher Algorithm is doing.

  • What makes for a good v. bad secret key using the Vigenère cipher?

  • Compare and Contrast the difference between a substitution cipher (Caesar or Random) and Vigenere, using the message “I think I can I think I can I think I can” to explain why Vigenère is a stronger form of encryption than a substitution cipher.

  • Will frequency analysis work to crack the Vigenère cipher? Why or why not?

  • (paraphrase) Is it easier to crack a message if you know that it was encrypted with the Vigenère Cipher Widget?

  • (paraphrase) Is it easier to crack a message if you know that it was encrypted with the Vigenère Cipher Widget and that the key was 10 characters long?

Recap: Properties of strong encryption

You may wish to review students' responses on the activity guide at this point. Or you can move that to the wrap-up. We'd like to make a few points about encryption before moving to the next activity...

Prompt:

  • "From what you've seen what are the properties of the Vigenere Cipher that make it harder to crack? In other words, if you had to crack a vigenere cipher what would you do?"

Discussion

A few points should come out in discussion:

  • Vigenere is strong because looking at 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.

Content Corner

If you are interested in how the Vigenere cipher can be cracked there are a number of resources out there. See the "Extended Learning" section of the lesson plan for links.

Remarks

  • For a long time, the Vigenère cipher was considered to be an unbreakable cipher and was used by governments to send important messages.
  • But in the 1800s Vigenere was discovered to be susceptible to a modified form of frequency analysis. After that point it was considered insecure.
  • Still the properties of Vigenere that we've found are desirable.

Activity 2 (20 mins)

Computationally Hard Problems -- How good is your password?

Teaching Tip

Don't worry too much about the precise definitions of "computationally hard" and "reasonable time" here. It will be addressed more in the video at the end of this lesson as well as the next lesson.

You should know that the CSP Framework does have a learning objective that relates: 4.2.1 Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]

Introduction

  • 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. How good is your password?...

Go to Code Studio

How Secure is my Password - Code Studio Page

Students should read the text on this page about password security and choice.

Student tasks are listed...

1. Open up password strength checker

Students should open the external website howsecureismypassword.net in a separate tab or window and then try out these things listed:

Teaching Tips

Make sure you leave enough time for the wrap up.

Students may have a lot of questions about passwords and security that you feel like you might not be able to answer. That’s OK!

a) You don’t have to be an expert on this subject

b) The reality is that the world of cybersecurity changes every day

c) Some of the details can get very complicated, even for professionals.

So, encourage the students’ curiosity and perhaps say, “I don’t know, but I bet you could look it up.” Cybersecurity is an enormous topic. If students get interested, they could dedicate their whole life to this field.

2. Test some passwords

Try different passwords to see what the tool tells you:

  • 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.)
  • Try other things that interest you.

3. Answer Questions

Questions are listed in Keys and Passwords - Worksheet:

  • Create a few passwords using 8 lowercase ASCII characters (a-z). What’s the longest amount of time-to-crack you can generate?
  • Using any characters on the keyboard, what’s the longest amount of time-to-crack you can generate with an 8-character password?
  • As you try passwords, what seems to be the single most significant factor in making a password difficult to crack? Why do you think this is?
  • Opinion: Is an 8-character minimum a good password length for websites to require? Give your opinion, yes or no, and explain why you think that.
  • The AP CS Principles framework contains the following statement: Implementing cybersecurity has software, hardware, and human components. Based on what you’ve learned so far, describe at least one way that cybersecurity involves “human components.”

Hopefully you can now appreciate this comic: http://xkcd.com/936/

Wrap-up (10-15 mins)

Discussion Goal

The goal here is to recall that the reason we want to have encrypted transactions is for our own security.

We should feel good about well known strong encryption methods.

We want a world in which anyone can conduct secure transactions on the web; without this possibility, many things would be impossible.

Discuss:

  • Before the Vignere cipher was cracked, many governments openly used it. That is, they made no secret about the fact that they were using the Viginere 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?

    • 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.

Video: Encryption and Public Keys

Wrap up goals

The video re-iterates a number of points that came out in this lesson.

In wrapping-up, make sure students:

Understand the relationship between cryptographic keys and passwords.

  • A Key is an input to an encryption algorithm. A password is basically the same thing.

Understand why using longer passwords makes them harder to guess.

  • Longer passwords increase the number of possible keys making it Computationally hard to guess what the key is.

You should know about this video:

  • 0:00 to 4:11 covers Caesar and Vigenere ciphers and explains why they are hard to crack
  • After 4:11...it explains the difference between encryption that uses symmetric v. asymmetric keys which is related to material in the next lesson and is intended as a preview.
  • The next lesson begins by recalling symmetric v. asymmetric keys and getting into how they work.

Transitional Remarks

We’re circling in on some powerful ideas of how secure communication works on the Internet these days. But we need to learn two more things:

  1. We’ve seen how keys relate to the strength of encryption, but we haven’t seen the other side of it -- how modern encryption algorithms actually work. Vigenère was cracked, so what are we using now? In order to do this, we need to understand what kinds of problems are “hard” for computers to solve.
  2. Right now, the only encryption we know uses a "symmetric key" -- both sender and reciever need to know the secret key, and so they need to meet ahead of time.

But is it possible for you and me to have a secure, private, encrypted exchange without meeting ahead of time and agreeing on a secret password.

The answer is “yes,” and we'll find out how it works in the next lesson.

(Optional) How Not to Get Hacked by Code.org

You may want students read or review this little site put together by Code.org

Assessment

The worksheet contains several questions for assessment. Here are some additional questions (also included on Code Studio):

  1. (Choose two.) Why is the Vigenère 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 Vigenère cipher relies upon an "alphabet shift" algorithm.

  2. What problems exist with encryption schemes such as the Vigenère cipher, even when strong encryption keys are used?

  3. Why are computers better than humans at breaking encryptions such as the Vigenère?

    a) Computers are smarter than humans.

    b) Computers are faster than humans.

    c) The Vigenère was originally designed by a computer.

    d) They are not; humans are better as breaking Vigenère encryptions than computers.

  4. 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. ANSWER: E

  5. 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

  • Go down the rabbit’s hole of encryption at Crypto Corner: http://crypto.interactive-maths.com/

    • 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.

  • Caesar Cipher video from Khan Academy: https://www.khanacademy.org/computing/computer-science/cryptography/crypt/v/caesar-cipher

  • Real world stories of cracking codes:

    • Cracking a code as the key to understanding of ancient culture: http://www.wired.com/2012/11/ff-the-manuscript/all/
    • Cracking the human genome (NOVA Video): http://video.pbs.org/video/1841308959/
    • Nobel prize given for cracking the code of DNA: http://www.nobelprize.org/educational/medicine/gene-code/history.html
    • Navajo Code Talkers http://navajocodetalkers.org/
    • Read this quick overview that Code.org put together about How Not to Get Hacked, which summarizes some basic cybersecurity issues and how to prevent them.
  • Read Blown to Bits (www.bitsbook.com), Chapter 5, Secret Bits, pages 161-165, then answer the following questions:
    • 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? http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all&_r=0 (Teacher notes: 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 seen 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?
  • Vigenère cipher cracker tool on Simon Singh's website. It's a lot of fun and fairly similar to the frequency analysis tool used in class http://www.simonsingh.net/The_Black_Chamber/vigenere_cracking_tool.html
  • Have students find videos demonstrating these or other advanced encryption methods; ask them to describe each algorithm and what causes it to be “hard.”

Optional Lessons

To dive deeper into the notion of computationally hard problems, consider the following 2 optional lessons after this lesson:

View on Code Studio

Encrypt and decrypt a message with the Vigenère cipher

This is an interactive version of the Vigenère cipher that animates the encryption and decryption as it’s happening, given a piece of text to encrypt or decrypt and the key.

Do this

Encrypt a message

Click Step several times, and trace what’s happening. Pay attention to:

  • How the ciphertext is being produced
  • What happens when you get to the last character of the key
  • After you’ve stepped through a few characters click Play to watch the rest animate
  • Hit Restart and play the animation again. You can use the speed slider to speed it up or slow it down

Decrypt a message

Encrypt a message as above, then:

  • Highlight and copy the ciphertext
  • Paste it into the plaintext area. Note: Don’t change the key
  • Change the Encrypt/Decrypt toggle to Decrypt
  • Hit Step a few times, and then Play

You should see the original text emerge.

How hard would it be to crack a message encrypted with this cipher? Does the length of the key make a difference?

View on Code Studio

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.

When you created your password, the site may have presented you with some rules for your password, such as:

  • must be at least 8 characters long
  • must contain at least one number
  • must contain at least one uppercase letter
  • must contain at least one punctuation symbol (e.g. `-=[];',./~!@#$%^&*()_+{}|:"<>?)

Question: Based on what you know about how keys work in cryptography, give a reason for why these rules require:

a) a certain number of characters

b) a mix of letters, numbers, uppercase and symbols?

Try It: How Secure is your password?

1. Open password strength checker

In a separate tab or window:


NOTE: the link to How Secure Is My Password? goes to an old version of the site hosted on web.archive.org. This is intentional.

  • Go to: How Secure Is My Password?

  • Before you type anything: open the Developer Tools in your browser and make sure you can see any network traffic.

  • This website lets you test the strength of various passwords.

  • Should you trust this site? As the website tells you:

This site could be stealing your password...It's not, but it easily could be.
Be careful where you type your password.
  • By opening the developer tools to inspect the traffic, you can make sure that's true. In any event, if you want to be super careful, do not use any real password here.

2. Test some passwords

For everything you try, make sure to:

  • Click "show details."
  • Read the other statistics and facts about the password.

Try different passwords to see what the tool tells you:

  • 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.)
  • Try other things that interest you.

3. Answer Questions...

  • After trying the suggested tasks above, answer the questions provided...

Check with your teacher...

OR

  • Your teacher may have provided different questions or a different worksheet.
View on Code Studio

Student Instructions

What is the difference is between “cracking” a code and “decrypting” a message?

View on Code Studio

Student Instructions

View on Code Studio

Student Instructions

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?

View on Code Studio

Student Instructions

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? Yes or no? Explain your reasoning.

View on Code Studio

Teaching Tip

Answers:

  • One cannot solve using frequency analysis directly.
  • Long keys create exponential growth possibilities.

Note that a Caesar cipher relies upon an alphabetic shift

Student Instructions

Standards Alignment

View full course alignment

CSTA K-12 Computer Science Standards (2011)

CPP - Computing Practice & Programming
  • CPP.L3A:9 - Explain the principles of security by examining encryption, cryptography, and authentication techniques.
  • CPP.L3B:5 - Deploy principles of security by implementing encryption and authentication strategies.
CT - Computational Thinking
  • CT.L3B:2 - Explain the value of heuristic algorithms to approximate solutions for intractable problems.
  • CT.L3B:4 - Evaluate algorithms by their efficiency, correctness, and clarity.
  • CT.L3B:5 - Use data analysis to enhance understanding of complex natural and human systems.

Computer Science Principles

2.3 - Models and simulations use abstraction to generate new understanding and knowledge.
2.3.2 - Use models and simulations to formulate, refine, and test hypotheses. [P3]
  • 2.3.2A - Models and simulations facilitate the formulation and refinement of hypotheses related to the objects or phenomena under consideration.
3.1 - People use computer programs to process information to gain insight and knowledge.
3.1.1 - Use computers to process information, find patterns, and test hypotheses about digitally processed information to gain insight and knowledge. [P4]
  • 3.1.1A - Computers are used in an iterative and interactive way when processing digital information to gain insight and knowledge.
4.2 - Algorithms can solve many but not all computational problems.
4.2.1 - Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
  • 4.2.1A - Many problems can be solved in a reasonable time.
  • 4.2.1B - Reasonable time means that as the input size grows, the number of steps the algorithm takes is proportional to the square (or cube, fourth power, fifth power, etc.) of the size of the input.
  • 4.2.1C - Some problems cannot be solved in a reasonable time, even for small input sizes.
  • 4.2.1D - Some problems can be solved but not in a reasonable time. In these cases, heuristic approaches may be helpful to find solutions in reasonable time.
6.3 - Cybersecurity is an important concern for the Internet and the systems built on it.
6.3.1 - Identify existing cybersecurity concerns and potential options to address these issues with the Internet and the systems built on it. [P1]
  • 6.3.1C - Implementing cybersecurity has software, hardware, and human components.
  • 6.3.1H - Cryptography is essential to many models of cybersecurity.
  • 6.3.1I - Cryptography has a mathematical foundation.
  • 6.3.1J - Open standards help ensure cryptography is secure.
  • 6.3.1K - Symmetric encryption is a method of encryption involving one key for encryption and decryption.

CSTA K-12 Computer Science Standards (2017)

NI - Networks & the Internet
  • 2-NI-06 - Apply multiple methods of encryption to model the secure transmission of information.
  • 3A-NI-07 - Compare various security measures, considering tradeoffs between the usability and security of a computer system.
  • 3B-NI-04 - Compare ways software developers protect devices and information from unauthorized access.