# HW1

- Due Apr 21, 2018 by 11:59pm
- Points 100
- Submitting a file upload
- File Types pdf

**EE 595 (PMP) Introduction to Security and Privacy **

**Homework 1**

**Assigned: Saturday, April 7, 2018, Due: Saturday, April 21, 2018**

**Instructor: Tamara Bonaci**

**Department of Electrical Engineering **

**University of Washington, Seattle**

**Problem 1**

For each of the following pairs of integers (x, y), first determine whether x^{−1 }mod y exists. Then find x^{−1}(mod y) if it exists. Please do this problem by hand, and show all work.

(a) x=5, y=25

(b) x=24, y=35

(c) x=17, y=101

**Problem 2**

If an encryption function *e*_{K }is identical to the decryption function *d _{K}*, then the key

*K*is said to be an

*involutory key*. Find all the involutory keys in the Shift cipher over Z

_{26}.

**Problem 3**

Suppose *K *= (5, 21) is a key in an Affine cipher over Z_{29}.

(a) Express the decryption function d_{K }(y) in the form d_{K} = a′y + b′, where a′, b′ ∈ Z_{29}.

(b) Prove that d_{K}(e_{K}(x)) = x for all x ∈ Z_{29}.

**Problem 4**

The following ciphertext was encrypted using an Affine cipher:

####
edsgickxhuklzveqzvkxwkzukcvuh

The first two letter of the plaintext are if. Please decrypt.

**Problem 5**

Alice is sending a message to Bob using the ** Vigenere** cryptosystem. At some point, Alice gets bored, and starts sending plaintext that consists of a single letter (known only to her) repeated a few hundred times. Eve knows that the Vigenere cipher is being used, and that the plaintext consists of a single letter, repeated. Show how Eve can deduce the key.

**Problem 6**

Evan, an attacker, is on a mission. He is given a (plaintext, ciphertext) pair (relation, ORIENTAL), and his task is to determine the complete cryptographic key (table), if the given pair is generated using:

(a) Permutation cipher,

(b) Substitution cipher.

Please put your “black hat” on, and show Evan how to accomplish this mission, or show why it is impossible. In doing so, please assume that the set of possible plaintexts is equal to the set of possible ciphertexts, and that it is equal to Z_{26}.

**Problem 7**

Consider the DES cryptosystem. Suppose that the key scheduling algorithm (the algorithm used to compute the round keys) is as follows. For a given key *K*, the algorithm first computes round keys K_{1}, . . . , K_{8 }for the first eight rounds. The algorithm then sets

K_{9 }= K_{8},

K_{10 }= K_{7}

,...,

K_{16 }= K_{1},

so that K_{i }= K_{16−i+1 }for all *i* = 1, . . . , 16. (Note that the DES key scheduling algorithm does not actually work this way.) Suppose that you are given a ciphertext *Y* . Show how to determine the plaintext *x *using a chosen plaintext attack. Recall that in a chosen plaintext attack, an attacker is given a ciphertext *Y* . The attacker is allowed to choose a plaintext *x**′* not equal to *x *and receives the ciphertext *Y ′ *= e_{K }(x′). The attacker then attempts to compute the plaintext *x *satisfying *Y *= e_{K }(*x*).

**Problem 8**

In the CBC mode of encryption, suppose that there is a bit error in one block of ciphertext. If the error occurs in the first block of ciphertext Y_{1}, which blocks of the plaintext will be decrypted incorrectly?

**Problem 9**

In this exercise, we will see how a cryptosystem can fail if the encryption function is a linear function of the plaintext. Consider a cryptosystem that encrypts a 128-bit plaintext *x *with a 128-bit key *K *to get a 128-bit ciphertext *Y *. Let E_{K }(x) denote the encryption function, and suppose that

E_{K}(x_{1 }⊕ x_{2}) = E_{K}(x_{1}) ⊕ E_{K}(x_{2})

for all keys *K *and plaintexts *x _{1 }*and

*x*. Consider an attacker mounting a chosen ciphertext attack, in which the attacker chooses 128 ciphertexts

_{2}*Y*, . . . ,

_{1}*Y*

*and receives the plaintexts*

_{128 }*x*

_{1}*,*. . . ,

*x*

*with*

_{128 }*Y*

_{i }= E

_{K }(x

_{i}) for i = 1,...,128. Show how the attacker can choose Y

_{1},...,Y

_{128 }so that (s)he can decrypt any message

*Y*without knowledge of the secret key.