Homework 2 Assigned: Thursday, January 26, 2017, Due: Sunday, February 12, 2017
Instructor: Tamara Bonaci
Department of Electrical Engineering
University of Washington, Seattle
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, KE and a private (secret) key, KD. How many keys are needed for each type of cryptosystems if m = 1000?
Solve the following system of congruences:
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)
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.
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 toy, such that knowledge of the plaintext x' = dK(y') allows x= dK (y) to be computed.
Hint: Use the multiplicative property of the RSA Cryptosystem, i.e., that: eK(x1)eK(x2) mod n = eK(x1x2) mod n
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.
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, (Y1, Y2) can decrypt any other ciphertext (Y1′, Y2′).
Can't change a rubric once you've started using it.