Java Program for Hill Cipher Using Matrix Multiplication

Introduction

The Hill cipher was invented in 1929 by the American mathematician Lester S. Hill, a professor at City College of New York. It was the first cipher to use mathematics from linear algebra, specifically matrix multiplication over a finite field, to encrypt data. Hill published his invention in the journal American Mathematical Monthly and built a mechanical machine with gears and chains to perform the matrix multiplications automatically. In this hill cipher java tutorial we will implement the full algorithm in pure Java.

The Hill cipher matters historically because it was the first practical example of using serious mathematics in cryptography. Until Hill, ciphers were largely combinatorial and rule-based. Hill showed that linear algebra could be used as a cryptographic primitive, an idea that ultimately led to modern ciphers built on number theory and finite fields. Although the basic Hill cipher itself is now broken, its design philosophy is alive and well.

What is the Hill Cipher?

The Hill cipher is a polygraphic substitution cipher that uses matrix multiplication. To encrypt, we treat blocks of n plaintext letters as a column vector, multiply it by an n by n invertible key matrix, and take each entry modulo 26. The result is a column vector of ciphertext letters. Decryption uses the inverse of the key matrix, computed modulo 26.

For Hill to work, the key matrix must be invertible modulo 26. That means its determinant must be coprime with 26 (not divisible by 2 or 13). This is a stricter condition than ordinary invertibility. Not every random matrix will work as a Hill key.

Compared to Playfair, which works on digraphs (pairs), Hill can work on blocks of any size. A 2 by 2 Hill cipher works on digraphs, a 3 by 3 Hill cipher works on trigraphs (triples), and so on. The larger the block, the more resistant the cipher is to frequency analysis.

How the Hill Cipher Works Step by Step

Suppose our 2 by 2 key matrix is: [3 3] [2 5] and our plaintext is HI.

Step 1: Convert each plaintext letter to a number from 0 (A) to 25 (Z). H = 7, I = 8. We arrange these as a column vector: [7, 8] (written vertically).

Step 2: Multiply the key matrix by the plaintext vector, then take each entry modulo 26. Row 1: (3 * 7) + (3 * 8) = 21 + 24 = 45. Then 45 mod 26 = 19. Row 2: (2 * 7) + (5 * 8) = 14 + 40 = 54. Then 54 mod 26 = 2.

Step 3: Convert the result back to letters. 19 is T, 2 is C. So HI encrypts to TC.

Step 4: To decrypt, we need the inverse of the key matrix modulo 26. The determinant is (3 * 5) - (3 * 2) = 15 - 6 = 9. The modular inverse of 9 modulo 26 is 3 because 9 * 3 = 27 = 1 mod 26. The inverse of the matrix is 3 times the adjugate, which for a 2 by 2 matrix is the matrix with the diagonal swapped and the off-diagonal negated.

Step 5: Multiply the inverse matrix by the ciphertext vector modulo 26 to recover the plaintext. TC decrypts back to HI.

Java Program for Hill Cipher

public class HillCipher {

    static int[][] key = {{3, 3}, {2, 5}};

    public static int mod(int a, int m) {
        return ((a % m) + m) % m;
    }

    public static int modInverse(int a, int m) {
        a = mod(a, m);
        for (int x = 1; x < m; x++) {
            if (mod(a * x, m) == 1) return x;
        }
        throw new IllegalArgumentException("No modular inverse exists");
    }

    public static int determinant(int[][] m) {
        return m[0][0] * m[1][1] - m[0][1] * m[1][0];
    }

    public static int[][] inverseKey(int[][] k) {
        int det = determinant(k);
        int detInv = modInverse(det, 26);
        int[][] inv = new int[2][2];
        inv[0][0] = mod(detInv * k[1][1], 26);
        inv[0][1] = mod(detInv * (-k[0][1]), 26);
        inv[1][0] = mod(detInv * (-k[1][0]), 26);
        inv[1][1] = mod(detInv * k[0][0], 26);
        return inv;
    }

    public static String encrypt(String text, int[][] k) {
        text = text.toUpperCase().replaceAll("[^A-Z]", "").replace("J", "I");
        while (text.length() % 2 != 0) text += "X";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < text.length(); i += 2) {
            int p1 = text.charAt(i) - 'A';
            int p2 = text.charAt(i + 1) - 'A';
            int c1 = mod(k[0][0] * p1 + k[0][1] * p2, 26);
            int c2 = mod(k[1][0] * p1 + k[1][1] * p2, 26);
            sb.append((char) (c1 + 'A'));
            sb.append((char) (c2 + 'A'));
        }
        return sb.toString();
    }

    public static String decrypt(String text, int[][] k) {
        return encrypt(text, inverseKey(k));
    }

    public static void main(String[] args) {
        String plain = "HI";
        String cipher = encrypt(plain, key);
        String recovered = decrypt(cipher, key);
        System.out.println("Plain   : " + plain);
        System.out.println("Cipher  : " + cipher);
        System.out.println("Decoded : " + recovered);
    }
}

Code Explanation Line by Line

The mod helper method implements true mathematical modulo that always returns a non-negative result. This is needed because Java's % can return negative values, and our matrix arithmetic produces negative intermediate values.

The modInverse method finds the integer x in the range 1 to m such that (a * x) mod m equals 1. We do this with a simple linear search, which is fine for the small modulus 26. For larger moduli you would use the extended Euclidean algorithm.

The determinant method computes the determinant of a 2 by 2 matrix using the standard formula ad - bc. For a 3 by 3 matrix you would use the rule of Sarrus or cofactor expansion, but the 2 by 2 case is sufficient for a tutorial implementation.

The inverseKey method inverts a 2 by 2 matrix modulo 26. We compute the determinant, find its modular inverse, then multiply the adjugate matrix by the determinant inverse. For a 2 by 2 matrix the adjugate is the matrix with the diagonal swapped and the off-diagonal entries negated.

The encrypt method cleans the plaintext by uppercasing, stripping non-letters, and replacing J with I. It pads with X until the length is even. Then it processes the text two letters at a time, multiplying the 2 by 2 key matrix by the 2 by 1 plaintext vector modulo 26 to get the ciphertext vector.

The decrypt method is beautiful in its simplicity: it just calls encrypt with the inverse of the key matrix. This is the same mathematical trick that made Caesar decryption so compact. The elegance of linear algebra shines through here.

Sample Input and Output

Plain   : HI
Cipher  : TC
Decoded : HI

The output matches our manual calculation. The 2 by 2 matrix multiplied by the column vector [7, 8] gives the column vector [19, 2], which corresponds to the letters T and C. Decryption perfectly recovers the original HI.

Common Mistakes to Avoid

1. Using a non-invertible matrix. If the determinant is even or divisible by 13, the matrix has no inverse modulo 26 and decryption is impossible. Always check the determinant first.

2. Forgetting to take modulo after each multiplication. Without modulo, the intermediate values grow quickly and the encrypted letters fall outside the 0 to 25 range, producing garbage.

3. Using Java's % instead of true modulo. For negative numbers, % returns a negative result, which then breaks letter conversion. Always wrap with the mod helper.

4. Not padding the plaintext to a multiple of the block size. If the length is not a multiple of n, the last block is incomplete and the matrix multiplication fails.

5. Confusing row and column ordering when building the plaintext vector. The Hill cipher conventionally uses column vectors, so the plaintext vector is vertical and the matrix is on the left.

Real-World Applications

The Hill cipher is not used in modern security products because it is vulnerable to known-plaintext attacks. If an attacker has both a plaintext and its matching ciphertext, they can solve for the key matrix using linear algebra. This weakness makes the cipher unsuitable for any real-world threat model.

However, Hill's contribution to cryptography is enormous. The idea of using matrix multiplication over a finite field directly inspired modern ciphers like AES, which uses a similar mathematical structure in its MixColumns step. The 4 by 4 matrix used in AES MixColumns operates over the finite field GF(2^8) and is conceptually a descendant of Hill's idea.

In educational settings, the Hill cipher is a wonderful teaching tool because it combines linear algebra with number theory. Students learn modular arithmetic, matrix inversion, determinants, and the importance of coprimality, all in a single short program. CTF competitions occasionally include Hill cipher puzzles, usually with a 2 by 2 or 3 by 3 key, as a test of mathematical maturity.

Conclusion

In this hill cipher java tutorial we built a complete matrix-based polygraphic cipher, computed modular matrix inverses, and explained the linear algebra behind the encryption. You now understand polygraphic substitution, modular arithmetic over matrices, and the importance of an invertible key. Next, study transposition ciphers like columnar transposition, which work by rearranging letters rather than replacing them.