Example: ECDH with curve x25519 – Elliptic Curves
8.5.8 Example: ECDH with curve x25519
RFC 7748 [86] specifies how Alice and Bob must perform ECDH using curve 25519. The protocol is illustrated in Figure 8.12 and we will follow the notation in RFC 7748 in case you want to look into that standard for more detailed information.
Figure 8.12: ECDHE with curve 25519 as specified in RFC 7748
First, Alice generates a random 32-byte private key, a. She then uses the X25519() function for scalar multiplication on the Montgomery form of the x25519 curve and computes:
where 9 is the u-coordinate of the base point. It is encoded as a byte with value 9, followed by 31 zero bytes.
The u-coordinate is simply part of the pair (u,v) representing the coordinates on a Montgomery curve. Every u-coordinate is an element of the underlying finite field 𝔽2255−19.
The X25519 function takes a scalar and a u-coordinate as input and outputs the u-coordinate of the result of scalar multiplication. Thus, the inputs and the output of X25519 are 32-byte strings. Their encoding is specified in RFC 7748.
Alice then transmits KA to Bob. Analogous to Alice, Bob also generates his private 32-byte key b, computes:
and sends KB to Alice. Using these values, Alice computes:
and Bob computes:
In the last step, it is advisable for Alice and Bob to verify that K is not an all-zero value and immediately terminate the protocol if this is the case. Otherwise, if K is not an all-zero value, Alice and Bob now share a secret because it holds that:
8.6 Summary
In this chapter we learned about how to use elliptic curves in cryptography and especially within TLS. Elliptic curves are a special kind of mathematical structure that allows for a commutative group operation. It turns out that the discrete logarithm problem in these groups is harder than in other, more common groups such as 𝔽p∗. Moreover, they offer great flexibility via their curve parameters. We have seen how to perform Diffie-Hellman key exchange using these curves, and how secure curves are chosen to be used within the TLS handshake protocol.
In the next chapter, another application of asymmetric cryptography is introduced, namely digital signatures. Digital signatures are important tools for providing integrity protection and authenticity, but they can also serve yet another security service, namely non-repudiation. In this respect, they are very similar to physical, handwritten signatures.