The Hill Cipher as one of the classical cipher is invented by Lester S. Hill in 1929. It is the first polygraphic cipher that can operate more than one letter at a time.
- There is a rule for key K:
Determinant of matrix and number of characters of the alphabet must be coprime. What does this rule say? Why
it must be like this? So If I had determinant 5 and characters 30, it
would not work?
In the Hill cipher, there is an invertible matrix for the key $K$ of size $n\times n$, and the plaintexts $m_i$'s are row vectors of size $n$.
The encryption of a block $m$ is performed by $c = m K$ and the encryption of the message can be considered mathematically take $c = m K$. For decryption, multiply both sides with $K^{-1}$ and get $cK^{-1} = m K K^{-1}$ and $cK^{-1} = m I$. That is the inverse of a matrix and it is a well-known property that to be invertible a matrix must have of square size and have a non-zero determinant.
If the determinant has common factors with the alphabet size then it will not have inverse since invertible matrixes must have invertible determinants. This is due to fact that we are in the composite modulus. In this case, choose a new uniform random key or choose a prime alphabet.
- Let's assume I have key K which should be 3x3. I would get the key: ENCRYPT. I would create trigrams like ENC RYP T?? - now the last
trigraph is missing two characters. Should this input key be REFUSED
by application for example or should I fill it with some values like
#?(# alphabet must contain this char). Or how should the application behave when this happens?
- Let's assume I have plain text T which is: textabcd - again the same question (as 2.). I have TEX TAB CD? - (should I again insert
something in that empty space (?) (for instance #) ?
In modern Cryptography, we call it padding and the classical era has padding also. I'm not aware that Hill proposed any padding.
Fixed padding can cause serious problems with the Hill cipher since it hasn't got known-plaintext attack security. Putting X or any fixed character can cause information leak about the key.
Wikipedia states it very well. The messages are starting end ending with predictable ways, like my dear ambassador, Weather report, Sincerely your From .. To in the military, etc. Context can change according to the target. Therefore we need randomized padding in the beginning and at the end. This can cause confusion, too. The better one may use nonsense letters for this aim.
- Should HILL cipher accept MATRICES (input as matrices) or as alphabet key like ABCD?
If I've understood this part correctly; first, the messages are encoded into row vectors of numbers by using the alphabet then multiplied with the key matrix $K$. The key matrix is also a number matrix, not a character. We operate on the numbers then decode the information back to character.
Little proof of the claim that the determinant must have relatively prime to $n$. When $n$ is a prime it is clear that we are in a field and the determinant must be non-zero by the Invertible Matrix Theorem
The theorem also gives the general case for this as;
In general, a square matrix over a commutative ring is invertible if and only if its determinant is a unit in that ring.
The units are invertible elements. For a given $u$, if $\gcd(u,n)=1$ then it has an inverse, therefore it is a unit. The converse is also true that for a given unit the $\gcd(u,n)=1$ must hold. We can see it form that $u x \equiv 1 \pmod n$ then we can form the bezout's identity $ux+bn=1$ then we can conclude that they are relatively prime.
Or directly; if $ax\equiv 1 \pmod n$, then there is a $k$ such that $ax=bk+1$, equivalently $ax−bz=1.$ If $d=\gcd(a,b)$, then $d|a$ and $d|b$, so $d|ax−bz=1$. We can conclude that $d=1$.
