Hot answers tagged diffie-hellman
13
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 ...
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
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 ...
9
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 ...
9
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} = ...
9
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 ...
9
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 ...
7
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, ...
7
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 ...
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
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 ...
6
There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as ...
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
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, ...
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 ...
5
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 ...
5
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 ...
5
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 ...
5
There's nothing wrong with generating your own primes for DH, as long as you know what you're doing.
On the other hand, if you are a bit weak on number theory (or just glad that someone else has done the work, and had it double-checked), there's also nothing wrong with the modulii and generators in RFC 3526.
As for the paper, well, it chiefly noted that ...
5
Generating your own group for Diffie-Hellman is not a tough issue; but it is somewhat expensive (it depends on the context, but a 25 MHz ARM device would not like to do it often) and it is not really needed: a good point of DH (and DSA) is that the group parameters can be shared between many users, with no ill effect on the confidentiality of their ...
5
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 ...
5
This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen).
Here's how we can use an Oracle that can solve the above problem to solve the DDH problem:
In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$.
We call the ...
4
In the general case, for proper security with Diffie-Hellman, we need a value $g$ such that the order of $g$ (the smallest integer $n \geq 1$ such that $g^n = 1 \mod p$) is a multiple of a large enough prime $q$. "Large enough" means "of length at least $2t$ bits if we target $t$-bit security". Since $n$ necessarily divides $p-1$, $q$ divides $p-1$.
We ...
4
We choose $p$ to be such that $p = 2k +1$ where $k$ is also a prime. It is relatively fast to find such $p$.
Then any number in $\mathbb{Z}^*_p$ will have an order which is one of ${2, k, 2k, 1}$
We pick a random number $x$ and check if $x, x^2, x^k \not\equiv 1 \pmod{p}$. If so, then $x$ is a primitive root of $p$, otherwise, we start over.
If we pick ...
4
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}$ ...
4
The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security:
In the random oracle model ECIES-KEM and EC-Schnorr are
jointly secure if the gap-DLP problem and gap-DH problem are both hard
Ed25519 is extremely similar to EC-Schnorr, and both ECIES ...
4
Before we get to the questions, we need to understand what these attacks look like.
An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing ...
4
Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...
4
A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer.
There might be other groups in which DL problem is ...
Only top voted, non community-wiki answers of a minimum length are eligible
