HW3
 Due Nov 10, 2016 by 11:59pm
 Points 45
 Submitting a file upload
EE 418: Network Security and Cryptography Homework 3
Assigned: Wednesday, November 2, 2016, Due: Thursday, November 10, 2016
Instructor: Tamara Bonaci
Department of Electrical Engineering University of Washington, Seattle
Text describing the first project assignment is provide in Files/Homework/EE418_HW.pdf.
Problem 1 (Stinson, Problem 5.7)
Solve the following system of congruences:
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)
Problem 2
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 3
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 4 (Stinson, Problem 5.14)
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' \neq 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.
Problem 5 (Stinson, Problem 5.15)
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 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 encrypting each residue modulo 26 as a separate plaintext character.
(a) Describe how an attacker Eve can easily decrypt a message which is encrypted in this way.
(b) Illustrate this attack by decrypting the following ciphertext, which was encrypted using an RSA Cryptosystem with n = 18721 and b = 25 without factoring the modulus: 365, 0, 4845, 14930, 2608, 2608, 0.
Problem 6 (Stinson, Problem 5.16)
This exercise illustrates another example of a protocol failure (due to Simmons) involving the RSA Cryptosystem. Is is called the “common modulus protocol failure”. Suppose that Bob has an RSA cryptosystem with the modulus n and encryption exponent b, and Charlie has an RSA cryptosystem with the same modulus n and encryption exponent b_{2}. Suppose also that gcd(b_{1},b_{2}) = 1. Now consider the situation that arises if Alice encrypts the same plaintext x to send to both Bob and Charlie. Thus, she computes y_{1 }= x^{b1 }(mod n) and y_{2 }= x^{b2}_{ }(mod n), and then she sends y_{1 }to Bob and y_{2 }to Charlie. Suppose Eve intercepts y_{1 }and y_{2}, and performs the computation indicated in the following algorithm:
Algorithm 5.16: RSA Common Modulud Decryption(n, b1, b2, y1, y2)
c1 = inv(b1) mod(b2)
c2 = (c1 b1  1)/b2
x1 = y1^(c1)inv(y2^(c2)) mod(n)
return x1
(a) Prove that the value x1, computed in given algorithm in is fact Alice’s plaintext x. Thus eve can decrypt the message Alice sent, even though the cryptosystem may be “secure”.
(b) Illustrate the attack by computing x by this method if n = 18721, b1 = 43, b2 = 7717, y1 = 12677 and y2 = 14702.
Problem 7

(a) Ciphertext 5859 was obtained using the RSA cryptosystem with n = 11413 and e = 7467. Using the factorization 11413 = 101 × 113, find the plaintext.

(b) Ciphertext 75 was obtained using the RSA cryptosystem with n = 437 and e = 3. You know that the plaintext is either 8 or 9. Determine which it is without factoring n.]
Problem 8
Suppose that Alice and Bob communicate using ElGamal Cryptosystem and that, to save time, Bob uses the same random nonce 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 attacker who possesses a (plaintext, ciphertext) pair x, (Y_{1}; Y_{2}) can decrypt any other ciphertext (Y_{1}′; Y_{2}′).
Problem 9 (Trappe, Problem 13.5.5)
Bob, Ted, Carol and Alice want to agree on a common key (cryptographic key, that is). They publicly choose a large prime p and a primitive root α. They privately choose numbers b,t,c,a, respectively. Describe a protocol that allows them to securely compute (in doing so, please ignore the maninthemiddle attack):
K := α^{btca }(mod p)