Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“This destroys the RSA cryptosystem”

eprint.iacr.org

Post reply on HN
Print view View original

121–130 of 152 posts

Re: “This destroys the RSA cryptosystem”

#121

Post by aarchi »

yesenadam wrote: post #54
Centigonal wrote: post #13

The author of this paper is Claus P. Schnorr[1], of Schnorr signature fame. The paper has almost the same title as a 2017 draft paper[2] of his. The “This destroyes the RSA cryptosystem” quote is not in the linked paper abstract. This seems fishy. [1] https://en.wikipedia.org/wiki/Claus_P._Schnorr [2] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9...

> The paper has the same title as a 2017 draft paper Not quite the same title. He has papers with similar titles since at least 2010. I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies.. https://marc.info/?l=cypherpunks&m=95280154624588&w=2

I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures.

> Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It was hatched by men who obviously believe that Western liberal society is best safeguarded if the US can continue to gleen the benefits of the huge passive eavesdropping net that has for decades sustained America's geo-political dominance.

Re: “This destroys the RSA cryptosystem”

#122

Post by dleslie »

aarchi wrote: post #121
yesenadam wrote: post #54

Earlier quoted context omitted.

> The paper has the same title as a 2017 draft paper Not quite the same title. He has papers with similar titles since at least 2010. I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies.. https://marc.info/?l=cypherpunks&m=95280154624588&w=2

I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures. > Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It…

At the time ECHELON was well-known among hacker and conspiracy circles, and it was making big news overseas due to major disclosures by partner governments.

https://en.wikipedia.org/wiki/ECHELON

Re: “This destroys the RSA cryptosystem”

#124

Post by john_alan »

londons_explore wrote: post #45
smolder wrote: post #18

Earlier quoted context omitted.

If that's the case it's funny to think... NSA could have sat on this for years. Though that would be a really hard secret to keep.

RSA has always been a lot weaker than it seems at first... I mean, people have been moving from 1024 to 2048 bit primes... The biggest number I could conceivably brute force is probably about 2^50. Maybe 2^60 with a big budget, or 2^65 with a team of ASIC designers. The mere fact that 2^1024 is considered risky tells you how far from ideal RSA is!!

Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA).

I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.

    // get two random primes (pretend P, Q)
    sage: random_prime(2^34)
    12697300267

    sage: random_prime(2^33)
    3962800609

    // make a semi-prime (pretend N)
    sage: 12697300267*3962800609
    50316869230723462603

    // check length of semi-prime (65-bits)
    sage: log(50316869230723462603,2).n()
    65.4476759618453

    // factor it in 18milliseconds.
    sage: time factor(50316869230723462603)
    CPU times: user 9.78 ms, sys: 9.07 ms, total: 18.8 ms
    Wall time: 23.2 ms
2^1024 bit RSA is about 2^80 in bit strength.

This example was 2^65 bit RSA, which is negligible in bit-strength.

Re: “This destroys the RSA cryptosystem”

#125

Post by thomasahle »

ncann wrote: post #3

Obviously this went way over my head, but what is the claimed time complexity here?

It's hard to figure out what they are claiming, which makes the whole paper seem fishy.

On page 14 they seem to claim a factor 2 improvement in the exponent of the quadratic number field sieve, which might be better that the general sieve for some N, but is still worse asymptotically.

Re: “This destroys the RSA cryptosystem”

#126

Post by DanielMcLaury »

hn_throwaway_99 wrote: post #114

If this did actually "destroy the RSA cryptosystem", seems like a proof of concept would actually be trivial to demonstrate. Given that, my bet is on this (or, rather, at least that particular sentence) being BS.

That's not necessarily the case in general. If you had an algorithm which, given a billion dollars' worth of specialized lattice reduction ASICs, could break 2048-bit RSA in a few months' time, then for all practical purposes this would mean that 2048-bit RSA was broken -- there are plenty of state actors who would drop that kind of money in a heartbeat -- but that doesn't mean that some guy who came up with it would be able to do a demo on his laptop.

(Not saying that the above has anything to do with this paper in particular.)

Re: “This destroys the RSA cryptosystem”

#127

Post by elmo2you »

erincandescent wrote: post #102
elmo2you wrote: post #96

Earlier quoted context omitted.

> Why would someone backdoor their own key when they could instead just mirror the data or something? Ever thought about .. let say big commercial companies (e.g. social media platforms), using keys that are either knowingly or unknowingly tweaked? A backdoor might not be trivially simple (one of the primes being fixes), but e.g. one prime be somehow part of any collection that is smaller than the pool of truly rando…

> That's a whole different topic and not what I was pointing at. No, fundamentally it is If I'm Evil Social Media Company and I want to leak your secrets to someone (the NSA, KGB, whatever), I could 1. Send your plaintext to them (easy) 2. Send them the private key (arguably even easier - I don't have to mirror the traffic, and only my key security officers need to be aware of the fact that we are doing this) 3. Figu…

> If I'm Evil Social Media Company and I want to leak your secrets to someone ..

Apparently I failed to be clear. The companies in question might not (and probably don't) have evil intentions. They could either be forced (and equally forced to shut up about it), or might not even be aware of it (or not to full extend).

As business PR/politics go, a business would likely present itself safe and promoting how it cares about user privacy (bla, bla, etc). It could even publicly voice opposition to any government's wishes to extend control over them. What happens in PR/politics can be very different (and involve very different people) from what can simultaneously be dictated behind close doors in the name of compliance, national security, or whatever.

You are correct. You are indeed trusting the creator/owner of a private key with your data. It's also true that there are plenty of ways in which this trust can be violated. But to me, neither of those are what I have a gripe with.

What bugs me particularly, is that RSA intrinsically has an ability to put in a backdoor that is just as difficult to detect/determine for an outsider/user, as it is to actually break that key. What bugs me even more, is that I pretty much never hear anyone talk about that, or people countering with how there are easier (but harder to hide) ways to "break" RSA cryptography.

Maybe, in particular after Snowden, the premise of trusting the creators/owners of private keys just isn't good enough anymore (if it ever was in the first place).

The point is not that a bad actor may have six other ways till Sunday to be evil, but that the ability to add an undetectable backdoor is something I don't like for a public key scheme that still underpins the security of a majority part of the Internet today.

I guess time will tell if that was a mistake or not.

Re: “This destroys the RSA cryptosystem”

#128

Post by walrus01 »

aarchi wrote: post #121
yesenadam wrote: post #54

Earlier quoted context omitted.

> The paper has the same title as a 2017 draft paper Not quite the same title. He has papers with similar titles since at least 2010. I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies.. https://marc.info/?l=cypherpunks&m=95280154624588&w=2

I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures. > Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It…

James Bamford wrote a lot of books on the nsa before 9/11.

Re: “This destroys the RSA cryptosystem”

#129

Post by gerikson »

aarchi wrote: post #121
yesenadam wrote: post #54

Earlier quoted context omitted.

> The paper has the same title as a 2017 draft paper Not quite the same title. He has papers with similar titles since at least 2010. I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies.. https://marc.info/?l=cypherpunks&m=95280154624588&w=2

I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures. > Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It…

I've been aware of the Emacs function 'spook'[1] since the late 90s.

Here's a current output from `M-x spook` on my machine:

> Europol BATF bluebird secure Narco banners Blister agent BVD fraud SADMS UKUSA mania weapons of mass destruction Virii EDI Bin Laden

[1] https://www.gnu.org/software/emacs/manual/html_node/emacs/Ma...

Post reply on HN