HW2
 Due Feb 12, 2017 by 11:59pm
 Points 50
 Submitting a file upload
EE 595 (PMP) Introduction to Security and Privacy
Homework 2
Assigned: Thursday, January 26, 2017, Due: Sunday, February 12, 2017
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
Solve the following system of congruences:
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)
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' not equal to y, such that knowledge of the plaintext x' = d_{K}(y') allows x = d_{K }(y) to be computed.
Hint: Use the multiplicative property of the RSA Cryptosystem, i.e., that: e_{K}(x_{1})e_{K}(x_{2}) mod n = e_{K}(x_{1}x_{2}) 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 Cryp
tosystem with n = 18721 and b = 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 random 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}′).