Computer Security : Team Cracks Key to Many Secret Codes

Some secret codes that keep unauthorized people from gaining access to everything from military secrets to Swiss bank accounts may not be as safe as had been presumed, a team of computer experts demonstrated Tuesday.

The team succeeded in doing what security experts thought could not be done: using ordinary computers to break down a 100-digit number into the components that produce it when multiplied together.

That process, called factoring, holds the key to many security codes.

Linked Together

Before Tuesday, experts had believed that if the number was large enough--up to 100 digits--it would take about 10 months with a Cray supercomputer, one of the most powerful computers in the world, to factor it. But computer experts across the United States, Europe and Australia solved the problem more quickly by using 400 processors simultaneously. They linked their computers together electronically and factored a 100-digit number in just 26 days.

The number has two factors, one 41 digits long and the other 60 digits long.

And that, according to Arjen Lenstra, professor of computer science at the University of Chicago who headed the project, should be quite sobering to experts who believe that they are secure with codes based on numbers that large.

“We see that it’s unsafe” to use 100-digit codes, Lenstra said just hours after he and his colleagues completed their work at 4:03 a.m. CDT Tuesday.

Lenstra, who is one of the nation’s leading experts on computer science, said it was the first time that general purpose computers have been used to factor a number that large.

“Some crypto (security) systems are based on the fact that it is difficult to factor big numbers,” he said in a telephone interview. “Now we see we have this general purpose method, so you have to reconsider the bounds that you are going to use.”

Rodney M. Goodman, associate professor of electrical engineering and an expert on cryptography at Caltech, described the achievement as significant because it means that some systems may not be as secure as had been thought. But he said it does not mean security experts around the world will have to scramble to rebuild their systems.

“All the cryptographers will do is increase the length of the number by a few more digits,” he said, “because the problem gets exponentially worse as you increase the size of the number.”

Size Grows

The size of the number needed to assure secrecy has grown considerably over the years, Lenstra noted. A larger number is more cumbersome, and cryptographers had tried to keep the number as small as possible.

“A few years ago, people suggested that 100 digits would be safe,” Lenstra said. “Now, maybe it will take 150.”

The problem revolves partly around the desire to allow some people to contribute to a numbered bank account, for example, but restrict withdrawals to only those with the right combination.

Anyone given the right number, say the two-digit number 60 for the sake of simplicity, would be able to make deposits in the account.

But only someone who could figure out the designated factors of 60 (5, 3 and 4, for example) would be able to make withdrawals. The factors, in effect, are the combination to the lock.

In actuality, a number as low as 60 would not be used, and the factors themselves would be prime numbers--numbers that cannot be divided by any other number--because they are much more difficult to discover, Caltech’s Goodman said.

It does not take a mathematical wizard to figure out the factors of 60, but if the number is larger, the problem becomes vastly more difficult.

Mistaken Belief

And if it is 100 digits long, only a handful of supercomputers around the world could do it. Or so people thought.

Last year, Lenstra decided to tackle the problem on “a small scale, just to see if he could do it,” according to Larry Arbeiter, spokesman for the University of Chicago. “It was a pure science type of effort.”

Several months ago, Lenstra presented his idea to Mark Manasse, a computer research scientist with Digital Systems Research Center of Palo Alto. Manasse became so intrigued with the problem that his company agreed to fund much of the cost, including the use of more than 300 computer processors at the Palo Alto company during off-duty hours. The company manufactures Dec computers.

“I was interested in the general problem of taking a program and breaking it up into small pieces” so that many could work simultaneously toward the solution, Manasse said.

Other computer enthusiasts from the “factoring community” clamored to get aboard and this fall more than 400 computers around the globe were ready to give it a try.

Range of Sizes

The computers ranged in size from microcomputers to a Cray supercomputer, but even personal computers with large memories could have been used, Lenstra said. Each of the participating computers was given a different part of the problem to solve, and success came early Tuesday morning.

What makes the project intriguing to computer scientists, and possibly troubling to security experts, is that the computers were general purpose processors that were linked together through an electronic mailbox. That same technique is used by thousands of computer owners around the world for purposes ranging from shopping to exchanging technical data to banking.

“It’s so easy to tie everything together,” Lenstra noted, that a security system based on a 100-digit number is “not that secure anymore.”

He plans to crack a 110-digit number in the near future, but since the difficulty grows with the size of the number, even he admits there are limits.

“I think 150 is still out of reach,” he said.