Most Things In Cybersecurity Aren’t Perfect, and Just Hard Problems: Cracking Low-Order Elliptic Curves

In cybersecurity, I like to break things, as when you break things, you can understand how things actually work. And, so, are few things in cybersecurity that give perfect security, and most things are based on something that is difficult and expensive to solve. The Shamir method is one thing that gives perfect security, but most other methods are just hard problems. So, let’s crack the basis of the method that secures every single one of your browser connections to the Web: ECC (Elliptic Curve Cryptography).

The security of ECC is based on finding the discrete logarithm of a random elliptic curve element that relates to a publicly known point on a curve. This is defined as ECDLP (elliptic curve discrete logarithm problem). For this, we have a base point (G), and then a secret scale value (x), and compute a point on the curve of x.G. Overall, it should be computationally difficult to discover x from x.G, even though we know the point G. For a Koblitz curve, we have the form of:

y²=x³+ax+b (mod p)

and where a and b are well-defined parameters of the curve, and p is a prime number. The Bitcoin curve, for example, uses a=0 and b=7:

y²=x³+7 (mod p)