Enigma in foreground, English bombe in background.
Plato thought that certain natural gifts were required for the pursuit of learning. He stressed that anyone seeking wisdom in this way should be aware `how many subjects there are to study, how much hard work theyh involve, and how indispensible it is for the project to adopt a well-ordered scheme of living.'An expert problem solver must be endowed with two incompatible qualities -- a restless imagination and a patient pertinacity.--Anthony Gottlieb
-- Howard W. Eves
I recommend you use the computer language you are most proficient in, given it has adequate non-numeric facilities. I like PERL and Matlab for these exercises. Both offer "one-liner" capabilities for otherwise messy operations on strings and arrays, and both have an interactive interpreter. By no means do you have to be expert at either of these languages: Matlab has particularly good on-line help, and I did all the PERL work for my versions of these assignments with the manual in my lap. In general don't forget the Homework Helper page. What I'd like to see handed in (presumably through the WebCT mechanism) is the following.
For all of these exercises, hand in your writeup in PDF through webCT and hardcopy of everything to the prof.
Here are the exercises:
This kind of work, particularly in the early stages of a difficult cryptanalysis, is perhaps the most excruciating, exasperating, agonizing mental process known to man. Hour after hour, day after day, sometimes month after month, the cryptanalyst tortures his brain to find some relationship between the letters that hangs together, does not dead-end in self-contradiction, and leads to additional valid results. "Most of the time he is groping in the darkest night," one solver has written. "Now and again a little flicker of light gleams accross the darkness, tantalizing him with a glimpse of a path. Hopefully he dashes to it only to find himself in another labyrinth. His knowledge that night is inevitably followed by day keeps his waning courage up, and he steers his course towards where the morning sun is soon to appear. Except that sometimes he is engulfed in an interminable polar night."-- David Kahn
For all of these exercises, hand in your writeup in PDF through webCT and hardcopy of everything to the prof. The writeups have the same spirit as those for the programming work. They should be as long as necessary, as short as possible. Some of these reports will be mere placeholders (for the Zurbian Rotating Grill exercise there is almost nothing to say, I think). Others might be a few paragraphs (how you broke a simple substituation cipher and what capabilities you think might be useful in general) to a few pages.
You've been handed some aristocrat cryptograms (simple substitution, word divisions and punctuation preserved). At this point we have not discussed how to solve these in class. Do it anyway, recording in a TR-style manner the methods you used, looked up, invented, or think might be useful. Attach all extra "scratch", intermediate, hand-written work you do.
Here's my idea for the equivalent of one-time-pad, infinitely secure encryption. Start out with Vigenere of some key, but instead of repeating the key, substitute in the plaintext instead of the key repetitions. No key period, cipher varies with each message, never repeats, completely secure! So the situation could look like:
Autokey: COMETSENDSUPPLIESTOMORLEYS
Plain: SENDSUPPLIESTOMORLEYSSTATI
Cipher: USZHLMTCOAYHIZUSJESKGJEERA
Or somesuch. How about that? Assignment is to outline as many weaknesses and resulting attacks on this cipher as you can. HINT: This is NOT the equivalent of a one-time pad. If things were that simple, the field would have been over in 1577 instead of 1977! There are exploitable weaknesses: what are they?
Variant. If I wanted to be really clever, why wouldn't I use the emerging cipher itself as a key? Is that devious or what? MWAH-Hah-hahhaha! Something like
Autokey: COMETUSZHLMTCOAYHIZUSJESKGJEERA
Plain: SENDSUPPLIESTOMORLEYSSTATI
Cipher: USZHLOHOST....whatever
So analyze this idea too. Turn in the usual nicely-written and
formatted page or two of
thoughts on this problem.
You may well want to use the computer to help with this assignment, or possibly it's just fine as a written exercise. Especially if you want to try the 5x5 case.
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*
Rather tougher, strictly for extra credit. Same thing again! Hill's Cipher, with block size 5 this time. That means you are looking for the inverse of a 5x5 matrix. First you need to write a modular matrix inverse program, (I'd use the adjoint method), and then you may have to try several choices of encrypt-decrypt 5-tuples before you find five pairs that give you an invertible matrix. If you want to try this and remember your adjoint method, don't panic, it's in all linear algebra texts (and Mollin's Cryptography book, for that matter).
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. This
ESUYYOGOGTQJFNNDAVKW GYLFEKRVRNDKDZHQIVPEQQDAHSOLRE QXQMUKYMIRMMERAOGTBNIWYNF VRDQEIWYNFTPIIREGYLFODZVN OIPBTLTSOIBOBTGKCJRN GDRTEGGEASZGZVEZRELEENJHDVNAUI SAHLEFSKYYCAWWEPKTFTGPLLIXKELEIQMBN SMUNFNUMZTBUDZH UGVSAERODVAWDWSJUUSOKFFCO KTATTMYJFSPPCZH XDKSAWKQMBNJHXTMTEQMEMERNYSHZH DEFGH
Second is an Original Cipher used for an encrypted part of a document in the prof's past.
Speculations apparently the most unprofitable have almost invariably been those from which the greatest practical applications have emanated.--John Herschel
The Cocoanut problem: Three sailors are shipwrecked on an island where they find a monkey and a lot of cocoanut trees. They pick N nuts for a food supply and put them in a pile. During the night, the most distrustful sailor sneaks up and takes his fair share by dividing the pile into three and hiding his third. There is a nut left over, which he gives to the monkey before going back to sleep. Each of the other sailors does the same thing: divides the remaining pile into three, taking and hiding his third, and giving the lone remaining nut to the monkey. In the morning the 3 sailors meet, divide the remaining pile into three, each taking his third. Surprisingly, there is a nut left which, believe it or not, is given to the monkey. What is the minimum number of cocoanuts that could have been in the original pile?
This page is maintained by CB.
Last update: 29.07.01.