# HW2

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

EE 595 (PMP) Introduction to Security and Privacy Homework 2**Assigned: Friday, April 20, 2018, Due: Saturday, May 5, 2018**

Instructor: Tamara Bonaci

Department of Electrical Engineering

University of Washington, Seattle

**Problem 1**

Suppose that *m* > 2 users want to communicate securely and confidentially. Suppose further that each of the *m *users wants to be able to communicate with every other user without the remaining *m *− 2 users being able to listen on their conversation. How many distinct keys are needed if we are using:

• A **symmetric key cryptosystem****,** where two users use a shared secret key to communicate,

• A **public key cryptosystem**, where every user has a public key, *K*_{E }and a private (secret) key, *K _{D}*. How many keys are needed for each type of cryptosystems if

*m*= 1000?

**Problem 2**

Alice and Bob decide to communicate confidentially using the RSA cryptosystem where *p *= 5, *q *= 11 and *n *= *p *× *q*. Alices public key under this cryptosystem is (*e*, *n*) and her private key is (*d*, *n*). If *e *= 3, please find what is the value *d *of Alices private key, and show how can we find it in general.

**Problem 3**

In the RSA cryptosystem, a user’s public key is given as *e *= 31, *n *= 3599. Please find the user’s private key, and explain your procedure.

**Problem 4**

Prove that the RSA cryptosystem is insecure against a **chosen ciphertext attack**. In particular, given a ciphertext *y*, describe how to choose a ciphertext *y'* that is not equal to *y*, such that knowledge of the plaintext *x'** *= *d _{K}(y*

*)*allows an attacked to compute

*x = d*

_{K}(y*)*.

Hint: Use the multiplicative property of the RSA Cryptosystem, i.e., that: e_{K}(x1)e_{K}(x2) mod n = e_{K}(x1x2) mod n

**Problem 5**

This exercise exhibits what is called a **protocol failure**. It provides an example where ciphertext can be decrypted by an opponent without determining the key, if a cryptosystem is used in a careless way. The moral is that it is not sufficient to use a “secure” cryptosystem in order to guarantee “secure” communication.

Suppose Bob has an RSA cryptosystem with a large modulus *n *for which the factorization cannot be found in a reasonable amount of time. Suppose Alice sends a message to Bob by representing each alphabetic character as an integer between 0 and 25 (i.e., A ↔ 0, B ↔ 1, etc.), and then encrpyting each residue modulo 26 as a separate plaintext character

(a) Describe how Eve can easily decrypt a message encrypted in this way.

(b) Illustrate this attack by decrypting the following ciphertext (which was encrypted using an RSA cryptosystem with *n *= 18721 and *e* = 25) without factoring the modulus:

365, 0, 4845, 14930, 2608, 2608, 0.

**Problem 6**

Suppose that Alice and Bob communicate using **ElGamal Cryptosystem **and that, to save time, Bob uses the same number *k *each time he encrypts a plaintext message (i.e., *k *is a fixed secret of Bob, and it is not randomly generated each time encryption is performed). Show how an adversary who possesses a (plaintext, ciphertext) pair *x*, (*Y _{1}, Y_{2}*) can decrypt any other ciphertext (

*Y*).

_{1′}, Y_{2′}