How does the elliptic-curve version of Diffie-Hellman cryptography work?

Question

Does the Elliptic curve diffie hellman calculation look any different from the standard one defined here:

            /*
             * The basic Diffie-Hellman Key Agreement Equation 
             * 
             * The client initiates
             * A = g^a mod p
             * 
             * Sends (g p A) to the server
             * 
             * The server calculates B
             * B = g^b mod p
             * 
             * Sends B back to client
             * 
             * The client calculates K
             * K = B^a mod p
             * 
             * The server calucaltes K
             * K = A^b mod p
             * 
             */

Or is it just a specific way of selecting g, a, p and b? How are g,a,p and b selected anyway?

Saber

Answer 1

The basic principle is the same, but the selection of the private key and how the public key are computed are significantly different. In addition, everyone has to agree beforehand on the elliptic curve to use.

As noted, in the elliptic-curve version of Diffie-Hellman, you first decide which elliptic curve you're using. That determines a number of independent parameters called the domain parameters. Without getting too technical, it turns out that some curves are better than others for cryptographic purposes, so the parameters are actually chosen carefully rather than at random. This is somewhat analogous to picking good prime factors.

There are two sets of domain parameters:

• E, the elliptic curve itself.
• G, a point on E that is called the base point.

E and G are necessary and sufficient to describe all the information you need.

In ECC-DH, the private key d is computed by taking a randomly selected number on the interval [1, n-1], where n is the order of G. The public key Q is computed by taking Q = dG. After that the general idea is the same, except that instead of trying to solve a hard integer factorization problem, you're trying to solve a hard discrete logarithm problem.

Shaitan

Ok im not a mathematician, but I think this means: n is the order of G (which is of group E?) this means: n is the smallest positive integer such that G^n = e ...what's e?? e is the identity element of the group... ow now i get it... In algebra, an identity or identity element of a set E with a binary operation · is an element e that, when combined with any element x of S, produces that same x. That is, e·x = x·e = x for all x in E. How does this apply to G^n of set E where set E is (y^2 = x^3 + ax + b) How do I get the base point? How do I determine e, how do I solve n ? – Saber

Unfortunately, elliptic-curve cryptography isn't a trivial subject. I'm not sure that a comment is enough to cover everything you ask as follow-up questions. It might be better if you did a little research into the topic first, or at least know some group theory. Check out certicom.com/index.php/ecc-tutorial for a decent intro. – Shaitan

Some people have suggested I forget this whole idea, and use SSL. I like to create my own solutions. What a complicated solution this is proving to be. – Saber

Well, standard DH is also a discrete logarithm problem and not an integer factorization problem. And it also has domain parameters. – Roam

Good answer except that standard DH is also a discrete logarithm problem. – Slinky