The History and Mathematics of Codes and Code Breaking

Month: November 2012 Page 1 of 4

Math Exam Study Guide

Here's a study guide for this week's math exam, in both Word and PDF formats. (Some of the mathematical notation might not come through in the Word file, so check the PDF if you're confused.) The guide includes a list of topics covered by the exam, along with lots of practice problems. I'll post solutions to those practice problems tomorrow.

Update: Here are solutions to the practice problems in the study guide, in both Word and PDF.

Paper #3 - Big Questions Paper

Here's the assignment and rubric for your final paper assignment, the "big questions" paper. A draft outline of your paper is due in class on Tuesday, December 4th, and your final paper is due by noon on Thursday, December 13th. If you have any questions about the assignment or need help getting started, just ask.

Image: "Pen and Paper," Lucas, Flickr (CC)

Social Bookmarking Assignment #5

For your fifth bookmarking assignment, you're invited to bookmark anything you like that's related to cryptography. Look for a news article or resource on cryptography that's interesting to you, or find something that you might use in your "Big Questions" paper. Give your bookmark at least two useful tags.

Your bookmark is due by 8:00 a.m. on Tuesday, November 27th. We'll take a little time in class to share your finds.

Image: "Interesting Pin," by me, Flickr (CC)

Singh Chapter 7 - Reading Questions

We'll discuss the seventh chapter of The Code Book in class on Tuesday. In case you'd like a little guidance for your reading or would like to prepare for discussion tomorrow, here are a few questions about the chapter you might consider. I'm not expecting you to answer these questions (on the blog or in writing), I'm just providing them as a resource.

  1. What do you see as the two most compelling reasons why strong encryption should be available to the general public, even if that means it's available to criminals and terrorists?
  2. What do you see as the two most compelling reasons that strong encryption should be restricted by law enforcement and national security agencies?
  3. Singh, writing around 1999, makes several predictions about the role of the Internet in our lives in the opening paragraph of Chapter 7. To what extent have these predictions come true? Are there other ways that the Information Age in which we now find ourselves has elevated the importance of encryption among the general public?
  4. On page 315, Singh writes that Zimmerman, through a friend, “simply installed [PGP] on an American computer, which happened to be connected to the Internet. After that, a hostile regime may or may not have downloaded it.” In your opinion, do you think that someone who makes a piece of software available on the Internet should be held at least partially responsible for what criminals or foreign governments do with that software?

Problem Set 5, Question 4

As promised, here's a solution to Question 4 on Problem Set 5. I know it was a tough one, so if you didn't get it, hopefully you can at least understand the solution when it's all laid out.  You don't need to understand the proof of Theorem 4, also in that PDF, but I've included it for those interested.

Dead Pixels

Too Far, and yet Not Far Enough

One passage that I particularly liked for its relevance to modern day encryption, is when Randy and Avi are communicating using Ordo, a program that helps them encrypt their messages. It uses modern encryption where the user selects a key length and creates a key, which is used to encrypt the messages. The longer the key, the more other possible keys there are and the harder it is for someone to crack. In the book, Ordo gives the options of 768, 1024, 1536, 2048, and 3072 bit keys. A 768 bit key by itself is very difficult to break and would take a lot of time. However, Randy and Avi decide to use a 4096 bit key, which is effectively unbreakable. For reference, each additional bit added (like 768 to 769 bits) doubles the total number of possible keys, so 4096 bit keys are not just a lot harder to break, they are literally unbreakable in comparison.

Dead Pixels

Dead Pixels by coda

This is very similar to the RSA encryption we have discussed in class, as far as the prime numbers involved and the time it takes to crack. So the question is, how far does one really need to go to create a key? As Randy says, "it would take longer than the lifespan of the universe" to break the key (Page 54). Even with the advancement of technology at the rate it moves, a key only needs to last so long and surely 4096 bits accomplishes this completely.

This passage added to my understanding of the encryption by helping me get a perspective on just how big these keys are and how safe they are as far as ability to be broken. Like I said, these topics that deal with modern day encryption by far interest me the most since they are basically what we continue to use today. I feel that the more we know about the encryptions that we actually use, the more safe we can keep our information.

Image Credit: Dead Pixels by coda

Pecha Kucha

Before I share a few Pecha Kucha resources, here's the list of possible titles you generated for blog posts, short papers, or presentations:

  • Turning the Tide of WW2 Cryptography
  • Turing the Mathematics of Cryptonomicon
  • The Beautiful Mind of Lawrence Waterhouse
  • Ending Engima
  • Colors of the Rainbow: Japanese Ciphers of WW2
  • When You Can Go Too Far and Not Far Enough: Ordo and Keys
  • Only as Strong as the Weakest Link
  • Data Havens for Fun and Profit
  • Learning Modular Arithmetic in Three Pages or Less
  • Taking One for the Team: Detachment 2702’s Contribution to WW2
  • Lawrence Waterhouse: A Different View on Everything
  • The Psychology of Bobby Shaftoe
  • How Mathematicians Think
  • The Awesomeness of Bletchley Park
  • When Bits Become Bytes

(For the record, four of those suggestions are mine.)

Now for some Pecha Kucha resources. First, the Pecha Kucha organization, which coordinates Pecha Kucha nights all around the world, including Nashville. The organization has used their network in creative ways to aid in disaster recovery efforts, including the 2011 Japan earthquake.

Here's the sample Pecha Kucha presentation I shared, by the University of British Columbia's Tegan Adams:

For more examples, check out Pecha Kucha Atlanta's website, which features lots and lots.

Finally, if you forget how to pronounce Pecha Kucha, here's a Muppets-themed reminder.

Image: "pecha kucha night book," Brandon Shigeta, Flickr (CC)

Math Behind the Shark

In a section of Cryptonomicon entitled "Cycles," there are a few pages that go into detail explaining how the three wheels in the enigma machine give it a certain security level and how the adding of the fourth wheel in the system Shark increased the security of the machine. It is explained by comparing the chain of letters created by the enigma machine to a bicycle with a weak link in the chain. The "weak link" in the enigma machine is the first chain that is created to encipher the first letter and when the same chain is used again which occurs 17,576 letters later. When the Germans added another wheel they increased the number of links in the chain to 456,976 and since their messages were hardly ever that long the weak link usually never came into play.

This section of the book added onto my understanding of the enigma machine and how the 4th wheel added so much more security. The increased security was explained through a number of pages with a lot of mathematics on them which helped me see more clearly what factors were actually playing a role in increasing the security of the enigma machine when adding the fourth wheel and creating Shark.







Image: "Chain," by Pratanti, Flickr (CC)

Better Safe than Sorry

In the “Tube” chapter, Captain Waterhouse visits Detachment 2702 and discusses with Colonel Chattan the possible height problem of the women working the bombes. All of the women that work with the bombes need to be tall enough to wire up the tall machines, and Waterhouse and Chattan entertain the idea that the Germans can obtain the personnel record of Detachment 2702. The personnel record would reveal that there are an abnormally large number of tall women working at 2702. Waterhouse and Chattan then assume that the Germans have an open channel to retrieve the records and discuss possible solutions.

The dilemma that Waterhouse and Chattan face resembles a situation in which two parties are exchanging messages but do not know that a third party is reading the messages. As seen with Mary Queen of Scots, assuming that one’s cryptosystem is secure can lead to carelessness and result in severe consequences. The conclusion reached in class discussion is to act like there is a third party that can decrypt one’s messages and to take extra measures to conceal the meaning of the message through euphemisms or symbols. The military officers in this scene assume the position that their enemy is able to access their data freely.

Their solution to this problem is quite innovative. Instead of outright closing the channel and blocking their enemy’s access, they keep the channel open so the Germans won’t suspect anything. They also decide to feed false information through the channel to fix the height anomalies in their personnel records. Their strategy effectively turns their disadvantage into an advantage. Using an enemy’s advantage (breaking the cipher) to manipulate them (feeding them false information) is an ingenious strategy. But this strategy requires the knowledge that the original cipher is broken and that a third party can read the message. Employing this strategy requires an essential assumption discussed earlier in the course: no message is completely secure, and to be safe (and paranoid), one should act like the cipher is broken.

Image: "Bombe detail," by Garrett Coakley, Flickr (CC)

The Pursuit of Randomness

The section of Cryptonomicon that really caught my attention was the section between pages 422 and 427. This section describes the British interception of German messages from U-553. These messages are different from the previously intercepted Enigma messages. These messages are encrypted utilizing Baudot Code, a code that used thirty-two characters. The system was based off of a power of two and therefore each character had a unique binary representation that contained 5 binary digits.  As we learned in class, these digits were either 1 or 0.

My blog post for our last essay dealt with the Lorenz teleprinter cipher and the Lorenz machine. These new messages that Waterhouse has discovered are in fact encrypted with the Lorenz cipher. The idea behind the Lorenz cipher was that if the paper used in communication was pre-punched with a completely random set of excess or obscuring characters, the cipher would be unbreakable. However, both the sender and receiver would have to have this paper, which is impractical in wartime. In Cryptonomicon, Waterhouse figures this out and he and Alan conclude that the obscuring characters in the cipher text could only be pseudo-random. This lack of complete randomness, and German error, lead to the British being able to crack the Lorenz cipher without ever seeing a Lorenz machine.

This section also discussed the building of Colossus, the first electronic calculator. Colossus is ultimately used to decrypt many intercepted German messages, crack the Lorenz cipher and lead to many Allied victories. The issue of the Lorenz Cipher reinforces our class lesson on binary numbers and further discusses the idea of a one-time pad and whether something is truly random and unbreakable. This example in Cryptonomicon helped me understand how difficult pure randomness is to achieve, especially in a wartime situation.

Image: "Binary Blanket," by quimby, Flickr (CC)

Page 1 of 4

Powered by WordPress & Theme by Anders Norén