Elliptic Curve Cryptography

An elliptic curve is the set of points that satisfy an equation in the form of y^2 = x^3 + ax + b. It has interesting properties, such as symmetry over the x-axis. The second property is that any two points on the curve would make a line which crosses a third point on that curve. If the two points are exactly vertical, the third point is considered to be at infinity. If the two points are the same, the derivative of the curve is taken at that point (the slope of curve at that point). Entering two points and receiving the third one is defined to be the addition of two points. The third point is later reflected over the x-axis.

The idea behind encryption with an elliptic curve is of taking a plain message and defining it as a point in the curve (since a message can be turned into a long number). This point is added to itself over and over again a k number of times. The message turned into a point, and the point turned into another point in the curve multiple times, like a pool ball bouncing around. After some other manipulations depending on the system, we have our cypher-text, i.e., our encrypted message. Without knowing k (the private key), it is prohibitively hard to decrypt the message. i.e., without knowing how many times a pool ball bounced, it is impossible to know where it started.

In practice, the curve be made of discrete points, and not a continuous line, since only integer numbers are used. Furthermore, if we limit ourselves to a subset of numbers by picking a prime number as a maximum, and modulate through it so as numbers start over from 0 if they surpass the maximum, we get a scattered (but symmetrical) array of dots.

An elliptic curve system can be configured by picking:

  • a prime number as a maximum,

  • a curve equation,

  • a public point on the curve.

The private number is the number of times the public point will be added to itself. Computing the private key from the public key is called the elliptic curve discrete logarithm function, and is a trapdoor function.

Elliptic curve cryptography is a modern system and very efficient in time and space. It is slated to replace the ubiquitous RSA system based on prime factorization. Unlike factoring, there doesn’t appear to be shortcuts, and mathematicians still haven’t found an algorithm to solve this problem better than a naive approach. As such, its security is exponentially stronger than RSA.

It has been implemented in by the U.S. government to encrypt internal communications, the Tor project uses it, and it is the new default method for authentication for secure web browsing over SSL/TLS. Among cryptocurrencies, it is used by Bitcoin of course, as well as Ethereum, EOS and Zcash. And as the wiki page says, the list is incomplete, and we can help by expanding it.

Beam uses the libsecp256k1 optimized C library implemented in the Bitcoin Core client, for operation on a curve of type secp256k1, see also this answer. Secp256k1 refers to the parameters of the elliptic curve, as defined in Standards for Efficient Cryptography (SEC). The resulting curve is that of y^2 = x^3 + 7, defined over the field Z (integer numbers) modulo 2^256-2^32-977. Be prepared to use huge integer arithmetic, since this number is several lines long.