How Does Elliptic Curve Cryptography Work?

How Does Elliptic Curve Cryptography Work?
kdobieski
Fri, 01/04/2019 – 09:33

The need for a new cryptographic algorithm

The key characteristic of RSA algorithm is that is contains one process that is easy to do but difficult to undo. The easy part of the algorithm multiplies two prime numbers, while the difficult pair is factoring the product of the multiplication into its two component primes. Algorithms that have this characteristic are known as Trapdoor Functions. Finding a good Trapdoor Function is critical to making a secure public key cryptographic system. Simply talking, the bigger the spread between the difficulty of going one direction in a Trapdoor Function and going the other, the more secure a cryptographic system based on it will be.

Factoring is a very well-known problem and has been studied since antiquity like the Sieve of Eratosthenes for finding all prime numbers up to any given limit. With the advancement of mathematics and computational power, the gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking, hence the size of the keys need to grow even faster. This is not a sustainable situation for mobile and low-powered devices that have limited computational power. The gap between factoring and multiplying is not sustainable in the long term. This means is that RSA is not the ideal system for the future of cryptography.

 

Factoring is a very well-known problem and has been studied since antiquity like the Sieve of Eratosthenes for finding all prime numbers up to any given limit. With the advancement of mathematics and computational power, the gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking, hence the size of the keys need to grow even faster. This is not a sustainable situation for mobile and low-powered devices that have limited computational power. The gap between factoring and multiplying is not sustainable in the long term. This means is that RSA is not the ideal system for the future of cryptography. In fact, recent research has demonstrated that even 2048-bits long RSA keys can be effectively downgraded via either man-in-the-browser or padding oracle attacks. Going one step further, the report suggests that the best countermeasure is to deprecate the RSA key exchange and switch to ECC.

How does ECC work?

But what exactly is an elliptic curve and how does the underlying Trapdoor Function work? An elliptic curve is the set of points that satisfy a specific mathematical equation. The equation for an elliptic curve looks like this y2=x3+ax+b and is being represented graphically like the image below.

Picture 1: Elliptic curve (source: blog.cloudflare.com)

Multiplying a point on the curve by a number will produce another point on the curve, but it is very difficult to find what number was used, even if you know the original point and the result. Equations based on elliptic curves have a characteristic that is very valuable for cryptography purposes: they are relatively easy to perform, and extremely difficult to reverse.

The elliptic curve discrete logarithm is the hard problem underpinning elliptic curve cryptography. Despite almost three decades of research, mathematicians still haven’t found an algorithm to solve this problem that improves upon the naive approach. In other words, unlike with factoring, based on currently understood mathematics there doesn’t appear to be a shortcut that is narrowing the gap in a Trapdoor Function based around this problem. This means that for numbers of the same size, solving elliptic curve discrete logarithms is significantly harder than factoring. Since a more computationally intensive hard problem means a stronger cryptographic system, it follows that elliptic curve cryptosystems are harder to break than RSA and Diffie-Hellman.

To visualize how much harder it is to break, Lenstra, Kleinjung and Thome introduced in 2013 the concept of “Global Security.” You can compute how much energy is needed to break a cryptographic algorithm, and compare that with how much water that energy could boil. This is a kind of cryptographic carbon footprint. By this measure, breaking a 228-bit RSA key requires less energy to than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you’d need a key with 2,380-bits.

With ECC, you can use smaller keys to get the same levels of security. Small keys are important, especially in a world where more and more cryptography is done on less powerful devices like mobile phones. While multiplying two prime numbers together is easier than factoring the product into its component parts, when the prime numbers start to get very long even just the multiplication step can take some time on a low powered device. While you could likely continue to keep RSA secure by increasing the key length that comes with a cost of slower cryptographic performance on the client. ECC appears to offer a better tradeoff: high security with short, fast keys.

Elliptic curve cryptography is now used in a variety of applications: the U.S. government uses it to protect internal communications, the Tor project uses it to help assure anonymity, it is the mechanism used to prove ownership of bitcoins, it provides signatures in Apple’s iMessage service, it is used to encrypt DNS information with DNSCurve, and it is the preferred method for authentication for secure web browsing over SSL/TLS.

Although there are certain cautions when implementing ECC, such as the use of a good source of random numbers on the machine making the signatures, the advantages of elliptic curve cryptography over traditional RSA are widely accepted.

Conclusions

Many experts are concerned that the mathematical algorithms behind RSA and Diffie-Hellman could be broken within 5 years. In fact, the developments on quantum computing will derive computational powers that will allow us to solve mathematical problems, such as factoring very large prime numbers that were once unsolvable. It is the ability of quantum computing to crunch so much data so fast that creates game-changing possibilities in various science fields including the data protection methods. One area of data protection that will be affected by quantum computing capabilities is encryption, because current encryption algorithms will become obsolete since it could be deciphered in essentially less time. Will ECC be left as the only reasonable alternative or will Quantum Key Distribution prevail? Only time will show.

Related Articles

Elliptic Curve Cryptography
Guest Blogger: Anastasios Arampatzis
Introducing Elliptic Curve Cryptography

Diffie-Hellman and RSA cryptographic methods are based on the creation of keys by using very large prime numbers. Hence, key creation requires a lot computational power.

Elliptic 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 generates keys through the properties of the elliptic curve equation instead of the traditional method of generation as the product of very large prime numbers.

The technology can be used in conjunction with most public key encryption methods, such as RSA, and Diffie-Hellman. According to some researchers, ECC can achieve the same level of security with a 164-bit key that other systems require a 1,024-bit key. Because ECC helps to establish equivalent security with lower computing power and battery resource usage, it is becoming widely used for mobile applications. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985 and elliptic curve cryptography algorithms entered wide use around 2004.

*** This is a Security Bloggers Network syndicated blog from Rss blog authored by kdobieski. Read the original post at: https://www.venafi.com/blog/how-does-elliptic-curve-cryptography-work