Tutorial  Address Generation
In this tutorial, we’ll be creating our own Bitcoin addresses in Ruby. The easy way uses the bitcoinruby gem, but this doesn’t teach us much; so we’ll do it ourselves using only basic hashing and an elliptic curve cryptography libraries.
require 'bitcoin'
key = Bitcoin::generate_key
address = Bitcoin::pubkey_to_address(key[1])
# address => 16aqnGNe8GXKajL6Hjj6fGpPBqve8QnNfd
Introduction
Some high level notes:

We have 3 main components:
 Private keys
 Lets you sign new transactions, thereby spending your bitcoins.
 256 random bits
 Public Keys
 Proves that you own bitcoins associated with a certain address
 An elliptic curve public key of the above private key
 Public Address
 Give this to people, so that they can send you bitcoins.
 Hash of the public key
 Private keys

The private key deterministically generates the public key, which deterministically generates the public address (the same private key will always generate the same public key and public address).

These “generation” functions involve oneway functions (once you perform the function, you can’t go back and determine the inputs). It’s practically impossible to get the public key from a public address, or a private key from a public key.

Compressed public keys are now widely used amongst the most popular bitcoin software. The public address of a compressed public key is different than the public address of the uncompressed public key.
Disclaimer: I am not a cryptographer, this is for academic experimentation only.
I’ve used some helper functions for common conversions (hex converters, string converters, base58 encoding). This utility file can be downloaded here.
Private Key:
Step 1. Generate 256 random bits.
You can get this from /dev/urandom, flip a coin 256 times, roll a 16sided dice 64 times, point a webcam at your lavalamp, etc, but here, we’ll just take a hash of a simple phrase. Bear in mind that the elliptic curve is defined over a prime field, so our private key must be less than our chosen prime.
Note: Did I mention that this implementation should only be accepted as academic experimentation? Scammers have already generate addresses based on common words/phrases and steal any bitcoins that get sent to those addresses.
require digest
passphrase = "bitcoins are cool"
priv_key = Digest::SHA256.digest(passphrase)
p = 2**256  2**32  2**9  2**8  2**7  2**6  2**4  1
if priv_key.to_bignum > p
raise "Private key invalid"
end
# priv_key.to_hex => 9e524de478970a9621c0e52890805d5f28e3620892ba6bfa701b026c6ee10a52
Just to be clear, the private key can be exressed in multiple ways:
 Binary: 1001111001010010010011011110010001111000100101110000101010010110001000011100000011100101001010001001000010000000010111010101111100101000111000110110001000001000100100101011101001101011111110100111000000011011000000100110110001101110111000010000101001010010
 Integer: 71610849129504069670807627525562295685404995395280754758942009276479161043538
 Hex: 9e524de478970a9621c0e52890805d5f28e3620892ba6bfa701b026c6ee10a52
These are merely different representations of the same thing, and are all equivalent. As we proceed, we’ll need to jump around different representations depending on what we’re doing. Don’t be alarmed.
We could actually stop here. These 256 random bits ARE your private key, but if you want to use this key with any mainstream bitcoin application, the private key must be in wallet import format (WIF format). To do that:
Step 2. Prepend version, append compression flag
The version number depends on the network.
 Bitcoin = 0x80
 Testnet = 0xEF (Testnet is a “bitcoin playground” where developers can test their applications against a live, bitcoinlike network where coins have no value)
Compression Flag = 0x01
Note: Compression flag is needed to make private keys completely deterministic. As stated above, compressed and uncompressed public keys generate different public addresses. The compression flag signals which of those addresses this private key should generate.
# Note: adding the "b" makes a binary representation of our byte before concatenating, to avoid encoding issues
priv_key_and_version = "\x80".b + priv_key + "\x01".b
# priv_key_and_version.to_hex => 809e524de478970a9621c0e52890805d5f28e3620892ba6bfa701b026c6ee10a5201
Step 3. Add checksum
Checksum is the first 4 bytes of the double sha256 hash of our input. It is used to ensure that every bit is correct; if a single bit is off (mistyped), we will know about it.
def cat_checksum (input)
firstSHA = Digest::SHA256.digest(input)
secondSHA = Digest::SHA256.digest(firstSHA)
input + secondSHA[0,4]
end
priv_key_and_version_and_checksum = cat_checksum(priv_key_and_version)
# priv_key_and_version_and_checksum.to_hex => 809e524de478970a9621c0e52890805d5f28e3620892ba6bfa701b026c6ee10a520140d9c9e7
Step 4. Base58 Encoding
We currently have 38 bytes of data. Using the digits 09. we can express this data as a 92 digit long integer. Using hex (16 possible characters) we express this in 76 characters (as shown above). If we use 58 possible characters, the data can be expressed in only 52 characters. The characters used for Base58 are:

19 (9)

az except ‘l’ (25)

AZ except ‘I’,’O’ (24)
privateWIF = priv_key_and_version_and_checksum.to_base58
# privateWIF => L2XU3tBMCgmAb16LRcrPenccYdUCGKgahkW1oZ4diHuk3dvb6WDL
I’ve included the bitcoinruby base58 encoder here.
Public Key
Step 5. Evaluate:
This is where Elliptic Curve Cryptography comes in. I’ll go into how this all works in a later post, but for now, we’ll simply use this equation.
= 77 digit long integer that we generated in step 1.
G = the “generator point”, a special point on the elliptic curve
 It has x coordinate: 55066263022277343669578718895168534326250603453777594175500187360389116729240
 and y coordinate: 32670510020758816978083085130507043184471273380659243275938904335757337482424
When we multiply the generator point with our private key, we get a new point on the elliptic curve. The x and y cooordinates of this point act as our public key. Because you can’t easily divide points on an elliptic curve, it’s computationally impractical to generate the private key given our knowledge of the public key and the generator point.
Note: Bitcoin uses the “secp256k1” curve, which defines it’s own generator point. Every application which uses the secp256k1 curve uses the same generator point.
curve = ECDSA::Group::Secp256k1
pub_key = curve.generator.multiply_by_scalar(priv_key.to_bignum)
# pub_key.x => 107755497148048731412938604358975700840069163823903109146820905484112739528923
# pub_key.y => 24245920055987556528993042428760322520988269343242132634556250883291122420691
Note: We’re using the “ecdsa gem” because the OpenSSL library is poorly documented and confusing. Explanation here.
Step 6. Compress
Because elliptic curves are symmetric about the x axis; given any x coordinate, there exist only 2 possibilities for the y coordinate. Uncompressed public keys include the full y coordinate (a really big number), but we can save space on the blockchain by indicating which of the 2 possible ycoordinates we use.
If the y coordinate is even, public keys have the form:
 0x02 + x coordinate
If y coordinate is odd:
 0x03 + x coordinate
# pub.x is a Bignum, so we must concatenate our compression byte with the hex representation of pub_key.x
if pub_key_point.y % 2 == 0 # y is even
leader = "\x02"
else
leader = "\x03"
end
pub_key = leader + [pub_key_point.x.to_hex].pack("H*")
# pub_key.to_hex => 03ee3b7337eb52d1e8bd7ee271db9aa43a67750ff483870ab2753d2e13922970db
Why must the 2 y coordinates have unique parity? Because the elliptic curve is over a prime finite field, when we change sign, we flip parity. Illustrated simply, 5 modulus 7 = 5 is odd, but 5 modulus 7 = 2, which is even.
We now have our public key.
Public Address
Step 7. Hash public key
Next, we hash the public key. This compresses our key from 256 bits to 160 bits.
pub_key_sha256 = Digest::SHA256.digest(pub_key_with_lead)
pub_key_hash = Digest::RMD160.digest(pub_key_sha256)
# pub_key_hash.to_hex => 5355f7bb58765e07a20f978b6e2437e99a5e92d3
Step 8. Prepend version, append checksum
The version number depends on the network, and is different than the version used in step 2.
 Bitcoin = 0x00
 Testnet = 0x6F
Checksum is computed the same way it was in step 3.
pub_key_hash_and_version_and_checksum = cat_checksum("\x00" + pub_key_hash)
# pub_key_hash_and_version_and_checksum.to_hex => 005355f7bb58765e07a20f978b6e2437e99a5e92d3f612577e
Step 9. Base58 Encode.
pub_addr = pub_key_hash_and_version_and_checksum.to_base58
# pub_addr => 18be54dbyAth7CR4ymeoQBpzwinLW5Qe1K
We can now share this address with our friends, convert it to a QR code, get it tatooed on our bodies, and watch the bitcoins rush in.
– rf
===
Download the code here.
References/Additional Reading
 Andreas Antonopoulos on Bitcoin Wallet Encryption  youtube.com
 Generating a Bitcoin Address with JavaScript  procbits.com
 Elliptic Curve Crtyptography  wikipedia.org
 Introducing Ruby ECDSA Gem  davidgrayson.com
 Ruby ECDSA  github.com
 Why does Bitcoin use 2 hash functions?  stackexchange.com
 List of Address Prefixes  bitcoin.it
 Technical Background of Bitcoin Addresses