1
$\begingroup$

My basic question is: How does RSA compare to using Diffie-Hellman + <some symmetric key crypto, e.g. a polyalphabetic cipher>

Let's assume that factoring large numbers and computing discrete logs both approximately equally difficult, so diffie hellman is about as secure as RSA. What are the pros and cons of using RSA vs diffie-hellman + symmetric key crypto?

For the latter, for example one might consider using diffie-hellman to agree on a large key (corresponding to say $k$ permutations of the characters in the alphabet, where encryption is done by applying the $(i\text{ mod }k)$th permutation to the $i$th character), and using that to send a message of length $nk$, where $n$ is some small number, so that frequency analysis is not effective ($n = 1$ would give you a "one-time-pad").

(This is a possibly naive question (My background is in algebraic geometry))

$\endgroup$
2
  • 1
    $\begingroup$ polyalphabetic cipher? You are at least two centuries back. $\endgroup$
    – kelalaka
    Jun 1, 2021 at 2:06
  • $\begingroup$ @kelalaka I'm sure you're right! As I said this is a very naive question from someone whose background is not computer science! $\endgroup$
    – Will Chen
    Jun 1, 2021 at 2:30

1 Answer 1

2
$\begingroup$

RSA allows for signatures. Signatures are a system whereby someone with a private key can "sign" a message, and anyone with the corresponding public key can verify that that private key was used to sign the message.

(Elliptic-Curve) Diffie-Hellman (aka ECDH or DH) allows for exchanging a shared secret value, which is then passed through a Key Derivation Function (KDF) to create a shared symmetric key for use with a symmetric cipher like AES-GCM or ChaCha20-Poly1305. Preferably an Authenticated Encryption with Associated Data (AEAD) cipher instead of just any old symmetric cipher, and certainly not a thoroughly broken classical cipher like a polyalphabetic substitution cipher.

It's possible but inadvisable to use RSA to encrypt short messages directly. The maximum message length is very short: for RSA-2048 with OAEP (a "padding" scheme required for security) at most 190 bytes can be safely encrypted. This process is FAR slower than using ECDH and an AEAD. Also, it's wildly unsafe to re-use RSA keys for more than one purpose. Doing so improperly can leak the message plaintext. So no major protocol uses this.

RSA key generation is MUCH slower than ECDH key generation. RSA key generation consists of randomly generating large numbers and testing if they're prime. ECDH key generation consists of generating a random point on some elliptic curve, which can be as simple as generating a single 32-byte random value and performing some fast bitwise operations.

That speed of (EC)DH key generation enables an important security property: forward secrecy. By generating a new key pair for every new "session" (exchange of messages) the compromise of a past session's keys doesn't compromise future keys. RSA key generation is too slow on many systems (especially embedded systems) for this to be practical.

There's also RSA-KEM, a mode whereby RSA is used to exchange a secret value which is then passed through a Key Derivation Function. This operates a bit like (EC)DH, but it's slower. There's not much reason to use this.

Lastly, there are some more obscure but potentially useful things like Cryptographic Accumulators which are easier to implement using RSA-like operations than (EC)DH-like operations.

$\endgroup$
6
  • $\begingroup$ "Also, it's wildly unsafe to re-use RSA keys for more than one purpose. Doing so improperly can leak your private keys." - huh? How would that leak the private key? Even if you gave the adversary an RSA oracle (doing the private operation on attacker chosen values), that doesn't leak the private key value... $\endgroup$
    – poncho
    Jun 1, 2021 at 12:58
  • $\begingroup$ Thank you for your answer! I can definitely see that signatures and slow key generation are two interesting features of RSA. Again I apologize for my ignorance but why do you say the classical polyalphabetic substitution cipher is "thoroughly broken"? For example the one-time pad is an example of a polyalphabetic substitution cipher (this is "$n=1$" in my OP), which is unbreakable. Combined with Diffie-Hellman, you'd get something at least as secure as DH right? What are the weaknesses of DH + one-time-pad? How would this compare to DH + AES-GCM as you suggest? $\endgroup$
    – Will Chen
    Jun 1, 2021 at 14:10
  • $\begingroup$ Poncho: right. That was totally wrong. There are several ways to leak the private key by misusing RSA, that's not one of them. $\endgroup$ Jun 3, 2021 at 15:10
  • $\begingroup$ One-Time Pads could be seen as a polyalphabetic substitution cipher if you squint, but they're very different in a key aspect: they have a key exactly as long as the message that's never re-used. Classical polyalphabetic substitution ciphers don't have those restrictions, and those restrictions are what makes the OTP secure. DH shares a small secret value, likely much smaller than the message, and that value isn't uniformly random. So it'd turn into a many-time pad, which is not even secure against known-plaintext attacks. (EC)DH + AES-GCM is IND-CCA3 secure, much stronger. $\endgroup$ Jun 3, 2021 at 15:16
  • $\begingroup$ What's to stop you from using DH to exchange large keys? I.e. if you want to securely send an N-bit message, first use DH to agree on an N-bit key, and then use that key to encrypt the message. If you want to send another message, don't use the same key - agree on another one. This makes it so each message effectively becomes encrypted using a one-time-pad, right? $\endgroup$
    – Will Chen
    Jun 8, 2021 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.