Full HTML for

Scripted foilset Lessons and Implementation -- RSA Factoring on the Web

Given by Geoffrey Fox at CRPC Annual Meeting on May 14-17 1996. Foils prepared May 12 1996
Outside Index Summary of Material

We describe the RSA Factoring Problem and the solution developed by Lenstra and collaborators with sieving techniques of increasing power
The Web was used succesfully in the just completed RSA130 factoring -- an almost embarassingly parallel but very non trivial computation
The mathematicians are preparing code for RSA155 factorization and probably Web will be critical here to increase resources from Teraop-hours (RSA129/130) to the needed Teraop-Months (RSA155)
We overview architecture of FAFNER system used and lessons drawn for general Metacomputing administration MetaWeb
http://www.npac.syr.edu/factoring.html

Table of Contents for full HTML of Lessons and Implementation -- RSA Factoring on the Web

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 RSA Factoring on the Web -- Lessons and Implementation
2 Abstract for RSA Factoring on the Web
3 RSA Factoring on the World-Wide Computer
4 Digital Crime(!?) Home Page
5 Factoring RSA Codes -- Software Resource FAFNER
6 RSA: Public Key Cryptosystem
7 How hard is Factoring the Public Modulus?
8 General Number Field Sieve -- GNFS:
9 Sieving (RSA-129 and MPQS, RSA-130 and GNFS)
10 BASIC OBSERVATIONS AND TERMS
11 SIEVING THE Q-INTERVAL
12 Extracting The Relations
13 FIRST Backend Processing STAGE GRAPH REDUCTION
14 SECOND Backend Processing STAGE GRAPH REDUCTION
15 Web Virtual Machine and Server-Server Communication Model
16 Hierarchical FAFNER Servers
17 Features of FAFNER Server Code
18 Features of CLIENT CODE
19 TECHNICAL CHALLENGES
20 Social/Administrative CHALLENGES
21 RSA130 Factorization is completed!
22 Sieving was done on a great variety of workstations at many different locations:

Outside Index Summary of Material

HTML version of Scripted Foils prepared May 12 1996

Foil 1 RSA Factoring on the Web -- Lessons and Implementation

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
CRPC Annual Meeting
May 16 1996
Geoffrey Fox
NPAC
Syracuse University
111 College Place
Syracuse NY 13244-4100
HTML version of Scripted Foils prepared May 12 1996

Foil 2 Abstract for RSA Factoring on the Web

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
We describe the RSA Factoring Problem and the solution developed by Lenstra and collaborators with sieving techniques of increasing power
The Web was used succesfully in the just completed RSA130 factoring -- an almost embarassingly parallel but very non trivial computation
The mathematicians are preparing code for RSA155 factorization and probably Web will be critical here to increase resources from Teraop-hours (RSA129/130) to the needed Teraop-Months (RSA155)
We overview architecture of FAFNER system used and lessons drawn for general Metacomputing administration MetaWeb
http://www.npac.syr.edu/factoring.html
HTML version of Scripted Foils prepared May 12 1996

Foil 3 RSA Factoring on the World-Wide Computer

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Bellcore-Boston U.-Cooperating Systems-NPAC-Oxford U.
  • http://www.npac.syr.edu/factoring
This approach to factoring uses world-wide distributed computing and is based on computationally enhanced Web servers.
The project demonstrates the potential for self-organization of the resources of the World-Wide Web into a general-purpose parallel computing surface, overcoming geographic dispersion, architectural heterogeneity, and varying network connectivity
The innovation of the WWC approach is a new way to execute HPC applications over highly heterogeneous platforms.
  • The WWC uses the Web's client/server model to administer and optimize the distribution of work, and manage the entry of new Web volunteers into the pool of available computing resources.
HTML version of Scripted Foils prepared May 12 1996

Foil 4 Digital Crime(!?) Home Page

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Factoring on the Web Project
HTML version of Scripted Foils prepared May 12 1996

Foil 5 Factoring RSA Codes -- Software Resource FAFNER

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Factoring on the Web Project
HTML version of Scripted Foils prepared May 12 1996

Foil 6 RSA: Public Key Cryptosystem

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
RSA Security Systems built around numbers
RSA-N = Prime1 * Prime2
A Product of two large primes which are secret whereas "everybody" in principle is meant to be able to know public modulus RSAm which can be used by anybody to encrypt messages
Only the recipient is meant to be able to decrypt message using secret prime factor
Secrecy of the cryptosystem is that of the secret key
Secrecy of the secret key is no more than the factorization of the public modulus
HTML version of Scripted Foils prepared May 12 1996

Foil 7 How hard is Factoring the Public Modulus?

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Rivest, Shamir and Adleman (RSA!) posed RSA-129 in August 1977 Scientific American, predicting 40 quadrillion years as a solution time
Actual time to crack RSA-129 was about eight months on the Internet (April 1994)
  • A nice illustration of importance of algorithm improvements as well as VLSI based compute performance improvements!
Still, many sites still use keys as small as 512 bits long (155 decimal digits) to protect enormous amounts of code and data
Using the latest factoring technology it will only take a few tera-op months to factor a 512 binary bit number!
HTML version of Scripted Foils prepared May 12 1996

Foil 8 General Number Field Sieve -- GNFS:

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
The latest (mathematical) factoring technology
Sieving over sets of "Q-values" (i.e., very large ranges of integers)
Task specifications are small (the integer bounds of the Q-range)
Task results are large (collections of "partial relations")
These results must be accumulated, sorted, and run through a neat graph algorithm before they are fed into the final bitmatrix reduction step (done on Maspar in previous factoring efforts but any reasonable machine will handle)
Forms an ideal, embarrassingly parallel application for Web-wide coordination: very large, naturally distributed database computation which can be done with PC's up.
Note we build on and still support factoring by email preferred by users in secure/uncommunicative environments!
HTML version of Scripted Foils prepared May 12 1996

Foil 9 Sieving (RSA-129 and MPQS, RSA-130 and GNFS)

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
RSA129 used the double partial variation of the Multiple Polynomial Quadratic Sieve (MPQS), the predecessor to the Number Field Sieve (NFS), in turn the predecessor to the General Number Field Sieve (GNFS)
General factoring challenge: find x,y such that
  • x^2 == y^2 mod RSA-N.
This would give good odds that
  • gcd(x+y, RSA-N) is not 1 or RSA-N.
Therefore, we'd have a factor of RSA-N.
HTML version of Scripted Foils prepared May 12 1996

Foil 10 BASIC OBSERVATIONS AND TERMS

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Numbers, "a", for which we can find an integer "b" where
  • a == b^2 (modulo rsa129) are called quadratic residues modulo RSA-N .
  • Roughly half the integers are quadratic residues
Values of "a" which factorize into only small primes out of a short list (the "factor base") plus at most two more primes < 2^30 are "special"
If there are 2 more such primes in the factorization of "a", then "a" if a "double partial",
1 such prime, a "partial",
and none, a "full" relation.
HTML version of Scripted Foils prepared May 12 1996

Foil 11 SIEVING THE Q-INTERVAL

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Quadratic residues given by a certain polynomial and divisible by a particular prime are regularly spaced. (Don't ask why unless answerer is Math Whiz).
In sieving you add the log of the prime every such regular distance through initially zeroed memory, for each prime in the factor base.
When done, we pick out places where the accumulation exceeds a threshold; that's where you find quadratic residues divisible by lots of small primes.
These residues are therefore more likely to be double-partial, partial, or full relations!
HTML version of Scripted Foils prepared May 12 1996

Foil 12 Extracting The Relations

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
For places that satisfy threshold constraint, the client workers emit the prime factorizations for the "a"s and print out the matching "b"s.
If there's a set of "a"'s whose product's factorization consists of primes raised to EVEN powers, then the product is a square, and so is the product of all the matching b^2 terms (trivially).
This would give the happy result that
x^2==y^2 (modulo RSA-N), and we'd have our factorization!
HTML version of Scripted Foils prepared May 12 1996

Foil 13 FIRST Backend Processing STAGE GRAPH REDUCTION

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Finding such a set of "a"'s with prime factors raised to an even power, is pretty non-trivial, and is not performed by the sieving clients or servers.
Initially wee derive a network in which nodes are primes and edges are drawn between
  • the two large primes in a double-partial relation, or between 1 and the single prime of a partial relation.
Then we run around looking for cycles in the network, which represent large primes that appear as squares when the two corresponding residues are multiplied together.
Multiply all relations together, divide by all squared large primes, and you turn lots of partials and double partials into full relations.
HTML version of Scripted Foils prepared May 12 1996

Foil 14 SECOND Backend Processing STAGE GRAPH REDUCTION

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Take the processed partials/double-partials and the true "fulls" and now we want to find a new "a" which on combining current a's is a proper square number!
Perform a Gaussian elimination looking for a linear dependency module two of a bitmatrix of F columns and R rows, where F is the size of the small-primes factor base and R is the number of quadratic residues.
This is a big but not tera-op (for RSA155) computation. But at the end, if a dependency falls out, we know the factors of RSA-N.
HTML version of Scripted Foils prepared May 12 1996

Foil 15 Web Virtual Machine and Server-Server Communication Model

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Proposed Architecture of WWVM
HTML version of Scripted Foils prepared May 12 1996

Foil 16 Hierarchical FAFNER Servers

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
http://cooperate.com/cgi-bin/FAFNER/factor.pl
Features
  • Fill out a form and click to check out
  • "Server in a Box" includes server code
  • and initial task allocation
  • Automatically refills from the original source
  • Configurable to meet local standards of decency:
  • selective availability of services
months of runtime, dozens of collaborators,
eight nations, four continents
hardware platforms from an i386 laptop to an IBM SP/2 (including HPs, Alphas, MIPS, Suns, SGI machines, RS6000s)
Most Heterogeneous and Geographically Dispersed Award, 3rd Annual HPC Challenge, Supercomputing '95.
HTML version of Scripted Foils prepared May 12 1996

Foil 17 Features of FAFNER Server Code

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Implemented as Perl scripts, invoked via CGI
Hierarchy of cooperating World-Wide Web servers used for many functions in the collaboration:
  • sieving task distribution
  • email-to-HTTP gateway
  • user registration services (including anonymity)
  • computational status updates
  • solution data collection
  • automated archival services
HTML version of Scripted Foils prepared May 12 1996

Foil 18 Features of CLIENT CODE

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
General Number Field Sieve (GNFS)
  • legacy C code
  • uniprocessor (not network-aware)
  • internally fault-tolerant
GNFSD Wrapper Code
  • make a daemon out of GNFS
  • add knowledge of "task servers"
  • add external fault-tolerance to GNFS
HTML version of Scripted Foils prepared May 12 1996

Foil 19 TECHNICAL CHALLENGES

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Partition workload onto multiple servers
Avoid redundant task allocation
Accumulate large relation datasets
Manage evolving software base that's widely distributed
Coordinate many volunteer clients
Requires a distributed Web based cluster management support
HTML version of Scripted Foils prepared May 12 1996

Foil 20 Social/Administrative CHALLENGES

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
Offload administration (divert blame)
Coordinate volunteers with different computational capabilities
Encourage anonymity, minimize exposure to security risks
Tune task scheduling according to the individual workstation owner preferences
We have designed Metaweb to extend Fafner to address technical and administrative issues
HTML version of Scripted Foils prepared May 12 1996

Foil 21 RSA130 Factorization is completed!

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
http://www.npac.syr.edu/factoring/status.html
Web Sieving started in September 1995.
On April 10, 1996, we found that
RSA-130 = 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557 has the following factorization: RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 * 45534498646735972188403686897274408864356301263205069600999044599
HTML version of Scripted Foils prepared May 12 1996

Foil 22 Sieving was done on a great variety of workstations at many different locations:

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. *
Full HTML Index
28.37% by Bruce Dodson (Lehigh University)
27.77% by Marije Elkenbracht-Huizing (CWI, Amsterdam)
19.11% by Arjen K. Lenstra (Bellcore)
17.17% by contributors to the www-factoring project
  • (organized by Jim Cowie, Wojtek Furmanski, Tom Haupt, and Arjen Lenstra, among others)
4.36% by Matt Fante (IDA)
1.66% by Paul Leyland (Oxford University)
1.56% by Damian Weber (University of Saarland)
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Dec 14 1997