HillCipher.java

package project1;

public class HillCipher {

    // Encrypt using a key matrix
    public static String encrypt(String plaintext, int[][] keyMatrix) {
        StringBuilder cipher = new StringBuilder();

        int[][] plain_matrices = slice_plain(plaintext, 3);
        int[][] cipher_matrices = new int[plaintext.length()/3][3];

        cipher_matrices = multiplyMatrices(keyMatrix, plain_matrices);

        for (int i = 0; i < cipher_matrices.length; i++) {
            cipher.append(vectorToText(cipher_matrices[i]));
        }

        return cipher.toString().toUpperCase();
    }


    // Decrypt
    public static String decrypt(String ciphertext, int[][] keyMatrix) {
        int[][] inversedKeyMatrix = matrixInverse(keyMatrix);
        // Decryption is simply an encrypting but with inversed key
        return encrypt(ciphertext, inversedKeyMatrix).toLowerCase();
    }

    // take a text and convert it to matrix of vectors
    // using the method textToVector
    public static int[][] slice_plain(String plain, int part_len) {
        int plain_len = plain.length();
        // if text is not of a valid length fill it with filler letter "x"
        while (plain.length() % part_len != 0) {
            plain += (char)('x'-'a' + getBase(plain.charAt(0)));
            System.out.println(plain.length());
        }
        plain_len = plain.length(); // update length
        int[][] matrices = new int[plain_len/part_len][part_len];

        int part = 0; // parts iterator
        StringBuilder sb = new StringBuilder(); // string block

        for (int i = 0; i < plain_len; i++) {
            sb.append(plain.charAt(i));
            if ((i+1) % part_len  == 0) {
                // for each substring of size part_len convert it to a vector of one column to be a part of the plain/cipher matrices
                matrices[part++] = textToVector(sb.toString());
                sb.setLength(0);
            }
        }

        return matrices;
    }


    public static String vectorToText(int[] vector) {
        StringBuilder sb = new StringBuilder();
        for (int v : vector)
            sb.append((char) (v + 'a'));
        return sb.toString();
    }

    public static int[] textToVector(String block) {
        int[] int_block = new int[block.length()];
        for (int i = 0; i < block.length(); i++)
            int_block[i] = block.charAt(i) - getBase(block.charAt(i));
        return int_block;
    }


    public static int[][] multiplyMatrices(int[][] A, int[][] B) {
        int[][] multipliedMatrices = new int[B.length][B[0].length];
        // loop over the matrices and multiply row * column
        for (int i = 0; i < B.length; i++) {
            for (int j = 0; j < 3; j++) {
                int sum = 0;
                for (int k = 0; k < 3; k++)
                    sum += B[i][k] * A[j][k];

                multipliedMatrices[i][j] = sum % 26;
            }
        }
        return multipliedMatrices;
    }

    // determinant of a 3*3 matrix
    public static int determinant(int[][] 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]);
    }

    // check if the key matrix can be used in our hill cipher
    public static boolean isValidKey(int[][] keyMatrix) {
        if (keyMatrix.length != 3 || keyMatrix[0].length != 3)
            return false;
        int det = ((determinant(keyMatrix) % 26) + 26) % 26;
        // det must be coprime with 26
        return det != 0 && gcd(det, 26) == 1;
    }

    // inverse strictly for 3*3
    public static int[][] matrixInverse(int[][] m) {
        final int MOD = 26;

        int det = ((determinant(m) % MOD) + MOD) % MOD;

        int detInv = modInverse(det, MOD);

        int[][] adj = new int[3][3];
        adj[0][0] =  (m[1][1]*m[2][2] - m[1][2]*m[2][1]);
        adj[0][1] = -(m[0][1]*m[2][2] - m[0][2]*m[2][1]);
        adj[0][2] =  (m[0][1]*m[1][2] - m[0][2]*m[1][1]);
        adj[1][0] = -(m[1][0]*m[2][2] - m[1][2]*m[2][0]);
        adj[1][1] =  (m[0][0]*m[2][2] - m[0][2]*m[2][0]);
        adj[1][2] = -(m[0][0]*m[1][2] - m[0][2]*m[1][0]);
        adj[2][0] =  (m[1][0]*m[2][1] - m[1][1]*m[2][0]);
        adj[2][1] = -(m[0][0]*m[2][1] - m[0][1]*m[2][0]);
        adj[2][2] =  (m[0][0]*m[1][1] - m[0][1]*m[1][0]);

        int[][] inverse = new int[3][3];
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                inverse[i][j] = ((detInv * adj[i][j]) % MOD + MOD) % MOD;

        return inverse;
    }

    public static char getBase(char c) {
        return c >= 97 ? 'a':'A';
    }

    // EEA gcd in recursion
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static int modInverse(int a, int m) {
        // Based on EEA
        // A  |  B  |  R  |  Q  |  T  |  T1  |  T2(T - Q*T1)  |
        

        a = ((a % m) + m) % m;
        int t = 0, newT = 1, r = m, newR = a;
        while (newR != 0) {
            int q = r / newR;
            int tmp = t - q * newT; t = newT; 
            newT = tmp;
            tmp = r - q * newR; 
            r = newR; 
            newR = tmp;
        }
        if (r != 1) throw new ArithmeticException("No mod " + m);
        return (t % m + m) % m;
    }
}