The Cryptology Independent Study Project

This project is intended to fill a void in the area of cryptologic study and research. There are many universities with programs in computer science and mathematics that fail to address the area of cryptology. This is, perhaps, not the most surprising trend, but it does leave those of us who are genuinely interesting in the area with nowhere to turn. Our hopes are that this project will help fill this void, and that we can grow a community based on our common interest and love for making and breaking codes.

The central goal of this project is to facilitate learning in the area of cryptology by turning the current books and research papers into pseudo-courses. That is, if one is interested in Bruce Schneier's book Applied Cryptography, then one could build a study based on the readings, references, and projects mentioned in that text. Furthermore, each entry will allow the community to open a discussion about the information in the assignment, as well as post code and solutions to those assignments.

Anyone can become an author of this site. All you need is the passion and drive to either start a new project, or finish an old one. Please use the Author Self-Registration form on the side-bar to become an author. If you would like us to add another catagory so you can start your own independent study or research project, please join the cryptology list, as mentioned on the side-bar, and let us know. If you plan to become involved with the project, and would like more control over the content, call Chris Mooney in the U.S. at 207-450-2332.

There is also a mailing list for those of you who are interested. The list should be a forum for discussing everything related to cryptology. You can sign up to the list using the side-bar. Archives can be found here.

The following is bases on Bruce Schneier's book Applied Cryptography. The study includes reading papers mentioned in the pages of his book and trying experiments based on principals in the text. Each project will follow along with each chapter in the text so that the reader may gain a deeper understanding of the text's assertions. That is, rather than leaving the reader with an abstract idea of how the subject works, these projects should facilitate a deeper and more thorough understanding of cryptology.

Note: to get a head start on the projects always scan the next chapter's projects before you start on the current chapter's projects. Many of the assignments reiquire you to find papers and books. I have included all the papers I can, but you may need to get the books from your library, and this could take at least a week if they don't have it. It pays to start early.

Requirements:
Applied Cryptography, by Bruce Schneier (second edition) ISBN: 0-471-11709-9

The following is an independent study based on David Kahn's The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. This book is the must-start place for anyone interested in learning cryptology. The state of the art today is so different from that in the past that it would be all too easy to skip some of the fundamental principals behind cryptology. This is mostly a history book, but Kahn does a great job of covering the composition and decomposition of ciphers, cryptanalysis, and the mathematics behind some of the more important work in the field. The book is about 1000 pages long and, ultimately it took me an approximate total of 50 hours to read the entire book.

Requirements:
The Codebreakers : The Comprehensive History of Secret Communication from Ancient Times to the Internet by David Kahn (1996) ISBN: 0-684-83130-9

During the process of documenting human rights abuses Alice and Bob are taken captive by the secret police of some unnamed country. While the secret police suspect Alice and Bob are involved in a project to document these abuses, they are not quite sure how much the two know. As a result Alice and Bob are placed in two locked rooms connected by an air duct where Eve, a member of the secret police, has planted a listening device. The secret police hope to get a better idea of the type and nature of the information that Alice and Bob know by listening on their supposedly secret conversations. How can Alice and Bob communicate using the robust characteristics of their language, while still making their conversation secure. This scenario is intended to lay the groundwork for an interesting problem in secure communication, and our protagonists are here to help us examine the possible solutions to this dilemma. While almost every child in America learns Pig Latin or some other such system of pseudo-secret communication, this examination is intended to be a brief introduction to the actual problems, and possible solutions, of such systems. It is hoped that with a brief overview of cryptography and linguistics we can begin to find a possible solution to Alice and Bob’s situation.

One must start by examining the principals of good cryptography. That is, since we are aware of what makes cryptography successful it would appear logical to apply those same principals to Alice and Bob’s communication problem. A good cipher depends on a couple things, but we will examine one here. Experience has shown that long and pseudo-random keys are often best. Indeed the only unbreakable, though not practical, cipher is the one-time-pad where every element of plaintext is encrypted and decrypted with its own key value. If the algorithm is good, most of the security will reside in a good key. One must ask why this is the case. Well it stems from being unable to apply frequency analysis to find the unknown element of the cipher. That is, the trick is to use mathematics to deduce the key, and ultimately the plaintext. While this is certainly an oversimplification of the problem it serves one important purpose: namely, good cryptography is mathematically complex. This simple fact leads us to the initial and disappointing result that, while humans are geniuses when it comes to language, they are not equipped to perform the types of mathematical operations needed for good cryptography at the speed of language. This unfortunate reality does not mean that one should give up on spoken-word ciphers, but that we must figure out a satisfactory way to achieve our goal using speech and the innate genius humans have to both speak and perceive language.

What we must do is appeal to human language in hopes that we can find a system well suited to our needs. That is, what lessons can Alice and Bob learn from the field of linguistics and the unique nature of human’s ability with language. There are at least three linguistic categories that immediately stand out as interesting: lexicon, morphology, and phonetics. At first Alice and Bob might recognize that what they are trying to do, obscure the meaning of their language, has been done by militaries before. That is, military codes have been used to conceal language meaning by troops in the field when their communication channel is not secure. While this may appear to solve the problem Alice and Bob find themselves faced with, it falls far short of their needs. Codes, while applicable in some situations, are not robust enough to handle diverse and meaningful conversation. Furthermore, they suffer from a major problem: namely, they are based on a language’s lexicon. Codes usually map one-to-one, or one-to-many depending on context, between the lexicon of the speaker’s primary language and some other word in that language. With codes one needs a codebook, or mapping, which must be changed frequently to confuse the eavesdropper. If Alice were attempting to convey a complex idea to Bob she would need to look each word up in this code book to construct her sentence, and Bob would need to look each word up to deconstruct it. This means they would most likely need to write things down, and that will not solve Alice and Bob’s problem. It should immediately strike the reader that a code is very similar to the popular notion of a language. Alice and Bob would essentially need to learn a new language. Additionally a languages lexicon changes frequently and would require something akin to an English to Spanish translation dictionary to fully describe. In short, codes are not cryptography. Cryptography intends to change some plaintext, or in our case language, into some meaningless ciphertext, or cipherlanguage. This means that Alice and Bob can immediately dismiss lexicon as a useful solution to their problem. What they need is a system to quickly speak and perceive their language. What they need is a way to morph their existing language into something else.

This brings us to the next area of investigation: morphology. Morphology is most certainly the language analog to what one finds in other mediums of cryptography. Cryptography in computers morphs at the bit or byte level, in writing systems cryptography morphs at the single character level, and in spoken-language we would like morphology to work at the word or syllabic level. Such operations would appear to be the most efficient and effective way for humans to perform reversible changes on a language. Let us first examine morphemes and their traditional meaning in linguistics. An affix is a word element that is usually attached to the root of a word at the beginning, middle, or end. These are usually referred to as prefix, infix, and suffixes respectively, and most commonly show up as suffixes in the English language. The other important distinction is that affixes are either derivational or inflectional. For Alice and Bob’s purpose these traditional categories of affixes fail to fully describe what a spoken-word cipher does. What we want is an operation that we can perform on the existing root with all of its affixes as required by the languages grammar. This requirement is almost something of a super-affix that wraps one’s native language. Perhaps it is possible to make an argument that this type of affix should be classified as a phonological rule, but for now it is enough of an anomaly that we will leave the question open. Let us first examine the applicability of prefixes and suffixes in a spoken word cipher. Both affixes are appended to one or the other end of the root, which means the entire word, and therefore meaning, can be easily deduced. Because this is such a superficial change to the root the eavesdropper is much more likely to understand the context of the conversation based on the usage of the root. The infix affix, however, shows much more promise.

The traditional usage of an infix is to insert the affix word segment into the middle of a word root. This could help obscure the meaning of single or even double syllable words, but when Alice attempts to say the word ‘constitutionality’ to Bob the remaining six syllables of the word will contain enough familiarity to the eavesdropper that the word may be obvious. Because of this we will break with the more traditional notion of an infix word segment and propose a syllabic based solution. In this alternate usage we will break a word, both its root and its affixes, apart into syllables and insert the infix in between the vowel of that syllable. Traditionally affixes have word formation rules and, although we are not quite in that paradigm, it may help to think of this requirement as our WFM. This method should help resolve the problem above while maintaining our requirement that the rule be quick and natural to the speaker. But what should our infix word segment look like?

The next logical question is: how can the construction of our affixes maximize our cryptological objectives? First it is helpful to understand how these affixes are analogous to classical cryptography and its usage of keys. Because modern cryptography is so mathematically complex, Alice and Bob are better suited to start where classical cryptography did. That is, if one cannot perform operations similar to modern cryptography at the speed of language, can they perform operations similar to classical cryptography at that same speed? Please keep in mind that while classical methods may be better suited to our needs they fail spectacularly against frequency analysis and techniques such as counting the index of coincidence. This drawback may allow us to proceed, but we should always remain weary of the result: while we may find an adequate solution for the casual listener, it is much more difficult to fool Eve or any party that is willing to record and dissect the language. It is best to think of classical cryptography as a function machine. One usually has two inputs P[i], which represents one element of the plaintext, and K[j], which represents one element of the key. These two pieces are thrown into a function that produces C[k], which is a single element of ciphertext. On the other end C[k] and K[j] are fed into an inverse function that produces P[i], the original element of plaintext. With our syllabic rule we can say that we will pass each syllable of our native language and the key operation, which is our infix affix, into the function machine, and on the other end we get our cipherlanguage. Similarly the listener, aware of the infix affix, must listen to that cipherlanguage and deconstruct it into its original meaning. If this works and one can learn the affix rule relatively quickly, this is a true testament to innate human genius in language. Let us now examine our first affix.

Perhaps the most compelling way for one to see how this process works is to walk through the process that Eve must go through when she hears Alice speak with Bob for the first time. To this end please download and listen to the following 60-second audio clip of someone speaking American English with an infix that will be described later. Feel free to listen to the clip as much as is necessary to take a few guesses at its content.

spoken word cipher sample

In cryptography the hardest break is a ciphertext only break. This break, or its spoken-word cipher analog, is what Eve must attempt to perform. Please note any interesting results and leave them in the comments. The next type of attack in cryptography is a plaintext attack. In this attack the plaintext is known and one attempts to find statistical or other anomalies in the ciphertext that may lead to a solution. Now listen to the audio file again, but this time do it knowing that it is the two opening sentences of this essay. Because humans are so linguistically capable it should not be surprising if you can hear and learn the rule this way. Because the purpose of this exercise is to assess the effectiveness of the infix operation, please make a mention if you have already learned the rule. If you have not already learned the rule, which we hope you have not, it is simple. In each syllable after the vowel insert the sound [zlf] and repeat the vowel at the end of the word. So cat becomes ca[zlf]at, dog becomes do[zlf]og, and butterfly becomes bu[zlf]utter[zlf]erfly[zlf]ly. Notice that butterfly does not break down as perfectly with the rule as cat or dog. This anomaly is because the infix operation does not pander to the written language, but rather seeks to preserve some semblance of the original sound for the listener. The hard and fast written rule for butterfly would look like: bu[zlf]utte[zlf]erfly[zlf]y. The reason for this is that when speaking the language Alice needs to preserve enough of the original sound so that Bob can remove the infix and still solve for the word. This requirement is so natural that when this author originally made the rule I violated it unconsciously and almost immediately. Listen to the audio clip two more times. First attempt to understand what is being said without reading along, and then read along knowing the rule. If you have any observations please leave them in the comments. So now we have one infix element that Alice and Bob can use to communicate somewhat securely. Nevertheless, Eve is aware of frequency analysis and, since she read this paper, she knows that she is looking for single syllable words that occur frequently in American English. Once she collects enough audio data she can make a frequency count of the sounds she hears and assume that the most common is the word ‘the.’ Is there an improvement that Alice and Bob can make to further aggravate Eve’s attempts at a solution?

Let us turn again to our discussion of cryptographic functions. Remember the general rule that longer and more random keys are better. Well what Alice and Bob have so far is a key of size one. That is, every time there is a new syllable they use the same infix word segment. Let us now discuss a more complex word formation rule, and thus extend our key length. What if we chose three other infix word segments to go with our existing [zlf] word segment? This would make the key length four, which appears manageable for Alice and Bob, but should aggravate Eve. The question is: how should we use these new word segments. Well the word formation rule for [zlf]appears to serve us well, but wouldn’t it be difficult for both Alice and Bob to change infix word segments after every syllable? It most certainly appears to be difficult but there is a more compelling reason not to use the infix word segments this way. If there is a rhythmic steady repetition of the new key of size four, then Eve may have an easier time breaking the cipher. Imagine two other possibilities: word and sentence boundaries. The former would add a bit of entropy into the cipherlanguage because of the pseudo-random occurrence of multi syllable words, but it may still be too difficult to construct. One benefit would be that the listener could hear word boundaries tagged clearly. The latter would most certainly be easier to construct and would have the same source of entropy, but it may loose in the long repetition of the same sound. Clearly there are many possibilities here, and all would most certainly help to confuse cryptanalysis. Another approach would be to match our infix word segments with common endings or beginnings of words in the English language. Or one can do the opposite and find the most nonsensical segments like [zlf] above. Perhaps one could even attempt to add segments that would give the appearance of another language all together. For example, someone speaking Spanish may wish to construct their infix word segments to give a high occurrence of Italian sounds. There are definitely many possible morphemes worth exploring, and perhaps some other tricks not thought of here.

The last area of investigation, phonetics, includes speech perception and could be a very useful addition to what we have discussed so far. In fact, there may be an argument that much of what we have discussed above should be classified as phonetics. The ability to introduce sounds that are not part of normal speech may help to obscure their meaning; however, they may also be difficult for the listener to understand. The real question is: would such sounds introduce something so unnatural to the human ear that even a-priori knowledge of the key and process would not help the listener? Since this is a more involved area of linguistics we can leave it open for future discussion. For now we have the groundwork for a viable, although weak, spoken-word cipher.

So it would appear that Alice and Bob have a semi-secure means of communication. The cipher is certainly weak when the attacker can record and listen to the conversation later, but it would appear that without exploiting some interesting characteristic of the innate human ability for language one is restricted to this weaker cipher form. The fundamental problem is that cipher function mentioned above. While humans are amazing linguistic machines, the function is too restrictive. When the classical cryptographic ciphers were found lacking they were replaced with more complex and diverse functions. Our innate ability with language, although quite amazing, may be too restrictive for robust cryptographic operations. Ideally one must strive for a seemingly random occurrence of sounds in the resulting cipherlanguage of a spoken-word cipher. Perhaps speech perception and phonetics could make this type of cipher more robust. Furthermore, it should be noted that part of this innate ability humans have with language makes for great error correction. When teaching the basic infix operation above to my wife and friends I found they were less than perfect at speaking the cipher. Nevertheless, I was able to understand everything they said to me because of my ability to match sounds and context. If you, the reader, would like to open a discussion about spoken-word ciphers please do so. There may already be information in some obscure literature that you think would add to the topic. As for now, the spoken-word cipher is little more than something interesting to teach your friends and family.

Following the categories below, in order, is what we would recommend to anyone trying to cover the whole subject of cryptology. Perhaps there are more direct paths to the information your after, which is why we have also organized the list into sub-categories. We hope this helps you find specific information quicker. Please keep in mind that cryptology.dod.net is a work in progress, and if you find yourself overrunning the authors of this site, than we encourage you to start your own categories.

From Start to Finish:
1 - The Codebreakers
2 - Applied Cryptography
3 - Spoken Word Ciphers


Ancient to Modern Cryptology:
1 - The Codebreakers


Modern to Contemporary Cryptology:
2 - Applied Cryptography

Necessary Mathematics:
nothing yet

Thought Experiments:
3 - Spoken Word Ciphers

Read chapter twenty-seven, “Cryptology Goes Public.” This chapter covers cryptography’s growth into the public arena. There is a very basic write up of public key cryptography on page 982. Takes about 45 minutes to read.

Read chapter twenty-six, “Messages from Outer Space.” Some interesting discussions of how one would seed a conversation with another intelligent being. You have probably thought of something like this before, now you have a chance to read what people came up with. Takes about 1.25 hours to read.

Read chapter twenty-five, “Ancestral Voices.” This chapter was very interesting to me, but not from a pure cryptological perspective. If you are an anthropologist, linguist, or classicist you should find this interesting too. It contains three cases of how languages are constructed, and the process of reconstructing each. The most interesting part of the chapter is Miss Kober’s system, which ultimately leads to the decipherment of Linear B (pp. 924-927). Takes about 2 hours to read.

Read chapter twenty-four, “The Pathology of Cryptography.” This chapter is worth reading to understand the pitfalls of poor reasoning in cryptography. Stick with deduction and induction, and always think about the big picture. Takes about 1 hour to read.

Can you find a secret message in the above sentences? Good because there isn’t one

Read chapter twenty-three, “Ciphers in the Past Tense.” More history. Takes about 45 minutes to read.

Read chapter twenty-two, “Runners, Businessmen, and Makers of Non-secret Codes.” This chapter does have an interesting mention of the Acme Code (pp. 847-848). Takes about 2.5 hours to read.

Read chapter twenty-one, “Heterogeneous Impulses.” Just a warning: I think the book becomes repetitious from this point on. The ending 200 pages contain little nuggets here and there, but nothing like the first 800 pages of the book. Takes about 1.75 hours to read.

Read chapter twenty, “The Anatomy of Cryptology.” This is perhaps one of the single most important chapters in the book. I have highlighted almost every page fully, but will still attempt to give you direction. Pay very close attention from page 744 to the end of the chapter. For discussion you should read the steps for determining the entropy of a language on page 760. You can also find this C.E. Shannon paper here. Takes about 1.25 hours to read.

Read chapter nineteen, “N.S.A..” Well let’s face it: you can’t have a book on cryptography without a chapter on the N.S.A.. Just read and enjoy. This chapter may be a bit boring if you have already read the large body of books out there about the N.S.A.. Takes about 2.75 hours to read

Read chapter eighteen, “Pycckar Kphntororhr,” which is the best approximation of a Russian character set that I can do in English text. This chapter covers the more robust systems of the Russians. There is a system described on pages 650-654 that should afford one some security. Also on page 666 there is an interesting mention of microdots. The chapter concludes with a description of the nickel message on pages 669-670. Takes about 2.5 hours to read.

Read chapter seventeen, “The Scrutable Orientals.” This chapter contains more history on the Japanese and their systems and codes. Takes about 2.5 hours to read.

Read chapter sixteen, “Censors, Scramblers, and Spies.” This chapter discuses methods of obfuscation rather than real security. It is primarily concerned with steganography, but is still a worthwhile read. Pages 522-524 will talk about the different types of invisible ink. There is a type of quadratic code discussed on pages 546-547 used for phone conversations, and a more interesting system that works directly on speech on pages 551-554. There is also an interesting innovation for breaking such systems on pages 559-560. Takes about 2.25 hours to read.

Read chapter fifteen, “Duel in the Ether: Neutrals and Allies.” Again this is just the history of the neutrals and allies ciphers during WWII. Enjoy. Takes about 1.5 hours to read.

Read chapter fourteen, “Duel in the Ether: The Axis.” Pay attention to pages 440 to 443 for a description of how to apply the difference method on encicode to deduce the placode. The rest of the chapter is just history of axis WWII cipher and breaks. One can see how the SYKO system worked by reading to pages 463-464. Takes about 2 hours to read.

Read chapter thirteen, “Secrecy for Sale.” This chapter is particularly interesting for the information it contains on different cipher machines, including router machines. Note that 395-396 is basically the XOR cipher. Do a close reading of pages 398-400 for the empirical and a priori proofs of why a one-time-pad system, with a truly random key stream, is completely secure. Read pages 404-408 for a description of how the very first polygraphic crypto system is defined. Also, pages 411-413 will describe the basic principals behind any router machine. There are variations to this scheme like gear changes and cipher alphabets, but the basic principal still holds. From 413-415 one can get a fairly good description of the process for solving router machines. Takes about 1.75 hours to read.

Read chapter twelve “Two Americans.” Pay attention to pages 374-383, which talks about the achievements of William Friedman including the famous “The Index of Coincidence and Its Applications in Cryptanalysis.” This publication is especially important as it applies probability and statistics to the process of cryptanalysis. Takes about 2 hours to read.

Read chapter eleven, “A War of Intercepts: II.” This is more history with the most interesting passage on pages 341-343 where Kahn talks about how Painvin solves the German checkerboard system. Takes about 1.5 hours to read.

Read chapter ten, “A War of Intercepts: I.” This chapter basically talks about the systems each country used in WWI. Pay attention to pages 301-303 to find out about the double columnar transposition ciphers that the Germans used. Page 308-309 talk about the French cryptanalysis of turning grilles. Also pages 312-313 talk about the French systems. Takes about 1 hour to read.

Read chapter nine, “Room 40.” This is an interesting account of pre World War I information with a disclosure of the Zimmerman Telegram. Takes about 1.5 hours to read.

Read chapter eight “The Professor, the Soldier, and the Man on Devil’s Island.” Pay attention to page 235 where one can find the six fundamentals for selecting a usable field cipher. Also page 236-238 will give another derivative cryptanalysis of polyalphabetic substitution ciphers. Takes about 1.5 hours to read.