tag:blogger.com,1999:blog-3722233.post6559027588588772207..comments2020-08-08T16:54:01.950-04:00Comments on Computational Complexity: Can The Hill Cipher ever be used?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-87350472587224213852013-10-20T03:58:11.292-04:002013-10-20T03:58:11.292-04:00Please any one can provide python code for this pr...Please any one can provide python code for this procedure.<br />I try to code it but its time complexity is not good. help if any one know more about this if possible.<br />Thanks in advance!Anonymoushttps://www.blogger.com/profile/02187660602621382859noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76690638832233851012012-03-27T10:33:32.591-04:002012-03-27T10:33:32.591-04:00Hill cipher, being completely linear even in CBC m...Hill cipher, being completely linear even in CBC mode, is weak to differential cryptanalisys and "meet-in-the-middle"s.<br />There are few known results on the effects of adding some non-linear transformations, but then anyway it wouldn't be Hill cipher anymore...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4461695571593740462011-10-24T09:04:31.683-04:002011-10-24T09:04:31.683-04:00I suggest to choose a field as alphabet, so you...I suggest to choose a field as alphabet, so you'll have valid keys for every non singular matrix. Z_29 is good for encoding plain english.<br />GF(256) would be good for a more general encryptyon. Furthermore for n=8 the keyspace would have a lower bound of 256^28=2^224.<br /><br />What I was wondering about is: are there any other attacks apart from chosen plaintext?<br /><br />And,also: how using CBC would increase security?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28388778113454175702011-03-03T18:23:10.760-05:002011-03-03T18:23:10.760-05:00Very modest values of n lead to extremely large ke...Very modest values of n lead to extremely large keyspace. A lower bound can be found as follows: the upper triangular matrix with 1s along the diagonal is guaranteed invertible, regardless of the remaining entries. If the matrix is n by n, then there are (n^2-n)/2 entries, so there are at least 26^((n^2-n)/2) matrices you can use.<br /><br />If n = 4, this gives you at least 26^6 = 308915776 different keys.<br /><br />For n = 8, the number of keys grows to 26^28, or about 4 x 10^39.Jeff Suzukihttp://sites.google.com/site/jeffsuzukiproject/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20923647620283472442010-03-07T11:37:02.391-05:002010-03-07T11:37:02.391-05:00doing a Google search on
crypto uses of Sudoku...doing a Google search on <br /> crypto uses of Sudoku<br />brings up this post as #1 nowAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91883902260575180912010-03-05T08:56:11.472-05:002010-03-05T08:56:11.472-05:00Can you use a Sudoku matrix? A Sudoku matrix is (...Can you use a Sudoku matrix? A Sudoku matrix is (a special case of) a Latin square. but I'm not quite convinced that any Latin square is invertible (especially mod n), although I think that <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.1975&rep=rep1&type=pdf" rel="nofollow">this</a> maybe says that they are.<br /><br />At any rate, if Sudoku matrices are invertible, then you could just send the initially-filled-in digits, which would take less space. Deciphering then requires solving a Sudoku, which is sort of the reverse of the computational postmarks used by, e.g., MS Exchange ("pay-to-read" instead of, or maybe as well as, "pay-to-write".)<br /><br />For all I know, using Latin squares make the Hill Cipher even weaker, so this isn't a serious suggestion. (Although Google searching found some crypto uses of Sudoku.)Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66290788122705411302010-03-04T11:14:50.903-05:002010-03-04T11:14:50.903-05:00If you do a google search you can find some cipher...If you do a google search you can find some ciphertext-only attacks on the Hill cipher, better than brute force, relying on plaintext letter frequencies. Not sure what is the best known attack though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47280276114268201962010-03-03T22:24:30.083-05:002010-03-03T22:24:30.083-05:00@Anon: I imagine part of the motivation of the Hil...@Anon: I imagine part of the motivation of the Hill cipher is its simplicity.<br /><br />@Gasarch: Actually, if Eve gets only a single plaintext-ciphertext pair, that only takes care of a rank 1 part of the matrix. She has to get her hands on n linearly independent plaintext-ciphertext pairs in order to completely crack the code. (Obviously the more such lin. indep. pairs she gets ahold of, the easier it is to crack.)<br /><br />c^{n^2} grows rather rapidly, so I assume that there is in fact a Goldilocks n. The number of atoms in the universe is ~10^{80}~ 26^{57} and the square root of 57 is a little under 8. So it seems like even n as small as n=8 might do okay (assuming Eve doesn't get her hands on any plaintext-ciphertext pairs). Even n=16 won't break the bank for Alice & Bob though.Joshhttps://www.blogger.com/profile/12723950176543566251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84696357909958000752010-03-03T20:57:33.976-05:002010-03-03T20:57:33.976-05:00What is the motivation for using the Hill cipher i...What is the motivation for using the Hill cipher in the first place? The efficiency advantage as compared to using AES (with a good mode of encryption) seems negligible. Or you could switch to a faster (but possibly less secure) stream cipher which would still be better than using the Hill cipher.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26729692355556920102010-03-03T16:31:09.876-05:002010-03-03T16:31:09.876-05:00Luca and Warren- thank you, I have made the correc...Luca and Warren- thank you, I have made the correction in the origninal post.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33044805801193514592010-03-03T16:26:10.543-05:002010-03-03T16:26:10.543-05:00Luca's right. According to Wikipedia a matrix ...Luca's right. According to Wikipedia a matrix is invertible iff its determinant is invertible, which in this case occurs if the determinant and 26 are relatively prime.<br /><br />Or just do mod 29 instead.Unknownhttps://www.blogger.com/profile/01106301822827737278noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63323905471889407702010-03-03T14:43:26.673-05:002010-03-03T14:43:26.673-05:00the determinant being non-zero mod 26 does not imp...the determinant being non-zero mod 26 does not imply that the matrix has an inverse. Consider the 1 times 1 matrix "2"Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41689559743757139992010-03-03T14:32:24.416-05:002010-03-03T14:32:24.416-05:00Known plaintext attacks can be quite feasible in p...Known plaintext attacks can be quite feasible in practice, so I wouldn't want to use any cipher vulnerable to them. For example guessing pieces of the plaintext allowed Britain and its allies to crack the German Enigma during World War II. See http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma for that interesting story.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16354763030399475652010-03-03T11:52:04.208-05:002010-03-03T11:52:04.208-05:00“Is there a value of n that is both big enough and...“Is there a value of n that is both big enough and small enough (a Goldilocks n)”: this is one of the best maths jokes ever.Antonio E. Porrecahttp://www.disco.unimib.it/go/189963625noreply@blogger.com