17
$\begingroup$

This question already has an answer here:

I've been reading on a lot of websites that same thing: RSA is for communication using the public and private key for both the server and client, where Diffie-Hellman is just for exchanging the same secret key that will then be used for both encryption and decryption, but they both depend on the same MATHS, e.g: that question on quoraquestionThen I was confused when I also read that RSA shares a master and pre-master key, as well, like in this question:questionSO, the question here is, does RSA use the public and private key to encrypt the whole conversation, or is it used just to encrypt a key then the encryption depends on that symmetric key? And if it was used to encrpyt the key and it was the same MATH as Diffie-Hellman, so what is the difference anyways??

$\endgroup$

marked as duplicate by otus, e-sushi Dec 10 '16 at 21:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ In TLS RSA or DHE or ECDHE or several other rarer methods are used only to generate the Premaster Secret aka PMS. PMS is used to the derive the Master Secret and multiple symmetric keys ('those' not 'that') using symmetric algorithms. Applications other than TLS use RSA and/or [EC]DH and/or other algorithms differently. For the math difference, see crypto.stackexchange.com/questions/797/… . $\endgroup$ – dave_thompson_085 Dec 10 '16 at 1:49
17
$\begingroup$

In practice, in situations like TLS, public key encryption will be used to encrypt a secret for encrypting the actual messages, as part of a hybrid cryptosystem. This is done because Asymmetric cryptography is significantly slower than symmetric cryptography.

However, there are other cryptosystems and applications that utilize public key encryption directly. As an example, ransomware is not concerned with how long it takes to encrypt something, and it benefits immensely from not possessing the decryption key.

There are also cryptographic logging schemes that make use of public key encryption directly:

Due to the forensic value of audit logs, it is vital to provide compromise resiliency and append-only properties in a logging system to prevent active attackers. Unfortunately, existing symmetric secure logging schemes are not publicly verifiable and cannot address applications that require public auditing...

So whether or not public key encryption is used for key exchange or on the data itself is actually a matter of where the tools are being used.

RSA and Diffie-Hellman are based on different but similar mathematical problems. While they both make use of modular exponentiation, exactly what they do/why they work is different. This is evident when you look at how to attack each one: RSA is threatened by integer factorization, while DH is threatened by discrete logarithms.

Additionally: DH is a "key exchange" algorithm, which is different then "public key encryption"; It allows you and another person to mutually arrive at the same piece of information, while nobody else can. It is more or less equivalent to using public key encryption on a random message. This is in contrast to public key encryption, where you get to select the message that both parties will be aware of.

Note that Diffie-Hellman can be turned into public key encryption.

tl;dr

Both use modular exponentiation to provide the main functionality (encryption/signature generation for RSA, key agreement for DH), but the underlying problem, the key pair generation and the security properties of the input/output are different

$\endgroup$
  • $\begingroup$ so, are you saying that the difference is that they use different mathematic functions? $\endgroup$ – user3407319 Dec 9 '16 at 18:00
  • 2
    $\begingroup$ Both use modular exponentiation to provide the main functionality (encryption/signature generation for RSA, key agreement for DH), but the underlying problem, the key generation and the security properties of the input/output are different. $\endgroup$ – Maarten Bodewes Dec 9 '16 at 18:07
  • 1
    $\begingroup$ @user3407319 The point of my answer was that whether or not RSA is used for key exchange or for used for data directly depends on the use case. In the case of TLS, if RSA is used, it is as part of the key exchange, and not for the bulk of the data. DH and RSA do not use the same mathematical equation. They both happen to use modular exponentiation, however creating/using an RSA key pair is a different process then creating/using a DH key pair. For more info you will need to look at the actual algorithm - it should be clear the steps are different even if you don't understand the math. $\endgroup$ – Ella Rose Dec 9 '16 at 22:27
  • 3
    $\begingroup$ Basically, they are two different ways of accomplishing the same thing. As an analogy, "What's the difference" between a sandwich and a burrito? Both hold food in the middle so that you can eat it, but you wouldn't call a burrito a sandwich or claim that the recipes are identical. $\endgroup$ – Ella Rose Dec 9 '16 at 22:33
  • 1
    $\begingroup$ Just a minor correction: ransomware is usually very concerned about how much time it takes to encrypt something - it's whole extortion tactics depend on much data being encrypted before the ransomware is stopped. If it only manages to encrypts little data, more people would be more inclined to just remove the ransomware and ignore data loss (unless the chance was that this exact small part of data encrypted happens to be most critical) $\endgroup$ – Matija Nalis May 12 '17 at 9:33
44
$\begingroup$

Diffie-Hellman Key Exchange

Problem: We have a symmetric encryption scheme and want to communicate. We don't want anybody else to have the key, so we can't say it out loud (or over a wire).

Solution/Mechanics:

  1. We each pick a number, usually large, and keep it a secret, even from each other. I'll pick $x$, and you'll pick $y$.
  2. We agree on two more numbers, both prime, which anybody can know. We'll call them $g$ and $n$.

  3. I'll calculate $g^x\bmod n$ and tell you my answer. You'll calculate $g^y\bmod n$ and tell me your answer.

  4. Our shared key is $g^{xy}\bmod n = (g^y\bmod n)^x\bmod n = (g^x\bmod n)^y\bmod n$.

RSA Asymmetric Encryption

Problem: I want anybody to be able to encrypt a message, but I'm the only one who can decrypt it. I don't want to share decryption keys with anybody.

Solution/Mechanics:

  1. I choose two large primes, $p$ and $q$.

  2. I calculate $n$ such that $pq = n$.

  3. I calculate $t$ such that $(p-1)(q-1) = t$.

  4. I choose an integer $e$ that is both less than $t$ and coprime with $t$.

  5. I find $d$ such that $d$ is the multiplicative inverse of $e$ modulo $t$.

  6. I release $(e, n)$ as my public key, and retain $(d, n)$ as my private key.

  7. When you communicate with me, you treat your message as a large number $m$. The ciphertext $c$ is given by $c = m^e\bmod n$, and decrypted by $m = c^d\bmod n$.

$\endgroup$
  • 1
    $\begingroup$ @Wazoople "When you communicate with me, you treat your message as a large number m". This can't be true. You can't send your plain text message m. The following is true instead: "When you communicate with me, you treat your message as a large number c, which i can decrypt with my private key to produce m." $\endgroup$ – user47158 Mar 4 '18 at 23:30
  • $\begingroup$ @Nik-Lz I'm using m to refer to the cleartext I intend to communicate. If Alice wants to send a message to Bob, she takes her message m, computes the ciphertext with Bob's public key and sends the ciphertext over, which he can then decipher with his private key. $\endgroup$ – Wazoople Mar 30 '18 at 17:55
  • 2
    $\begingroup$ In Diffie-Hellman the $x$ and $y$ doesn't need to be prime number. Any random number suffices because solving the discrete logarithm won't be any harder for prime exponents. $\endgroup$ – Calmarius May 4 '18 at 20:48
  • $\begingroup$ Oh man, you're absolutely right. $g$ and $n$ need to be prime, not $x$ and $y$. Good catch +1 $\endgroup$ – Wazoople May 10 '18 at 22:05
  • 1
    $\begingroup$ What a clear and concise explanation! $\endgroup$ – neevek Jul 28 '18 at 12:21

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