Talk:Hill cipher

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science   
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the quality scale.
 ???  This article has not yet received a rating on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science.
 

Notation[edit]

Nice article! One thing, though: all finite fields have order p^n, where p is prime. I think the notation GF(p^n) is used to denote these fields. So GF(26^n) cannot be a field because 26 is composite. Would \mathbb{Z}_{26}^n, work? Sorry if I'm wrong, it's quite possible that my maths is getting rusty...! — Matt 17:05, 27 Oct 2004 (UTC)

Aargh, as I'm sure you're aware Matt it's me who is rusty! Please feel free to make the correction, I have to dash away just now. Incidentally a big "To Do" for this article would be finding Hill's patent. Securiger 07:25, 31 Oct 2004 (UTC)
I've made that change. The patent is US patent 1,854,947 but the scans at the USPTO website seem to be broken. I found someone else had scanned some diagrams at the "Crypto Drop Box" though:
I presume that as scans of public documents from more than 70 years ago, it would be OK to use one of these? In particular, Fig. 4 would make a nice illustration. Securiger 13:05, 1 Nov 2004 (UTC)
Yeah, I think these fall into PD. — Matt 01:39, 22 Nov 2004 (UTC)
While it's of course true that ℤ/26ℤ ('ℤ26') is not a field, it is a commutative ring, and so it is possible to define the general linear groups over it. The group GL(n, R) for R a commutative ring consists of those nxn invertible matrices with elements in R; a matrix over R is invertible if and only if its determinant is a unit in R, that is, if its determinant is invertible in R. Therefore GL(n, R) may be defined as the group of matrices whose determinants are units. The only difference between the case of the general linear group over a field and a commutative ring is that not every non-zero element of R need have an inverse; the general linear group is precisely those matrices whose determinants are invertible in R. In fact, for any n, the general linear group GL(n,-) is a functor from the category of commutative rings to that of groups; the determinant is a natural transformation of functors GL(n,-) → (-)* ≅ GL(1,-), sending each invertible matrix to its determinant in the group of units of the ground ring. In fact, were we to generalize to the category of monoids, GL(n,R) would be the pullback of R* and Mn(R) over R (where the map R* → R is the inclusion, and the map Mn(R) → R is again determinant); that is the maximal subgroup of (the multiplicative monoid) of Mn(R), as determined by the determinant. --Daviddwd (talk) 04:28, 8 September 2014 (UTC)

Image added[edit]

OK, I cropped a copy of that image, shrank it a bit, cleaned up a few glitches, and removed the figures. At the moment it's at the top of the page, since it's the only illustration for the article. But that kind of spoils the surprise (that the cipher was implemented mechanically). Securiger 08:30, 22 Nov 2004 (UTC)

nice[edit]

One might naïvely think that the key size, in bits, is n2log226 or about 4.7n2. In fact, it is slightly less than this because not all randomly selected matrices are usable. A slightly less naïve view might guess that 1/2 + 1/26 of candidate keys would be unusable, reducing the keyspace by about 54%.

Wow, I didn't know encyclopedia articles could be this condescending. I mean, what the fuck? Since when do reference works pass judgment on what is "naïve"? Does Britannica ever try to be this didactic and insulting? The preceding unsigned comment was added by 68.35.148.201 (talk • contribs) 07:01, 11 February 2006 (UTC)

Feel free dive in and make whatever changes you think are needed. — Matt Crypto 14:39, 11 February 2006 (UTC)
But there is nothing "insulting" or "condescending" about it. "Naïvely" or the "naïve approach" are standard phrases in mathematics -- and many other fields -- to indicate a method which omits various complications (usually, thereby becoming less accurate). And no-one is suggesting that you are naïve (the subject of the phrase is "one", i.e. some hypothetical person), still less that you are socially inept or some such thing. -- Securiger 04:22, 14 February 2006 (UTC)

security question. Exponential - linear[edit]

this page says that the security value is low. i understand that it is nothing compared to modren standards. the page also says that the number of combanations grows in a linear fashion but if the cipher is a

    two by two matrix and you say the highest number you allow in the key is a 5 then the posable number of combinations is 5^4 or 625
    two by two matrix and you say the highest number you allow in the key is a 10 then the posable number of combinations is 10^4 or 10,000
    two by two matrix and you say the highest number you allow in the key is a 20 then the posable number of combinations is 20^4 or 160,000
    yes any coumputer in the world could easily go through 160,000 combinations but if yoy used a 10 by 10 matrix and allow any number in the   
    key be from 1 to 10,000 then you would have 100^10,000.  i would think that even for a fairly new coumputer that would take a while to 
    decrypt if you where using a brute force attack. and then if you use the modul function you can increse that number a lot.  —Preceding unsigned comment added by Keanwood (talkcontribs) 07:39, 7 November 2009 (UTC) 
I assume you are refering to the following claim:
Unfortunately, the basic Hill cipher is vulnerable to a known-plaintext attack because it is completely linear.
This claim is indeed somewhat ambiguous. However, it does not talk about the key space. Rather it refers to the observation that the encryption is a linear function. The consequence is that if an attacker knows some plaintext and the corresponding ciphertext, then the attacker can find the key by solving a system of linear equations. Hence finding the key under such an assumption is quite easy. Conversely, a modern cryptosystem has the property that it is infeasible to find the key given any number of plaintext and corresponding ciphertext.81.62.129.109 (talk) 09:38, 7 November 2009 (UTC)
but wouldent you still not know what the key was and still have to use brute force to come up with a key that could match your plain text to your cipher text?  —Preceding unsigned comment added by 75.26.158.189 (talk) 04:02, 9 November 2009 (UTC) 

Inversion of the encrypting matrix for decryption.[edit]

There seems to be a hole in the description of the inversion of the encrypting matrix to get the decrypting matrix. The hole, specifically, is in the handling of the determinant value. For example, I am not sure that it is obvious that the determinant value of 9^-1 should be handled as the value 3.

Jerry McCarthy (talk) 11:51, 19 April 2012 (UTC) How to break Hill cipher? — Preceding unsigned comment added by 117.4.133.191 (talk) 05:54, 20 May 2012 (UTC)