Playfair密码

Playfair密码出现于1854年，它将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文双字母组合。Playfair密码基于一个字母矩阵，该矩阵使用一个关键词（密钥）来构造。

字母矩阵

其构造方法是：从左至右、从上至下依次填入关键词的字母（去除重复的字母），然后再以字母表顺序依次填入其他字母。字母I和J被算为一个字母（即J被当做I处理）。

如密钥为monarchy，则构造字母矩阵如下：

当密钥串有重复字符出现时，需要去重，否则矩阵将无法覆盖26个字母。

我们可以方便地实现字母矩阵的数据结构的代码如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

class AlphaMatrix {
   private:
    vector<char> data{};
    unordered_map<char, int> index;

   public:
    AlphaMatrix(string key) : data(vector<char>(25)) {
        // 用于记录某个字符是否已经被添加过字母矩阵
        unordered_set<char> m;

        // 认为i与j为同一个字符
        // 故一开始就再集合m种添加字母j视作已添加
        m.insert('j'); 

        // ss作为一个字符队列可以不断向队尾添加元素
        stringstream ss;

        // 准备将密钥串添加至队列
        for (int i = 0; i < key.size(); i++) {
            // 如果已经添加过了，即出现重复字符，那么跳过本字符
            if (m.count(key[i])) continue;

            // 追加字符至队列
            ss << key[i];

            // 并记录该字符已添加
            m.insert(key[i]);
        }
        // 将密钥串中需要添加到字母矩阵的字符添加到矩阵中去
        string s = ss.str();
        for (int i = 0; i < s.size(); i++) data[i] = s[i];

        // 记录矩阵插入位置的指针p
        // 初始状态应当指向密钥串的最后一个添加到字母矩阵中的位置的下一个位置
        // 即p = s.size()
        int p = s.size();

        // 遍历字母a-z
        for (char c = 'a'; c <= 'z'; c++) {
            // 若字母矩阵种已存在，则跳过
            if (m.count(c)) continue;
            data[p++] = c; // 添加
        }

        // 后续需要频繁使用到根据字母查询行号和列号的操作
        // 故直接在此处建立索引表，即map实现快速查询
        for (int i = 0; i < 25; i++) index[data[i]] = i;

        // 当查询字母时，视作查询字母i
        index['j'] = index['i'];
    }

    // 获取指定行列的字符
    char get(int row, int col) {
        row = (row+5) % 5;
        col = (col+5) % 5;
        return data[row * 5 + col];
    }

    // 获取指定字符的行号
    int row(char ch) {
        int idx = index[ch];
        return idx / 5;
    }

    // 获取指定字符的列号
    int column(char ch) {
        int idx = index[ch];
        return idx % 5;
    }

    // 打印输出该字母矩阵
    void display() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cout << data[i * 5 + j] << ' ';
            }
            cout << endl;
        }
    }
};

编写主函数测试当key="monarchy"时的字母矩阵的输出：

1
2
3
4
5
int main() {
    AlphaMatrix am("monarchy");
    am.display();
    return 0;
}

输出结果如下:

1
2
3
4
5
m o n a r 
c h y b d 
e f g i k 
l p q s t 
u v w x z

测试结果符合预期的输出

加密算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 暂时不考虑p1=p2与奇数字母数的情况下的加密算法
void encryptTwoChar(char p1, char p2, char& c1, char& c2, AlphaMatrix& key) {
    // p1,p2同一行
    if (key.row(p1) == key.row(p2)) {
        // 获取所在行
        int r = key.row(p1); 

        // 获取密文c1,c2所在列
        int c1c = key.column(p1) + 1;
        int c2c = key.column(p2) + 1;

        // 读取密文c1,c2
        // get函数已经自动完成了越界时回卷处理
        c1 = key.get(r, c1c);
        c2 = key.get(r, c2c);
    }
    // p1,p2同一列
    else if (key.column(p1) == key.column(p2)) {
        // 获取所在列
        int c = key.column(p1);

        // 获取密文c1,c2所在行
        int c1r = key.row(p1) + 1;
        int c2r = key.row(p2) + 1;

        // 读取密文c1,c2
        // get函数已经自动完成了越界时回卷处理
        c1 = key.get(c1r, c);
        c2 = key.get(c2r, c);
    }
    // 不同行不同列
    else {
        // 确定p1, p2构成的矩阵
        int row1 = key.row(p1);
        int col1 = key.column(p1);
        int row2 = key.row(p2);
        int col2 = key.column(p2);

        // 取别于p1,p2的另一条对角线上的字符
        // 作为c1,c2
        c1 = key.get(row1, col2);
        c2 = key.get(row2, col1);
    }
}

// 实现完整的加密函数
// 当p1==p2时，插入字母Q
// 当字母数为奇数时，插入字母X
string encrypt(string message, char Q, char X, AlphaMatrix& key) {
    stringstream ss;

    int p = 0;
    while(p<message.size()) {
        char p1 = message[p++];

        // 跳过空格
        while(p1 == ' ') p1 = message[p++];
        char p2;
        if(p<message.size()) {
            p2 = message[p++];
            while(p2 == ' ') p2 = message[p++];
        }else{
            p2 = X;
        }
        if(p1 == p2) {
            // 插入一个字母Q
            p2 = Q;
            // 此时指针p需要回退
            p--;
        }
        char c1,c2;
        encryptTwoChar(p1,p2,c1,c2,key);
        ss<<c1<<c2;
    }
    return ss.str();
}

编写main函数测试代码如下，

1
2
3
4
5
6
7
8
9
10
int main() {
    AlphaMatrix am("monarchy");
    am.display();

    string src = "aamuhsea";
    string result = encrypt(src, 'b', 'x', am);
    cout << result<<endl;

    return 0;
}

输出结果如下：

1
2
3
4
5
6
m o n a r 
c h y b d
e f g i k
l p q s t 
u v w x z
rmcmbpim

符合预期输出

实践

已知密钥key=“hello”，试用Playfair算法加密明文“enjoy your life”，注意：两个相同的字母之间可以插入字母“x”，如果明文为奇数个字符，末尾可以加字符“z”。

手动计算

写出字母矩阵

h e l o a
b c d f g
i/j k m n p
q r s t u
v w x y z

加密过程

两两划分

  1. en

    1. en不同行列，另一个对角线上的元素为ok(c1,c2的顺序同p1,p2的行号)

  2. jo

    1. jo不同行列，另一条对角线上的元素为nh

  3. yy会发现重复了，故插入字母x，得到yx

    1. yx同行，故同行向后各推一个得到zy

  4. 上一次因重复残留了一个y，故继续使用得到yo

    1. yo同列，故同列向下各推一个得到of

  5. ur

    1. ur同行，qs

  6. li

    1. li不同行列，hm

  7. fe

    1. cf不同行列，co

得到最终密文为：oknhyxzy ofqs hmco

代码计算

1
2
3
4
5
6
7
8
9
int main() {
    AlphaMatrix am("hello");
    am.display();

    string src = "enjoy your life";
    string result = encrypt(src, 'x', 'z', am);
    cout << result<<endl;
    return 0;
}

得出结果如下：

1
2
3
4
5
6
h e l o a
b c d f g
i k m n p
q r s t u
v w x y z
oknh zyofqs hmco