Hill Cipher

Definition

Definition

The Hill Cipher is a polygraphic substitution cipher based on linear algebra. It operates on blocks of plaintext letters, typically 2 or 3 at a time, and uses modular arithmetic for encryption and decryption

Explanation

To begin the Hill Cipher algorithm, select a key matrix that is invertible modulo the alphabet size, typically 26 for English. Each letter in the plaintext is assigned a numerical value based on its position in the alphabet (A=0, B=1, ..., Z=25). The plaintext is then divided into blocks of the same size as the key matrix. During encryption, each plaintext block is multiplied by the key matrix modulo the alphabet size. For decryption, the block is multiplied by the inverse of the key matrix. Finally, the resulting numerical values are converted back into letters to generate the ciphertext

Guidance

• Choose a key matrix, ensuring it is invertible modulo the alphabet size
• Represent each plaintext letter by its numerical equivalent
• Break the plaintext into blocks of the same size as the key matrix
  • for each block
    • multiply the block by the key matrix modulo the alphabet size
    • convert the resulting numbers back to letters
• Concatenate the encrypted blocks to form the ciphertext

Tips

• ensure the key matrix is invertible modulo the alphabet size to enable decryption
• if the key matrix is not invertible, choose another key matrix
• the size of the key matrix determines the size of the blocks of plaintext that can be encrypted or decrypted

Practice

Practice

hillCipher(plaintext, keyMatrix, alphabetSize):
  ciphertext = ""
  for each block in plaintext:
    numericalBlock = convertToNumerical(block)
    encryptedBlock = multiplyMatrix(keyMatrix, numericalBlock, alphabetSize)
    ciphertext += convertToLetters(encryptedBlock)
  return ciphertext

multiplyMatrix(keyMatrix, block, alphabetSize):
  result = []
  for row in keyMatrix:
    value = 0
    for i in range(len(row)):
      value += row[i] * block[i]
    result.append(value % alphabetSize)
  return result

convertToNumerical(block):
  numericalBlock = []
  for letter in block:
    numericalBlock.append(letterToNumber(letter))
  return numericalBlock

convertToLetters(block):
  letters = ""
  for num in block:
    letters += numberToLetter(num)
  return letters

Solution

package main

import (
    "math"
)

// Define the key matrix
var keyMatrix [][]int

// Function to initialize the key matrix
func initializeKeyMatrix(key string, size int) {
    keyMatrix = make([][]int, size)
    for i := range keyMatrix {
        keyMatrix[i] = make([]int, size)
    }

    // Fill the key matrix with values from the key string
    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            keyMatrix[i][j] = int(key[i*size+j]) - 65 // Assuming uppercase English letters
        }
    }
}

// Function to calculate the determinant of a matrix
func determinant(matrix [][]int, size int) int {
    if size == 1 {
        return matrix[0][0]
    }
    if size == 2 {
        return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]
    }

    det := 0
    for i := 0; i < size; i++ {
        minor := make([][]int, size-1)
        for j := range minor {
            minor[j] = make([]int, size-1)
        }

        for j := 1; j < size; j++ {
            for k := 0; k < size; k++ {
                if k < i {
                    minor[j-1][k] = matrix[j][k]
                } else if k > i {
                    minor[j-1][k-1] = matrix[j][k]
                }
            }
        }
        det += int(math.Pow(-1, float64(i))) * matrix[0][i] * determinant(minor, size-1)
    }
    return det
}

// Function to calculate the modulo inverse of a number
func modInverse(a, m int) int {
    a %= m
    for x := 1; x < m; x++ {
        if (a*x)%m == 1 {
            return x
        }
    }
    return 1
}

// Function to calculate the cofactor matrix of a matrix
func cofactor(matrix [][]int, size int) [][]int {
    cofactorMatrix := make([][]int, size)
    for i := range cofactorMatrix {
        cofactorMatrix[i] = make([]int, size)
    }

    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            minor := make([][]int, size-1)
            for k := range minor {
                minor[k] = make([]int, size-1)
            }

            for x := 0; x < size; x++ {
                for y := 0; y < size; y++ {
                    if x != i && y != j {
                        minorX, minorY := 0, 0
                        if x < i {
                            minorX = x
                        } else {
                            minorX = x - 1
                        }
                        if y < j {
                            minorY = y
                        } else {
                            minorY = y - 1
                        }
                        minor[minorX][minorY] = matrix[x][y]
                    }
                }
            }
            cofactorMatrix[i][j] = int(math.Pow(-1, float64(i+j))) * determinant(minor, size-1)
        }
    }
    return cofactorMatrix
}

// Function to transpose a matrix
func transpose(matrix [][]int, size int) [][]int {
    transposed := make([][]int, size)
    for i := range transposed {
        transposed[i] = make([]int, size)
    }

    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            transposed[i][j] = matrix[j][i]
        }
    }
    return transposed
}

// Function to multiply two matrices
func multiplyMatrices(matrix1, matrix2 [][]int, size int) [][]int {
    result := make([][]int, size)
    for i := range result {
        result[i] = make([]int, size)
    }

    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            for k := 0; k < size; k++ {
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            }
            result[i][j] %= 26
        }
    }
    return result
}

// Function to encrypt a message using Hill Cipher
func encrypt(message string) string {
    size := len(keyMatrix)
    paddedMessage := message
    if len(message)%size != 0 {
        // Padding the message with 'X' if its length is not divisible by the key matrix size
        paddedMessage += string('X' * (size - len(message)%size))
    }

    encryptedMessage := ""
    for i := 0; i < len(paddedMessage); i += size {
        segment := paddedMessage[i : i+size]
        segmentMatrix := make([][]int, size)
        for j := range segmentMatrix {
            segmentMatrix[j] = make([]int, 1)
        }

        for j := 0; j < size; j++ {
            segmentMatrix[j][0] = int(segment[j]) - 65 // Assuming uppercase English letters
        }

        encryptedSegmentMatrix := multiplyMatrices(keyMatrix, segmentMatrix, size)

        for j := 0; j < size; j++ {
            encryptedMessage += string(encryptedSegmentMatrix[j][0] + 65)
        }
    }
    return encryptedMessage
}

// Function to decrypt a message using Hill Cipher
func decrypt(encryptedMessage string) string {
    size := len(keyMatrix)

    inverseDet := modInverse(determinant(keyMatrix, size), 26)
    if inverseDet == 0 {
        return "Key is not invertible"
    }

    keyMatrixInverse := cofactor(keyMatrix, size)
    keyMatrixInverse = transpose(keyMatrixInverse, size)

    for i := range keyMatrixInverse {
        for j := range keyMatrixInverse[i] {
            keyMatrixInverse[i][j] = (keyMatrixInverse[i][j] * inverseDet) % 26
            if keyMatrixInverse[i][j] < 0 {
                keyMatrixInverse[i][j] += 26
            }
        }
    }

    decryptedMessage := ""
    for i := 0; i < len(encryptedMessage); i += size {
        segment := encryptedMessage[i : i+size]
        segmentMatrix := make([][]int, size)
        for j := range segmentMatrix {
            segmentMatrix[j] = make([]int, 1)
        }

        for j := 0; j < size; j++ {
            segmentMatrix[j][0] = int(segment[j]) - 65 // Assuming uppercase English letters
        }

        decryptedSegmentMatrix := multiplyMatrices(keyMatrixInverse, segmentMatrix, size)

        for j := 0; j < size; j++ {
            decryptedMessage += string(decryptedSegmentMatrix[j][0] + 65)
        }
    }
    return decryptedMessage
}

import java.util.Scanner;

public class HillCipher {

  private static int[][] keyMatrix;

  // Function to initialize the key matrix
  private static void initializeKeyMatrix(String key, int size) {
    keyMatrix = new int[size][size];

    // Fill the key matrix with values from the key string
    int index = 0;
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        keyMatrix[i][j] = key.charAt(index++) - 'A'; // Assuming uppercase English letters
      }
    }
  }

  // Function to calculate the determinant of a matrix
  private static int determinant(int[][] matrix, int size) {
    if (size == 1) {
      return matrix[0][0];
    }
    if (size == 2) {
      return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
    }

    int det = 0;
    for (int i = 0; i < size; i++) {
      int[][] minor = new int[size - 1][size - 1];
      for (int j = 1; j < size; j++) {
        for (int k = 0; k < size; k++) {
          if (k < i) {
            minor[j - 1][k] = matrix[j][k];
          } else if (k > i) {
            minor[j - 1][k - 1] = matrix[j][k];
          }
        }
      }
      det += Math.pow(-1, i) * matrix[0][i] * determinant(minor, size - 1);
    }
    return det;
  }

  // Function to calculate the modulo inverse of a number
  private static int modInverse(int a, int m) {
    a %= m;
    for (int x = 1; x < m; x++) {
      if ((a * x) % m == 1) {
        return x;
      }
    }
    return 1;
  }

  // Function to calculate the cofactor matrix of a matrix
  private static int[][] cofactor(int[][] matrix, int size) {
    int[][] cofactorMatrix = new int[size][size];

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        int[][] minor = new int[size - 1][size - 1];
        for (int x = 0; x < size; x++) {
          for (int y = 0; y < size; y++) {
            if (x != i && y != j) {
              int minorX = (x < i) ? x : x - 1;
              int minorY = (y < j) ? y : y - 1;
              minor[minorX][minorY] = matrix[x][y];
            }
          }
        }
        cofactorMatrix[i][j] = (int) (Math.pow(-1, i + j) * determinant(minor, size - 1));
      }
    }
    return cofactorMatrix;
  }

  // Function to transpose a matrix
  private static int[][] transpose(int[][] matrix, int size) {
    int[][] transposed = new int[size][size];

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        transposed[i][j] = matrix[j][i];
      }
    }
    return transposed;
  }

  // Function to multiply two matrices
  private static int[][] multiplyMatrices(int[][] matrix1, int[][] matrix2, int size) {
    int[][] result = new int[size][size];

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        for (int k = 0; k < size; k++) {
          result[i][j] += matrix1[i][k] * matrix2[k][j];
        }
        result[i][j] %= 26; // Mod 26 operation for letters
      }
    }
    return result;
  }

  // Function to encrypt a message using Hill Cipher
  private static String encrypt(String message, int size) {
    String paddedMessage = message;
    if (message.length() % size != 0) {
      // Padding the message with 'X' if its length is not divisible by the key matrix size
      paddedMessage += new String(new char[size - message.length() % size]).replace('\0', 'X');
    }

    StringBuilder encryptedMessage = new StringBuilder();
    for (int i = 0; i < paddedMessage.length(); i += size) {
      String segment = paddedMessage.substring(i, i + size);
      int[][] segmentMatrix = new int[size][1];

      for (int j = 0; j < size; j++) {
        segmentMatrix[j][0] = segment.charAt(j) - 'A'; // Assuming uppercase English letters
      }

      int[][] encryptedSegmentMatrix = multiplyMatrices(keyMatrix, segmentMatrix, size);

      for (int[] row : encryptedSegmentMatrix) {
        encryptedMessage.append((char) (row[0] + 'A')); // Convert to character
      }
    }
    return encryptedMessage.toString();
  }

  // Function to decrypt a message using Hill Cipher
  private static String decrypt(String encryptedMessage, int size) {
    int inverseDet = modInverse(determinant(keyMatrix, size), 26);
    if (inverseDet == 0) {
      return "Key is not invertible";
    }

    int[][] keyMatrixInverse = cofactor(keyMatrix, size);
    keyMatrixInverse = transpose(keyMatrixInverse, size);

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        keyMatrixInverse[i][j] = (keyMatrixInverse[i][j] * inverseDet) % 26;
        if (keyMatrixInverse[i][j] < 0) {
          keyMatrixInverse[i][j] += 26;
        }
      }
    }

    StringBuilder decryptedMessage = new StringBuilder();
    for (int i = 0; i < encryptedMessage.length(); i += size) {
      String segment = encryptedMessage.substring(i, i + size);
      int[][] segmentMatrix = new int[size][1];

      for (int j = 0; j < size; j++) {
        segmentMatrix[j][0] = segment.charAt(j) - 'A'; // Assuming uppercase English letters
      }

      int[][] decryptedSegmentMatrix = multiplyMatrices(keyMatrixInverse, segmentMatrix, size);

      for (int[] row : decryptedSegmentMatrix) {
        decryptedMessage.append((char) (row[0] + 'A')); // Convert to character
      }
    }
    return decryptedMessage.toString();
  }
}

// Function to initialize the key matrix
function initializeKeyMatrix(key, size) {
  const keyMatrix = [];
  let index = 0;
  for (let i = 0; i < size; i++) {
    keyMatrix.push([]);
    for (let j = 0; j < size; j++) {
      keyMatrix[i].push(key.charCodeAt(index++) - 65); // Assuming uppercase English letters
    }
  }
  return keyMatrix;
}

// Function to calculate the determinant of a matrix
function determinant(matrix) {
  const size = matrix.length;
  if (size === 1) {
    return matrix[0][0];
  }
  if (size === 2) {
    return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
  }

  let det = 0;
  for (let i = 0; i < size; i++) {
    const minor = [];
    for (let j = 1; j < size; j++) {
      minor.push(matrix[j].filter((_, index) => index !== i));
    }
    det += Math.pow(-1, i) * matrix[0][i] * determinant(minor);
  }
  return det;
}

// Function to calculate the modulo inverse of a number
function modInverse(a, m) {
  a %= m;
  for (let x = 1; x < m; x++) {
    if ((a * x) % m === 1) {
      return x;
    }
  }
  return 1;
}

// Function to calculate the cofactor matrix of a matrix
function cofactor(matrix) {
  const size = matrix.length;
  const cofactorMatrix = [];
  for (let i = 0; i < size; i++) {
    cofactorMatrix.push([]);
    for (let j = 0; j < size; j++) {
      const minor = [];
      for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
          if (x !== i && y !== j) {
            minor.push(matrix[x][y]);
          }
        }
      }
      cofactorMatrix[i].push(Math.pow(-1, i + j) * determinant([minor]));
    }
  }
  return cofactorMatrix;
}

// Function to transpose a matrix
function transpose(matrix) {
  const size = matrix.length;
  const transposed = [];
  for (let i = 0; i < size; i++) {
    transposed.push([]);
    for (let j = 0; j < size; j++) {
      transposed[i].push(matrix[j][i]);
    }
  }
  return transposed;
}

// Function to multiply two matrices
function multiplyMatrices(matrix1, matrix2) {
  const size = matrix1.length;
  const result = [];
  for (let i = 0; i < size; i++) {
    result.push([]);
    for (let j = 0; j < size; j++) {
      let sum = 0;
      for (let k = 0; k < size; k++) {
        sum += matrix1[i][k] * matrix2[k][j];
      }
      result[i].push(sum % 26); // Mod 26 operation for letters
    }
  }
  return result;
}

// Function to encrypt a message using Hill Cipher
function encrypt(message, key) {
  const size = Math.sqrt(key.length);
  const keyMatrix = initializeKeyMatrix(key, size);
  const paddedMessage = message + "X".repeat(size - (message.length % size)); // Padding with 'X'
  let encryptedMessage = "";
  for (let i = 0; i < paddedMessage.length; i += size) {
    const segment = paddedMessage.substring(i, i + size);
    const segmentMatrix = segment
      .split("")
      .map((char) => char.charCodeAt() - 65); // Assuming uppercase English letters
    const encryptedSegmentMatrix = multiplyMatrices(
      [segmentMatrix],
      keyMatrix,
    )[0];
    encryptedMessage += encryptedSegmentMatrix
      .map((num) => String.fromCharCode(num + 65))
      .join(""); // Convert back to letters
  }
  return encryptedMessage;
}

// Function to decrypt a message using Hill Cipher
function decrypt(encryptedMessage, key) {
  const size = Math.sqrt(key.length);
  const keyMatrix = initializeKeyMatrix(key, size);
  const inverseDet = modInverse(determinant(keyMatrix), 26);
  if (inverseDet === 0) {
    return "Key is not invertible";
  }
  const keyMatrixInverse = transpose(cofactor(keyMatrix)).map((row) =>
    row.map((num) => (num * inverseDet) % 26),
  );
  let decryptedMessage = "";
  for (let i = 0; i < encryptedMessage.length; i += size) {
    const segment = encryptedMessage.substring(i, i + size);
    const segmentMatrix = segment
      .split("")
      .map((char) => char.charCodeAt() - 65); // Assuming uppercase English letters
    const decryptedSegmentMatrix = multiplyMatrices(
      [segmentMatrix],
      keyMatrixInverse,
    )[0];
    decryptedMessage += decryptedSegmentMatrix
      .map((num) => String.fromCharCode(((num + 26) % 26) + 65))
      .join(""); // Convert back to letters
  }
  return decryptedMessage;
}

import kotlin.math.pow

// Function to initialize the key matrix
fun initializeKeyMatrix(key: String, size: Int): Array<IntArray> {
    val keyMatrix = Array(size) { IntArray(size) }
    var index = 0
    for (i in 0 until size) {
        for (j in 0 until size) {
            keyMatrix[i][j] = key[index].toInt() - 65 // Assuming uppercase English letters
            index++
        }
    }
    return keyMatrix
}

// Function to calculate the determinant of a matrix
fun determinant(matrix: Array<IntArray>): Int {
    val size = matrix.size
    if (size == 1) {
        return matrix[0][0]
    }
    if (size == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
    }

    var det = 0
    for (i in 0 until size) {
        val minor = Array(size - 1) { IntArray(size - 1) }
        for (j in 1 until size) {
            for (k in 0 until size) {
                if (k < i) {
                    minor[j - 1][k] = matrix[j][k]
                } else if (k > i) {
                    minor[j - 1][k - 1] = matrix[j][k]
                }
            }
        }
        det += (-1.0).pow(i) * matrix[0][i] * determinant(minor)
    }
    return det.toInt()
}

// Function to calculate the modulo inverse of a number
fun modInverse(a: Int, m: Int): Int {
    var a = a
    a %= m
    for (x in 1 until m) {
        if (a * x % m == 1) {
            return x
        }
    }
    return 1
}

// Function to calculate the cofactor matrix of a matrix
fun cofactor(matrix: Array<IntArray>): Array<IntArray> {
    val size = matrix.size
    val cofactorMatrix = Array(size) { IntArray(size) }

    for (i in 0 until size) {
        for (j in 0 until size) {
            val minor = Array(size - 1) { IntArray(size - 1) }
            for (x in 0 until size) {
                for (y in 0 until size) {
                    if (x != i && y != j) {
                        val minorX = if (x < i) x else x - 1
                        val minorY = if (y < j) y else y - 1
                        minor[minorX][minorY] = matrix[x][y]
                    }
                }
            }
            cofactorMatrix[i][j] = (-1.0).pow(i + j) * determinant(minor)
        }
    }
    return cofactorMatrix
}

// Function to transpose a matrix
fun transpose(matrix: Array<IntArray>): Array<IntArray> {
    val size = matrix.size
    val transposed = Array(size) { IntArray(size) }

    for (i in 0 until size) {
        for (j in 0 until size) {
            transposed[i][j] = matrix[j][i]
        }
    }
    return transposed
}

// Function to multiply two matrices
fun multiplyMatrices(matrix1: Array<IntArray>, matrix2: Array<IntArray>): Array<IntArray> {
    val size = matrix1.size
    val result = Array(size) { IntArray(size) }

    for (i in 0 until size) {
        for (j in 0 until size) {
            for (k in 0 until size) {
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            }
            result[i][j] %= 26 // Mod 26 operation for letters
        }
    }
    return result
}

// Function to encrypt a message using Hill Cipher
fun encrypt(message: String, key: String): String {
    val size = kotlin.math.sqrt(key.length.toDouble()).toInt()
    val keyMatrix = initializeKeyMatrix(key, size)
    val paddedMessage = message + "X".repeat(size - (message.length % size)) // Padding with 'X'
    var encryptedMessage = ""
    for (i in paddedMessage.indices step size) {
        val segment = paddedMessage.substring(i, i + size)
        val segmentMatrix = segment.map { it.toInt() - 65 }.toIntArray() // Assuming uppercase English letters
        val encryptedSegmentMatrix = multiplyMatrices(keyMatrix, arrayOf(segmentMatrix))
        encryptedMessage += encryptedSegmentMatrix.flatten().joinToString("") { (it + 65).toChar().toString() } // Convert back to letters
    }
    return encryptedMessage
}

// Function to decrypt a message using Hill Cipher
fun decrypt(encryptedMessage: String, key: String): String {
    val size = kotlin.math.sqrt(key.length.toDouble()).toInt()
    val keyMatrix = initializeKeyMatrix(key, size)
    val inverseDet = modInverse(determinant(keyMatrix), 26)
    if (inverseDet == 0) {
        return "Key is not invertible"
    }
    val keyMatrixInverse = cofactor(keyMatrix).map { row -> row.map { (it * inverseDet) % 26 }.toIntArray() }
    var decryptedMessage = ""
    for (i in encryptedMessage.indices step size) {
        val segment = encryptedMessage.substring(i, i + size)
        val segmentMatrix = segment.map { it.toInt() - 65 }.toIntArray() // Assuming uppercase English letters
        val decryptedSegmentMatrix = multiplyMatrices(keyMatrixInverse, arrayOf(segmentMatrix))
        decryptedMessage += decryptedSegmentMatrix.flatten().joinToString("") { (it + 26) % 26 + 65 }.toInt().toChar().toString() // Convert back to letters
    }
    return decryptedMessage
}

import numpy as np

# Function to initialize the key matrix
def initialize_key_matrix(key, size):
    key_matrix = np.zeros((size, size), dtype=int)
    index = 0
    for i in range(size):
        for j in range(size):
            key_matrix[i][j] = ord(key[index]) - 65  # Assuming uppercase English letters
            index += 1
    return key_matrix

# Function to calculate the determinant of a matrix
def determinant(matrix):
    return int(round(np.linalg.det(matrix)))

# Function to calculate the modulo inverse of a number
def mod_inverse(a, m):
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return 1

# Function to calculate the cofactor matrix of a matrix
def cofactor(matrix):
    return np.linalg.inv(matrix).T * determinant(matrix)

# Function to encrypt a message using Hill Cipher
def encrypt(message, key):
    size = int(len(key) ** 0.5)
    key_matrix = initialize_key_matrix(key, size)
    encrypted_message = ""
    for i in range(0, len(message), size):
        segment = message[i:i + size]
        segment_matrix = np.array([[ord(char) - 65] for char in segment])  # Assuming uppercase English letters
        encrypted_segment_matrix = np.dot(key_matrix, segment_matrix) % 26  # Mod 26 operation for letters
        encrypted_segment = ''.join([chr(num[0] + 65) for num in encrypted_segment_matrix])  # Convert back to letters
        encrypted_message += encrypted_segment
    return encrypted_message

# Function to decrypt a message using Hill Cipher
def decrypt(encrypted_message, key):
    size = int(len(key) ** 0.5)
    key_matrix = initialize_key_matrix(key, size)
    inverse_det = mod_inverse(determinant(key_matrix), 26)
    if inverse_det == 0:
        return "Key is not invertible"
    key_matrix_inverse = cofactor(key_matrix) * inverse_det % 26  # Mod 26 operation for letters
    decrypted_message = ""
    for i in range(0, len(encrypted_message), size):
        segment = encrypted_message[i:i + size]
        segment_matrix = np.array([[ord(char) - 65] for char in segment])  # Assuming uppercase English letters
        decrypted_segment_matrix = np.dot(key_matrix_inverse, segment_matrix) % 26  # Mod 26 operation for letters
        decrypted_segment = ''.join([chr(num[0] + 65) for num in decrypted_segment_matrix])  # Convert back to letters
        decrypted_message += decrypted_segment
    return decrypted_message

use nalgebra::{Matrix, U2, U3};

// Function to initialize the key matrix
fn initialize_key_matrix(key: &str, size: usize) -> Matrix<i32, U3, U3> {
    let mut key_matrix = Matrix::<i32, U3, U3>::zeros();
    let mut index = 0;
    for i in 0..size {
        for j in 0..size {
            key_matrix[(i, j)] = key.chars().nth(index).unwrap() as i32 - 65; // Assuming uppercase English letters
            index += 1;
        }
    }
    key_matrix
}

// Function to calculate the determinant of a matrix
fn determinant(matrix: &Matrix<i32, U3, U3>) -> i32 {
    matrix.determinant()
}

// Function to calculate the modulo inverse of a number
fn mod_inverse(a: i32, m: i32) -> i32 {
    for x in 1..m {
        if (a * x) % m == 1 {
            return x;
        }
    }
    1
}

// Function to calculate the cofactor matrix of a matrix
fn cofactor(matrix: &Matrix<i32, U3, U3>) -> Matrix<i32, U3, U3> {
    matrix.adjoint().map(|x| x * (-1 as i32).powf((x.row + x.column) as f32))
}

// Function to multiply two matrices
fn multiply_matrices(matrix1: &Matrix<i32, U3, U3>, matrix2: &Matrix<i32, U3, U3>) -> Matrix<i32, U3, U3> {
    matrix1 * matrix2
}

// Function to encrypt a message using Hill Cipher
fn encrypt(message: &str, key: &str) -> String {
    let size = (key.len() as f64).sqrt() as usize;
    let key_matrix = initialize_key_matrix(key, size);
    let padded_message = format!("{}{}", message, "X".repeat(size - (message.len() % size))); // Padding with 'X'
    let mut encrypted_message = String::new();
    for i in (0..padded_message.len()).step_by(size) {
        let segment = &padded_message[i..(i + size)];
        let segment_matrix: Vec<i32> = segment.chars().map(|c| c as i32 - 65).collect(); // Assuming uppercase English letters
        let segment_matrix = Matrix::from_row_slice(size, 1, &segment_matrix);
        let encrypted_segment_matrix = multiply_matrices(&key_matrix, &segment_matrix);
        for j in 0..size {
            encrypted_message.push((encrypted_segment_matrix[(j, 0)] % 26 + 65) as u8 as char); // Convert back to letters
        }
    }
    encrypted_message
}

// Function to decrypt a message using Hill Cipher
fn decrypt(encrypted_message: &str, key: &str) -> String {
    let size = (key.len() as f64).sqrt() as usize;
    let key_matrix = initialize_key_matrix(key, size);
    let inverse_det = mod_inverse(determinant(&key_matrix), 26);
    if inverse_det == 0 {
        return String::from("Key is not invertible");
    }
    let key_matrix_inverse = cofactor(&key_matrix).map(|x| (x * inverse_det) % 26); // Mod 26 operation for letters
    let mut decrypted_message = String::new();
    for i in (0..encrypted_message.len()).step_by(size) {
        let segment = &encrypted_message[i..(i + size)];
        let segment_matrix: Vec<i32> = segment.chars().map(|c| c as i32 - 65).collect(); // Assuming uppercase English letters
        let segment_matrix = Matrix::from_row_slice(size, 1, &segment_matrix);
        let decrypted_segment_matrix = multiply_matrices(&key_matrix_inverse, &segment_matrix);
        for j in 0..size {
            decrypted_message.push((((decrypted_segment_matrix[(j, 0)] + 26) % 26) + 65) as u8 as char); // Convert back to letters
        }
    }
    decrypted_message
}

// Function to initialize the key matrix
function initializeKeyMatrix(key: string, size: number): number[][] {
  const keyMatrix: number[][] = [];
  let index = 0;
  for (let i = 0; i < size; i++) {
    keyMatrix.push([]);
    for (let j = 0; j < size; j++) {
      keyMatrix[i].push(key.charCodeAt(index++) - 65); // Assuming uppercase English letters
    }
  }
  return keyMatrix;
}

// Function to calculate the determinant of a matrix
function determinant(matrix: number[][]): number {
  const size = matrix.length;
  if (size === 1) {
    return matrix[0][0];
  }
  if (size === 2) {
    return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
  }

  let det = 0;
  for (let i = 0; i < size; i++) {
    const minor: number[][] = [];
    for (let j = 1; j < size; j++) {
      minor.push(matrix[j].filter((_, index) => index !== i));
    }
    det += (-1) ** i * matrix[0][i] * determinant(minor);
  }
  return det;
}

// Function to calculate the modulo inverse of a number
function modInverse(a: number, m: number): number {
  a %= m;
  for (let x = 1; x < m; x++) {
    if ((a * x) % m === 1) {
      return x;
    }
  }
  return 1;
}

// Function to calculate the cofactor matrix of a matrix
function cofactor(matrix: number[][]): number[][] {
  const size = matrix.length;
  const cofactorMatrix: number[][] = [];

  for (let i = 0; i < size; i++) {
    cofactorMatrix.push([]);
    for (let j = 0; j < size; j++) {
      const minor: number[][] = [];
      for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
          if (x !== i && y !== j) {
            minor.push(matrix[x][y]);
          }
        }
      }
      cofactorMatrix[i].push((-1) ** (i + j) * determinant(minor));
    }
  }
  return cofactorMatrix;
}

// Function to transpose a matrix
function transpose(matrix: number[][]): number[][] {
  const size = matrix.length;
  const transposed: number[][] = [];

  for (let i = 0; i < size; i++) {
    transposed.push([]);
    for (let j = 0; j < size; j++) {
      transposed[i][j] = matrix[j][i];
    }
  }
  return transposed;
}

// Function to multiply two matrices
function multiplyMatrices(
  matrix1: number[][],
  matrix2: number[][],
): number[][] {
  const size = matrix1.length;
  const result: number[][] = [];

  for (let i = 0; i < size; i++) {
    result.push([]);
    for (let j = 0; j < size; j++) {
      let sum = 0;
      for (let k = 0; k < size; k++) {
        sum += matrix1[i][k] * matrix2[k][j];
      }
      result[i][j] = sum % 26; // Mod 26 operation for letters
    }
  }
  return result;
}

// Function to encrypt a message using Hill Cipher
function encrypt(message: string, key: string): string {
  const size = Math.sqrt(key.length);
  const keyMatrix = initializeKeyMatrix(key, size);
  const paddedMessage = message + "X".repeat(size - (message.length % size)); // Padding with 'X'
  let encryptedMessage = "";
  for (let i = 0; i < paddedMessage.length; i += size) {
    const segment = paddedMessage.substring(i, i + size);
    const segmentMatrix = segment
      .split("")
      .map((char) => char.charCodeAt() - 65); // Assuming uppercase English letters
    const encryptedSegmentMatrix = multiplyMatrices(
      [segmentMatrix],
      keyMatrix,
    )[0];
    encryptedMessage += encryptedSegmentMatrix
      .map((num) => String.fromCharCode(num + 65))
      .join(""); // Convert back to letters
  }
  return encryptedMessage;
}

// Function to decrypt a message using Hill Cipher
function decrypt(encryptedMessage: string, key: string): string {
  const size = Math.sqrt(key.length);
  const keyMatrix = initializeKeyMatrix(key, size);
  const inverseDet = modInverse(determinant(keyMatrix), 26);
  if (inverseDet === 0) {
    return "Key is not invertible";
  }
  const keyMatrixInverse = cofactor(keyMatrix).map((row) =>
    row.map((num) => (num * inverseDet) % 26),
  );
  let decryptedMessage = "";
  for (let i = 0; i < encryptedMessage.length; i += size) {
    const segment = encryptedMessage.substring(i, i + size);
    const segmentMatrix = segment
      .split("")
      .map((char) => char.charCodeAt() - 65); // Assuming uppercase English letters
    const decryptedSegmentMatrix = multiplyMatrices(
      [segmentMatrix],
      keyMatrixInverse,
    )[0];
    decryptedMessage += decryptedSegmentMatrix
      .map((num) => String.fromCharCode(((num + 26) % 26) + 65))
      .join(""); // Convert back to letters
  }
  return decryptedMessage;
}