Would discrete-log-based signing and encryption have been a better choice than RSA?

Question

Diffie-Hellman can be used for key exchange, and can be used as part of an integrated encryption scheme ("DLIES"). Schnorr signatures are possible by relying only on the discrete-log problem, and without resorting to using RSA.

Since RSA implementations are more complicated because of the need for padding schemes, why were signing and encryption schemes based only on the discrete-log problem not more popular?

Perhaps there were patent licensing issues? Schnorr signatures were patented in 1989 and the patent expired in 2010. Diffie-Hellman key exchange was patented in 1977 and the patent expired in 1997. RSA was patented in 1977 and the patent expired in 2000.

Or perhaps there were communication overhead or performance issues? Or maybe RSA was simply more commercially successful and more widely adopted as a standard?

Note that the modulus size is the same. https://www.keylength.com/en/compare/ — kelalaka, Jan 04 '22 at 16:02
@kelalaka thanks, I'm surprised that FDH was not the most obvious and popular choice. It can't have been that hard to HDKF-Expand multiple times to get to the desired hash output length. — knaccc, Jan 04 '22 at 18:42
Well, that will need an additional security analysis since parameters changes. Even for RSAES-OAEP one needed to construct MFG and analyze it, though, it is now easy with XOFs. — kelalaka, Jan 04 '22 at 18:47

score 3 · Accepted Answer · answered Jan 04 '22 at 16:49

why were signing and encryption schemes based only on the discrete-log problem not more popular?

Well, I expect any answer is somewhat opinion based; however, my perspective:

RSA didn't have many significant disadvantages compared to discrete-log-based solutions. You mentioned that RSA required a "complicated padding scheme"; many discrete-log solutions required similar complications (e.g. DLIES requires a key derivation function), and in any case, the padding scheme really isn't that much of a complication.

The points where discrete-log-based schemes had an advantage over RSA had were:

Signature size (at least, compared to DSA), however, RSA signature sizes were considered 'small enough'.
Key generation time; however you rarely did key generation, and so that was tolerated.

I suspect RSA was widely used because it was first (and hence became entrenched) and it was good enough. The only exception to that general statement would be DH (which was actually published earlier) and that was, in fact, commonly used (although ECDH is more common now).

Would discrete-log-based signing and encryption have been a better choice than RSA?

1 Answers1