One paper outlined attempts to implement a cryptography algorithm in programmable hardware, while another showed how an FPGA's architecture can speed the effort to factorize large numbers, a task essential for cracking common public-key encoding schemes.

Worcester Polytechnic Institute professor Christof Paar and graduate student Adam Elbirt outlined how his team tried to craft a reconfigurable FPGA to execute Serpent, a cryptographic scheme being considered for the Advanced Encryption Standard.

The purpose of the exercise was to find the best architecture for representing Serpent in reconfigurable hardware, Elbirt said. The use of a reconfigurable part allows the algorithm to be changed or swapped entirely, a requirement in some multi-algorithmic cryptographic systems such as the Secure Socket Layer. It also would allow vendors to design AES hardware now, before the standard is established.

"The whole industry knows the new standard will be here," Paar said. "In the meantime, they are still selling devices."

On a more general level, a hardware implementation is desirable because it will run inherently faster than a software implementation—in this case, beating software's 100 MHz mark by an order of magnitude, Elbirt said.

The Serpent algorithm includes a 32-iteration loop of substitution functions, and the WPI team tried multiple ways of implementing that loop. Hard-wiring one loop and running it 32 times resulted in a circuit that consumed unexpectedly large die area due to the amount of multiplexing required. But as the team spread out the look—hard-wiring eight circuits that ran four times each, for example—the timing began to suffer.

In the end, Elbirt reported, the team got its best results with a fully pipelined layout, one that required extra registers but was able to break gigabit speeds. "With a few tweaks, we crested the 5G-bit mark," he said. "The throughput just screams."

Software implementations of Serpent top out around 100 MHz, by contrast, Elbirt said. A subsequent paper delivered by Ph.D. candidate Hea Joung Kim of UCLA showed how FPGA hardware could speed up the factorization of large numbers.

Sieving, a number-theoretical method for quick factorization, can take up 75 percent of CPU cycles, Kim said. But FPGA hardware can take advantage of "some inherent parallelism that is available due to the nature of prime numbers."

The trick involves setting up four memory banks which are accessed simultaneously, allowing faster execution of the repetitive calculations required for sieving.

The UCLA team reported speeds 28 times faster than an UltraSparc workstation, Kim said. In fact, the speed of the implementation is limited by the speed of the SRAMs inside the FPGA. Using a board laced with 8-ns SRAMs, Kim expected the speed factor to increase to 160 times that of a workstation.

In fact, Kim said, this is a case where the faster speed of an ASIC isn't helpful. "Because the FPGA [implementation] is fast enough to saturate almost every SRAM on the market, you don't need an ASIC," he said.

Kim took a moment to compare his implementation against Twinkle. Proposed by Adi Shamir, co-creator of the RSA algorithm, a theoretical box that performs factorization in hardware, able to analyze 100 million large integers in 10 milliseconds.

Kim's FPGA handles the same task in around 65 milliseconds, but he made the point that Twinkle exists only on paper. The UCLA project doesn't " have a product yet, and it'll cost $1 million to make, plus $5,000 per wafer," Kim said, quoting Shamir's own estimates.