Keys and Bitcoin Addresses

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.

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 \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.

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:

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 P₃ 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
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.

Starting with a private key in the form of a randomly generated number $k$, we multiply it by a predetermined point on the curve called the generator point $G$ to produce another point somewhere else on the curve, which is the corresponding public key $K$. The generator point is specified as part of the secp256k1 standard and is always the same for all keys in bitcoin:

$\begin{equation} {K = k * G} \end{equation}$

where $k$ is the private key, $G$ is the generator point, and $K$ is the resulting public key, a point on the curve. Because the generator point is always the same for all bitcoin users, a private key $k$ multiplied with $G$ will always result in the same public key $K$. The relationship between k and K is fixed, but can only be calculated in one direction, from $k$ to $K$. That's why a bitcoin address (derived from $K$) can be shared with anyone and does not reveal the user's private key ($k$).

Tip: A private key can be converted into a public key, but a public key cannot be converted back into a private key because the math only works one way.

Implementing the elliptic curve multiplication, we take the private key $k$ generated previously and multiply it with the generator point $G$ to find the public key $K$:

K = 1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD * G

Public key $K$ is defined as a point $\text{K = (x,y)}$:

K = (x, y)

where,

x = F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A
y = 07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

To visualize multiplication of a point with an integer, we will use the simpler elliptic curve over real numbers - remember, the math is the same. Our goal is to find the multiple $kG$ of the generator point $G$, which is the same as adding $G$ to itself, $k$ times in a row. In elliptic curves, adding a point to itself is the equivalent of drawing a tangent line on the point and finding where it intersects the curve again, then reflecting that point on the x-axis.

Elliptic curve cryptography: visualizing the multiplication of a point $G$ by an integer $k$ on an elliptic curve shows the process for deriving $G$, $2G$, $4G$, and  $8G$ as a geometric operation on the curve.

Tip: Bitcoin uses the secp256k1 optimized C library to do the elliptic curve math.

Figure 4. Elliptic curve cryptography: visualizing the multiplication of a point $G$ by an integer $k$ on an elliptic curve