Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Can The Hill Cipher ever be used?

Expand Messages
  • GASARCH
    Alice and Bob want to sent a message so that even if Eve intercepts it, she cannot tell what it is. We will allow Alice and Bob a short private meeting to
    Message 1 of 1 , Mar 3, 2010
    • 0 Attachment
      Alice and Bob want to sent a message so that even if Eve intercepts it, she cannot tell what it is. We will allow Alice and Bob a short private meeting to exchange information (or perhaps they will use RSA or Diffie-Helman for that). But the key can't be that long and has to be reusable (so one-time pad does not qualify). I describe below a well known cipher called the Hill Cipher. I think that there are circumstances where it could do well; however, I am curious what you think.
      Let n be a parameter we pick later. Alice generates a random n x n matrix of elements from {0,...,25} and checks that the Det mod 26 is nonzero. Alice gives this to Bob. Alice and Bob both compute its inverse. Alice and Bob can exchange messages by encoding every block of n by this matrix. So the first n letters of the text get multiplied by the matrix to get a diff n letters. Then the next n letters after that, etc.
      1. n has to be small enough so that Alice and Bob don't mind exchanging n2 elements of {0,...,25}
      2. n has to be large enough so that going through all possible n x n matrices is not practical for Eve.
      3. n has to be large enough so that tables of how often particular n-sized blocks occur are useless.
      4. Can combine with other techniques. Perhaps Alice and Bob first encode using the Vigenere Cipher and then apply the Matrix. They would then have to also share the Key for the Vigenere Cipher.
      5. QUESTION: If ALL Eve gets is the text then is this a good cipher? Clearly if Eve also somehow gets her hands on a message and what it was coded to she will easily crack the code. But if not then does this work well? This code is not used because Eve might get her hands on such, but I wonder if these are circumstances where it would be reasonable.
      6. Is there a value of n that is both big enough and small enough (a Goldilocks n).
      7. What else is known about this?


      --
      Posted By GASARCH to Computational Complexity at 3/03/2010 10:29:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.