[y7r4m]

Back in university I learned the in and outs of RSA, and to be honest, it seemed simple, understandable, and frankly, quite solid. It absolutely depends that p and q are chosen at random, but besides that, should be basically uncrackable.

Please let me know if I am wrong (outside of a quantum computing breakthrough).

edit: I understand that p and q need to be large primes. But there are a gargantuan number of large primes. AFAIK, if 52 cards in a deck shuffled randomly outnumbers in possibilities than the number of atoms in the universe, than surely RSA beats that by many many orders of magnitude in terms of computational complexity even at 1024 key length?

[benlivengood]

The article does list several real-world attacks on:

  - Lack of padding
  - Padding oracles
  - small public exponents
  - badly chosen private exponents
  - Badly randomized large primes
  - Re-used large primes

[klyrs]

It's the "steel door in a wooden frame" problem. The implementation is the weakest link, and not the theory.

Don't worry too much about quantum computers for now; worry about the attacks listed tfa, about the history of attacks being discovered, and the history of implementations being weak years after those attacks being discovered. And then consider that the NSA is the world's largest employer of mathematicians, who have each been toying with RSA since the very beginning of their career.

[hamilyon2]

I am not cryptographer, just developer who used cryptography in the past.

I find historical argument not very convincing. RSA have been around for a long time.

Will we be reading "do not use ECC" articles in 2039 after comparable amount of research will be put into finding subtle unexpected errors in ECC?

[klyrs]

RSA has been around a long time, yes, and Caesar cipher has been around for even longer. Part of the historical argument that you're dismissing is a very persistent Dunning-Kreuger effect: very smart software developers don't know how much there is to know about crypto, and since RSA is "simple" it's easy to delude yourself into thinking that you can do it right.

And, yes. Expect ECC to be broken. It was initially developed by Miller at the NSA, who only released that information when Koblitz discovered the cryptosystem independently. So they've been trying to crack it for a very long time, and you can be certain that they know of unpublished breaks. It's almost certain that they can break certain parameter classes, but the discrete log problem itself keeps getting weaker and weaker.

If moving away from weak crypto on a regular basis sounds like an undue burden, get out of the game, don't roll your own, leave it to the experts or you'll be doing yourself and your users a disservice.

I'm not a number theorist, but I did a lot of crypto and rubbed elbows with several NSA-employed cryptologists in my undergrad. I'm a decent developer, too, but I know far too much to think that I'm qualified to roll my own.

[BlueTemplar]

The main point of the article is that RSA is easy to use wrong, unlike ECC, so, no, we won't (at least for the same reason).

[jopsen]

I suppose you could argue that weaknesses in ECC just haven't been discovered yet.

Whereas RSA is more thoroughly researched and various weaknesses revealed.

I don't know if that's true, I wrote a toy ECDSA implementation years ago (during highschool), and compared to RSA, ECC is certainly more complicated. Sure there are fewer parameters, and we currently know of fewer requirements for these parameters. But who is to say a weak class of ECC private keys won't be discovered in the future?

If you're paranoid about what weaknesses might be discovered, I suppose using RSA+ECC is a option :)

[klyrs]

You're getting downvotes and not replies, so I'll bite. My guess is that it's because you're advancing a common crypto fallacy. Two weak cryptosystems do not combine into a strong cryptosystem. Do not wing it. Use vetted code; don't roll your own.

[BlueTemplar]

Speaking of NSA, libsodium looks nice, but isn't anyone a bit worried that it's still hosted on Github ?

That Microsoft is in bed with NSA is common knowledge at this point, and that the libsodium authors choose to (keep being) associate(d) with them doesn't exactly fill me with confidence…

(yes, the actual risk of NSA messing with the repository without libsodium authors' knowledge is probably very low, but still, it doesn't give the best impression… )

[ganafagol]

That's not how git works.

[muldvarp]

> Back in university I learned the in and outs of RSA, and to be honest, it seemed simple, understandable, and frankly, quite solid.

If you have a degree in computer science and not in cryptography it is quite frankly unlikely that you learned more than the basics of RSA.

> It absolutely depends that p and q are chosen at random, but besides that, should be basically uncrackable.

No. There are many things that can go wrong even if you choose p and q adequately.

[nmadden]

See for example Dan Boneh’s “20 years of attacks on the RSA cryptosystem” [1]. Itself now written 20 years ago and the attacks keep coming.

[1]: http://www.ams.org/notices/199902/boneh.pdf

[kebman]

tl;dr: "The attacks discovered so far mainly illustrate the pitfalls to be avoided when implementing RSA. At the moment it appears that proper implementations can be trusted to provide security in the digital world." (My own emphasis.)

[nmadden]

We’re still waiting to find one of those proper implementations 20 years later.

[TwoBit]

> Back in university I learned the in and outs of RSA, and to be honest, it seemed simple, understandable, and frankly, quite solid.

No offense, but typical uni knowlege of these things is woefully underprepared for understanding security subtleties, and uni-level api design in my experience is not mature and skews towards power and flexibility instead of ease and safety.