AP Computer Science Principles

About AP Computer Science Principles  |  All posts  |  Post list

Google Classroom  |   App Inventor

Cryptography - Securing the Internet

This lesson focuses on the modern cryptographic systems that are used to secure the Internet. It describes how the Diffie-Hellman algorithm solves the key exchange problem, a crucial step in making the Internet possible. Without the ability to securely exchange secret keys, it would be impossible to conduct financial transactions over a network. As we shall see, it is the intractability of solving a certain one-way math function that makes Diffie-Hellman possible.

It also describes the Rivest-Shamir-Adleman (RSA) public key algorithm. In this case we'll see that it's the intractability of the prime factorization problem that makes RSA possible.

The lesson concludes by describing the handshake that takes place between your browser and a web server whenever a secure transaction is involved. Secure transactions include accessing a Web page through the HTTPs protocol. Or exchanging information through the Internet's Secure Socket Level (SSL). As we will see both symmetric and public key algorithms are used in this process.

The lesson will also describe the Internet's trust model -- i.e., a model that uses digital certificates to ensure that your browser can trust Google or Amazon when their servers share their public keys with the browsers.

The system that guarantees the security of the Internet is an amazingly complex and fascinating system that pulls together many of the concepts we've been studying in this course.

Part 1: Diffie-Hellman Key Exchange (VIDEO)

This video includes video clips from Brit Cruise's excellent explanation of the Diffie-Hellman key exchange algorithm. You may wish to pause the video where suggested to try the hands-on color-mixing demo below.

Activity: Diffie-Hellman Exchange Secret Color Demo

This Web app provides an implementation of the color-mixing analogy presented in the Brit Cruise video. You can select a shared public color and then your own private (secret) color. When you click "Show Shared Secret!" the app will display the secret color that it shares with you.

The app will also give you an opportunity to use the hexadecimal number system that we talked back in Unit 2. Colors are represented in an RGB system -- i.e., by mixing Red (R), Green (G), and Blue (B) primary colors in varying quantities. The mixtures are represented by 6-digit hexadecimal numbers, where the first two digits represent the amount of red, the next two represent the amount of green, and the last two represent the about of blue. For example, pure red is FF0000. In this case FF is the maximum amount of red (equal to 255 in decimal). The hex number 00FF00 would represent pure green. If you mix lots of blue and green, 00FFFF, you should get aqua. If you mix lots of red with some green, FF8500, you should get orange.

Give it a try. Just your hex numbers into the text boxes and click the "Show Shared Secret!" button.

Part 2: RSA and HTTPs (VIDEO)


Answers the following questions on Google Classroom:

  1. Explain in your own words how public key encryption is not symmetric.
  2. Cryptography relies on open standards - protocol or standard that is publicly available. Why are open standards necessary?

Cryptography Basics

Cryptography means secret writing. It is the art and science of sending secret messages and it has been used by generals and governments and everyday people practically since the invention of written language.

As we will see in the next lesson, modern cryptographic techniques are essential to guaranteeing the security of our transactions on the Internet. Cryptography plays a role whenever you make an online purchase at Amazon or provide your password to Google. If we couldn't rely on those transactions being secure -- i.e., being encrypted using some cryptographic algorithm -- we really wouldn't have the Internet as we know it today.

This lesson focuses on some of the classical ciphers, going all the way back to one of the first ciphers, the Caesar cipher, which Julius Caesar used in 34 B.C. Like the other ciphers we study in this lesson, it is what is known as a symmetric cipher, which means that the same key is used both for encrypting and decrypting messages. As we will also see, all ciphers consist of two parts, the key and their algorithm. And it is the key, not the algorithm, that allows the cipher to create secret messages. In fact, in modern cryptography the algorithms are all based on open standards that are created by teams of experts, discussed openly and adopted and maintained by standards organizations.

So, let's take a look at some of the classical ciphers and some of the basic principles of cryptography. There are several hands-on activities in this lesson, where you'll have a chance to practice encrypting and decrypting messages and analyzing ciphers.

Part 1: Caesar Cipher (VIDEO)

Activity: Caesar Cipher

  1. By Hand: Use the Caesar cipher to encrypt your name. Use a key of 3 on the first try. Then use the script above to check your answer.
  2. Brute force search. A brute force search for a Caesar key would be to test every possible key. How many keys would you have to test?

    Use brute force search to crack the following message. What is the key?


Part 2: Simple Substitution Cipher (VIDEO)

Activity: Simple Substitution Cipher

  1. By Hand: Use the Simple Substitution cipher to encrypt your name. Choose your own keyword to create a cipher alphabet. Then use the script to check your result.
  2. Decrypt: The following word, SIRTQSMTCKJ, was encrypted with the keyword simple. Can you decrypt it?
  3. Brute force attack. How many keys (arrangements of the alphabet) would you have to try to perform a brute force attack?

Part 3: Frequency Analysis (VIDEO)

Activity: Frequency Analysis

  1. Frequency analysis: One of the following messages was encrypted using a substitution cipher and the other with a transposition cipher. Can you identify which is which? Paste the messages into the frequency analyzer tool (above) and observe their frequency histograms?.

    Text 1.
    nybfx ymjgj xytky nrjxn ybfxy mjbtw xytky nrjx nybfx ymjfl jtkbn xitrn ybfxy mjflj
    tkktt qnxms jxxn ybfxy mjjut hmtkg jqnjk nybfx ymjju thmtk nshwj izqny dnyb fxymj
    xjfxt stkqn lmyny bfxym jxjfx tstki fwpsj xxny bfxym jxuwn sltkm tujny bfxym jbnsy
    jwtki jxufn wbjm fijaj wdymn slgjk twjzx bjmfi stymn slgjk twjzx bjbj wjfqq ltnsl inwjh
    yytmj fajsb jbjwj fqqlt nslin wjhy ymjty mjwbf dnsxm twyym jujwn tibfx xtkfw qnpjy
    mjuwj xjsy ujwnt iymfy xtrjt knyxs tnxnj xyfzy mtwny njxns xnxyj itsny xgjn slwjh jnaji
    ktwlt titwk twjan qnsym jxzuj wqfyn ajijl wjjt khtru fwnxt stsqd

    Text 2.
    ttbti swhot istta osmwh gflhs tsecf liaho ondia henit ahena nwtpnf ewtie fpree rhbou
    hnhbo uerli deovw rlode oeasr hrdsa itrei ttein ittie ntote gceoo rrits etegc psoya hsfmt
    sesfm iahew dtseo oiewh pheet tecir uytss sohts ssoks isero oisen oeawa vtnee watne
    ewagn rtenw egnit htwih tpiao reeet eoaoo sieuo tiiei ieidg dfvih pliee omrol setet wtese
    iotao siaoo fwphe lwtof wtofs tsipt wtsid egfed gfweo gtaea grehn oeofl psrdm fssri
    sdbnv foone avefi nweoi arowg fiaef nsteb isefc tieag ieare ahgha hrdhy irsoi rseli ceeli
    ctryt ewskh nphst oahss nsrer oelur droan

Part 4: Vigenere Cipher (VIDEO)

Activity: Vigenere Cipher

  1. By Hand: Use the Vigenere cipher to encrypt your name. Choose your own keyword.
  2. Decrypt the following message, which was encrypted using Vigenere cipher with the keyword zebras.

  3. Frequency analysis: Use the Frequency Analyzer tool (above) to count the letter frequencies in the following text, which is the same text that was encrypted in an earlier exercise. In this case it was encrypted using Vigenere cipher. What differences do you observe from the histograms you used in the previous exercise.
    sabjt zdffj tgexj dekhx xrslg ixfrk ssgki edwj kwsrx ivayd sgnik csnzt ozwuy esfip wfgnp
    jjhfd wtzt ozwuy ewosd yoxai mzexh xxrsl gifgo ugsgz nuqie llasc jkws rxivs wzwpe
    oxhki kilve tkhwr ibjof njbik fdwt ztozw uyeko vjegg elpge asabj tzdaj etwqs gueko ejiw
    wgeev vwqcu yifff fwojd ytnez zhoft zhrhs exnvf lsod afies kphfi ffhji eusxp vandr xvwwq
    ibcly nmoxd aqidk tzds uyejv ezznk gsskt zdtfi igcab jsgee scicd xivpj dwfet hdvj fdlge
    ujoed sgztk msjji wrxbl tznvj kiwrm ojiks iefna swcv iffvf teaui ewojf spuoj essvv akmok
    hwryq vrdzx jmevd ksve gegpd psqmt fngmp z

Part 5: Perfect Secrecy and the Key Exchange Problem (VIDEO)


Reflection: Answers the following questions on Google Classroom:

  1. Explain briefly how the following substitution ciphers can be broken: Caesar cipher, Simple substitution cipher, Vigenere cipher.
  2. Define symmetric encryption.

All posts  |  Post list