Cài đặt Hill Cipher trong C++

Hill Cipher (Lester Hill, 1929) là mật mã đa đồ họa (polygraphic) dựa trên đại số tuyến tính. Mã hóa khối ký tự bằng phép nhân ma trận modulo 26.

Nguyên lý toán học

• Khóa: Ma trận vuông K kích thước n x n (độ dài khối = n).
• Yêu cầu: det(K) nguyên tố cùng nhau với 26 (gcd(det(K), 26) = 1) để ma trận khả nghịch modulo 26.
• Mã hóa: C = (K * P) mod 26 (P, C là vector cột).
• Giải mã: P = (K⁻¹ * C) mod 26.

Ví dụ n = 3

Khóa K = |1 0 1|   Bản rõ "ABC" = |0|   C = K*P mod 26 = |2| → "C"
         |2 4 0|                |1|                   |4|   "E"
         |3 5 6|                |2|                   |17|  "R"
Kết quả: "CER"

Chương trình hoàn chỉnh (n=3)

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

const int N = 3;
const int MOD = 26;

using Matrix = vector>; // Dùng double cho dễ tính nghịch đảo
using Vec = vector;

// Nhân ma trận * vector modulo 26
Vec mulMatVec(const Matrix& A, const Vec& v) {
    Vec res(N, 0);
    for (int i = 0; i < N; ++i)
        for (int k = 0; k < N; ++k)
            res[i] += A[i][k] * v[k];
    for (int i = 0; i < N; ++i)
        res[i] = fmod(res[i], MOD);
    return res;
}

// Nghịch đảo ma trận modulo 26 (Gauss-Jordan)
Matrix inverseMatrixMod(Matrix A) {
    Matrix inv(N, vector(N, 0));
    for (int i = 0; i < N; ++i) inv[i][i] = 1; // Ma trận đơn vị
    
    for (int col = 0; col < N; ++col) {
        // Tìm pivot
        int pivot = col;
        while (pivot < N && fmod(A[pivot][col], MOD) == 0) ++pivot;
        if (pivot == N) throw runtime_error("Ma tran khong kha nghich modulo 26");
        
        if (pivot != col) {
            swap(A[pivot], A[col]);
            swap(inv[pivot], inv[col]);
        }
        
        // Chuẩn hóa hàng pivot
        double pivotVal = A[col][col];
        // Tìm nghịch đảo modulo của pivotVal
        int pivotInv = -1;
        for (int x = 1; x < MOD; ++x)
            if (fmod(pivotVal * x, MOD) == 1) { pivotInv = x; break; }
        if (pivotInv == -1) throw runtime_error("Pivot khong co nghich dao");
        
        for (int j = 0; j < N; ++j) {
            A[col][j] = fmod(A[col][j] * pivotInv, MOD);
            inv[col][j] = fmod(inv[col][j] * pivotInv, MOD);
        }
        
        // Khử các hàng khác
        for (int i = 0; i < N; ++i) {
            if (i == col) continue;
            double factor = A[i][col];
            for (int j = 0; j < N; ++j) {
                A[i][j] = fmod(A[i][j] - factor * A[col][j], MOD);
                if (A[i][j] < 0) A[i][j] += MOD;
                inv[i][j] = fmod(inv[i][j] - factor * inv[col][j], MOD);
                if (inv[i][j] < 0) inv[i][j] += MOD;
            }
        }
    }
    return inv;
}

string encrypt(const Matrix& K, const string& plain) {
    Vec p(N);
    for (int i = 0; i < N; ++i) p[i] = plain[i] - 'A';
    Vec c = mulMatVec(K, p);
    string res;
    for (int i = 0; i < N; ++i) res += char('A' + int(round(c[i])));
    return res;
}

string decrypt(const Matrix& K_inv, const string& cipher) {
    Vec c(N);
    for (int i = 0; i < N; ++i) c[i] = cipher[i] - 'A';
    Vec p = mulMatVec(K_inv, c);
    string res;
    for (int i = 0; i < N; ++i) res += char('A' + int(round(p[i])));
    return res;
}

int main() {
    Matrix K = {{1, 0, 1},
                {2, 4, 0},
                {3, 5, 6}};
    
    string plain = "ABC";
    cout << "Ban ro: " << plain << '\n';
    
    string cipher = encrypt(K, plain);
    cout << "Ban ma: " << cipher << '\n';
    
    try {
        Matrix K_inv = inverseMatrixMod(K);
        cout << "Ma tran nghich dao:\n";
        for (auto& row : K_inv) {
            for (double v : row) cout << setw(10) << v;
            cout << '\n';
        }
        string decrypted = decrypt(K_inv, cipher);
        cout << "Giai ma: " << decrypted << '\n';
    } catch (exception& e) {
        cerr << "Loi: " << e.what() << '\n';
    }
    return 0;
}

Kết quả

Ban ro: ABC
Ban ma: CER
Ma tran nghich dao:
   1.09091   0.227273  -0.181818
  -0.545455   0.136364   0.0909091
  -0.0909091 -0.227273   0.181818
Giai ma: ABC

Lưu ý quan trọng

• Ma trận khóa phải khả nghịch modulo 26 — không phải mọi ma trận đều dùng được.
• Triển khai trên dùng double để đơn giản hóa Gauss-Jordan; thực tế nên dùng số nguyên modulo (integer arithmetic) để tránh lỗi làm tròn.
• Padding: Nếu độ dài bản rõ không chia hết n, padding bằng 'X' hoặc 'Z'.
• Mở rộng: Chữ thường, khoảng trắng, ký tự đặc biệt → mở rộng modulo (ví dụ 52, 64, 95).

Bảo mật

• Kháng cự phân tích tần suất đơn biến (do mã hóa khối).
• Yếu trước tấn công known-plaintext (nắm được n cặp plaintext-ciphertext → giải hệ tuyến tính tìm K).
• Chỉ dùng cho mục đích học tập.

Hill Cipher là ví dụ điển hình ứng dụng đại số tuyến tính trong mật mã học, tiền đề cho các mật mã khối hiện đại (AES cũng dùng phép biến đổi tuyến tính trên trường Galois).