Questions   
Sort: 
 #5
avatar
+5

DavidQD requested commentary from a mathematician on his summary of the difficulty to break RSA-2048 via the number field sieve (NFS).  I run NFS software as a hobby, and am well-versed in its use. I happen to be a mathematician also, but my knowledge of NFS is empirical, rather than via academic interests.

1. There are two flavors of NFS:  The special NFS (SNFS) and general (GNFS).  SNFS is usable only if the input composite has a certain known form (such as a Mersenne number, 2^p-1). SNFS is quite a lot faster than GNFS, but RSA keys cannot take advantage of SNFS.  The factorization records mentioned in David's post are SNFS records, so aren't relevant to an attempt on an RSA key.
2. The largest GNFS factorization I know of is RSA-768, 232 digits. A summary of the effort is at http://www.loria.fr/~zimmerma/records/rsa768.txt.
3. The difficulty of a GNFS job roughly doubles every 5 digits in length of the composite.  It does not double for every bit added to the length of the input.
4. A fast home desktop can factor an RSA-512 key in 7-10 days, not 4 months.  I have a haswell-E 6-core and can complete such a job in just under a week; a quad-core at 3.5ghz should take 10 days.
5. The estimate of 7-10 years of technological and software advances followed by 2-5 years for a factorization to be carried out is for RSA-1024, not RSA-2048.  There is no hope of cracking RSA-2048 via the number field sieve in our lifetimes; a quantum computer or a breakthrough in integer factorization that renders this form of security useless would be required. The 2015 state of the art software package is CADO-NFS, and is freely available.  This package may be capable of an attempt on RSA-1024, but the matrix-solving step is a hurdle.
6. It does not take a mathematician to run the first step of polynomial selection; the selection is a matter of letting automated software search for a period of time to find one that allows the longest step (sieving) to run faster. Anyone could produce a polynomial for RSA-1024 in a day, but spending a few hundred CPU-years will yield much greater reductions in sieve time.  Polynomials are ranked roughly by score, which is generated by the searching software; the scores are rough estimates (say, within 5% of actual sieve-performance ranking) of how well the sieve step will run, but anyone can fire up the sieve to see how fast a polynomial works.  The poly-search step is traditionally run for 3-4% of expected project length, as finding a poly that sieves 4% faster would shorten the sieve step by 4%, making up the time spent on poly search.  It is not known how to find a "best" polynomial; the search is akin to pulling needles out of a haystack, and it's always possible that a longer search produces a polynomial that saves sieve time.
7. More info:  Poly search and the sieve step are highly highly parallel; any number of machines can participate, with the simplest of organizational structure to distribute workload.  Collecting data is slightly less trivial; an individual machine might produce a couple of GB/month in data from the sieve step that needs to be collected in one place. If 10,000 machines are recruited for a year to crack RSA-1024, collecting the data is nontrivial- the sieve data will be measured in petabytes.  Unfortunately, the matrix step that comes last must be performed by a single machine; it can be multi-threaded, but the data exchanged among threads is much too great for a massively parallel effort.  RSA-768's matrix was 192M by 192M, and took 13 months on a 144-core cluster to solve. RSA-1024 will have ~1000 times as much data, a matrix of perhaps 4G by 4G and a larger memory footprint than is available today.
8. More reading at the NFS@home website, or mersenneforum.org's factoring subforum, or the CADO-NFS software website.

Dec 2, 2015
 #3
avatar+118725 
+10
Dec 2, 2015
 #5
avatar+1667 
0
Dec 2, 2015
 #4
avatar+1667 
0
Dec 2, 2015
 #13
avatar+1038 
+20

Hummm . . . .This looks like a preview for CPhill’s new TV show. Under the Bridge:  Mathematics of Trolling. Staring CPhill and Melody, aka Sisyphus and Queen Guinevere, with a cameo appearance by Nauseated. 

 

For a listing of CPhill’s previous shows look here:

 

http://web2.0calc.com/questions/are-any-of-the-people-who-give-answers-here-math-teachers#r4

 

For a look at Nauseated fan club stats (105 points)

 

http://web2.0calc.com/questions/how-long-did-it-take-for-the-grand-canyon-to-form#r3

 

For information on Nauseated’s fan club president and ambassador to the humanoid population.  

 

http://web2.0calc.com/questions/a-year-and-one-day

 

A great fan post from someone with above average writing skill. This casually mentions Lancelotlink, the buffalo chimp. We may be different species, but we are both Trolls. 

 

http://web2.0calc.com/questions/the-search-function-really-sucks

 

BTW the search function is now vastly improved. 

 

This is Nauseated signing off with the required snarky comment(s):

 

Hayley, I’ve read your last two-dozen posts. If you want to make an “A” on your essay you will need to hire someone to write it for you.  You might consider having the writer compose a “B” paper – you don’t want the teacher becoming too suspicious.

Dec 2, 2015
 #4

1 Online Users