|
|
|
 |
 |
The Enigma Challenge |
Although perhaps not fully appreciated, mathematical decryption techniques made a huge contribution to the Allied victory in World War II. In that war, Germany encrypted most of its military transmissions with a machine called “Enigma.” Part electrical, part mechanical, it was like a combination lock with more than 10^23 possible combinations. (For comparison, this is roughly the number of tablespoons of water in all the world’s oceans.) Moreover, the Germans changed the combination every day—sometimes several times a day. Recipients of the transmissions needed to possess not only a duplicate Enigma machine, but also to know the correct combination.
If the Allies had had to rely solely on frequency analysis or trial and error, they would still be hunting for that one tablespoon of water in an ocean of possibilities. However, thanks in large part to crucial earlier work by Polish cryptographers and mathematicians, a team of British codebreakers led by mathematician Alan Turing found a shortcut that eliminated almost all of the trial and error for finding the current combination. Now it was more like hunting for one particular tablespoon of water in a small wading pool. Turing’s solution exploited both the mathematical structure of the Enigma machine and certain regularities in the German transmissions, such as their punctual release each morning of a weather bulletin containing the word “Wetter” (the German word for “weather”).
As this episode shows, complexity is no guarantee of security. The most elaborate cryptosystem in the world can be broken if it contains hidden patterns, or if its users unintentionally introduce patterns (such as the weather bulletins). To be truly unbreakable, a cipher would have to be pattern-free. Imagine, for example, a Vigenère cipher whose key is an endless string of randomly generated letters. Such a method has actually been used: It is called a “one-time pad,” because the sender and recipient typically store the key on identical pads of paper, use each page once, tear it off, and never use it again.
However, even though the one-time pad offers the ultimate in security, it dismally fails a second important criterion for a successful code: It is not easy to use. For the method to work the sender somehow has to deliver to the recipient—in a secure fashion—a key pad that is longer than the messages to be sent. This might just be feasible for messages to a single spy, but it would never be practical for widespread military or commercial use. The “key distribution problem,” as this difficulty is known, would remain an obstacle until the latter part of the twentieth century, when mathematics once again came to the rescue. |
|
 | | | CRISIS - Cryptography's Role in Securing the Information Society. A report from the Computer Science and Telecommunications Board of the National Research Council. |  | | Historical Cryptography Web Site - Get an overview of historical ciphers. | | | Mathematical Moments - "Securing Internet Communication" and other PDF flyers for use in teaching and promoting mathematics. | | | Pierre de Fermat - A description of the mathematician's life and work. | | | Primes is in P - The announcement of the discovery of the prime testing algorithm by Manindra Agarwal, Neeraj Kayal, and Nitin Saxena. | | | Spy Museum Game - Email a coded message to a friend (requires Flash). | | | Station X - The official website for Bletchley Park, where Alan Turing and his team cracked the German Enigma cipher. | | | The Prime Pages - Learn more about research into prime numbers. | | | The Quantum Computer - A brief introduction to quantum computers. | | | What is ASCII? - A description of the ASCII coding system. |  |
|
|
|
|
|
