The ultimate bitcoin paper wallet

(updated )

% Remco Bloemen % 2015-08-26

Relevant algorithms

But really only private key generation and ECDSA public key derivations need to be done securely, the rest can be done computer assisted.

Top level strategy

1 Generate a private key 2 Derive the public key 3 Take the SHA-256 hash of the public key 4 Take the RIPEMD-160 hash of the SHA-256 5 Prefix the result with 0x00 6 Base58Check encode the result: 6.1 Take the SHA-256 of (5) 6.2 Take the SHA-356 of (6.1) 6.3 Take the first four bytes of (6.2) 6.4 Concatenate (5) and (6.3) 6.5 Interpret (6.4) as a big-endian number, no leading zeros 6.6 Convert to base-58

But really only 1 and 2 have to be done offline.

Consider the prime

$$ p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 $$

and the elliptic curve equation

$$ y² = x³ + 7 \mod p $$

This is a curve of the form y² = x³ + a x + b with a = 0 and b = 7.

The private key is a 256 bit number modulo p, since p is almost 2^{256} we can just take a random 256 bit number.

Reduction modulo p can be done to good approximation by subtracting p until the result is 256 bits.

2 Derive the public key

Start with the point $G = (x_G, y_G)$ with

$$ \begin{aligned} x_G &= 55 066 263 022 277 343 669 578 718 895 168 534 326 250 603 453 777 594 175 500 187 360 389 116 729 240 \\ y_G &= 32 670 510 020 758 816 978 083 085 130 507 043 184 471 273 380 659 243 275 938 904 335 757 337 482 424 \end{aligned} $$

and compute $k · G$.

We need to multiply this point with the private key. One method is double and add

Q ≔ 0
P₀ ≔ G
for i in [0…255]:
	Pᵢ = 2 · Pᵢ₋₁
	if bit i is set in the private key:
		Q ≔ Q + Pᵢ

The points Pᵢ can be precomputed and provided in a table. What remains is elliptic curve addition. You would need to do on average 128 additions, depending on the private key.

This is 256 pre-computed values. We can go further and pre-compute groups of bits. Say a nibble, then we have 512 pre-computed values, but only 32 additions.

bit grouping b

n = 256 / b table size = (2^b\ -\ 1)\ *\ n\ approx.\ addition\ =\ (1\ -\ 2^ (-b)) * n

Bit grouping Table size Additions

1 256 128 2 384 96 3 602 75 4 960 60 5 1612 50 6 2709 42 7 4699 37 8 8160 32 9 14819 29 10 26598 26 11 49128 24 12 90090 22 13 163820 20 14 311277 19 15 589806 18 16 > 10⁶ 16

Its best to do as few additions as possible, but there is only limited table space. Let’s settle on bytes. This will give a manageable 32 tables of 256 entries each.

Elliptic curve addition

Given two points $P = (x_P, y_P)$ and $Q = (x_Q, y_Q)$ we want to compute $R = P + Q$. Let’s write R out as $(x_R, y_R)$, then:

$$ \begin{aligned} λ &= \frac{y_Q - y_P}{x_Q - x_P} \\ x_R &= λ^2 - x_P - x_Q \\ y_R &= λ\left(x_P - x_R\right) - y_P \end{aligned} $$

The addition and subtraction are laborious, but straightforward in $\mathbb F_p$. Squaring and multiplication can probably use some aid, but the hardest part is likely the division.

The division can be done using an inversion and multiplication.

We need to do about 32 of these operations each of which involves:

Point doubling

Just adding this for completeness, with the pre-computed tables you don’t need this. The chances of accidentally ending up with two identical points are insignificant.

$$ \begin{aligned} λ &= \frac{3 x_P^2 + a}{2 y_P} \\ x_R &= λ^2 - 2 x_P \\ x_R &= λ\left(x_P - x_R\right) - y_P \end{aligned} $$

Field subtraction

Schoolbook.

Field multiplication

Long multiplication.

Field squaring

Multiply by itself.

Field inverse

Taking the inverse modulo p is the same as exponentiation by p - 2. This in turn can be done as a square-and-multiply. A fast method uses first uses the addition chain:

$$ \begin{aligned} \color{red}{1}, \color{red}{2}, 3, 6, 9, 11, \color{red}{22}, 44, 88, 176, 220, \color{red}{223} \end{aligned} $$

And the proceeds with repeated squaring and multiply.

Field inverse using Euclids algorithm

$$ n · m = r \mod p $$

$$ n · m - g · p = r $$

Field using logarithms

Take $g$ a generator of $\mathbb F_p$. Private key is $n$. Public key is $g^n G$. Arithmetic is done in $\mathbb F_{p - 1}$

$$ \begin{aligned} λ &= (y_Q ⊖ y_P) - (x_Q ⊖ x_P) \\ x_R &= 2 λ ⊖ x_P ⊖ x_Q \\ y_R &= λ \left(x_P ⊖ x_R\right) ⊖ y_P \end{aligned} $$

But now ⊖ is a hard operation.

In the one exponentiations need to be done to find the x point of the public key.

Sources

Good overview on methods and strategies!

"Most works publishedin this area have strived for reducingthe cost associated to the double-and-add method by following two main strategies: reducing the computational complexity of point addition and point doubling primitives, and reducing the number of times that the point addition primitive is invoked during the algorithm execution. A significant improvement in performance can be obtained when the point P is known in advance by using precomputation (if memory space permits) and techniques such as the comb method [Hankerson et al. 2004]"

http://cdn.preterhuman.net/texts/cryptography/Hankerson,%20Menezes,%20Vanstone.%20Guide%20to%20elliptic%20curve%20cryptography%20%28Springer,%202004%29%28ISBN%20038795273X%29%28332s%29_CsCr_.pdf

http://eprint.iacr.org/2014/161.pdf

https://github.com/bitcoin/secp256k1

Remco Bloemen
Math & Engineering
https://2π.com