Hill密码

已知明文“Thank  you”，密钥为

K=[1203]K=\begin{bmatrix} 1 & 2\\ 0 & 3 \end{bmatrix}

加密公式为C=KmC=Km ，试用Hill密码算法进行加密，并求出K−1K^{-1}，用你得到的密文进行解密验算。

手算过程

加密过程

将消息划分为m1,m2,…,m8 = t,h,…,u

[c1c2]=K⋅[m1m2]=[1203]⋅[197]=[3321]mod 26=[721]=[hv]\begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = K \cdot \begin{bmatrix} m_1 \\ m_2 \end{bmatrix} = \begin{bmatrix} 1 & 2\\ 0 & 3 \end{bmatrix} \cdot \begin{bmatrix} 19 \\ 7 \end{bmatrix} = \begin{bmatrix} 33 \\ 21 \end{bmatrix} mod \space 26 =\begin{bmatrix} 7 \\ 21 \end{bmatrix} = \begin{bmatrix} h \\ v \end{bmatrix}

同理可得

c = hvanguci

解密过程

求K的伴随矩阵

二阶矩阵的伴随矩阵主对角线互换，副对角线取相反数

K∗=[3−201]K^*=\begin{bmatrix} 3 & -2\\ 0 & 1 \end{bmatrix}

求K的行列式

∣K∣=3−0=3|K| = 3 - 0 = 3

求|K|的乘法逆元|K|^-1

(∣K∣⋅∣K∣−1)%26=1(|K|\cdot |K|^{-1}) \% 26 = 1

已知∣K∣|K|，求∣K∣−1|K|^{-1}

故满足条件的∣K∣−1=9|K|^{-1}=9

求K的逆矩阵

K−1=(∣K∣−1⋅K∗) mod 26K^{-1} = (|K|^{-1} \cdot K^*) \space mod \space 26

K−1=[1809]K^{-1} = \begin{bmatrix} 1 & 8\\ 0 & 9 \end{bmatrix}

解密

m=K−1⋅cm=K^{-1} \cdot c

[m1m2]=K−1⋅[c1c2]=[1809]⋅[721]=[197]mod 26=[197]=[th]\begin{bmatrix} m_1 \\ m_2 \end{bmatrix} = K^{-1} \cdot \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 1 & 8\\ 0 & 9 \end{bmatrix} \cdot \begin{bmatrix} 7 \\ 21 \end{bmatrix} = \begin{bmatrix} 19 \\ 7 \end{bmatrix} mod \space 26 =\begin{bmatrix} 19 \\ 7 \end{bmatrix} = \begin{bmatrix} t \\ h \end{bmatrix}

同理可得m1,m2,…,mn = thankyou

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <sstream>

using namespace std;

class Vector2x2 {
   public:
    int a, b;

    Vector2x2(int _a, int _b) : a(_a), b(_b) {}

    Vector2x2 mod(int n) {
        int ta = a;
        int tb = b;
        while (ta <= 0) ta += n;
        while (tb <= 0) tb += n;
        int ia = int(ta) % 26;
        int ib = int(tb) % 26;
        return Vector2x2((int)ia, (int)ib);
    }
};

// 已知 x, m
// 求(x * y) % m = 1 时 y 的值
int mul_inv(int x, int m) {
    int y = 0;

    // y 的取值范围为[0,m)
    while (y < m) {
        if ((x * y) % m == 1) {
            break;
        } else {
            y++;
            // 不存在乘法逆元
            if (y == m) {
                return 0;
            }
        }
    }
    return y;
}

class Matrix2x2 {
   private:
    int a, b;
    int c, d;

   public:
    Matrix2x2(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d) {}

    int determinant() { return a * d - b * c; }

    // 求伴随矩阵
    Matrix2x2 getAdjugateMatrix() {
        return Matrix2x2(  //
            d, -b,         //
            -c, a          //
        );
    }

    // 求矩阵的逆
    // 注意这里伴随矩阵前的系数需要求模m乘法的逆元
    // 而不是常规的行列式倒数
    Matrix2x2 inverse() {
        return getAdjugateMatrix().mul(mul_inv(determinant(), 26));
    }

    // 矩阵x向量
    Vector2x2 mul(Vector2x2 v) {
        return Vector2x2(       //
            a * v.a + b * v.b,  //
            c * v.a + d * v.b   //
        );
    }

    // 矩阵数乘
    Matrix2x2 mul(int n) {
        return Matrix2x2(  //
            a * n, b * n,  //
            c * n, d * n   //
        );
    }

    void display() {
        cout << a << ", " << b << endl  //
             << c << ", " << d << endl;
    }
};

string encrypt(string message, Matrix2x2& key) {
    stringstream ss;
    for (int i = 0; i < message.size(); i += 2) {
        Vector2x2 m(message[i] - 'a', message[i + 1] - 'a');
        Vector2x2 c = key.mul(m).mod(26);
        ss << char(c.a + 'a') << char(c.b + 'a');
    }
    return ss.str();
}

string decrypt(string clip, Matrix2x2& key) {
    Matrix2x2 K_1 = key.inverse();
    return encrypt(clip, K_1);
}

int main() {
    Matrix2x2 K(1, 2,  //
                0, 3);

    K.inverse().display();

    string message = "thankyou";
    string clip = encrypt(message, K);
    cout << "密文：" << clip << endl;

    cout << "明文：" << decrypt(clip, K) << endl;
    return 0;
}

输出结果如下：

1
2
3
4
27, -18
0, 9
密文：hvanguci
明文：thankyou