20160502, 10:32  #1 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
RSA supercollider
http://phuctor.nosuchlabs.com/phuctored
All the poor keygen in the world on shameful display. Several keys there have extremely small primes (such as 7) as a factor. What in the world is going on there, I wonder... Mine is clean. 
20160502, 12:43  #2 
Dec 2014
3×5×17 Posts 
I like the N that end in '5'.
Security people feel 1024bit keys are a little risky. They are currently just out of reach of SNFS but some small improvement could make them breakable. http://stackoverflow.com/questions/5...lcertificates The NSA is worried about RSA falling apart when quantum computers start working so they are looking for alternatives to RSA. https://www.schneier.com/blog/archiv...ans_for_a.html 
20160502, 15:38  #3  
"Curtis"
Feb 2005
Riverside, CA
3^{3}×5×37 Posts 
Quote:
2. How would you use SNFS to crack an RSA key? Do you mean GNFS? 

20160502, 16:18  #4 
Aug 2006
3×1,993 Posts 
SNFS > GNFS would fix both of those issues, yes?

20160502, 20:36  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
I've nearly convinced myself that the NSA has cracked 1024 RSA keys.

20160502, 21:31  #6 
Dec 2014
3·5·17 Posts 

20160503, 06:27  #7 
Aug 2006
3×1,993 Posts 

20160503, 13:01  #8 
Tribal Bullet
Oct 2004
6727_{8} Posts 
It's a straightforward calculation to estimate how much memory the linear algebra would take on a matrix with a billion columns. I think I came up with a figure of 11TB of RAM, and NFS@Home has proven that block Lanczos on highend hardware with highend interconnect scales up very nicely, IIRC the scaling was P^0.83 speedup for P processors.
It is much less straightforward to estimate what the sieving would take, since even the sieving would need highend machines for extended periods of time. Presumably the NSA has better things to do with a big datacenter than break a single RSA key, and google is now lobbying for more powerefficient computers because you can't just clock them down if they are 100% busy all the time. Of course that's for GNFS in its currently understood form. Whether you believe an improved algorithm or a tweak on current GNFS exists in secret, or not, depends on whether you believe all those cryptomathematicians are ahead of the public state of the art, or not. 
20160503, 15:12  #9  
Aug 2006
1011101011011_{2} Posts 
Quote:
https://cr.yp.to/nfscircuit.html would not be surprising. Quote:


20160503, 16:50  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
25306_{8} Posts 
Quote:
If the rumour is correct, then perhaps we can deduce that the algorithm requires finding O(sqrt(N) smooth integers of size bounded by O(sqrt(N)) . I've been thinking about such things for a little while now  unsucessfully it's needless to say. Last fiddled with by xilman on 20160503 at 16:50 Reason: Fix tyop. 

20160503, 17:23  #11 
Einyen
Dec 2003
Denmark
3175_{10} Posts 
That would be O(sqrt(N)) smooth integers with sqrt(N) = 2^512 ?
