Slashdot Mirror

CWI has several source code license agreements with companies in The Netherlands, USA, Germany and France which allow them to use the Number Field Sieve factorization code as this was and is being developed by P.L. Montgomery, A.K. Lenstra, M. Elkenbracht-Huizing, S. Cavallar and B. Dodson. On a non-commercial basis, the NFS source code has also been made available for research purposes to other cooperating groups. A group of the Royal Institute of Technology in Stockholm (Hastad) has used this code as a basis for factoring a hard 512-bit challenge number in October 2000.

The current record factorings were done with the GNFS (General Number Field Sieve).

GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.

The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.

Some pointers:

• Integer factorization
• RSA-155 English press release
• Description of the task, from Singh's The Codebook Challenge
• RSA-129 factoring
• What are the best factoring methods in use today? (RSA Security FAQ)
• A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths by Bob Silverman

In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.

to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.

to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.

Good luck.

Quote from How we Cracked the Code Book Ciphers
---
From: Fredrik Almgren
Subject: RE: Nervous
Date: Fri, 6 Oct 2000 11:07:44 +0200

I have just talked on the phone with an English-speaking gentleman who said he was Simon Singh. He started off the call with a short discussion on how he was going to make me believe that he was indeed Simon Singh. After some rambling from my side, he said that the first part of the plaintext for Stage 10 consisted of fourteen words and that words 5 and 14 rhyme. At that point, I felt about ready to accept that he was really who he claimed.
----

This is the first time "normal" computer hardware has been used to break a 512-bit RSA key.

The first public break of an RSA key of this size was performed using 224 CPU hours on a Cray C916 whilst the team that cracked the codebook puzzles took just 13 days on a quad-Alpha Compaq beast.

Don't forget, before the export rules were changed around 90%+ of all "secure" SSL transactions on the internet were using 512-bit keys. Scary, huh?

--

And did anyone else notice that the Codebook Solution, http://codebook.org/codebook_solution .ht ml, is missing the section on Stage 5! I had to DL the pdf document to read that.

Get the PDF - Stage 5 is in there in detail. It was a bitch indeed...