Elliptic Curve Cryptography - Basic Math

• Communications
• Applied Math
• Algorithms

Quick Links

• Part 1: New book on Elliptic Curve Cryptography
• Part 2: Elliptic Curve Cryptography - Basic Math
• Part 3: Elliptic Curve Cryptography - Security Considerations
• Part 4: Elliptic Curve Cryptography - Key Exchange and Signatures
• Part 5: Elliptic Curve Cryptography - Extension Fields
• Part 6: Elliptic Curve Cryptography - Multiple Signatures

Cryptography is the art of hiding messages, NOT writing on graves, which is a direct translation a friend of mine once asked. I should have said "that's engraving!", but I was a week late. The main engine of encrypting a message uses a single key and a fast algorithm. The NIST standard is AES which can use key sizes of 128 bits, 192 bits, or 256 bits. Each of these is considered a level of security.

The problem with this single key is that both the sender and receiver must know it. For spies it is pretty easy to send them out with a keypad book with instructions on which page to use for a key depending on some public information. For people who don't know each other this key exchange problem becomes a much more difficult task.

The key exchange problem is solved using a "one way trap door function". The public exchange of information which allows an easy computation to create a common key but is nearly impossible for anyone else to figure out, is a "one way" function.

It turns out that the solution to this problem also allows digital signatures. The one way function "signs" a document so that nobody else can forge the signature or the document. The one way function I'm going to describe in this blog uses elliptic curve math over finite fields. This method has shorter keys and more security than other methods, but it is a bit out of the way for most engineers.

For lots of details and subroutines to implement the math on an embedded system, check out Elliptic Curve Cryptography for Developers. I would love to see someone translate that into an FPGA. I think it is possible, but certainly not very easy.

It turns out the equation for elliptic curves over real numbers, complex numbers, and finite fields is the same (as long as the field characteristic is greater than 3): $$y^2 = x^3 + a x + b$$ The points on an elliptic curve are values of $(x, y)$ which satisfy the elliptic curve equation.

An algebra is created by "adding" points. Every algebra has an identity element. For elliptic curve mathematics, the identity element is NOT on the curve. It is called the "point at infinity" $\mathscr O$. Here's a graph of an elliptic curve over the real numbers which shows how point addition works

The equation of this curve is $y^2 = x^3 - 5 x + 5$. Let's start with the points $R$ and $-R$. For a useful algebra we require $$R - R = \mathscr O.$$ We see that the points $R$ and $-R$ lie on a vertical line. The result of adding these two points is the point at infinity $\mathscr O$. Graphically that makes sense.

The addition of arbitrary points $P$ and $Q$ is performed by drawing a line between the two points. The third intersection point is the negative of the sum $P + Q$. Formally $$P + Q - R = \mathscr O$$ or simply $$P + Q = R.$$ This process works for curves over real, complex, and finite fields. A finite field is used for cryptography because we always represent numbers as a finite number of bits - integers modulo some large prime number. For reals or complex numbers, we can't get infinite precision, so the translation might not be the same between two different computers.

The formulas for adding points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ with result $R = (x_3, y_3)$ is $$x_3 = \lambda^2 - x_1 - x_2$$ $$y_3 = \lambda(x_1 - x_3) - y_1.$$ The value for $\lambda$ is an interesting problem. As I explain elsewhere, for embedded systems we want a value for $\lambda$ which is the same if $P$ and $Q$ are the same point or different points. This formula is $$\lambda = \frac{x_1^2 + x_1 x_2 + x_2^2 +a}{y_1 + y_2}.$$ 

Care is required to look for a result which is the point at infinity. If $y_1 = -y_2$ but $x_1 \neq x_2$ this formula does not work. When that happens we use $$\lambda = \frac{y_2 - y_1}{x_2 - x_1}.$$The typical code problem is to first check if either $P$ or $Q$ is the point at infinity. If one of them is, just return the other point. Then check if $x_1 = x_2$ and $y_1 = -y_2$ in which case return the point at infinity.

Adding a point to itself multiple times is called multiplication. Rather than actually add the points using the formula $$5P = P + P + P + P + P,$$this is computed using a double and add formula. Starting with $$P$$we then double this to $$2P = P + P.$$Doubling again we have $$4P = 2P + 2P$$and then adding in the original point gives $$5P = 4P + P.$$

The number 5 is 101 in binary. The most significant bit is the first $P$ value, and that's always going to be set. We then double that value, and note that the next bit is clear. We double again and see the last bit is set, so the original point $P$ is added in. So multiplication is computed using a double and add algorithm, but consists of adding two points at every step. It is either the same two points which is a doubling, or the result of a previous doubling and the original point.

Now that we know the basic algebra, let's look at some confusing gotchas. The first important concept is that the finite field is defined by some large prime number. So all the formulas listed above are modulo that prime number. The second important concept is that the number of points on an elliptic curve over a finite field is finite. The algebra of the elliptic curve acts just like a modulo addition. For cryptographic usefulness we want the elliptic curve to have a group of points which is a very large prime number.

As a trivial example, suppose we have a curve which has 26 points. There will be a group of points which when added to themselves will only be 13 of those points. These points are said to have "order" 13. 

Fortunately for cryptographic purposes we can find curves over large prime fields where the order of the curve is a large prime number. The two numbers will not be the same in a cryptographic setting. I think this is one of the most confusing aspects of elliptic curves over finite fields - the field prime is essential for computing equations and the order of points is essential for security. The two are related, and if you want to know more, dive into the details with Elliptic Curve Cryptography for Developers.

In future blogs I'll go into the math of a key exchange routine and a digital signature routine. Multiplication of points is the core of these algorithms. I should also have a blog on security - there is just a lot to cover!

Sign in