Hacker News Reader

Comment by jrmg | Hacker News Reader

In the 90s, how long did people expect it would be until consumer computer hardware would be able to do this so quickly?

View on HN

In Schneider's 1995 book he estimated factoring a 512-bit number would take roughly 30,000 MIPS-years (a one-million-instruction-per-second computer running for one year).

When a research team actually factored RSA-155 in August 1999, it took 8,400 MIPS-years due to efficiencies discovered. It still took 35 CPU-years spread across a cluster of 300 fast SGI/SUN workstations and Pentium II PCs (400-500 MIPS each), crunching in parallel for seven months. https://cs.ccsu.edu/~pelletie/local/risks/cryptography/Facto...

Robert Silverman, a senior research scientist at RSA Laboratories, published an analysis projecting these new hardware requirements against Moore's Law. His expectation was that within 10 years (roughly 2009–2010), common desktop machines would possess the speed and memory necessary to handle a 512-bit factorization entirely on their own. https://cr.yp.to/bib/2000/silverman.pdf

I don't know how fast my CPU cores are in MIPS, but it's 4.5 Ghz and some random googling indicates that might be about 10 MIPS per Mhz, so 45,000 Dhrystone MIPS.

And assuming about ((32x32 core-hours) / 8766 (hours/year)) x 45,000 = 5256 MIPS-years.

So within the order of magnitude of the 1999 factoring! Of course, the MIPS number is kinda made up, so

Only lunatics would do it on CPU's though. They'd use their GPU cluster, with custom SW (not yet online). RSA-1024 would cost about a week then.

GPUs may have existed in the 90's but they were very specialized to graphics and couldn't do general purpose computation like factoring integers.

From my recalling, a few years at most. There was, and apparently still exists, distributed.net which was aimed at brute forcing DES (easy), RC5-56 bits and then RC5-64 bits by establishing a web of personal computers (via a client one had to install). Thus it was well known brute forcing was achievable in a reasonable time.

PGP (1991) was considered secure as it was considered not brute forceable. With 128 bits, it was considered military grade at the time and the US had an export restriction due to that. That might have been an incentive for GNU Privacy Guard. In France you had to give your private key to the government authority if an encryption system used anymore than 56 bits (as I recall, I don't remember the exact number).

It was also illegal to export software with cryptography in the early 90s, anything with keys bigger than 40 bits, so there was a lot of intentionally weak connections.

At least in the US in the 90s, crypto was effectively required to be breakable. There expectation was this was possible at that time.

In 1999, factoring RSA-512 required roughly 292 CPU-years of work distributed across hundreds of academic machines, running for about 7 months. The community already knew it was weak -- the US export restrictions on 512-bit RSA were explicitly calibrated so the NSA could break it while casual adversaries couldn't.

Consumer hardware doing it in a couple of days in 2025 is roughly in line with Moore's Law extrapolations people were drawing at the time. The surprise isn't really the timeline. It's that someone did it as a weekend project rather than a nation-state effort.

Reply on news.ycombinator.com