What is elliptical curve cryptography (ECC)?
Elliptical curve cryptography (ECC) is a public key encryption technique based on elliptic curve theory that can be used to create faster, smaller and more efficient cryptographic keys.
ECC is an alternative to the Rivest-Shamir-Adleman (RSA) cryptographic algorithm. It is often used for digital signatures in cryptocurrencies such as Bitcoin and Ethereum and one-way encryption of emails, data and software.
Public key cryptography systems, such as ECC, use a mathematical process to merge two distinct keys. They then use the output to encrypt and decrypt data. One key is public and known to anyone, and the other is private and known only to the sender and receiver of the data.
What is an elliptic curve?
An elliptic curve is not an ellipse or oval shape. Instead, it is represented as a looping line intersecting two axes, which are lines on a graph used to indicate the position of a point. The curve is completely symmetric, or mirrored, along the x-axis of the graph.
From a cryptographic perspective, the points along the graph can be formulated using the following equation:
y²=x³ + ax + b
When a set of points satisfies the above equation, they create an elliptic curve.
A and b are constants in this equation, and x and y are variables. Also, the curve stays the same because any point on it can be mirrored on the X-axis and intersect with a non-vertical line in three places or fewer. The points that satisfy the equation above do so in two variables: degree two in one variable and degree three in the other.
For example, the figure below shows an elliptical curve with three intersection points. Each point lies on a 2D plane with X and Y values. The curve itself is known as a plane curve or prime curve, and the field it lies in is finite.
How does elliptic curve cryptography work?
ECC is like most other public key encryption methods, such as the RSA algorithm and Diffie-Hellman. Each of these cryptography mechanisms uses the concept of a one-way, or trapdoor, function. A mathematical equation with a public and private key can get from point A to point B easily. But without knowing the private key and depending on the key size, getting from B to A is difficult, if not impossible.
Algorithms that use a trapdoor are easy to compute in one direction but hard in the other, meaning the inverse is very difficult to find. In this sense, ECC is like a padlock that doesn't require a key to close but is impossible to open without the correct key.
The basis of ECC is the elliptic curve discrete logarithm problem (ECDLP), which involves finding the logarithm (also known as the exponent) in the elliptic curve equation (given above) from the two points on the curve. ECC generates keys through the properties of the equation given above instead of the traditional method of generation as the product of large prime numbers (such as RSA uses).
The system is based on the properties of a set of values for which operations can be performed on any two members of the group to produce a third member. This third member is derived from points where the line intersects the axes, as shown with the green line and three blue dots in the above diagram labeled A, B and C.
Multiplying a point on the curve by a number produces another point on the curve (C). Taking point C and bringing it to the mirrored point on the opposite side of the x-axis produces point D. From here, a line is drawn back to the original point A, creating an intersection at point E. This process can be completed n number of times within a defined maximum value. The n is the private key value, which indicates how often the equation should be run, ending on the final value used to encrypt and decrypt data. The maximum defined value of the equation relates to the key size used.
Here is an explanation of the working of the ECC cryptography when two parties are involved:
- Select the elliptic curve: An elliptic curve with known parameters is selected.
- Generate the private key: Party 1 (P1) generates a random number as their private key.
- Generate the public key: P1 then uses this private key and the chosen elliptic curve to calculate the corresponding public key.
- Share the public key: P1 provides the ECC public key to Party 2 (P2).
- Message encryption: P2 uses the public key to encrypt a plain-text message into ciphertext.
- Message decryption: P1 receives the ciphertext and uses their private key to decrypt the message and obtain the original plaintext message.
ECC vs. RSA
RSA is one of the oldest public-key cryptography systems. It's a type of asymmetric or "public key" encryption that, like ECC, uses two private and public keys. Either key can be used to encrypt a message, while the other key is used to decrypt it. The security of the RSA algorithm comes from choosing two large and distinct prime numbers (p and q) and then multiplying them to calculate a large integer (known as a "modulus" and represented as n). Then, this modulus is used to generate the public key.
Choosing sufficiently large prime numbers reduces the probability that they can be determined from the total to reverse engineer the algorithm (say, by a threat actor). Due to this feature, RSA is still used for many applications, including software programs, VPNs, and web browsers.
That said, RSA does have some vulnerabilities. For example, suppose the prime numbers chosen to factor the modulus are not large or random enough. In that case, a determined adversary may be able to calculate the modulus and, ultimately, crack the encryption and the application it is meant to protect. A small key size can also expose it and make the underlying algorithm susceptible. Due to these weaknesses, RSA is not immune to cyberattacks like factorization attacks where attackers attempt to discover the original prime numbers from the modulus; side-channel attacks, where they analyze the decryption process to deduce the private key; and plaintext attacks, where they use some parts of the plaintext to get the ciphertext and then use the ciphertext to deduce the remaining parts of the plaintext.
ECC can yield a higher level of security than RSA, mainly because the elliptic curve equation is significantly more challenging to resolve than factoring a modulus to find the prime numbers used to calculate it. Because ECC presents a hard mathematical problem that's computationally intense, it translates into a stronger cryptographic system that's harder to break than a system that's protected by RSA.
Moreover, ECC security requires fewer computing resources to encrypt and decrypt data than alternative methods, including RSA. For example, ECC using a 256-bit key would require a 3,072-bit RSA key to achieve equivalent protection. In other words, using a smaller key in ECC can provide the same level of security as using a larger key in RSA. This is beneficial when the cryptography is done on a less powerful device, such as a mobile phone.
In sum, ECC offers several benefits compared to RSA:
How secure is elliptical curve cryptography?
The primary benefit of ECC is the inherent efficiencies gained when encrypting and decrypting data. The sizes of the key and underlying elliptic curve also determine its security and chance of being broken. For this reason, even the U.S. government used ECC in the past. Internal government communications use either 256- or 384-bit key sizes, depending on the sensitivity level of the information being transmitted.
As with many other cryptographic systems, using a key that's too small can compromise the ECC system's security. Even so, powerful quantum computers are needed to break ECC, something that's very difficult, if not impossible, to do with the current computational power.
Benefits of elliptical curve cryptography
ECC is generally considered more secure than many other cryptographic systems, including RSA, because it is based on a complex mathematical problem that's hard to reverse engineer. It also provides higher security for less effort (smaller keys and lesser computational power).
The keys used in ECC are smaller, so they are easier to store and manage. Another benefit of ECC is that the keys and signatures can be generated faster than the alternatives. Finally, ECC enables lower latency and is supported by strong protocols for authenticated key exchange for encryption/decryption.
Drawbacks of elliptical curve cryptography
One critical drawback of ECC is that it can be hard to implement compared to other systems, such as RSA.
Another problem is that the private key could be compromised if the random number generator used to generate the key is weak or compromised. For example, the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG) standardized by the National Institute of Standards and Technology (NIST) may include a back door that could allow an adversary to predict the keys and use them to break the cryptography. Similarly, private keys could be revealed if the random numbers generated to calculate the keys are not actually random.
Applications of elliptical curve cryptography
Because ECC establishes equivalent security with lower computing power and battery use than RSA, it is widely used for mobile applications and internet of things (IoT) devices with limited central processing unit (CPU) resources. ECC is also used to implement digital signatures in cryptocurrencies. These currencies use the Elliptic Curve Digital Signature Algorithm (ECDSA) to sign transactions and prove coin ownership.
With its shorter key length and efficiency, ECC is also used in web applications and web browsers to secure online communications over SSL/TLS and ensure users' online privacy.
Other applications of ECC include:
- email encryption
- encryption of DNS information
- online banking
- online payments (e.g., e-commerce)
- software load balancers
- chat messaging applications (e.g., Apple iMessage)
The history of elliptical curve cryptography
The properties and functions of elliptic curves in mathematics have been studied for more than 150 years. Their use within cryptography was first proposed in 1985, separately by Neal Koblitz from the University of Washington and Victor Miller at IBM.
ECC was first developed by Certicom, a mobile e-business security provider, and was then licensed by Hifn, a manufacturer of integrated circuitry and network security products. Vendors, including 3Com, Cylink Corp., Motorola, Pitney Bowes, Siemens, TRW Inc. (acquired by Northrop Grumman) and Verifone, supported ECC in their products. Today, companies such as Apple, Google, and Blackberry Certicom also use ECC in their products.
The use of ECC in public and private sectors has increased over the past few years. While RSA continues to be widely used and is easier to understand and implement compared to ECC, the efficiency benefits of ECC make it appealing for many use cases. These include speeding up secure access to Secure Sockets Layer-encrypted websites and streaming encrypted data from devices with limited computing power.
Data encryption is a must-have for cloud environments, but organizations face many challenges as they try to secure their data. Learn what cloud encryption strategies organizations can implement to overcome these limitations.
