Keys and Bitcoin Addresses

One of the ways that Bitcoin uses cryptographic keys is in generating Bitcoin addresses, which are often derived from public keys. This chapter covers public keys and how they are used to generate addresses.

Elliptic Curve Cryptography Explained

Elliptic curve cryptography is a type of asymmetric or public key cryptography based on the discrete logarithm problem as expressed by addition and multiplication on the points of an elliptic curve.

An elliptic curve is an example of an elliptic curve, similar to that used by bitcoin.

Figure 2. An elliptic curve
 

Bitcoin uses a specific elliptic curve and set of mathematical constants, as defined in a standard called secp256k1, established by the National Institute of Standards and Technology (NIST). The secp256k1 curve is defined by the following function, which produces an elliptic curve:

\begin{equation} {y^2 = (x^3 + 7)}~\text{over}~(\mathbb{F}_p) \end{equation}

or

\begin{equation} {y^2 \mod p = (x^3 + 7) \mod p} \end{equation}

The mod p (modulo prime number p) indicates that this curve is over a finite field of prime order p, also written as  \mathbb{F}_p , where p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1, a very large prime number.

Because this curve is defined over a finite field of prime order instead of over the real numbers, it looks like a pattern of dots scattered in two dimensions, which makes it difficult to visualize. However, the math is identical to that of an elliptic curve over real numbers. As an example, Elliptic curve cryptography: visualizing an elliptic curve over F(p), with p=17 shows the same elliptic curve over a much smaller finite field of prime order 17, showing a pattern of dots on a grid. The secp256k1 bitcoin elliptic curve can be thought of as a much more complex pattern of dots on a unfathomably large grid.

Figure 3. Elliptic curve cryptography: visualizing an elliptic curve over F(p), with p=17

 

So, for example, the following is a point P with coordinates (x,y) that is a point on the secp256k1 curve:

P = (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

Using Python to confirm that this point is on the elliptic curve shows how you can check this yourself using Python:

Example 1. Using Python to confirm that this point is on the elliptic curve
Python 3.4.0 (default, Mar 30 2014, 19:23:13)
[GCC 4.2.1 Compatible Apple LLVM 5.1 (clang-503.0.38)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
>>> y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
>>> (x ** 3 + 7 - y**2) % p
0

In elliptic curve math, there is a point called the "point at infinity," which roughly corresponds to the role of zero in addition. On computers, it's sometimes represented by x = y = 0 (which doesn't satisfy the elliptic curve equation, but it's an easy separate case that can be checked).

There is also a + operator, called "addition," which has some properties similar to the traditional addition of real numbers that gradeschool children learn. Given two points P_{1} and P_{2} on the elliptic curve, there is a third point P_{3}=P_{1}+P_{2}, also on the elliptic curve.

Geometrically, this third point P3 is calculated by drawing a line between P_{1} and P_{2}. This line will intersect the elliptic curve in exactly one additional place. Call this point P_{3} = (x, y). Then reflect in the x-axis to get P_{3} = (x, \, –y).

There are a couple of special cases that explain the need for the "point at infinity".

If P_{1} and P_{2} are the same point, the line "between" P_{1} and P_{2} should extend to be the tangent on the curve at this point P_{1}. This tangent will intersect the curve in exactly one new point. You can use techniques from calculus to determine the slope of the tangent line. These techniques curiously work, even though we are restricting our interest to points on the curve with two integer coordinates!

In some cases (i.e., if P_{1} and P_{2} have the same x values but different y values), the line between P_{1} and P_{2} will be exactly vertical, in which case P_{3} = \text{"point at infinity"}.

If P_{1} is the "point at infinity," then P_{1} + P_{12} = P_{2}. Similarly, if P_{2} is the point at infinity, then P_{1} + P_{2} = P_{1}. This shows how the point at infinity plays the role of zero.

It turns out that + is associative, which means that (A + B) + C = A + (B + C). That means we can write A + B + C without parentheses and without ambiguity.

Now that we have defined addition, we can define multiplication in the standard way that extends addition. For a point P on the elliptic curve, if \text{k} is a whole number, then \mathrm{kP}=\mathrm{P}+\mathrm{P}+\mathrm{P}+\ldots+\mathrm{P}(\mathrm{k} times ). Note that k is sometimes confusingly called an "exponent" in this case.


Source: Andreas M. Antonopoulos, https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc
Creative Commons License This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.