Consider a block cipher whose block length is 𝑛. 𝑁 = 2𝑛 is number of possibilities. Imagine we have 𝑑 plain text-cipher text pairs { 𝑃𝑖, 𝐢𝑖 = 𝐸𝐾(𝑃𝑖) } , where the key 𝐾 selects one of the 𝑁! Possible mappings.

Now, imagine you want to brute force this encryption algorithm for the key. In each try, you generate the test key 𝐾′ and check whether 𝐢𝑖 = 𝐸(𝐾′,𝑃𝑖); i=1,…,t. If 𝐾′ maps 𝑃𝑖 to its proper 𝐢𝑖, we have an evidence that 𝐾′ = 𝐾. However, it could be the case that 𝐸𝐾(.) and 𝐸𝐾′(.) exactly map the 𝑑 given plain-texts to the same set of cipher-texts but map the other inputs differently.
a) what’s the probability that 𝐸𝐾(.) and 𝐸𝐾′(.) are distinct mappings? b) what’s the probability that 𝐸𝐾(.) and 𝐸𝐾′(.) agree on another 𝑑′ plain-text cipher-text pairs where 0 ≀ 𝑑′ ≀ 𝑁 βˆ’ 𝑑?

How can I solve this problem?

  • 2
    $\begingroup$ looks a bit like a homework assignment, what have you tried? $\endgroup$
    – kodlu
    Nov 26, 2020 at 23:28
  • $\begingroup$ Be specific about what you have tried and what you do not understand. Show the effort you have made by describing the exact point or points that have held you up. $\endgroup$
    – Patriot
    Nov 27, 2020 at 14:33
  • $\begingroup$ While the problem statement in Probability of false positive key matching two plaintext/ciphertext pairs is with specific numbers, that's actually the same problem. Also, the notation there is correct, when here it is not (𝑁 = 2𝑛 where $N=2^n$ applies). And, there the question is presented as personal research with some effort shown, when here we have a straight dump. $\endgroup$
    – fgrieu
    Nov 27, 2020 at 15:00