| Viewing Single Post From: Affine Hill Cipher via Homogeneous coordinates | |
|---|---|
| jdege | Jun 15 2009, 11:10 PM |
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. | |
 |
|
| Affine Hill Cipher via Homogeneous coordinates · General | |
7:55 AM Nov 25
