mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Tales From the Crypt(o)

Reply
 
Thread Tools
Old 2016-05-02, 10:32   #1
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default 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.
Dubslow is offline   Reply With Quote
Old 2016-05-02, 12:43   #2
bgbeuning
 
Dec 2014

3×5×17 Posts
Default

I like the N that end in '5'.

Security people feel 1024-bit 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...l-certificates

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
bgbeuning is offline   Reply With Quote
Old 2016-05-02, 15:38   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

33×5×37 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
I like the N that end in '5'.

Security people feel 1024-bit keys are a little risky.
They are currently just out of reach of SNFS but some
small improvement could make them breakable.
1. SNFS has cracked numbers quite a bit larger than 1024-bits. "just out of reach" is not accurate, at all. "within reach for the forum in 6 months, or Ryan in 2 weeks" is more like it.

2. How would you use SNFS to crack an RSA key? Do you mean GNFS?
VBCurtis is offline   Reply With Quote
Old 2016-05-02, 16:18   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

SNFS -> GNFS would fix both of those issues, yes?
CRGreathouse is offline   Reply With Quote
Old 2016-05-02, 20:36   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

I've nearly convinced myself that the NSA has cracked 1024 RSA keys.
Dubslow is offline   Reply With Quote
Old 2016-05-02, 21:31   #6
bgbeuning
 
Dec 2014

3·5·17 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Do you mean GNFS?
Yes, got my acronyms confused.
bgbeuning is offline   Reply With Quote
Old 2016-05-03, 06:27   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by Dubslow View Post
I've nearly convinced myself that the NSA has cracked 1024 RSA keys.
I think that's the general consensus, yes. It's possible that they haven't, but I'd consider that surprising.
CRGreathouse is offline   Reply With Quote
Old 2016-05-03, 13:01   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67278 Posts
Default

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 high-end hardware with high-end 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 high-end 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 power-efficient 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 crypto-mathematicians are ahead of the public state of the art, or not.
jasonp is offline   Reply With Quote
Old 2016-05-03, 15:12   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010110112 Posts
Default

Quote:
Originally Posted by jasonp View Post
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 crypto-mathematicians are ahead of the public state of the art, or not.
My feeling is that they are no further, or not much further, on the theory, but far ahead on the engineering. Something like
https://cr.yp.to/nfscircuit.html
would not be surprising.

Quote:
Originally Posted by jasonp View Post
Presumably the NSA has better things to do with a big datacenter than break a single RSA key
I certainly don't think they break 1024-bit keys routinely, but I expect they know which keys are worth the effort to crack. Shamir & Tromer estimated that the cost of factoring a 1024-bit number as $10M in 2003. Since then computers have become cheaper and faster. Somewhat unfairly comparing the Nov 2003 Top500 with the Nov 2015 Green500 performance/watt increased by well more than 100x (11.2 to 7031 MFLOPS/W) since then, and so the expected cost should have dropped similarly.
CRGreathouse is offline   Reply With Quote
Old 2016-05-03, 16:50   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

253068 Posts
Default

Quote:
Originally Posted by jasonp View Post
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 crypto-mathematicians are ahead of the public state of the art, or not.
I've heard persuasive rumours for a few years now that GCHQ / NSA have developed and implemented a L(1/4) algorithm. The implication is that those organizations could break any kilobit RSA key they want, but not every key they would like. A further rumour has it that the Utah facility not only has a copy of the internet, a la Google, but factors integers in its idle cycles. Treat this rumour-mongering and speculation with as much suspicion as you think appropriate.

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 2016-05-03 at 16:50 Reason: Fix tyop.
xilman is offline   Reply With Quote
Old 2016-05-03, 17:23   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

317510 Posts
Default

Quote:
Originally Posted by xilman View Post
IIf 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.
That would be O(sqrt(N)) smooth integers with sqrt(N) = 2^512 ?
ATH is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 05:26.


Wed Oct 20 05:26:41 UTC 2021 up 88 days, 23:55, 0 users, load averages: 1.34, 1.23, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.