Question

If there are 2^56 cipher texts per plain text and a total of 2^18 plaintexts of length 18 exists. Then determine the number of distinct ciphertexts?

(a) 761

(b) 2^74

(c) 186

(d) 2^89

I got this question in an internship interview.

This intriguing question comes from Cryptography topic in section Number Theory and Cryptography of Discrete Mathematics

Answer 1

Right choice is (b) 2^74

To elaborate: If there are 2^56 cipher texts per plain text and a total of 2^18 plaintexts of length 18 exists which will all decrypt to the same plaintext, and this holds for every plaintext. There are a total of 2^56  plaintexts of length 56. Now, there must be 2^56. 2^18 = 2^74 distinct ciphertexts which all decrypt to plaintexts of length 56. If all those ciphertexts are the same length, they must be at least 74 bits long.