Diffie Hellman applied to an Elliptic Curve

As we saw, the basic Diffie Hellman algorithm can be applied to any commutative group in which there exists a computationally efficient algorithm that allows the group operation to be applied n times on a base point b but it is not possible to efficiently calculate n knowing the result.

[To be strictly accurate, the group need not even be commutative for the cryptographic system to work but seems to be a requirement for the efficient calculation part. It is quite possible that this particular fact might be exploited to create a quantum cryptanalysis resistant version of Diffie-Hellman that only relies on the associativity property. Or it may not.]

An elliptic curve is an equation of the form:

y2 = x3 + ax + b

From the set theory point of view, the fact that the x and y coordinates form points on a curve is irrelevant. All that matters is that a set of pairs of such coordinates is define and an operation is defined on those pairs of coordinates that meets the requirements of a commutative group.

This operation is called point addition. The way in which it is defined really does not matter and seeing a graphical explanation doesn't really seem to help understanding so for the purposes of this discussion it is just the group operation. For an in depth discussion, see the WikiPedia article which is actually quite good.

As with the integer logarithm, regular elliptic curves don't provide the security properties we need. So what we actually use are elliptic curves over finite fields. The result doesn't really look like a curve of any sort at all:

Set of affine points of elliptic curve y2 = x3 − x over finite field F89.

Elliptic Curve Diffie-Hellman is like and unlike regular Diffie-Hellman in the following ways:

  • The mathematical calculations are performed using modular arithmetic with a prime modulus [same]
  • The private key is an integer that is greater than 0 and less than the prime [same]
  • The curve is defined by the curve co-efficients (the values a and b above.
  • The generator of the group and the public key are points on the curve, not an integer [different].
  • The group operation is repeated point 'addition' which corresponds to scalar multiplication rather than repeated multiplication giving exponentiation [different]
  • The group order is not one less than the prime.

From the point of view of the advanced Diffie-Hellman schemes used in Mesh/Recrypt, these do not have a significant impact.

There is however one other major difference which is that elliptic curves form a family of curves several of which rather surprisingly turn out to be equivalent (isomorphic) under certain geometric transformations. And this fact is used in certain elliptic curve systems to improve performance or achieve certain security objectives.

In particular the Montgomery curve form has the surprising property that we can perform a point doubling operation using just the x coordinate. This very useful for the basic ECDH protocol which only uses point multiplication which only requires a doubling operation.

The disadvantage of this approach comes when implementing some of the advanced techniques that require the ability to add two points. While this particular operation is quite easy to implement, it requires us to know the y coordinate and that requires functions that are not usually implemented in cryptographic modules that implement Montgomery curves.

The practical consequence of this is that for the purposes of recryption and other advanced techniques, the Edwards curve forms are generally preferred.