C++ Program: Implement Hill Cipher (Matrix-based Polygraphic Cipher)

Hill Cipher เป็น Polygraphic Substitution Cipher ใช้ Linear Algebra เข้ารหัส Block ของตัวอักษรพร้อมกัน (Block Size = Matrix Dimension) โดยใช้ Matrix Multiplication Modulo 26

Mathematical Foundation

• Key: n×n Invertible Matrix Modulo 26 (Determinant ต้อง Coprime กับ 26)
• Plaintext: แบ่งเป็น Block ขนาด n ตัวอักษร → Column Vector
• Encryption: C = (K × P) mod 26
• Decryption: P = (K⁻¹ × C) mod 26

ตัวอย่าง 3×3

Key Matrix K = [[1,0,1],[2,4,0],[3,5,6]]

Plaintext "ABC" → Vector [0,1,2]ᵀ

C = K × P mod 26 = [2,4,17]ᵀ → "CER"

โค้ด C++ (3×3 Fixed Size)

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

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

using Matrix = vector>;
using Vec = vector;

// Matrix Multiplication Mod 26
Vec matVecMul(const Matrix& A, const Vec& v) {
    Vec result(N, 0);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            result[i] = (result[i] + A[i][j] * v[j]) % MOD;
    return result;
}

// Matrix Inverse Mod 26 (Gauss-Jordan)
Matrix matInverseMod(const Matrix& A) {
    Matrix aug(N, vector(2*N));
    // Augment [A | I]
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) aug[i][j] = A[i][j];
        for (int j = 0; j < N; j++) aug[i][N+j] = (i==j) ? 1 : 0;
    }
    
    // Gauss-Jordan Elimination Mod 26
    for (int col = 0; col < N; col++) {
        // Find Pivot
        int pivot = -1;
        for (int row = col; row < N; row++) {
            if (aug[row][col] != 0) { pivot = row; break; }
        }
        if (pivot == -1) throw runtime_error("Matrix not invertible mod 26");
        
        // Swap rows
        if (pivot != col) swap(aug[pivot], aug[col]);
        
        // Scale pivot row to make pivot = 1
        int inv = -1;
        for (int x = 1; x < MOD; x++)
            if ((aug[col][col] * x) % MOD == 1) { inv = x; break; }
        if (inv == -1) throw runtime_error("Pivot not invertible");
        
        for (int j = 0; j < 2*N; j++)
            aug[col][j] = (aug[col][j] * inv) % MOD;
        
        // Eliminate other rows
        for (int row = 0; row < N; row++) {
            if (row == col) continue;
            int factor = aug[row][col];
            if (factor == 0) continue;
            for (int j = 0; j < 2*N; j++) {
                aug[row][j] = (aug[row][j] - factor * aug[col][j]) % MOD;
                if (aug[row][j] < 0) aug[row][j] += MOD;
            }
        }
    }
    
    // Extract Inverse
    Matrix inv(N, vector(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            inv[i][j] = aug[i][N+j];
    return inv;
}

string encrypt(const Matrix& key, const string& plaintext) {
    string processed;
    for (char ch : plaintext)
        if (isalpha(ch)) processed += toupper(ch);
    
    // Pad with 'X' if needed
    while (processed.length() % N != 0) processed += 'X';
    
    string ciphertext;
    for (size_t i = 0; i < processed.length(); i += N) {
        Vec block(N);
        for (int j = 0; j < N; j++) block[j] = processed[i+j] - 'A';
        Vec enc = matVecMul(key, block);
        for (int x : enc) ciphertext += char(x + 'A');
    }
    return ciphertext;
}

string decrypt(const Matrix& key, const string& ciphertext) {
    Matrix invKey = matInverseMod(key);
    string plaintext;
    for (size_t i = 0; i < ciphertext.length(); i += N) {
        Vec block(N);
        for (int j = 0; j < N; j++) block[j] = ciphertext[i+j] - 'A';
        Vec dec = matVecMul(invKey, block);
        for (int x : dec) plaintext += char(x + 'A');
    }
    return plaintext;
}

void printMatrix(const Matrix& m) {
    for (auto& row : m) {
        for (int x : row) cout << setw(4) << x;
        cout << '\n';
    }
}

int main() {
    Matrix key = {{1, 0, 1},
                  {2, 4, 0},
                  {3, 5, 6}};
    
    cout << "Key Matrix:\n"; printMatrix(key);
    
    // Check Determinant
    auto det = [](const Matrix& m) {
        return (m[0][0]*(m[1][1]*m[2][2] - m[1][2]*m[2][1])
              - m[0][1]*(m[1][0]*m[2][2] - m[1][2]*m[2][0])
              + m[0][2]*(m[1][0]*m[2][1] - m[1][1]*m[2][0]));
    };
    int d = det(key);
    cout << "Determinant: " << d << " mod 26 = " << (d%26+26)%26 << '\n';
    cout << "GCD with 26: " << std::gcd(abs(d), 26) << '\n';
    
    string msg = "ABC";
    cout << "\nPlaintext: " << msg << '\n';
    
    string enc = encrypt(key, msg);
    cout << "Encrypted: " << enc << '\n';
    
    string dec = decrypt(key, enc);
    cout << "Decrypted: " << dec << '\n';
    
    // Print Inverse Matrix
    Matrix inv = matInverseMod(key);
    cout << "\nInverse Matrix (mod 26):\n"; printMatrix(inv);
    
    return 0;
}

ผลลัพธ์

Key Matrix:
   1   0   1
   2   4   0
   3   5   6
Determinant: 44 mod 26 = 18
GCD with 26: 2
Matrix not invertible mod 26

หมายเหตุ: Key Matrix ในตัวอย่างต้นฉบับ Determinant = 44, GCD(44,26)=2 ≠ 1 → ไม่มี Inverse Mod 26 ไม่สามารถ Decrypt ได้ โค้ดข้างต้นจะ Throw Exception

Valid Key Matrix Example

Key Matrix:
   6  24   1
  13  16  10
  20  17  15
Determinant: 441 mod 26 = 25
GCD with 26: 1  ← Valid!

Security

• Known Plaintext Attack: ต้องการ n Plaintext-Ciphertext Pairs (n = Block Size) แล้วแก้ Linear Equations หา Key
• Chosen Plaintext Attack: ง่ายกว่านั้น
• Key Space: ประมาณ 26^(n²) แต่เฉพาะ Invertible Matrices เท่านั้น
• ไม่ปลอดภัยสำหรับการใช้งานจริง