2015-07-10

b433. 中間相遇法

1. Problem
1. 1.1. 背景
2. 1.2. 問題描述
2. Sample Input
3. Sample Output
4. Solution
1. 4.1. Hash
2. 4.2. Array

Problem

背景

加密的每一道過程若存在反運算，則存在解密的程序。絕對安全的加密沒有反運算，那解密也是沒有辦法做到的。通常加解密中一定會用到互斥或 (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)$ 解決這個問題。

Sample Input

1 2	40380 23333 30767 13657

Sample Output

1 2	114688 45568

Solution

套用中間相遇法$E_{key_1}(M) = D_{key_2}(C)$ 分別對等式兩邊進行計算，查看相碰情況。

複雜度為窮舉所有可能的 $key_1$ 和 $key_2$，若用平衡樹進行碰撞檢查 $O(2^{16} \times 16)$，利用 HASH 可以降到 $O(2^{16})$，由於 $O(2^{16})$ 是記憶體可以宣告的，則直接使用數組來完成。

Hash

#include <bits/stdc++.h> 
using namespace std;
typedef unsigned short int UINT16;
class SimpleIdea {
public:
    UINT16 key;
    SimpleIdea(UINT16 k = 0):
        key(k) {}
    UINT16 encrypt(UINT16 m) {
        return (rotate_left(m, key&15) + key)^key;
    }
    UINT16 decrypt(UINT16 m) {
        return rotate_left((m^key)+(~key)+1, 16 - (key&15));
    }
private:
    UINT16 rotate_left(UINT16 x, UINT16 n) {
    	return  (x << n) | (x >> (16-n));
    }
} test;
int main() {
    int C, M;
    while (scanf("%d %d", &C, &M) == 2) {
        unordered_map<int, int> H1, H2;
        for (int i = 0; i < (1<<16); i++) {
            int key1 = i, key2 = i;
            test.key = key1;
            H1[test.encrypt(M)]++;
            test.key = key2;
            H2[test.decrypt(C)]++;
        }
        
        int ret = 0;
        for (auto &x : H1) {
            if (H2.count(x.first))
                ret += H2[x.first] * x.second;
        }
        printf("%d\n", ret);
    }
    return 0;
}

Array

#include <bits/stdc++.h> 
using namespace std;
typedef unsigned short int UINT16;
class SimpleIdea {
public:
    UINT16 key;
    SimpleIdea(UINT16 k = 0):
        key(k) {}
    UINT16 encrypt(UINT16 m) {
        return (rotate_left(m, key&15) + key)^key;
    }
    UINT16 decrypt(UINT16 m) {
        return rotate_left((m^key)+(~key)+1, 16 - (key&15));
    }
private:
    UINT16 rotate_left(UINT16 x, UINT16 n) {
    	return  (x << n) | (x >> (16-n));
    }
} test;
int main() {
    int C, M;
    while (scanf("%d %d", &C, &M) == 2) {
        int H[1<<16] = {}, ret = 0;
        for (int i = 0; i < (1<<16); i++) {
            test.key = i;
            H[test.encrypt(M)]++;
        }
        for (int i = 0; i < (1<<16); i++) {
            test.key = i;
            ret += H[test.decrypt(C)];
        }
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog