- The Washington Times - Friday, March 3, 2006

Would you like to defeat the German army of World War II? It’s already been done, of course. But, oddly enough, you can use your PC to help break undeciphered military messages from the Third Reich.

The M4 project (at bytereef.org) has broken one message and is working on three more. From the M4 site: “The M4 project is an effort to break three original Enigma (the German code machine) messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed to be unbroken. Ralph Erskine has presented the intercepts in a letter to the journal Cryptologia. The signals were presumably enciphered with the four rotor Enigma M4 — hence the name of the project.”

M4 allows you to download a small program that runs only when your computer is doing nothing else, which for most of us tends to be a lot of the time. The M4 server periodically sends your machine bits of data that need to be processed to break the message. Having done its part of the calculation, your machine sends the results back to M4. You then receive another part of the problem.

The idea is that by putting together the efforts of a large number of personal computers, you get a whole lot of computing power for free. This has been done before for other purposes, such as analyzing radio-telescope data in the search for extraterrestrial intelligence, or SETI. (It hasn’t found any.)

Another such project, more important mathematically, is the discovery of huge prime numbers, in one case consisting of more than nine million digits. The technique is useful for problems requiring phenomenal amounts of calculation when the sponsors don’t have the money to buy supercomputers.

The approach is inherently less efficient than a dedicated computer, because of transmission time and the administrative overhead of tying many computers together. But, with enough computers, it works.

The Enigma machine used by the Germans in WWII to encrypt messages basically used several wheels with alphabets on them to scramble messages. They trusted it, and it worked almost well enough.

But, at Bletchley Park in England, smart people with huge amounts of patience managed to decrypt German traffic. Large steps toward modern computing were made along the way. The program was a well-kept secret with very bad effects for the German military. There are still messages that haven’t been decrypted. With today’s technology, breaking them is a lot easier.

Why does M4 need a lot of computers? Ciphers (often called “codes”) use what are called “keys” to encrypt messages. As an example, you could shift each letter of your secret message two letters to the left in the alphabet: “A” would become “C”, “B” would become “D”, and so on. The “key” here is two. Since for this method there are only 26 possible keys, it is easy to try them all until you get the right one. This is sometimes called “key-space exhaustion.”

Real-world ciphers are designed to have astronomical numbers of possible keys, so that it would be impractical to try them all. However, depending on the cipher being used, there are many shortcuts and techniques to shorten or avoid this “brute force” approach.

Further, cryptography is no longer almost the exclusive province of governments. Judging by results to date, M4 is doing it. It might be more fun than a screensaver with dimwitted fish swimming around.



Click to Read More

Click to Hide