Cryptography is a mixture of mathematics and muddle, and without the muddle the mathematics can be used against you.Ian Cassells
The following plaintext is encoded with Hill's cipher, using a block size of 2.
Here is known plaintext and resulting cipher.
CENTRAL TO OUR FEELINGS OF AWARENESS IS THE SENSATION OF THE PROGRESSION OF TIME*
GKGZRRE XC QLC JNPAVIYQ TY WSRIREWOA IL ELP WAFXTMWKB PY RLP GXUAVZKCWKB PY RUGQC*
Here is the cipher to be solved. Use the known plaintext to to construct the inverse of the key matrix.
AE LEDS TM DOIMNL QEHUKB TOTELLKO OKBU UHMYWO TBOS BBWHFMCQJH NA EFPAUIZK UQLPVZ LWAOLE ZUVM MAAHVM VJME MU SS QENOVIHK JD BBQT KORVRR DVHVVZ NA ZVLPVZ TM LW SZICJB TY AH HKYW AH XQQCDR AS AHTM DKKM VJRV SKGUKSTMWO EMAH AH PAZY NCRI HV FF NNYRVMBPBO. 'ZQPANA' - GJVMOY DDDLWO*
OK, that was easy, but what about larger blocks where there is no
closed
form for the modular inverse of a matrix?
Write a program to find the modular inverse of a matrix if it exists,
and thus to determine if a particular matrix is a good Hill key. OR
simply use the cute trick in Section 3.8 of Trappe and Washington,
using
your favorit
If you decide to go with Section 3.8, you can skip the next several paragraphs. If you want to get into a little numerical analysis, read on! If you decide to write your own modular matrix routine (more fun than Section 3.8, but there's plenty of fun in this exercise, so feel free not to), you will need to write a program (probably by modifying or using existing code) to find the multiplicative inverse, mod 26 for a square matrix if it exists, and report that it does not exist if that is the case. This can be done using an adapation of the Gauss-Jordan technique, but as of 2003 I'm thinking that the adjoint method is much easier: the tutorial example in this link is quite clear and the code can be used for inspiration or even a template (doubles changed to ints, etc....). As of 2003 there is useful java source code for determinants, adjoints, and inverse at this Matrix Calculator site.
For a fairly abstract background to the method, Mollin's excellent book Introduction to Cryptography mentions the adjoint method in the appendix; as in Gauss Jordan, the reason you can use the algorithm is that it works in any polynomial ring. Of course in all cases you'll use modular multiplicative inverses instead of 1/x wherever that's needed (only once in the adjoint method). You do not need to compute these multiplicative inverses on the fly - since you are only using mod 26, you can use a lookup table - which is practical to initialize by hand if you do not feel like implementing the inverse-by-euclidean-algorithm technique.
Gauss Jorden is complicated by pivoting, which can actually be eschewed if you don't mind doing more trials to find an invertible matrix. I can give sample C code if you're interested. For pivoting to work, you need to reduce using a pivot that is not even or equal to 13. This may necessitate some row exchanges that you need to keep track of. If you get to a point in the reduction where no such pivot exists, then you have a non-invertable matrix. Fortunately the choice of pivot does not seem to propagate - i.e., if you have two or more valid pivots, it does not matter which one you take in terms of whether you get stuck later on. This is fortunate, as otherwise there would be a nasty search problem. Bo Hu, the stalwart TA in 2003, implemented an end-to-end Hill deciphering package using the Gauss-Jordan method. He has these hints for you. On the whole, however, students seem happier with the adjoint method, which seems easier to CB too. Though untried in the field at this writing, the method of Section 3.8 looks to be much easier still.
Bo Hu also has created a program to help you decide if a string is actually English or not. This helpful utility is pointed to from his "hints" link above.
If you are feeling frisky you might write a modular inverse for matrices for any modulus N, not just N = 26 . This would presumably require writing a Euclidean algorithm to find inverses to any modulus, but you're going to be writing that anyway, so...
At any rate, then you use this routine to write a program that encrypts and decrypts messages using the Hill cipher. Demonstrate that your en- and decryption steps both work with the keys you find.
As soon as your encryption code is working, Generate two (good) 4x4 keys, and use them to encrypt two pieces of text at least 256 characters long. Give these encryptions along with a 30 character crib to two classmates. Also generate two 3x3 keys and use them to encrypt two pieces of text at least 1800 characters. Give these encryptions to two classmates. DO NOT REUSE TEXT FROM A PREVIOUS ASSIGNMENT, and BE PREPARED TO DEMONSTRATE YOUR KEYS ACTUALLY WORK.
Decrypt the two Hill ciphers you were given, one 4x4 using supplied cribs, and one 3x3 without a crib, using a probable trigram attack. You should make use of your matrix inversion programs to check the invertablility of cribs and probable trigrams. You may also want to develop some simple statistical checkers to reduce your load in determining whether trial decryptions are correct or not.
In your writeups, TR style as usual, document to whom you gave your encryptions, AND you should document from whom you got your encryptions. You lose credit if you don't use others' encryptions and you lose credit if your encryptions aren't used, so be conscientious about doing and reporting this aspect.
Extra Credit: This is Hill's Cipher, with block size 5 this time. That means you are looking for the inverse of a 5x5 matrix. Recall you may have to try several choices of encrypt-decrypt 5-tuples before you find five pairs that give you an invertible matrix. Here is known plaintext...
JE VOUDRAIS QUE MON AMOUR MEURE QU'IL PLEUVE SUR LE CEMETIERE ET LES RUELLES OU JE VAIS PLEURANT CELLE QUI CRUT M'AIMER 1948 S. BECKETT
and its encipherment...
QHDIU URAAS OYEAO HUUIU SBPLR 'HDNTL TETPV SOWCL AWUQE AHZVE EAHWS LUAWL NJRDJ ZVAAS PAPLR MMZGE KZOKU OGENT 'KYYQE 1948 . QZHGC CSOVC
Here is the cipher to be solved.
ESUYYOGOGTQJFNNDAVKW GYLFEKRVRNDKDZHQIVPEQQDAHSOLRE QXQMUKYMIRMMERAOGTBNIWYNF VRDQEIWYNFTPIIREGYLFODZVN OIPBTLTSOIBOBTGKCJRN GDRTEGGEASZGZVEZRELEENJHDVNAUI SAHLEFSKYYCAWWEPKTFTGPLLIXKELEIQMBN SMUNFNUMZTBUDZH UGVSAERODVAWDWSJUUSOKFFCO KTATTMYJFSPPCZH XDKSAWKQMBNJHXTMTEQMEMERNYSHZH DEFGH
This page is maintained by CB.
Last update: 10.07.04.