Lester Hill was a mathematics professor at Hunter College in New York who in 1929 invented a cipher system based on algebraic principles, primarily matrix arithmetic.
A simple substitution cipher, as
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
J P G Q W T C I H A X V Y Z S B D U O F R L E K M N
is easy enough to break: a reasonably accomplished amateur can readily resolve SUBIW ROVRF WEJOO FURZC EHFIB SWFOO HZWEO into "Orpheus' lute was strung with poets' sinews" even without the aid of the key. This is because it operates on 26 elements which vary greatly in frequency.
Slightly more difficult to crack is a digraphic system such as the Playfair cipher, with (ideally) 676 elements and a somewhat flatter frequency distribution. As the number of letters in each chunk of plaintext goes up, so do the number of elements and the flatness of the distribution.
Unfortunately, so does the unwieldiness of the key. Even a list of digraphs proved too long and complex for inclusion in this node, and a list of three- or four-letter groups would be almost useless given the time required to look anything up in it (at least in Hill's day, before computers). In addition, a number of the 17,576 possible trigraphs or 456,976 possible tetragraphs never appear in English, and listing them would be a waste. Hill's solution was to apply a mathematical formula to these or larger blocks, similar to the procedure users of Playfair perform on digraphs, so that a list is unnecessary.
Constructing a key
From here out all numbers are modulo 26
To use the Hill cipher, we must first construct a key, a matrix with a determinant relatively prime to 26.
The first step is to use the matrix (3x3 in our examples)
( 1 0 0)
( a 1 0)
( b c n)
where n is relatively prime to 26. Then, add rows or columns to multiples of other rows or columns until satisfied.
For instance, starting from
( 1 0 0)
( 3 1 0)
(23 11 9)
after a small amount of manipulation we end up with
(24 3 19)
(18 19 22)
(23 2 10)
The next part of creating our key is assigning integers from 0 to 25 to letters of the alphabet. Any assignment is equally useful for this step. For this example we'll use simple sequential ordering.
Depending on how your memory works, once you've done this it may be easiest to record the encription matrix as letters: Y D T/S T W/X C K.
"Now my soul hath elbow-room" is no more arbitrary than most sample messages in these sorts of descriptions, and suits our purposes. The first step, for a 3x3 matrix, is to divide it in groups of three letters:
NOW MYS OUL HAT HEL BOW ROO MAA
To encrypt each group, arrange the corresponding numbers in a 3x1 matrix:
(N) (13)
(O) or (14)
(W) (22)
and multiply the key matrix by it:
(24 3 19) (13)
(18 19 22)*(14)
(23 2 10) (22)
This gives us
(18) (S)
(22) or (W)
( 1) (B)
The line in full becomes SWBAC KHQEJ YNZCT QOLOW NCIQ.*
Deciphering is performed by multiplying the inverse of the key matrix by successive blocks of three ciphertext letters in the same way.
Security and usefulness
The Hill method is complicated without a spreadsheet, or at least a machine of some sort to do most of the figuring -- years ago I programmed a TI-86 calculator to encipher and decipher messages using a 5x5 matrix. However, it can in principle be done with paper and pencil, and the security it offers is quite good given that level of simplicity.
If you're 15 years old, and interested in passing notes at school, Hill is not ill-suited to that purpose. It's a block cipher, and with a large matrix -- 15x15 or bigger, perhaps -- encryption must in practical terms be completed as its own step before the message is sent. Unfortunately, the system is highly prone to garbles. Since two blocks of plaintext that differ by just one letter are likely to be represented by entirely different blocks of ciphertext, a single mistranscribed letter in the cryptographic message can obscure a large block of plaintext, and a dropped or added letter can render the entire rest of the message unreadable.
*For three months, the H in the second word was inadvertantly omitted; discovery of this gave rise to the mention of garbles.
Thanks, lj; some day I'll learn how to read