Encryption

Goal

By the end of today, you should:

1. understand the terminology used when talking about encryption, decryption, and cryptography

2. understand encryption systems that use private keys and public keys

3. use public key encryption for your own communication

4. be informed of the different uses of private and public key cryptography

Encryption Recap

Foundation

• What makes general-purpose encryption possible is that everything can be represented using bits. This is crucially important.
• Encryption just works on the bits; it doesn't care whether the bits are text, images, sound, movies, or anything else

Kinds of Encryption:

• Symmetric or private key encryption. The idea is relatively intuitive, even if the implementations are complex. Examples:
  • Caesar,
  • Vigenere,
  • Enigma

  The weakness of private key encryption is the key distribution problem:

  How do you securely transmit the secret key to your interlocutor so that you can securely communicate with them?

• Public key or asymmetric encryption. The idea is revolutionary.
  • Solves the key distribution problem
  • How do you prove who you are without giving away your identity? Solved!
  • Allows for digital signatures, which is amazing:

    How can you sign a document without allowing others to forge your signature or to copy/paste your signature onto another document? Solved!

Communication using Symmetric Encryption

• Alice and Bob somehow share a secret key, K, that Eve does not
• Alice composes a message, M, to Bob. She encrypts it with the key. She sends E_K(M) to Bob.
• Bob decrypts it with K by computing D_K(E_K(M)) = M and reads the message.
• He can reply the same way.

Communication using Public Key Encryption

• Alice creates a key pair (P,S). They are inverses: S can decrypt what P encrypts (and vice versa).
• Alice sends Bob her public key, P. She can send a copy to Eve, too.
• Bob composes a message, M to Alice. He encrypts it with P. He sends E_P(M) to Alice.
• Alice decrypts it with the secret key, computing D_S(E_P(M)) = M and reads the message.

The trick is to come up with algorithms and key pairs where knowing P doesn't help Eve find S.

One such trick is factoring, which is the basis of the RSA (Rivest-Shamir-Adelman method). If P is the product of two very large prime numbers, and S is related to those prime factors, Eve can only find S by factoring P.

Digital Signatures

First, digital signatures have nothing to do with privacy and security. Just the opposite. You may want to prove to the world that you signed something. Don't confuse these.

• Alice wants to sign a public message. She already has a public key pair and everyone has P.
• She composes the message to be signed, M.
• She posts M and E_S(M). That is, she posts the message and its encryption using her secret key.
• Anyone can compute D_P(E_S(M)) and check that it matches M.
• Since only Alice could have created such an encrypted form of that message, it must have been signed by Alice.

The same idea can be used for Alice to prove her identity! All she has to do is sign a message and anyone can verify that the message was signed by her.

Message Digests

Because digital signatures take significant computing time, in practice Alice doesn't sign M, but rather a message digest. A message digest algorithm puts M through a kind of deterministic cuisinart that reduces it to just a small number of bits, say 128 or 256. However, the digest is (essentially) unique, like fingerprints.

Just as your fingerprint is much smaller than you, but just as unique as you are, message digests are smaller but uniquely identify a message.

Quiz Question Nr. 1

Encryption is:

1. information that cannot be read without special information

2. the process of converting plaintext into ciphertext

3. the process of converting ciphertext into plaintext

4. the process of cracking the code with the use of a computer program

Quiz Question Nr. 2

Which of the following codes cannot be used in creating a cipher?

1. The Caesar Code

2. The Vigenere Code

3. The ASCII Code

4. The Enigma Code

Quiz Question Nr. 3

Assuming a Caesar code with rotation 10 and the use of the whole ASCII set of 128 characters for typing a message, which of the following numbers will represent the letter lowercase z (its ASCII is 122) in the ciphertext?

1. 2

2. 4

3. 16

4. 132

Do you see any problem with the setup described in Quiz Question Nr. 3?

Quiz Question Nr. 4

Which of the following statements about breaking the Caesar Code is TRUE?

1. It can be broken only if we figure out the rotation amount.

2. It can be broken only with the help of a computer to execute many trial-and-error runs.

3. It can be broken with the help of ASCII encoding and the modulo operator.

4. It can be broken with the help of statistical functions.

Quiz Question Nr. 5

The Vigenere Cipher would work better if:

1. the codeword is short

2. the codeword is long

3. many codewords are used for every message

4. the codeword has a predefined, fixed length

Quiz Question Nr. 6

Systems that use private keys are unbreakable.

1. True.

2. False.

3. Only the ones that don't use polyalphabetic ciphers.

Quiz Question Nr. 7

Which of the following statements is TRUE?

1. Public key encryption is insecure because it needs two keys.

2. Public key encryption is secure because it needs two keys.

3. Public key encryption is insecure because everyone knows your public key.

4. Public key encryption is secure because no one else knows your private key.

Task 1: Play the RSA game with a friend

Instructions can be found here.

For simplicity, I may just demo this on a single machine, but you can test that I'm not cheating by doing the exercise.

Quiz Question Nr. 8

Public key encryption is useful because:

1. it is used by people who want to keep their communication secret from the government

2. it is used by websites such as Google, Facebook, Tumblr, etc.

3. it is used for financial transactions on the web

4. it is used by users who value private communication

But, of course, the most important thing it does is solve the key distribution problem.

Quiz Question Nr. 9

Which of the following is TRUE:

1. the public key encrypts a message that is decrypted by the private key

2. the private key encrypts a message that is decrypted by the public key

3. both A and B

4. neither A nor B

Quiz Question Nr. 10

Which of the following is TRUE about message digests:

1. it is infeasible to find two different messages with the same digest

2. it is infeasible to modify a message without changing the digest

3. it is infeasible to recreate a message knowing its digest

4. it is easy to compute the digest for any given message

Task 2: Practice Digital Signatures with a friend

Instructions can be found here.

Task 3: Write a Caesar encryption function

The purpose of the following is to make encryption less magical by implementing a simple cipher.

• Implement a function, caesar, taking two arguments, some plaintext (a string) and a rotation amount (an integer).
• It should iterate through the string, converting each character and constructing another string containing the ciphertext.
• To get the Unicode value for a character at position i in a string, use the charCodeAt method.
• To convert a Unicode value into a character, use the fromCharCode method on the String object.
• You may assume that the string contains only ASCII characters.

Summary

We hope that after these activities you can:

• understand how encryption and decryption work
• undertand the difference between private and publick key cryptography
• the uses of private and public key cryptography

Solutions

Will be posted later, visit again after .

function caesar(plaintext, rotAmount) {
   ciphertext = "";
   for( i = 0; i < plaintext.length; i++ ) {
      var ch = plaintext.charCodeAt(i); // the Unicode/ASCII value
      var enc = (ch+rotAmount)%128;     // Unicode/ASCII value of encrypted
      ciphertext += String.fromCharCode(enc);
   }
   return ciphertext;                   
}