| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
| Affine Hill Cipher via Homogeneous coordinates | |
|---|---|
| Topic Started: Jun 15 2009, 11:10 PM (92 Views) | |
| jdege | Jun 15 2009, 11:10 PM Post #1 |
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
The classic Caesar shift is a simple substitution cipher based on addition:
It's perfectly feasible to build a cipher based on multiplication: - provided that you use a key that is relatively prime to 26 - odd numbers other than 13. Numbers that are not prime to 26 cannot be inverted, and hence a ciphertext constructed using one cannot be uniquely decoded. The Caesar shift has a very small keyspace - 26. The multiplication cipher is even smaller - 12. And you can build a cipher based on both: . This last is known as the Affine cipher. It's keyspace is 12*26 = 312. Still small, but an improvement. OK: Then there's the Hill cipher. This is a cipher based on the multiplication of matrices. The plaintext is divided into vectors of length n, and the key is a nxn matrix. Just as in the multiplication and the affine ciphers just mentioned, only invertible matrices can be used - those whose determinant is non-zero and is relatively prime to 26. The formula is the same: - except that in this case P and C represent (for n=2) two letters, and K represents a 2x2 matrix. There is also an affine Hill Cipher - , where C, P, and K2 are vectors and K1 and is a matrix. And just as the affine cipher increases the key space of the multiplication cipher, the affine Hill cipher increases the keyspace of the Hill cipher. I'm sure most of you are familiar with all of that. But I was musing about it, and I was struck by a thought. Computer graphics is done by using matrices to manipulate vectors. Points, lines, etc., are represented by vectors, scaling and rotating are performed by multiplying vectors by matrices. What's really neat about the process is that multiple transformations can be combined - by matrix multiplication, into a single matrix. So instead of multiplying each point by each transformation, the transformations are combined into a single matrix, by multiplying them all together. Except for shifting. To move a point, you need to add vectors. Which wrecks the whole framework. So computer graphics programmers add an additional dimension, working in what are known as Homogeneous coordinates, in which shifts can also be represented by a matrix multiplication. And there's where the affine Hill cipher comes in. If we could represent both the multiplication and the addition by matrix multiplies, we could create a single matrix combining both operations - which significantly reduce the amount of work that had to be performed on each plaintext vector. Anyone aware of anyone who's played around in this area? Admittedly, the Hill cipher is only useful as academic toy, but this may be a new take on it. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
 |
 
|
| jdege | Jun 20 2009, 07:47 PM Post #2 |
|
Elite member
|
OK, I tried this out, and it works. I built a little command-line calculator that does matrix math, mod-26, and then used it in some scripts to try Affine Hill Cipher encoding and decoding, both in the normal manner and by using homogeneous coordinates. Start, our plaintext: "HELLO". Converted to vectors of two ints mod-26, this is [7 4] [11 11] [14 0]. For encrypting, we'll use the key matrix and the key vector . Encryption is multiplying each vector by the key matrix and then adding the key vector:
[12 23] [4 20] [11 8] converts to the letters "MXEULI". To decrypt, we need to invert the key matrix, and negate the key vector. This gives us and . We need to subtract the negated key vector and then multiply by the inverted key matrix:
Which gives us "HELLOA" - our original string plus the padding we added to make up the final vector. OK. Now let's do it with homogeneous coordinates. Our conversion to integers is the same, but we now make up three vectors of size three, using 1 as the last coordinate of each vector. Our plaintext vectors, then, are . Our multiplication matrix is now . Our addition step is now another matrix: . Because these are matrices, we can multiply them together: . The encrypting math, then, is: . In no great surprise, this gives us the same results as the first method. To decrypt in homogeneous coordinates, we need to first, subtract by the additive matrix, and then multiply by the inverse of the multiplicative matrix. The negation of is . The inverse of . These follow directly from the keys we used in the two-dimensional case. Again, we can combine them by multiplying - in the opposite order than we did in encrypting. Remember, matrix math is not commutative, and the inverse of the product of two matrices is the product of the inverses in reverse order. So, . And our decryption step is:
Which is, again, exactly what we got before. All-in-all, the whole exercise was pretty much a waste of time, except that now and again it's fun to dig in and confirm what you thought you understood of what other people have been teaching you. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · General · Next Topic » |
1:46 AM Nov 25
