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

knaccc

5/4/23, 3:27 PM

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?

0 + 0

rsa

discrete-logarithm

schnorr-signature

kelalaka

5/4/23, 4:02 PM

Note that the modulus size is the same. https://www.keylength.com/en/compare/

kelalaka

5/4/23, 6:22 PM

[RSA-FDH signature is so simple](https://crypto.stackexchange.com/a/95940/18298)

knaccc

5/4/23, 6:42 PM

@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.

kelalaka

5/4/23, 6:47 PM

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.

Score:3

Crypto

poncho

5/4/23, 4:49 PM

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).

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: การเซ็นชื่อและการเข้ารหัสแบบไม่ต่อเนื่องจะเป็นทางเลือกที่ดีกว่า RSA หรือไม่

RO: Semnarea și criptarea bazate pe jurnal discret ar fi fost o alegere mai bună decât RSA?

RU: Будет ли подписание и шифрование на основе дискретного журнала лучшим выбором, чем RSA?

VI: Việc ký và mã hóa dựa trên nhật ký rời rạc có phải là lựa chọn tốt hơn RSA không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.