Mission #2

Due: Friday, Sept 9.  As usual, hand in a typset account of your answers to these tasks, and a group report (which can be handwritten).


You are undercover in Eviladia.  Eviladia is using the Hill Cipher now, and they use exclusively a block size of 4.  They think you have turned spy for them, and as part of your initiation, you have to set up a secret Hill cipher key to use when contacting Eviladia headquarters.  Eviladia knows that you Americanadians are moral to a fault and cannot choose which of two comrades to sacrifice.  They are going to toilet paper the house of one of your coworkers, either JESS or JEFF.  As your initiation, you must choose one of them to sacrifice, and send them the name via Hill cipher.

This absurdly contrived situation leaves you in the pickle of having to choose JEFF or JESS to send.  But you have a clever way out.  If you can choose a Hill cipher key which encrypts both plaintexts JEFF and JESS to the same ciphertext, you will have fooled them (in a way).  At least, it will be a good laugh.

Task 1.  Find a Hill cipher key (block size 4) which encrypts both plaintexts (JESS and JEFF) to the same ciphertext.   Eviladia will be pretty suspicious if your matrix has determinant 0 and might cut you off before you get to make your joke.  So make sure the determinant of your key is non-zero.

Ok, so that kind of ended your career as a double agent for now, but at least you got to show off your mathematical prowess.  Headquarters wasn’t super pleased with your prank, so they’ve sent you to teach at Spy School.  You have just explained to your class how the Euclidean algorithm works.  You begin to wonder which coprime pairs of integers are most annoying to run in the Euclidean algorithm, because you want to assign something to keep your students out of your hair.  You decide that the unluckiest case is when the quotients (the q’s) are all 1.

Task 2.  Which pairs of coprime numbers have all quotients 1 in the Euclidean algorithm?  It turns out they are a well-known collection of numbers with a familiar name.  Conjecture a theorem, then state it and write a nice proof.

One of your students approaches you after class and says he has invented the perfect, most amazing, unbreakable cryptosystem, and can you please send his CV up to Headquarters so he can get out of your tedious class and begin spying.  The system encrypts as follows.  First, you use an affine cipher on the plaintext, then a Hill cipher on the result, and finally a Caesar cipher on the result of that.

Task 3.  Explain to your student how to perform a chosen plaintext attack on this system, if the block length is known.  Give a full explanation: which plaintexts do you use, and how to recover the key.

Task 4. When you hit the following button, you’ll find an encryption machine for this ‘unbreakable cryptosystem’ with block length 3, over integers modulo 26. You can enter a plaintext and hit enter, and it will give you the ciphertext. Use your chosen plaintext attack from Task 3 to determine the key. Please document your computation.