Week 5

Question 1

What is cryptography?

Answer 1

The study of how codes and ciphers can be used to protect the confidentiality of secret data.

Question 2

What is a codebook?

Answer 2

Allows you to map from code to characters to decipher a message.

Question 3

What are ciphers?

Answer 3

Algorithms that take as input a key and your message, and scramble the message using the key so that other parties that have access to the key can decipher it.

Question 4

What is a modern day use of cryptography that is not for encrypting passwords?

Answer 4

It is used to create digital signatures with the prevention of forgery.

It’s also the basis for cryptocurrency where it prevents the double spending of currency.

Question 5

What is Homomorphic Encryption?

Answer 5

It’s when you take some input and encrypt it, and you can send the cipher texts to a cloud provider like AWS and you can ask them to compute some function on the input (ML, matrix multiplication, etc.), and it will output the encrypted output.

It allows the cloud to handle computations without ever learning what the inputs are. The only thing it knows is which functions were used.

Question 6

What is Verifiable Computation?

Answer 6

This is where we have a function f with input x which outputs y and confirms that y = f(x). This is for weak computers like a mobile device that can’t compute function f. You basically are using a cloud to do the computation, and it returns the proof to you. How do we know “y” was calculated correctly?

The only way to check is if you locally compute f(x) but we already said that’s too expensive to do. BUT, cryptography allows the cloud provider to not only give you y, but also a cryptographic proof that y = f(x). Verifying this proof is much more efficient than computing f(x) yourself, so this works.

Question 7

What is Secure Multiparty Communication?

Answer 7

It lets two parties compute joint results without either knowing the other’s inputs.

Question 8

What do we need for cryptography?

Answer 8

• Formal definitions of the property/guarantee
• Mathematically precise threat models
• Construction of a cryptosystem
• Mathematical proof showing correctness and security of construction

Question 9

Generally, how does a cipher work?

Answer 9

Alice and Bob have a communication. They have a shared key for communicating their messages.

If Alice were to send a message to Bob over the internet saying “hey Bob, let’s meet for coffee”, someone could intercept it. So, encryption allows us to leverage this key that they share to encode a message.

Question 10

How does an encryptopn function work?

Answer 10

It takes two arguments, the message, and a key to encrypt the message. It outputa ciphertext.

Question 11

How does a decryption function work?

Answer 11

It takes two arguments as input, one is the ciphertext and one is the key with which to decrypt the ciphertext. The output is plaintext.

Question 12

What is the Plaintext Space?

Answer 12

It is the set of all valid messages that can be created from the available characters within the length of the message.

Question 13

What is the Ciphertext Space?

Answer 13

It is often times the same as the plaintext space, but it is the set of all possible messages that can be created from the character set in the provided length.

Question 14

What is the Key Space?

Answer 14

The set of all possible keys.

Question 15

What is the simplest cipher and how does it work?

Answer 15

The Shift Cipher is simplest. Assume we are working with the english alphabet, {a,…,z}. In this scenario, our key space is Z₂₅ since each letter can assume an integer value of 0 to 25.

You first devise a mechanism for sampling a key from the key space. To do this, pick one randomly.

Then, to encrypt a message, shift each letter in the message by the value of the key k. For example, a = 0, so if the key is 2, then we move to 2 and c = 2, so a encrypts to c.

Decryption works by subtracting, i.e. doing the reverse.

Question 16

What is the key in the Shift Cipher?

Answer 16

Given an alaphabet of N elements, the key is just a random integer in the set 0 to N modulo N.

Question 17

What are the drawbacks of the Shift Cipher?

Answer 17

There are very few keys, so through process of elimination you can figure out what the shift is.

Question 18

What is the Affine Cipher?

Answer 18

It is a generalization of the Shift Cipher. It works off of the same alphabet but the key space is different.

The key is a tuple of two integers a and b, both from the set of integers Z_N.

a is used to do an additional multiplication when encrypting. a must be relatively prime to N. This is because we need an inverse of a to decrypt. If there is not one, we cannot decrypt. When a = 1, then we basically have a shift cipher.

If our message is m…

1. We multiply m[i] by a and then we add b to it.
2. The corresponding value mod N is the entry in the ciphertext.
3. Decryption is the inverse, so you take the ciphertext c[i], subtract b from it, and then multiply by the inverse of a (a^-1) mod n.

Question 19

What is a Multiplicative Modular Inverse?

Answer 19

It’s some element we denote as a^-1 which is an element in the set Z_N such that when you multiply a by it, you get 1 mod N.

IF we are working with integers mod 4, then the multiplicative inverse of 3 is 3 since 3 * 3 = 9 = 1 mod 4.

Not all elements in our set N will have an inverse.

Question 20

When does a multiplicative inverse exist?

Answer 20

It exists IFF x and N are coprime, meaning relatively prime. This means that the gcd between both numbers x and N is 1.

The gcd between 3 and 4 is 1, so that is why 3 has a multiplicative inverse in Z₄.

2 and 4 are NOT coprime so there is no inverse for 2.

If N is prime, then all keys are coprime to N except 0 which we ignore.

Question 21

How do we encrypt “I like the zoo” with an Affine Cipher?

Answer 21

Map all letters to integers:

“i like the zoo” = [8,11,8,10,4,19,7,4,25,14,14]

We then pick a key by sampling. We randomly pick:

(a,b) = (7,4) –> this works because 7 is relatively prime to 26.

Next we take all the integers from our message and encrypt.

Take each integer, multiply it by 7, and add 4 to it. Then take the result mod 26 = mapping. For example, if we have the letter “i”, we have: 7 * 8 + 4 = 60 mod 26 = 8. In this case, i maps to itself.

We do that for each letter.

Question 22

How do we decrypt the message “idiwg hbg wyy”?

Answer 22

We take the same key as used for encryption, (7,4).

We first get the multiplicative inverse of 7 which is 15.

Then we use the formula: mulinv(a) * (c[i] - 4) = m[i]

15 * (8 - 4) = 60

60 mod 26 = 8

8 is the number corresponding to our plaintext letter m[i]

Question 23

What are the drawbacks of the Affine Cipher?

Answer 23

The key space is still very small. We have 26 keys for b (0 to 25) - same as shift cipher. Then for a we have only the values that are coprime with 26, which is 12.

So, we have 26 * 12 = 312 possible keys. We could easily try them all.

Question 24

What is a Substitution Cipher?

Answer 24

It has a much larger key space than Shift and Affine.

The key is not an integer, but rather a mapping between letters of the alphabet (a becomes d, x becomes e, etc.). The mapping as a whole is our key.

Question 25

How do encryption and decryption work for the Substitution Cipher?

Answer 25

We just perform substitution. If we encrypt “bad day”,. we just substitute out the letters based on the key’s mappings. We do this for each letter.

Decryption is just reversing the map.

Question 26

What is the total number of keys for the Substitution Cipher?

Answer 26

26! or 2⁸⁸

This is the total number of ways to permute the 26 characters.

Question 27

What is the drawback of the Substitution Cipher?

Answer 27

Every letter in plaintext maps to the same letter in the key. So the letters in plaintext are not uniform. This allows for frequency analysis.

Question 28

What is Frequency Analysis?

Answer 28

This is where you use statistics to determine which letters in a ciphertext are most likely to be a certain plaintext letter.

“e” is the most common letter in the english language, so with a large ciphertext, you can likely deduce that the most common letter in the ciphertext is “e”. You then look for the second most common and third most common.

This will not get you all letters, but it may get you enough to guess the remaining ones.

Question 29

What is a more advanced version of Frequency Analysis than the one previously mentioned?

Answer 29

Analyzing the frequenct of digrams and trigrams, etc. to see which ones are most common and try to deduce which english digrams they could be: if “xd” appears a lot, it might be “is” if “is” is super common.

Question 30

What are Ciphertext Only attacks?

Answer 30

These are attacks that can be done without keys, just by looking at the cipghertext. Frequency Analysis is a type of ciphertext-only attack.

Question 31

What is the major drawback of the Substitution Cipher?

Answer 31

It is vulnerable to ciphertext-only attaxks (frequency analysis).

Question 32

What is the Vigenere Cipher?

Answer 32

The idea here is that a key is a word that is of variable length. Alice and Bob might use a 4 character key while Doug and Erin use a 20 character key.

k is a secret word composed of letters in the alphabet of size N.

Question 33

How does encryption work for Vigenere Ciphers?

Answer 33

Alice selects a key. She modifies her key so that it is as long as the plaintext. She repeats the key as many times as it takes to make it the same length (even if the last one is not the full key). Say her key is 4 characters and the plaintext is 8. She multiplies her key by 2 to make her key 8 characters.

Then, she takes her plaintext message at position i and shifts it by the value of the letter in the key at location i mod N.

Question 34

How does decryption of the Vigenere Cipher work?

Answer 34

Instead of shifting by a constant k, we shift by a variable k, so k[i]. It’s sort of backwards, so to decrypt, Bob takes c[i] and shifts it by c[i] - k[i].

Question 35

How would Alice encrypt the message “CRYPTOISREALLYAWESOME”?

Answer 35

She needs to replicate the key UPENN as many times as needed to get to the number of characters in the string she is sending. Notice that the key does not need to be fully repeated, just enough to fill the space. See example below.

Then encryption is just take each letter m[i] and shift it PLUS kl[i] mod N

C + U mod N

= 2 + 20 mod N

= 22 mod 26

= W

Question 36

How do we decrypt a Vigenere Cipher?

Answer 36

Bob replicates the key UPENN to be the same length as Alice’s plaintext. He then performs subtraction:

W - U = 22 - 20 = 2 = C, and the first letter is C in Alice’s message, so we know it worked.

Question 37

How many keys are there in the Vigenere Cipher?

Answer 37

It is hard to estimate since key length is variable. If key length is L, then there are N^{<span>L</span>} possible combinations.

Question 38

What is the weakeness of the Vigenere Cipher?

Answer 38

Once again, the weakness is frequency analysis. To do this, you break the ciphertext into chunks which you expect to be the key size.

Then, you find the most common letter for each slot in that key size, and assume it is E. You then subtract E’s integer value from the integer value of most common letter in each slot of the key. This leaves you with the integer for the key letter.