Week 1 Part 1

Question 1

Kerckhoff’s Principle

Answer 1

• The Encryption and Decryption algorithms are public knowledge
• Security relies entirely on the secrecy of the key

Question 2

What are the 4 types of attacks for an adversary and what does the adversary receive on each?

Answer 2

1. Known CipherText Attack
   - gets a bunch of random ciphertext
2. Known Plaintext Attack
   - Attacker has a copy of the plaintext and CipherText versions of the protected file. Corresponding pairs (m1,c1),…, (mn,cn)
3. Chosen Plaintext Attack
   - Attacker gets a encryption oracle and encrypts as much as he wants (IND-CPA secure)
4. Chosen Ciphertext Attack
   - Adversary gets an encryption and decryption oracle (IND-CCA secure) STRONGEST SECURITY

Question 3

What is the Caesar Cipher encryption and decryption formulas?

Answer 3

• Enc: c = (m + k) mod 26
• Dec: m = (c − k) mod 26

Question 4

Why is the Caesar cipher not secure?

Answer 4

• Key space K consists of 26 possible keys, i.e. K = {0, . . . , 25}
  
  • Very easy to brute force, i.e. try all 26 possibilities (one of them will make sense!)

Question 5

What is the key space of the substitution cipher

Answer 5

• Key space K is all possible permutations of the alphabet {A, B, C, . . . , Z} ⇒ |K| = 26! ≈ 4 × 10^26 possible keys
  
  • Brute-force is not practical

Question 6

How can you attack a substitution cipher?

Answer 6

Cipher maintains the redundancy present in plaintext
- Can be broken with a ciphertext-only attack using language statistics

Question 7

How can you attack a Vigenere Cipher?

Answer 7

Attack using Kasiski method
1. Identify pairs of identical segments (of length ≥ 3) in c
2. Find the distance (∆i) between such pairs & use that to guess |k|
- Hint: |k| divides GCD(∆1, ∆2, . . .)
3. Apply frequency analysis separately to each (of the |k|) Shift cipher(s)

Question 8

What are the three rules to make a cipher secure? What do they protect against?

Answer 8

1. Needs to have a large key space (to resist brute-force)
2. Provide Confusion (complex relationship between c and k) (protects against kasiski method and defends against chosen ciphertext attacks)
3. Provide Diffusion (complex relationship between m and c) (protects against frequency analysis and defends against chosen plaintext attacks)

Question 9

Discuss how would the security of interleaving 4 rounds (each with its own Shift cipher key) of the Shift cipher, where in each round the round encrypts the ciphertext from the preceding round, compare with just using the normal Shift cipher (i.e. just one round)

Answer 9

This interleaving does not offer any additional security as this is equivalent to one round with the key (k1 + k2 + k3 + k4) mod 26.

Question 10

If theShift (Caesar)cipher was used to encrypt the plaintext “HI” to produce “KJ” . What would the key be?

Answer 10

The shift would have to be 3 for ‘H’ and 1 for ‘I’ which is not possible. So there is no one key that could produce this result.

Question 11

Double encryption with the Shift (Caesar)cipher, where in the first round the key is k=2 whereas in the second round the key is k=7, is used to obtain the ciphertext “BNLDARCH”. By double encryption we mean the second round encrypts the ciphertext from the first round, what is the corresponding (original) plaintext?

Answer 11

To solve this problem I used the shift cipher to shift 7 places and worked backwards. This produced UGEWTKVA. I then shifted the cipher 2 places, worked backwards and got SECURITY.

Question 12

If the ciphertext is “DIQD”, the key used is “KEY” and the cipher used is the Vigenère cipher, what is the corresponding plaintext?

Answer 12

To solve this problem, I used the vigenere cipher. I used the key: KEYK as there are 4 letters. As the word given to us is the ciphertext. I looked up the letters of the keys and scanned to find the corresponding ciphertext letter and then looked at the plaintext field to decipher the plaintext. I checked my answer by encrypting, if we want to encrypt we can use the key KEYK and the plaintext TEST to produce DIQD.

Question 13

In an attempt to decrypt a very large ciphertext that was obtained using the Vigenère cipher, we found that the distance between identical segments in the ciphertext is always 10. Which of the following is definitely not a valid guess for the key length? 2, 5, 3, 10

Answer 13

As per this rule:2 identical segments ofmwill lead to the same segments ofcif the distance between them is a multiple of the (original)key length (|k|). The answer is 3 because it is not a multiple of 10