Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Tom Ritter August 26, 2012
file 74 lines (56 sloc) 3.535 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
This folder is a subsection of a presentation on distributing high-CPU activities (like factoring) using
BOINC (the thing behind SETI@Home). This is a dry howto of factoring a 512 bit semiprime using the raw tools
and NOT distributing it using BOINC. The $140 and 30 hour figure comes when you wire it all up in BOINC so
parts are automated and you're not going crazy trying to control 200 computers at once. (BOINC does that for you.)
I mean you could try of course, but your Alt+Tabbing would have to be mighty strong. ;)

Likewise, the slides just brush over the math very briefly and don't go into much detail. (This was afterall a
spoken presentation.) The slides in the main directory may shed a little more light on the subject and BOINC:
  https://github.com/tomrittervg/cloud-and-control/blob/master/Cloud & Control - notes.txt

While there are the perl and python drivers that try to make it 'easy' to do,
I find it more straightforward to compile and run the tools myself.

1) Download and compile msieve and ggnfs
   http://sourceforge.net/projects/msieve/
   http://sourceforge.net/projects/ggnfs/

2) Take the modulus you want and put it, in base 10, in a file.
   If you're attack a SSL cert, here's the openssl 7 python commands to get it in base 10:
   $ openssl x509 -noout -modulus -in cert.pem
   $ python
   >>> int('hexstring', 16)
  
  I'll pretend you put it in rsa100.n
 
3) Run Poly Search. You may want to distribute this. Here's how:
 
./msieve -s ./rsa100.intermediate.dat -l ./rsa100.log -i ./rsa100.n -nf ./rsa100.fb -d 20 -v -np 1,500
./msieve -s ./rsa100.intermediate.dat -l ./rsa100.log -i ./rsa100.n -nf ./rsa100.fb -d 20 -v -np 500,1000
./msieve -s ./rsa100.intermediate.dat -l ./rsa100.log -i ./rsa100.n -nf ./rsa100.fb -d 20 -v -np 1000,1500
...
 
4) Pick the largest Murphy Score
   The Murphy score is the second-best poly scorer there is. The best is test
   sieving. So unless you want to test sieve, go with the best Murphy Score.
 
5) Convert the msieve output to something GNFS can read.
   scripts/gengnfsjob.php rsa100.fb
 
6) Sieve an aweful lot.
   a) Copy the rsa100.job to a whole bunch of job files:
      rsa100.job.1, rsa100.job.2, rsa100.job.3, ...
   b) Edit each job file to have a different __START__, and fill in a __COUNT__
      for the range.
   c) Run the correct siever. This is the second siever, and is probably not
      correct. The gengnfsjob.php will tell you the siever to use.
Make sure they write to different output file.
   
      gnfs-lasieve4I12e -a -o spairs.out.X -v rsa100.job.X
 
7) Run the combine.
   Do it with:
     - x64 box
- gcc >4.1 (e.g. 4.4.5)
- recent gmp (e.g. 5.0.2)
 
   a) cat the individual spairs files into rsa100.dat
   b) ./msieve -v -s ./rsa100.dat -i ./rsa100.n -nf ./rsa100.fb -t 8 -nc1 -v
Note that -t 8 means use at most 8 threads.
   c) ./msieve -v -s ./rsa100.dat -i ./rsa100.n -nf ./rsa100.fb -t 8 -nc2 -v
   d) ./msieve -v -s ./rsa100.dat -i ./rsa100.n -nf ./rsa100.fb -t 8 -nc3 �v

8) Hope. I have had msieve crash on the last mile. That's why I gave those
   version recommendations - I found what worked for me. Yep, more
   superstition than engineering there.

9) Use your primes. You may be interested in this set of scripts:
   https://github.com/tomrittervg/prime2pem



Update:
For factoring >512 bit, you may want to investigate CADO-NFS, which was used to factor RSA-704
http://cado-nfs.gforge.inria.fr/
Something went wrong with that request. Please try again.