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.
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?
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'= dK(y') allows x = dK (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.