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. For our example key matrix: So, modulo 26, the determinant is 25. Since and , 25 has no common factors with 26, and this matrix can be used for the Hill cipher. The risk of the determinant having common factors with the modulus can be eliminated by making the modulus prime. Consequently, a useful variant of the Hill cipher adds 3 extra symbols (such as a space, a period and a question mark) to increase the modulus to 29. Example Let be the key and suppose the plaintext message is 'HELP'. Then this plaintext is represented by two pairs Then we compute and and continue encryption as follows: The matrix K is invertible, hence exists such that . The inverse of K can be computed by using the formula This formula still holds after a modular reduction if a modular multiplicative inverse is used to compute Hence in this case, we compute Then we compute and Therefore, . Security The basic Hill cipher is vulnerable to a known-plaintext attack because it is completely linear. An opponent who intercepts plaintext/ciphertext character pairs can set up a linear system which can (usually) be easily solved; if it happens that this system is indeterminate, it is only necessary to add a few more plaintext/ciphertext pairs. Calculating this solution by standard linear algebra algorithms then takes very little time. While matrix multiplication alone does not result in a secure cipher it is still a useful step when combined with other non-linear operations, because matrix multiplication can provide diffusion. For example, an appropriately chosen matrix can guarantee that small differences before the matrix multiplication will result in large differences after the matrix multiplication. Indeed, some modern ciphers use a matrix multiplication step to provide diffusion. For example, the MixColumns step in AES is a matrix multiplication. The function g in Twofish is a combination of non-linear S-boxes with a carefully chosen matrix multiplication (MDS). Key space size The key space is the set of all possible keys. The key space size is the number of possible keys. The effective key size, in number of bits, is