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?
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.
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' that is not equal to y, such that knowledge of the plaintext x' = dK(y) allows an attacked to compute x = dK(y).
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 cryptosystem with n = 18721 and e = 25) without factoring the modulus:
365, 0, 4845, 14930, 2608, 2608, 0.