mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Tales From the Crypt(o) (https://www.mersenneforum.org/forumdisplay.php?f=130)
-   -   RSA supercollider (https://www.mersenneforum.org/showthread.php?t=21261)

Dubslow 2016-05-02 10:32

RSA supercollider
 
[url]http://phuctor.nosuchlabs.com/phuctored[/url]

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...


[URL="http://phuctor.nosuchlabs.com/gpgkey/522730C131BD3CB85234D74BCBBF7E19CE448CE8C463C7690E74587D38127611"]Mine[/URL] is clean.

bgbeuning 2016-05-02 12:43

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.

[URL="http://stackoverflow.com/questions/589834/what-rsa-key-length-should-i-use-for-my-ssl-certificates"]http://stackoverflow.com/questions/589834/what-rsa-key-length-should-i-use-for-my-ssl-certificates[/URL]

The NSA is worried about RSA falling apart when quantum
computers start working so they are looking for alternatives
to RSA.

[URL="https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html"]https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html[/URL]

VBCurtis 2016-05-02 15:38

[QUOTE=bgbeuning;432929]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.
[/QUOTE]

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?

CRGreathouse 2016-05-02 16:18

SNFS -> GNFS would fix both of those issues, yes?

Dubslow 2016-05-02 20:36

I've nearly convinced myself that the NSA has cracked 1024 RSA keys.

bgbeuning 2016-05-02 21:31

[QUOTE=VBCurtis;432935] Do you mean GNFS?[/QUOTE]

Yes, got my acronyms confused.

CRGreathouse 2016-05-03 06:27

[QUOTE=Dubslow;432960]I've nearly convinced myself that the NSA has cracked 1024 RSA keys.[/QUOTE]

I think that's the general consensus, yes. It's possible that they haven't, but I'd consider that surprising.

jasonp 2016-05-03 13:01

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.

CRGreathouse 2016-05-03 15:12

[QUOTE=jasonp;433010]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.[/QUOTE]

My feeling is that they are no further, or not much further, on the theory, but far ahead on the engineering. Something like
[url]https://cr.yp.to/nfscircuit.html[/url]
would not be surprising.

[QUOTE=jasonp;433010]Presumably the NSA has better things to do with a big datacenter than break a single RSA key[/QUOTE]

I certainly don't think they break 1024-bit keys routinely, but I expect they know which keys are worth the effort to crack. [url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.5881&rep=rep1&type=pdf]Shamir & Tromer[/url] 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 [url=http://www.top500.org/lists/2003/11/]Nov 2003 Top500[/url] with the [url=http://www.green500.org/lists/green201511]Nov 2015 Green500[/url] 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.

xilman 2016-05-03 16:50

[QUOTE=jasonp;433010]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.[/QUOTE]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.

[b]If[/b] 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.

ATH 2016-05-03 17:23

[QUOTE=xilman;433022]I[b]If[/b] 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.[/QUOTE]

That would be O(sqrt(N)) smooth integers with sqrt(N) = 2^512 ?


All times are UTC. The time now is 03:54.

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