SCIENCE & ENGINEERING NEWS

San Diego, CALIF. — What do five Swedish scientists, Robinson Crusoe and a Compaq AlphaServer all have in common? Using a speedy 64-bit Compaq SMP system, the computer scientists completed on October 7th the Cipher Challenge, an international contest that required them to decipher ten progressively more difficult encrypted messages including a book cipher prompting them to sift through Robinson Crusoe, Treasure Island and other books.

Capping a yearlong effort, the team cleared the final hurdle by using creative-problem solving along with a four-CPU Compaq AlphaServer ES40 system to solve equations normally reserved for multimillion-dollar, vector-processor supercomputers.

The Cipher Challenge was conceived by British author Simon Singh and included in The Code Book, his history of codes and code breaking since ancient times, published in 1999. The Cipher Challenge consisted of a set of ten encrypted messages of progressive difficulty with target keywords, beginning with a simple substitution cipher and concluding with two computerized encryption methods known as DES and RSA, the latter commonly employed for encrypting sensitive information such as credit card numbers and electronic signatures.

The five-member Swedish team – Fredrik Almgren, a mobile Internet solution designer; Torbjˆrn Granlund, owner of an Open Source software company; and Gunnar Andersson, Lars Ivansson, and Staffan Ulfberg, three Ph.D. candidates at the Royal Institute of Technology in Stockholm – joined the competition when Almgren bought Singh’s book in London shortly after its publication and discovered the Cipher Challenge inside.

The team worked through the early stages of the challenge with relative ease, solving seven stages in about three weeks and an eighth stage a month later. Only Stage 5, the troublesome “book cipher,” and the computer-based cipher of Stage 10 remained. All the while, the team watched and worried about the progress of other competitors, which they monitored through Usenet news groups and mailing lists that quickly sprang up in the wake of the book’s publication. While taking part in the discussions, the team operated in “stealth mode,” keeping its own progress mostly to itself.

Although they were not the first, the Swedish participants solved Stage 5 on May 10, 2000 after a laborious, computer-aided search through dozens of sources – The Bible, The Divine Comedy, Robinson Crusoe, The Adventures of Sherlock Holmes, Treasure Island and many more – to discover the proper text to which to apply the code. Suggested by the mere fact that Singh, the Cipher Challenge’s creator, had written a book, Fermat’s Last Theorem, the correct source turned out to be a marginal note in Latin, well known in mathematical circles, by mathematician Pierre de Fermat.

The daunting final stage was based on a 155-digit RSA encryption. Factoring the 155-digit number became a multiphase undertaking using the General Number Field Sieve (GNFS) to identify relations – 75 million relations were used -an iterative filtering process to reduce the variables and simplify the equation, and finally the immense number-crunching task to solve the linear equation system. The search for relations was conducted on hundreds of workstations at the computer science department of the Royal Institute. Filtering was performed primarily on an AlphaServer DS20 system with dual 500 MHz processors at UMS Medicis in Palaiseau, France.

To complete the factoring process, the team adapted the program that was used in 1999 by the Centrum voor Wiskunde en Informatica (CWI) in The Netherlands to factor a 155-digit RSA number, then a world record. The CWI program was optimized to run on vector computers and had taken 10 days to solve a slightly smaller equation system on a 16-processor Cray C90 system. After modifying the program to run on non-vector systems, the Swedish team figured that the two-processor DS20 would still require 37 days to reach a solution – more time than they could get.

At that point, in September 2000, they approached Compaq for help with the computation, thinking, “This was a great opportunity to show how powerful the Alpha is for scientific computation.” Randy Doering, at Compaq’s Washington Benchmark Center in Greenbelt, Md., and Roland Belanger, of Compaq’s High Performance Expertise Center in Marlboro, Mass., arranged access for them to a quad-processor AlphaServer ES40 system.

The total running time to solve the equation on the AlphaServer ES40 came to 13 days – almost as fast as the 16-processor Cray system. On October 4 at 5:05 a.m. in Stockholm, the program produced the result, yielding 11 true dependencies, which were then used to get the factors – another 11-hour process.

At last, during the morning of October 5, they found the factors and performed the final decryption, revealing the vital keyword. After sending a letter and a fax to London, another anxious day passed before Almgren received a call from Simon Singh to confirm that the Swedish team had indeed won the competition and the top prize of £10,000.

“Thanks to the Alpha processor, we have thus been able to show that it is possible to factorize 155-digit numbers without using expensive vector computers,” the team wrote.

“Our, and Alpha’s, achievement to factor a 512-bit RSA key without using vector computers is getting a lot of attention in Sweden and other countries,” said Granlund. “We even got calls from CNN.

“We take each opportunity to say that we ran this on Compaq Alpha hardware and try to explain the significance of that,” Granlund said. “Alpha is truly amazing technology, which I tell to whoever listens.”

============================================================