# Is there a truly safe signing algorithm?

After reading this question, I'm pretty shaken up. A determined attacker with \$100 in loose change can crack any RSA key in a couple of hours. After believing that these algorithms would take millions of years to brute force, I'm questioning the security of everything.

What should I move to if RSA isn't safe anymore? Are Elliptic Curve signatures likely to have a similar crack in the near future?

• Those answers say that 512-bit RSA keys can be broken, not RSA in general. 2048-bit RSA keys are completely secure if used correctly. – Maeher Apr 25 '18 at 6:41
• Ah I misunderstood that they were referring to the number of bits, I thought they were saying RSA512 is broken, even though that uses 4096 bits. (I am correct right? I'm a crypto newbie) – blaineh Apr 25 '18 at 6:48
• I'm not aware of anything commonly called RSA512. Neither a signature scheme, nor any of the RSA challenges. But the question you linked to explicitely refers to 512-bit RSA, i.e. RSA with a modulus 512 bit in length. And one of the answers referred to the confusingly named "RSA-155" challenge of RSA Security whichhas 512 bits but is 155 decimal digits in length. – Maeher Apr 25 '18 at 6:59

The signing algorithms most often used nowadays are:

• RSA based signature algorithms such as RSA-PKCS#1 v1.5 and the more recent RSA-PSS (currently specified in PKCS#1v2.2)
• ECDSA, which is the "Elliptic Curve Digital Signature Algorithm", which will probably become the most used one, if not already, since RSA is not as efficient in practice as ECDSA for signing purpose, while validation of signature is faster with RSA. (You can see the Crypto++ benchmarks to get a better idea of their performance)
• EdDSA, which is gaining more and more traction nowadays, as it is both easy to implement and secure, plus it is even faster than ECDSA and has plenty of secure open-source code available to use it.
• DSA, which has lost the battle and is now less and less encountered on the field, since it is somewhat too complicated for nothing (we use to say it's because the better Schnorr's signatures were patented, that DSA had to circumvent, which made it a too convoluted algorithm)

None of these algorithm have been definitively broken, but it is true that certain instances of them are known to be weak.

First and foremost, note that RSA with a key of 2048 bits or more, is considered secure and should be fine for the next 10-15 years. So are instances of the other algorithms such as ECDSA with secp256k1, EdDSA with Curve25519, known as Ed25519, etc. This basically means that the crypto we use nowadays is not easily broken, since it would require both extreme computing power and patience to break it. (As pointed out in the comments, this translates also into large costs, but estimating the costs of breaking these instances would be a question in itself. See for example this question about 256 bits security and the cost of breaking it and keep in mind that we are generally considering anything that is belove 100 bits of security as broken.)

Typically in the question you linked, the RSA algorithm is used with a 512-bit modulus, which is known to be weak, as it is said to correspond to roughly 50-bits of security.

It is also true for the other algorithm, ECDSA, DSA, etc. that if you use them on too small groups, that it is possible to break them, however RSA is probably the one algorithm which has seen the most teams trying to break always larger modulus, there are even RSA challenges which used to have money at stake (but they were discontinued in 2007).

But the discrete logarithm world (on which most other signing algorithms are based) is not left behind and there are (fewer) teams working on trying to break it too.

So, in the end, there is no need to be questioning the security of everything because RSA has been broken when used with 512-bits modulus, however if someone were to come up with a device (maybe a quantum computer) able to break RSA with 2048-bits modulus, or 4096 bits, in a reasonable (typically polynomial) time, then we should all be worried.

But there is currently a competition to try and find the so-called post-quantum primitives that will safeguard us against such things.

• Nits: RSA signature verification is the fastest kid on the block; no elliptic-curve verification is likely to beat it. Attacks should be quantified in cost, not in time; area*time is a good cost model because it's easy to reason about and serves as a proxy for pecuniary cost in euros or energy cost in joules, and some area-time tradeoffs are worthwhile while others are not. Consider suggesting concrete instantiations earlier on rather than burying the lede: RSA-2048, Ed25519, ECDSA with secp256k1, since the original poster was led astray by missing the key number 512. – Squeamish Ossifrage Apr 25 '18 at 16:27
• There hasn't been money in the former-RSALabs challenges for a decade, after RSA was acquired by EMC (and before EMC was acquired by Dell). Although I believe some people are still working on them for the 'props'. – dave_thompson_085 Apr 26 '18 at 3:51
• @SqueamishOssifrage True, thanks. I've picked your nits. – Lery Apr 26 '18 at 7:53
• @dave_thompson_085 Wow, I actually remember learning about it a few years back, but it slipped out of my mind! Thanks. – Lery Apr 26 '18 at 7:54
• @blaineh: RSnnn for JWS only, which you didn't say in your Q, is the size in bits of the HASH, which is independent of the RSA size. See stackoverflow.com/questions/39239051/… – dave_thompson_085 Apr 27 '18 at 3:11