Hill Cipher
Algorithm · Stretch
The Hill cipher is a polygraphic substitution cipher based on linear algebra.
Each letter is represented by a number modulo 26. Though this is not an essential feature of the cipher, this simple scheme is often used:
| Letter | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Number | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Encryption
To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, against modulus 26.
The matrix used for encryption is the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo 26). The cipher can, of course, be adapted to an alphabet with any number of letters; all arithmetic just needs to be done modulo the number of letters instead of modulo 26.
Consider the message ACT, and the key below (or GYB/NQK/URP in letters):
| 6 24 1 |
| 13 16 10 |
| 20 17 15 |Since A is0, C is 2 and T is 19, the message is the vector:
| 0 |
| 2 |
| 19 |Thus, the enciphered vector is given by:
| 6 24 1 | | 0 | | 67 | | 15 |
| 13 16 10 | | 2 | = | 222 | ≡ | 14 | (mod 26)
| 20 17 15 | | 19 | | 319 | | 7 |which corresponds to a ciphertext of POH.
Now, suppose that our message is instead CAT (notice how we're using the same letters as in ACT here), or:
| 2 |
| 0 |
| 19 |This time, the enciphered vector is given by:
| 6 24 1 | | 2 | | 31 | | 5 |
| 13 16 10 | | 0 | = | 216 | ≡ | 8 | (mod 26)
| 20 17 15 | | 19 | | 325 | | 13 |which corresponds to a ciphertext of FIN. Every letter has changed.
Decryption
To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. We turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFK/VIV/VMI in letters). (See matrix inversion for methods to calculate the inverse matrix.) We find that, modulo 26, the inverse of the matrix used in the previous example is:
-1
| 6 24 1 | | 8 5 10 |
| 13 16 10 | (mod 26) ≡ | 21 8 21 |
| 20 17 15 | | 21 12 8 |Taking the previous example ciphertext of POH, we get:
| 8 5 10 | | 15 | | 260 | | 0 |
| 21 8 21 | | 14 | = | 574 | ≡ | 2 | (mod 26)
| 21 12 8 | | 7 | | 539 | | 19 |which gets us back to ACT, as expected.
Defining the encrypting matrix
Two complications exist in picking the encrypting matrix:
- Not all matrices have an inverse. The matrix will have an inverse if and only if its determinant is not zero.
- The determinant of the encrypting matrix must not have any common factors with the modular base.
Thus, if we work modulo 26 as above, the determinant must be nonzero, and must not be divisible by 2 or 13. If the determinant is 0, or has common factors with the modular base, then the matrix cannot be used in the Hill cipher, and another matrix must be chosen (otherwise it will not be possible to decrypt). Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.
Code
import * as mtrx from '../../math/matrix/Matrix';
// The code of an 'A' character (equals to 65).
const alphabetCodeShift = 'A'.codePointAt(0);
const englishAlphabetSize = 26;
/**
* Generates key matrix from given keyString.
*
* @param {string} keyString - a string to build a key matrix (must be of matrixSize^2 length).
* @return {number[][]} keyMatrix
*/
const generateKeyMatrix = (keyString) => {
const matrixSize = Math.sqrt(keyString.length);
if (!Number.isInteger(matrixSize)) {
throw new Error(
'Invalid key string length. The square root of the key string must be an integer',
);
}
let keyStringIndex = 0;
return mtrx.generate(
[matrixSize, matrixSize],
// Callback to get a value of each matrix cell.
// The order the matrix is being filled in is from left to right, from top to bottom.
() => {
// A → 0, B → 1, ..., a → 32, b → 33, ...
const charCodeShifted = (keyString.codePointAt(keyStringIndex)) % alphabetCodeShift;
keyStringIndex += 1;
return charCodeShifted;
},
);
};
/**
* Generates a message vector from a given message.
*
* @param {string} message - the message to encrypt.
* @return {number[][]} messageVector
*/
const generateMessageVector = (message) => {
return mtrx.generate(
[message.length, 1],
// Callback to get a value of each matrix cell.
// The order the matrix is being filled in is from left to right, from top to bottom.
(cellIndices) => {
const rowIndex = cellIndices[0];
return message.codePointAt(rowIndex) % alphabetCodeShift;
},
);
};
/**
* Encrypts the given message using Hill Cipher.
*
* @param {string} message plaintext
* @param {string} keyString
* @return {string} cipherString
*/
export function hillCipherEncrypt(message, keyString) {
// The keyString and message can only contain letters.
const onlyLettersRegExp = /^[a-zA-Z]+$/;
if (!onlyLettersRegExp.test(message) || !onlyLettersRegExp.test(keyString)) {
throw new Error('The message and key string can only contain letters');
}
const keyMatrix = generateKeyMatrix(keyString);
const messageVector = generateMessageVector(message);
// keyString.length must equal to square of message.length
if (keyMatrix.length !== message.length) {
throw new Error('Invalid key string length. The key length must be a square of message length');
}
const cipherVector = mtrx.dot(keyMatrix, messageVector);
let cipherString = '';
for (let row = 0; row < cipherVector.length; row += 1) {
const item = cipherVector[row];
cipherString += String.fromCharCode((item % englishAlphabetSize) + alphabetCodeShift);
}
return cipherString;
}
// @TODO: Implement this method.
export const hillCipherDecrypt = () => {
throw new Error('This method is not implemented yet');
};References
Spotted a mistake or something unclear? Report it on GitHub.