背景

加密的每一道過程若存在反運算，則存在解密的程序。絕對安全的加密沒有反運算，那解密也是沒有辦法做到的。通常加解密中一定會用到互斥或 (XOR) 運算，從表格來看，單獨看任何一行一列都恰好分配一半的 0、一半的 1。對於密碼來說，明文跟密文的關係，不管知道的明文還是密文的部分，猜中的機率只有 $1/2$，只要位元數一多，猜中的機率近乎 $(\frac{1}{2})^n \cong 0$。

「只用 XOR key 是不行的，再做一次不就回來了嗎？」

「那用循環位移和加法的 overflow 破壞線性結構！」

「但記得要能解密回來哦。」

於是某 M 提供一個簡單的加密運算，明文 $M$，加密金鑰 $key$

• 密文 $C =  ((M \text{<<<} key) + key) \text{ XOR } key$
• 明文 $M =  ((C \text{ XOR } key) + (\sim key) + 1) \text{>>>} key$

其中每一個運算都在 16-bit CPU 上運作，$\text{<<<}$ 表示循環左移 (circular shift)，$\sim$ 表示 1 補數。

用抽象化表示加解密流程

• $C = E_{key}(M)$
• $M = D_{key}(C)$

問題描述

現在某 M 正用他自己設計的加解密協定跟未來的自己溝通，但發現到這種加解密，如果對方知道某 M 一定會傳送哪一個明文，接著只要匹配密文，窮舉 $O(2^{16})$ 來找到加密金鑰就會破功。

在電影《模仿遊戲》中，德國納粹 Enigma 密碼機，訊息中的結尾一定會附加「希特勒萬歲！(Heil Hitler!)」匹配密文後，窮舉金鑰就能破解。而某 M 常常傳送「萌萌哒！(Moe Moe Ta!)」只需要 $O(2^{16})$ 就能被破解。

於是某 M 強化他的加密協定，希望破解者至少要在 $O(2^{32})$ 的時間內找到，拖延破解時間。

• $C = E_{key_2}(E_{key_1}(M))$
• $M = D_{key_1}(D_{key_2}(C))$

現在知道某 M 傳送的其中一組 $(C, M)$，請告訴某 M 有多少組 $(key_1, key_2)$ 的可能性。萬萬沒想到，中間相遇法能在 $O(2^{16} \times 16)$ 解決這個問題。