Why don't we use a Hill cipher of 100 × 100? Or even bigger? That would be close to unbreakable.
The number of possible keys in a 2 × 2 Hill cipher is 157248. For 100 × 100 the number is beyond limits.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not proved but considered secure against known-plaintext attack, see this question for details.
And, also, key size itself doesn't represent the security. High key sizes are necessary but not sufficient. As an example from history, Enigma was beyond its time as having around $87$ to $88$-bit key size which is greater than the key size of DES. We have already know that Enigma is broken.
Answer to comment: We work in Kerckhoffs's principles and are not accepting security by obscurity. So the attacker knows everything but the key.
answered Jan 31, 2019 at 16:11
$\begingroup$
$\endgroup$
5
Everything said by @kelalaka is true, but I have proposed a Hill Cipher variant which resolves the vulerability of some attacks like Known Plaintext Attack and Chosen Plaintext Attack.
Allow me to reference myself:
"The Hill Cipher is a classical example of a cryptosystem with interesting properties, namely that it implements the diffusion and confusion concepts coined by Shannon as essential properties for ciphers; nonetheless, its basic form is vulnerable to KPAs. This dissertation presents an efficient method to generate nonsingular key matrices, based on the Gauss-Jordan elimination procedure, which provides means to generate a new matrix per each block submitted to encryption.
RKHC, described along this dissertation, uses that method and adds a step to both the encryption and decryption algorithms to deal with messages containing patterns (e.g., a sequence of zeros), in order to increase their strength against KPAs, CPAs and CCAs.
A performance evaluation of a non-optimized implementation in the C programming language of RKHC is also included, compared with those of optimized implementations of AES and Salsa20, along with a discussion of its security and limitations under the well-known cryptanalysis attacks. The claim that the proposed method embeds randomness with high entropy into the generated matrices and ciphertext is corroborated by results of the TestU01 library for stringent randomness statistical tests".
By the way, I tested this several times, and believe me, 100x100 matrix generation would be very time-consuming. As you can see I used 32x32 and 64x64 matrices.
You can find the source code and the full document on my github: https://github.com/mafone/rkhc.
-
$\begingroup$ The description rightly states that "the generation of the pseudo-random mask and key matrix should use a CSPRNG each". OK, but with a CSPRNG (and a single one), we can make a stream cipher, and it's CPA secure under the hypothesis used to prove CPA security of RHKC, with lower computational cost. That severely limits the practical interest of RHKC. $\endgroup$– fgrieu ♦Commented Aug 16, 2021 at 14:42
-
$\begingroup$ There is also the issue of which CSPRNG you'd use. Are there any at all with a (usable) seed size of >= 256 bits? $\endgroup$ Commented Aug 16, 2021 at 15:07
-
$\begingroup$ Notice that the Hill Cipherpresented here is a block cipher, not a stream cipher which is another topic. Also despite being faster the stream ciphers do not provide data integrity by design. You can read a little bit about their difference, starting from here: security.stackexchange.com/questions/334/… $\endgroup$– MafCommented Aug 16, 2021 at 15:32
-
$\begingroup$ Is this even a Hill cipher anymore? Is your proposal beyond the scope of the question? $\endgroup$ Commented Jul 3, 2022 at 8:08
-
$\begingroup$ HC variant, a variant introduces variations. Not original HC anymore. $\endgroup$– MafCommented Jul 3, 2022 at 12:46