暗号化の分析

昔の日記にも書いてあると思いますが復習します。
One type of cryptanalysis is the Meet in the Middle Attack. I am trying to recall how this works and where it is relevant. It seems that this applies where the cipher is the composition of multiple functions, each using a different key. The example given is C = Ek1(Ek2(P)). Ek1 is encryption using key 1 (n bits) and Ek2 is encryption using key 2 (n bits). We know at least two plaintext-ciphertext pairs. Let the first pair be P and C. P is in the domain of Ek2, and C is in the range of Ek1. We want to map P forward to the range of all outputs of Ek2 (for all possible keys, of which there are 2^n), and C backward (using decrypt function, assumed to be inverse of Ek1)to the domain of all possible inputs to Ek1 (again, for all possible keys k1). This leads to 2^(n+1) encryptions. The outputs of the Ek2 encryptions are stored in a hash table. Then, for each of the inverse Ek1 decryptions, we check the result against the lookup table. If a match is found, we call Ek1(Ek2(P')) on another known plaintext P' and check that it matches the known ciphertext C'. If so, we are done. Thus, for a two-key algorithm like that above, we achieve much better performance than the brute-force time complexity of O(2^2n) encryptions.

Another problem I am interested in reviewing is when hash collisions can render a hash-based security scheme to be insecure.