# Tag Info

16

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way: In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one ...

16

The security of Diffie-Hellman depends upon the group in which DH is used, but not upon which generator is used for this group. See note 3.53 (chapter 3, page 103) of the Handbook of Applied Cryptography. In more details: for DH, we use a subgroup of size $q$ of the integers modulo $p$ (a big prime) with the multiplication as group operation. $q$ should be ...

15

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using. This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, ...

13

I assume you're talking about SSL/TLS or a similar protocol. In these protocols there are two reasons to use Diffie-Hellman: Your certificate only supports signing Either it is an RSA certificate restricted to signing, or it uses an algorithm that doesn't support encryption, such as DSA or ECDSA. Forward security - What happens if the server's private key ...

12

The really great thing about Diffie-Hellman is how light it is, network-wise: both parties send each other a single message; neither has to wait for the message from the peer before beginning to computing his own message. If you can tolerate something heavier, you can have a look at what @Paŭlo describes; with $n$ participants, it requires $n-1$ messaging ...

11

The problems: The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$. The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$. The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide if they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = ... 11 First, we are talking about multiplications, so we work in$\mathbb{Z}_p^*$, not$\mathbb{Z}_p$. By definition, any integer$g \in \mathbb{Z}_p^*$is the generator for... the subgroup generated by$g$, i.e. the set of$g^k \mod p$for all integer values$k$. The order of$g$is the smallest$k \geq 1$such that$g^k = 1 \mod p$. For soundness (Alice and ... 11 The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator$g$, and relies on $${y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A},$$ where$y_A$and$y_B$are publicly transmitted, while$x_A$and$x_B$remain private. With three parties, we still have$$((g^{x_A})^{x_B})^{x_C} = ... 10 On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ... 10 As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met: p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with ... 9 Not only does g not need to be a generator for the entire group, general practice is that it is not. As Thomas has mentioned, the order of$g$is the smallest$k \ge 1$such that$g^k = 1 \mod p$. Let$q$be the order of the value$g$we use. If$g$is a generator for the entire group, then$q = p-1$, if not, it is some proper divisor of$p-1$. Now, if ... 8 Well, the advantages of static-ephemeral ECDH (and, they apply to DH as well): You get one-way authentication for free. That is, if Bob has Alice's public ECDH key, and uses it to talk to someone, Bob knows that that someone is Alice, without doing any further checks. Now, Alice has no idea who she's talking to; on the other hand, for some scenarios, ... 8 Well, yes, that is generally good advice about DH. Here is some background on this: support you were given a value$g^x \bmod p$, and you were also told that$1 \le x \le A$for some value$A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover$x$in about$\sqrt A$steps. If we have as our ... 8 Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP. Here's what's going ... 8 Shared secret resulting from the Diffie-Hellman step is a mathematical object; namely, the X coordinate of a curve point. It is a value in a non-binary range; moreover, it is indistinguishable from randomness only up to the security against discrete logarithm, i.e. about 128 bits. Thus, it is at least debatable that parts of the key might be guessable from ... 7 Well, to answer your questions in order: How big should$p$be? Well, it should be large enough to defend against the known attacks against it. The most efficient attack is NFS; that has been used against numbers on the order of$2^{768}$(a 232 digit number). It would appear wise to pick a$p$that's considerably bigger than that; around 1024 bits at a ... 7 The check$y_b^q = 1 \mod p$is there to prevent two possible weaknesses: Suppose someone gave us (either because of a programmer error or deliberate attack) gave us a$y_b$value of small order. If so, then someone listening in can guess the shared secret you derive. Suppose an attacker gave us a$y_b$value with an order with a small factor$r$. Then, ... 7 Rather risk vulnerabilities of third party library than implement your own. If you feel novice on this field, only implement cryptography yourself as an learning exercise. Why: Mistakes, lack of know-how and maintenance. It is very easy to make novice mistakes in custom implementation of cryptography. Even battle scarred veterans of the field do mistakes ... 7 Actually, there is no major difference between$p \equiv 23\ (\bmod\ 24)$vs$p \equiv 11\ (\bmod\ 24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?". OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred ... 7$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x$of them]$\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.03 in}y$of them]$\ldots \cdot g\cdot g\cdot g)= \;\;\; g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$of them] ... 6 For Diffie-Hellman, adequate security is achieved provided that: we work modulo a prime$p$big enough to resist discrete logarithm (1536 bits are sufficient); the order of the subgroup generated by$g$is a multiple of a big-enough prime integer$q$($q$should have length$2n$bits to achieve$2^n$security); the private exponents are randomly chosen in ... 6 Actually the presentation of digital signatures as "encryption with the private key" is a misleading historical way of explaining RSA signatures; but it really works only for RSA. For such a scheme to work, you need the asymmetric encryption algorithm to be a trapdoor permutation, so that the space of encrypted messages is the same than the space of ... 6 For Diffie-Hellman or any variants like Elgamal or DSA, you're better off using the established primes. It doesn't matter what primes you use, really, as long as they're prime. The standard primes have had someone nod at them. If you generate your own prime and there's a problem (e.g. it's not really prime), then you're on your own and we will all laugh at ... 6 That's because you can do ECDH by exchanging only the X coordinates of your public value; as long as the shared secret depends only on the x coordinate, everything works out. Here's the fundamental property of elliptic curves that makes this work, the x coordinate of$nP$is only a function of the x coordinate of$P$(and$n$); it does not depend on the y ... 6 The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though. Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical ... 6 An attack would be trivial if the seed of the RNG was only 32 bits; just enumerate the seeds, and test which matches the intercepted messages. That's easy. However the default Java Random class uses a 48-bit state and seed (which would still be attackable, though$2^{16}$times less easily), and there are safe subclasses, thus use of Random does not imply ... 6 There is nothing related to passwords in AES. AES uses 128-bit keys, i.e. sequences of 128 bits. How you come up with such a key is out of scope of AES. In some contexts, you want to generate these 128 bits in a deterministic way from a password (and possibly some publicly known contextual data, like a "salt"); this is a job for password hashing. In other ... 6 How long are parameters used for? Usually$g$and$p$are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago. So the answer is basically decades. The impossibility of brute force Let's suppose that I as an attacker decide I'm going ... 6 ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to ... 5 It means that if you have an oracle access to CDH, then you can solve DDH, but we do not know if there exists a reduction the other way round. Technically, suppose$\mathsf{CDH}$is an oracle that finds$g^{xy}$, given$(g^x,g^y)$, then for a DDH instance, say$(a,b,c)$, you can feed$\mathsf{CDH}$with$(a,b)$and output$1$if output of$\mathsf{CDH}\$ ...

Only top voted, non community-wiki answers of a minimum length are eligible