Hacker News Reader

Comment by yifanlu | Hacker News Reader

First, the 3DS mostly uses RSA for code signing, something I didn't really touch on since there's no serious mistakes there. Second, while RSA does not fair well against quantum attacks, as of today, there is still no way of factoring a 2048 bit key that won't take you at least (being generous) hundreds of years (provided no quantum computers). So if you have proof that it's (today) achievable in polynomial time, please email me ;)

But turning the question around, what do you think we should do to achieve asymmetric encryption? If you don't want it to break with Shor, then RSA and ECDSA are off the table. If you want small message size, you can't use Lamport.

View on HN

if i had that proof an email would be unnecessary, you'd already know :p

to address your question i'll say this, crypto is only interesting to me in securing my own work and because my interests are in number theory that, due to rsa popularity, would incidentally affect crypto

i lack an intimate familiarity with the optimisation requirements of rolling production crypto, meaning i can comfortably ignore any message size restraints for my personal uses

instead of implying i know how crypto should be enacted.. with my current knowledge and interest i would be wholly unable to deduce as you did in your article.. i was simply stating that i am interested in factoring large integers and i wonder why anyone thinks open problems in number theory are a sound means of crypto

superb write up by the way

> i wonder why anyone thinks open problems in number theory are a sound means of crypto

The short answer is that the numbers are so large that with current state of the art means (which I'm sure you know a lot about), factoring a 2048 bit number takes around 1000 years and 4096 bit keys takes about 2^32 times more years. Even if computers get faster every 10 years, you can see that it won't improve much. That's why we use number factoring for crypto; because it takes so long to break.

However, as you've pointed out, since the problems are open, the calculations are meaningless. And of course all this analysis goes out the window with quantum computers. But the unfortunate truth (the "biggest embarrassment of computer science" as Dan Boneh calls it) is that we don't actually have any proof that security exists. All crypto is built on open problems. So better choose open problems that's been open for a long time.

> is that we don't actually have any proof that security exists

again you speak from a practical perspective, right?

because i was under the assumption onetime pad is provably secure

Reply on news.ycombinator.com