The mathematical properties and concepts of elliptic curves are used in asymmetric key exchange cryptography schemes. Common applications include:
In this article, we’ll take a deep dive into elliptic curve cryptography. We aim to take a digestible, slightly less academic look that still thoroughly explains this technical topic. For something a little lighter, explore our introduction to cryptography.
Elliptic curve cryptography was introduced in 1985 by two scientists, N. Koblitz and V. Miller. They proposed the idea of using points defined by elliptic curves instead of the finite prime fields such that the Discrete Logarithm problem assumption holds, as commonly used in the standard Diffie-Hellman key exchange protocol.
This assumption serves as the fundamental security principle for asymmetric key exchange cryptography methods. The elliptic curve cryptography takes it one step ahead by providing an efficient mathematical approach to compute the necessary cryptographic operations.
Yes, these topics get quite technical — but the underlying mathematical concepts are rather straightforward. This simplicity is precisely what makes elliptic curve-based cryptosystems so efficient for use in securing modern devices that:
Let’s explore how elliptic curve cryptography helps achieve this goal using simple explanations of these underlying concepts.
Let’s first review the generalized Diffie-Hellman key exchange protocol:
Both Alice and Bob now possess the same group elements such that (g^{β})^{α} =(g^{α})^{β} of G and so, g^{βα}=g^{αβ} of G. Now, an adversary Eve may be intercepting the communications channel. Note that the values α and β are kept private by Alice and Bob. And since G is a large prime order group, there exists no efficient algorithm to compute g^{αβ} from g, g^{α}, g^{β}, which are shared over the public channel.
The computational Diffie Hellman assumption holds: it is hard to compute g^{αβ} correctly by multiplying g^{α}, g^{β}, since mathematically, g^{α} x g^{β}= g^{(α+β)}. No efficient algorithm exists to solve this Diffie-Hellman problem.
Now let’s look at the mathematical concepts behind elliptic curves and how these underlying concepts are exploited to develop a secure implementation of the Diffie Hellman key exchange protocol.
In the steps below, we define the Elliptic Curve Diffie-Hellman key exchange protocol:
Now, both Alice and Bob possess the same group elements generated using the points (P = βaG = aβG) on the elliptic curve over the finite field. It is not possible for Eve intercepting the communications as a Man-in-the-Middle adversary to compute P using only G, A = α*G and B = β*G. This is because the Diffie-Hellman assumption as discussed earlier, holds. Note that other variations of elliptic curve cryptography exist (other than using the D-H key exchange scheme).
But why use elliptic curves for the generator function G, when any finite cyclic field generator can do the job well enough? Consider the mathematical properties of elliptic curves, and the mathematical functions required to implement the D-H key exchange protocol. The group operations on the elliptic curve can be performed as follows:
(Image source @VitalikButerin)
This scalar multiplication is a one-way function, which means that it is possible to find the output of a function given any integer input, but very hard to find the inverse function value that is generated from any random integer. In simple terms, it is easy to find the image from an original input, but hard to invert the image reflection such that it produces the original image.
The elliptic curve is defined as the field of integers modulo prime P. Considering any points P and Q on this curve, Q being some multiple of P, it is find to hard exactly the chosen integer value k such that Q = k*P. This assumption refers to the Elliptic Curve Discrete Logarithm problem and is the fundamental principle behind the Elliptic Curve implementation of the Diffie Hellman key exchange protocol.
But why use the Elliptic Curve implementation instead of a standard finite cyclic group field for the generator function? You can notice how computing the direct sum and scalar multiplication between two points in the field of the elliptic curve does not have an algebraic structure, and yet, any set of (different) points from this field can be chose such that the Discrete Log security assumption of the D-H algorithm also holds.
This means that in order to achieve the same levels of security, the Elliptic Curve Diffie Hellman cryptography requires much shorter key length. This results in fewer memory cycles and CPU resources consumed to implement the elliptic curve based cryptography key exchange protocol.
For example, a symmetric encryption of 56 bits key size may require 512 bits for the RSA and standard Diffie Hellman implementation (modulus size for bits) and 112 bits for the elliptic curve cryptography. Now for stronger security, the symmetric encryption security worth 256 bits requires 15360 bits key size implementation using the RSA and standard D-H algorithm, but only 512 bits using the elliptic curve DH implementation.
This makes elliptic curve cryptography particularly suitable for efficient cryptographic implementations in mobile devices.
See an error or have a suggestion? Please let us know by emailing ssg-blogs@splunk.com.
This posting does not necessarily represent Splunk's position, strategies or opinion.
The Splunk platform removes the barriers between data and action, empowering observability, IT and security teams to ensure their organizations are secure, resilient and innovative.
Founded in 2003, Splunk is a global company — with over 7,500 employees, Splunkers have received over 1,020 patents to date and availability in 21 regions around the world — and offers an open, extensible data platform that supports shared data across any environment so that all teams in an organization can get end-to-end visibility, with context, for every interaction and business process. Build a strong data foundation with Splunk.