This article is all about two ways of generating a Bitcoin address: the hard way using simple math and the easy way using an existing Bitcoin library.

A. The hard way

In this first section I am going to use simple math functions like addition and multiplication to generate a valid Bitcoin address starting from a number, the private key and calculating everything all the way up to public key and final Bitcoin address.

TL;DR;

private key is just a number (like a PIN code) but a very very large one, 10^77 order of magnitude (put this in context of number of atoms in the known, observable universe which is 10^80)
public key is the result of scalar multiplication of private key and a point on Elliptic curve
Bitcoin address is derived from public key by doing SHA256 / RIPE160 hashing and adding network prefix and checksum suffix
we will generate valid Bitcoin address using two hash functions and simple math operations like addition, multiplication
copy / paste Ruby code snippets below or get thegist

Elliptic Curve domain parameters

First of all let's talk about the 6 domain parameters that are defined in secp256k1: p,a,b,G,n,h. Read this Slashdot thread if you want to dive into a little bit of conspiracy theory.

Prime number - p

The migthy prime number itself.

ruby> p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
 => 115792089237316195423570985008687907853269984665640564039457584007908834671663

Elliptic Curve (EC) - a, b

In general elliptic curves are defined as y^2 = x^3 + ax + b equation but since a = 0 and b = 7 it becomes y^2 = x^3 + 7 which is the elliptic curve used in Bitcoin.

Generator point, order and cofactor - G, n and h

These 3 are all related and together they define a cyclic subgroup of elliptic curve where:

G is a point on EC, also called the generator or base point, (x,y) coordinates represented in uncompressed format as a concatenation of x and y prefixed with 04 or in compressed format as x coordinate prefix with 02.
n is the order of subgroup generated by point G; in other words it is the number of points that belong to this subgroup
h is called cofactor and can be calculated as N/n where N is the order of the entire elliptic curve group. In this case cofactor is 1 so the order of the subgroup is equal to the order of the entire elliptic curve.

ruby> G = '0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8'
 => "0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"
ruby> Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
 => 55066263022277343669578718895168534326250603453777594175500187360389116729240
ruby> Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
 => 32670510020758816978083085130507043184471273380659243275938904335757337482424
ruby> n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
ruby> h = 1

0. Private key

We all know that Bitcoin's private key is 256 bits long that has to be an integer between 1 and n, the order of subgroup. Here is my take in binary representation.

ruby> k = 0b1100011100001010010100111101101101010001100000111111101000010011010101001010011111000000100010100011100000001111001111100100011100111011101001110011111111001101001000111111000101100001000000011010111011011001010011010001000000110001100100001011100100101
 => 11253563012059685825953619222107823549092147699031672238385790369351542642469
ruby> k.to_s 16
 => "18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725"

1. Public key

Now, public key is just a scalar multiplication of private key (k) and elliptic curve generator point (G) as P = k * G. The result is another point (x, y) on elliptic curve, we take that x coordinate, prefix it with 02 if y is positive or 03 if y is negative and there it is, the public key in compressed format.

A little bit of math and a few algorithms that we need to use for this calculation. For scalar multiplication you can add G to itself k number of times but this will be very inefficient so we are going to use "double and add" algorithm implemented in ec_multiply that in turn uses ec_add and ec_double, addition and doubling operations on elliptic curves. And last, since division is not defined over finite fields we need to multiply by the multiplicative inverse and use extended_euclidean_algorithm to find the greatest common divisor.

def ec_multiply(m, px, py, pn)
  nx, ny = px, py
  qx, qy = 0, 0
  while m > 0
    qx, qy = ec_add qx, qy, nx, ny, pn if m&1 == 1
    nx, ny = ec_double nx, ny, pn
    m >>= 1
  end
  [qx, qy]
end

def ec_add(ax, ay, bx, by, pn)
  return [ax, ay] if bx == 0 && by == 0
  return [bx, by] if ax == 0 && ay == 0
  return ec_double(ax, ay, pn) if ax == bx && ay == by

  i_bax = inverse(ax - bx, pn)
  slope = ((ay - by) * i_bax) % pn
  x = (slope**2 - ax - bx) % pn
  y = (slope*(ax - x) - ay) % pn
  [x, y]
end

def ec_double(px, py, pn)
  i_2y = inverse(2 * py, pn)
  slope = (3 * px**2 * i_2y) % pn
  x = (slope**2 - 2 * px) % pn
  y = (slope*(px - x) - py) % pn
  [x, y]
end

def inverse(n, p)
  gcd, x, y = extended_euclidean_algorithm(n, p)
  (n * x + p * y) % p == gcd || raise('invalid gcd')
  gcd == 1 || raise('no multiplicative inverse')
  x % p
end

def extended_euclidean_algorithm(a, b)
  s, old_s = 0, 1
  t, old_t = 1, 0
  r, old_r = b, a
  while r != 0
    quotient = old_r / r
    old_r, r = r, old_r - quotient * r
    old_s, s = s, old_s - quotient * s
    old_t, t = t, old_t - quotient * t
  end
  [old_r, old_s, old_t]
end

And here it is, point on elliptic curve and scalar multiplication.

ruby> Px, Py = ec_multiply(k, Gx, Gy, p)
 => [36422191471907241029883925342251831624200921388586025344128047678873736520530, 20277110887056303803699431755396003735040374760118964734768299847012543114150]
ruby> P = "#{Py > 0 ? '02' : '03'}#{Px.to_s(16)}"
 => "0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352"

We can easily check if resulting point is still on elliptic curve.

((Px**3 + 7 - Py**2) % p == 0) || raise('public key point is not on the curve')

2. SHA256 hashing

Standard SHA256 hashing here, I am going to use the implementation provided in Ruby.

ruby> require 'digest'
ruby> sha256 = Digest::SHA256.hexdigest([P].pack('H*'))
 => "0b7c28c9b7290c98d7438e70b3d3f7c848fbd7d1dc194ff83f4f7cc9b1378e98"

3. RIPEMD160 hashing

Same here, nothing new, standard RIPEMD160 hashing, no point reinventing the wheel.

ruby> ripemd160 = Digest::RMD160.hexdigest([sha256].pack('H*'))
 => "f54a5851e9372b87810a8e60cdd2e7cfd80b6e31"

4. Add version byte

Here are a few but see Bitcoin address prefixes for a complete list of all supported prefixes and resulting Base58 encodings:

0x00 - Bitcoin address - result prefix is 1
0x05 - Pay-to-Script-Hash address - result prefix is 3
0x6F - Testnet address - resulting prefix is either m or n

ruby> with_version = "00#{ripemd160}"
 => "00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31"

5.6.7. Calculate checksum

Double SHA256 of previously calculated RIPEMD160 prefixed with version byte:

ruby> checksum = Digest::SHA256.hexdigest(Digest::SHA256.digest([with_version].pack('H*')))[0, 8]
 => "c7f18fe8"

8. Wrap encoding

ruby> wrap_encode = "#{with_version}#{checksum}"
 => "00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31c7f18fe8"

9. Bitcoin address

The Base58 algorithm removes confusing characters like "oOiI" and also "+/" signs to make entire address selectable on double click.

def base58(binary_hash)
  alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
  value = binary_hash.unpack('H*')[0].to_i 16
  output = ''
  while value > 0
    remainder = value % 58
    value /= 58
    output += alphabet[remainder]
  end
  output += alphabet[0] * binary_hash.bytes.find_index{|b| b != 0}
  output.reverse
end

Base58 encoding and the final Bitcoin address:

ruby> base58([wrap_encode].pack('H*'))
 => "1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs"

B. The easy way

All the steps above can be done 'the easy way', as one-liner, using excellent Libbitcoin Explorer tool:

shell> echo 18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725 | bx ec-to-public | bx sha256 | bx ripemd160 | bx wrap-encode | bx base58-encode
1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs

C. Conclusions

And here we are, the exact same Bitcoin address used in Bitcoin address generation tutorial is generated the hard way and the easy way. You can check the address.

References

See the most important references below and feel free to contact me if you need more info on this subject.

The hard way - Bitcoin: private key, public key, address