# HW2

- Due Oct 25, 2016 by 11:59pm
- Points 45
- Submitting a file upload
- File Types zip and pdf

**EE 418: Network Security and Cryptography Homework 2 **

**Assigned: Tuesday, October 11, 2016, Due: Tuesday, October 25, 2016 **

**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. Show all work.

(a) x=5, y=25

(b) x=12, y=29

(c) x=24, y=35

(d) x=17, y=101

(e) x=87, y=102

**Problem 2 (Stinson, Problem 1.2) **

Suppose that *a, **m* > 0 and a not congruent to 0 (mod *m*). Prove that

(−*a*) mod *m *= *m *− *a* (mod *m*).

**Problem 3 (Stinson, Problem 1.6) **

If an encryption function *e _{K }*is identical to the decryption function

*d*, then the key

_{K}*K*is said to be an involutory key. Find all the involutory keys in the Shift Cipher over Z

_{26}.

**Problem 4 (Stinson, Problem 1.7) **

Determine the number of valid keys (*a*,* b*) in an Affine cipher over Z_{m }for *m *= 30, 100 and 1225.

**Problem 5 (Stinson, Problem 1.10) **

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 6 (Trappe, Washington, Problem 2.13.3) **

The following ciphertext was encrypted by an affine cipher:

```
edsgickxhuklzveqzvkxwkzukcvuh
```

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

**Problem 7 (Trappe, Washington, Problem 2.13.4) **

The following ciphertext was encrypted by an affine cipher using the function 3*x *+ *b *for some *b*: tcabtiqmfheqqmrmvmtmaq

Please decrypt.

**Problem 8 (Stinson, Problem 1.15) **

Determine the inverses of the following matrices over Z_{26}.

(a) *M _{1}* = [2 5; 9 5]

(b) *M _{2 }*= [1, 11, 12; 4, 23, 2; 7, 15, 9]

**Problem 9 (Stinson, Problem 1.16) **

Suppose that *π *is the permutation of {1, . . . , 8} given in Figure 1:

(a) Compute the permutation π^{−1}.

(b) Decrypt the following ciphertext, for a Permutation Cipher with *m *= 8, which was encrypted using the

key *π*:

TGEEMNELNNTDROEOAAHDOETCSHAEIRLM

**Problem 10 (Trappe, Washington, Problem 2.13.16) **

Alice is sending a message to Bob using one of the cryptosystems listed below. In fact, Alice is bored and her plaintext consists of one letter (known only to her) repeated a few hundred times. Eve know what system is being used, but not the key, and she intercepts the ciphertext. For systems (a) and (b), state how Eve will recognize that the plaintext is one repeated letter and decide whether or not Eve can deduce the key. For system (c), assume that Eve guesses that the plaintext is one repeated letter, and show how Eve can then deduce the key.

(a) Shift cipher,

(b) Affine cipher,

(c) Vigenere cipher (assume that the key is an English word of length between 8 and 12 letters.)