Cryptography

The History and Mathematics of Codes and Code Breaking

Author: sareennl

Understanding the Enigma

Cryptonomicon by Neal Stephenson is an interesting and informative novel tying together different generations of cryptography.   A passage I found most interesting was in the chapter ‘Cycles’.  In this chapter, Stephenson expands on the fundamental mathematics behind the Enigma machine: modular arithmetic.

Stephenson compares modular arithmetic to Turing’s bike.  For some reason, Turing’s bike has a rear wheel with one bent spoke and a weak chain link.  When the spoke comes into contact with the chain at a certain position the chain will fall apart.  The mathematical take on this occurring utilizes a series of variables.  We assume that the spoke is at a degree of 0 (Θ=0) and the position of the chain (C) is at C=0, when the spoke can break the chain.  The weak link is numbered 0, and follows, with I equaling the total number of links in the chain. The sprocket has n teeth, and after one full revolution of the wheel C=n (after two revolutions Θ =0 but now C=2n).  With these variables, Stephenson draws an incredible connection to modular arithmetic.  While C increases infinitely, the number of links does not, and at C=I the chain returns to C=0.  According to Stephenson’s example, if there are 100 links (I=100) and 135 links have passed, C will equal 35 instead of 135.  To put this into mathematical terms, C = 135 mod 100.  In this way, Turing’s bicycle offers an interesting connection to the way an Enigma machine works.  According to the period of an individual cycle within the machine, the difficulty in cracking a code increases.  This period is similar to how Turing’s bicycle returns to Θ=0 and C=0.  How exactly does this help determine when the chain will fall apart? According to Stephenson, this will happen when a multiple of n is also a multiple of I.  This perspective provided me with a better understanding of modular arithmetic and showed how complex the Enigma machine can be when the period increases.

Image: "Hydroelectric Turbine," by Guy Mason, Flickr (CC)

Should Unlimited Security be Limited?

When the Data Encryption Standard (DES) was created, the National Security Agency made sure that it was weak enough that they could break it.  The Data Encryption Standard was a result of Horst Feistel’s product, Lucifer.  Lucifer was a machine that could encrypt data, making the encryption nearly impossible to decrypt.  In 1976, the NSA made the decision to limit the DES to 100,000,000,000,000,000 possible keys.

The strength of a cipher is directly correlated to the number of possible keys.  With so many possible keys, no common computer could possibly decrypt a DES encrypted cipher.  Most powerful computers are capable of finding the correct key when the number of possible keys is only 1,000,000.  By limiting the number of possible keys to a number higher than what a typical computer is capable of breaking, the NSA justified its decision.  The DES was created so that all businesses could communicate securely and reliably.  Even with a limit on the number of possible keys, the same goal was achieved.  Though the security was less than optimal, the security would still be unbreakable.   More importantly, if the DES were too strong, the government and NSA would be incapable of tapping information.  As we’ve previously discussed in Little Brother, there are times where the government needs full access to all forms of communication.  If the NSA did not limit the number of possible keys, it would put domestic and international security at risk.  In this way, the NSA was justified in making sure it was weak enough that they could break it.

Image: "Bokeh Command" by Robert S. Donovan, Flickr (CC)

The Costs of Privacy

Cary Doctorow’s Little Brother tells the story of Marcus Yallow, a high school student who rebels against the Department ofHomeland Security for violating his rights to privacy.  Marcus goes to the extent of creating a new secure Internet, hacking transportation systems, and much more to protect himself and others from the DHS.  I found Chapter 3 and 4 to be most interesting because Doctorow directly questions whether our rights to privacy are more or less important that protecting our country.  The unreal treatment Marcus faces while being interrogated changed my opinion over the topic entirely.  When Marcus was interrogated by the lady, why did Marcus feel so strongly over maintaining his privacy?  At first, I felt Marcus’ innocence was more important, and since he had nothing to hide he should hand over his phone.  I tried to put myself in his position and then realized I would feel uncomfortable if I was forced to hand over my text messages and emails to a random stranger.  Marcus maybe felt that because he was innocent he should continue to refuse to give his phone up.

Our right to privacy is a central theme in Little Brother, and is constantly questioned throughout the novel.  It is this right that has pushed cryptography to even larger extents, including securer methods of sending information on the Internet or keeping your information private entirely.  Surely, Google and Facebook use information for advertisements and other services, however, this is information that I’ve openly displayed to the public.  I have willingly put this information on the Web, knowing that it will not be private anymore.  Should any stranger attempt to access other private information, then my right to privacy has been violated.  In Marcus’ case, he faced the latter situation, and retained his privacy.  Ultimately, Marcus took a stand to end violations of this right, due to one instance of injustice.  As terrorism continues to rise, the government has increased its control over private information through phone taps and keyword tracking.  Should government control continue to increase, the people will have to decide if the costs of retaining privacy are too great.

Image: "Keep Out from Francisco Huguenin Uhlfelder," by Francisco, Flickr (CC)

The Motivation of Mystery

The Beale Ciphers have challenged thousands of cryptanalysts for the past hundred years.  The Beale Ciphers consist of three ciphers and are seemingly unbreakable.  While most professionals would give up after several unsuccessful attempts, people still continue to try and break them.  The ciphers remain a mystery while hiding a very rewarding treasure.  The motivation to break these ciphers may simply lie in the wealth one could acquire if they cracked the ciphers.  However, the human mind is very curious, and with each uncovered step, our curiosity increases.  The Beale Ciphers possess a lure due to the fact that one of the ciphers has already been broken.  This has provided hope for current professionals and amateurs, making them believe that the key can be found.  On the other hand, history has shown that even the most difficult ciphers (i.e. the Great cipher) can be cracked.  People still attempt to break them because the fame associated with such a discovery would be equally as rewarding. Ultimately, these factors have kept the Beale Ciphers under constant scrutiny to this day, despite how difficult they are to solve.

Image "Keyhole" by StudioTempura, Flickr (CC)

A Great Deal of Creativity

As cryptographers attempted to improve the security of ciphers, while maintaining their practicality, more complex ciphers were being created.  The monoalphabetic substitution cipher was becoming less secure, leading to the advent of the polyalphabetic cipher and the homophonic cipher.  Yet, these ciphers required much more time to encipher, and were too complex for everyday use.  Cryptographers were on a mission to develop a cipher that was less complex than a polyalphabetic cipher and just as secure.  By the 17th century Antoine and Bonaventure Rossignol met that goal by creating the Great Cipher of Louis XIV.  The Great Cipher was simply an enhanced version of a monoalphabetic cipher, yet it remained unbroken for over two hundred years.  How was the Great Cipher so secure?

The Rossignol's were both excellent cryptographers and cryptanalysts.  As cryptanalysts, they had much more insight when creating the Great Cipher.  The Rossignol’s knew that this new cipher had to be very different from ciphers in the past.  This would ensure the security of Louis XIV’s messages and French secrets.  By acknowledging this idea, and using their past experiences as cryptanalysts, the Rossignol’s created a cipher that used numbers to encode syllables.  In the past, no cryptographer attempted to encipher a plaintext according to anything but letters.  By using syllables, it would take years for any cryptanalysts to decipher their codes.  Cryptanalysts rely on past information in order to solve a cipher.  Because the Great Cipher utilized a new method, cryptanalysts found it very difficult to solve.  Another factor that led to such a secure cipher was that the probability of solving the Great Cipher was so low.  The Great Cipher utilized 578 numbers, whereas typical monoalphabetic substitution ciphers featured 26 letters.  The Rossignol’s didn’t rely on just the use of syllables as their only method of security.  They also included traps in their ciphers to confuse cryptanalysts.  Sometimes numbers represented a single letter instead of a syllable, while other times a number represented nothing at all.  Ultimately, the Great Cipher represented a significant change in cryptography.  It utilized creativity and several lines of defense to keep the French secrets safe.

The Accessibility of Knowledge

In Simon Singh’s The Code Book, he states “Cryptanalysis could not be invented until a civilization has reached a sufficiently sophisticated level of scholarship.”  If such a sophisticated level of scholarship was needed to invent cryptanalysis, and cryptanalysts were considered to be of ‘higher’ scholarship, why are amateurs capable of decoding ciphers themselves?

Is the world becoming more intelligent? That I do not know.  But it is obvious that knowledge is spreading and learning is occurring more vigorously throughout the world than in the past.  As children grow, they are expected to conquer challenges using the mind, not their fists, and grow mentally as they progress through the education system.  They are expected to continue their path of learning to higher degrees in high school and college, and expand on their critical thinking abilities.  Therefore, society's expectations have furthered amateur cryptanalysts ability to decode messages.

Frequency analysis is a very complex approach to cracking a code.  Yet our minds are capable of applying frequency analysis subconsciously when the opportunity presents itself.  For example, in the word game, Hangman, our mind subconsciously guesses letters that are frequently seen in words (vowels, specific consonants).  Ultimately, people can only apply “on their own” approaches if they have been exposed to higher levels of critical thinking.  Education and the accessibility of knowledge provide the world with these abilities to critically think and solve problems. Amateur cryptanalysts, though untrained, can accredit their code breaking skills to the education they’ve received from such an early age.

Powered by WordPress & Theme by Anders Norén