Understand cryptocurrency (Bitcoin, Monacoin) protocols: public and private keys

Overview

In recent years, cryptocurrencies such as Bitcoin and Litecoin have become a hot topic (for better or worse). Cryptocurrencies are currently extremely chaotic, and hundreds of derivative currencies (Alt currencies) have been crowded so far, but here in Japan as well, a derivative currency from Japan called "Monacoin" has recently been born, and it is secret in the corner of 2ch. Is showing excitement. This author is the one who runs the so-called cryptocurrency version of gumroad's web service called "Monapay".

Previously, on a whim, I proposed the following type of game and pasted it on 2ch.

I would like to play a game with prize money for promotion + killing time. The content is "Steal my monacoin"

M9WJPA8npJQEwcxXwvzKHwWz5msQfEKzf5 I have just deposited 10MONA to this address. You can check with Abe whether the deposit was actually made. And here is the raw private key encoded in Base64. 0fHys0+Iy89GnEUfA0ZCJ652Tf8409Yor4ekLdazlXE= A long time ago, when I copied a Bitcoin gift card on TV, it was stolen by Sokko. The same thing is happening. By exposing the private key on the Internet, anyone can get the 10MONA deposited at this address.

The game is super easy. Please use this private key as soon as possible to steal 10MONA from this address. Can you really be a hacker? ?? Do what the TV presenter did! (If it is a TV, it is stolen by haste, but if it is not stolen this time, 10 MONA will be added every day)

10MONA refers to the Monacoin currency, which is a cryptocurrency. The simple reason for proposing this "theft problem" is that I was wondering how many people can actually solve this problem. I thought that it would take more than a day as expected, but the actual result was solved for the first time 2 hours after pasting, and Finally, a total of 3 people succeeded in capturing it. I did it. 10MONA was cheap at about 5,60 yen when converted to the current Japanese yen, but I was glad that there were people who challenged and solved this problem (Thanks to those who cooperated). There is).

In order to solve this problem, it is necessary to convert the private key to a format called Wallet Import Format and have the Monacoin client read it, but for that purpose, not only knowledge about cryptocurrencies, but also [Monacoin source code] You need to read (https://github.com/monacoinproject/monacoin). The purpose of this article is to provide a commentary on this issue and at the same time to deepen your knowledge of Bitcoin and the Monacoin protocol. Currently, there are almost no technical Japanese articles on cryptocurrencies, so I think it will be useful to some extent.

In addition, this article also includes Python code for explanation. And finally, another theft game is posted as an exercise. The prize money is small, but please forgive me because I have almost no money on hand.

Donations are always accepted :) MKrJpLy8Dg8mATKdH5zWCYiUVYQGvVW5Sx

Electronic signature

As you know, many cryptocurrencies, including Bitcoin and Monacoin, have all transaction history (Transactions) in the "[Blockchain]( It consists of a distributed database consisting of "https://en.bitcoin.it/wiki/Block_chain)". The user makes an actual transaction by writing the details of the transaction he / she wants to execute in this huge database. In other words, remittance in cryptocurrency is equivalent to writing a transaction with the content of "sending the amount of money in your (A) account to B" to the blockchain.

The problem that arises here is that you need to prove that "Is the person who instructed the transfer from A's account really A himself?" To prove this, Monacoin uses a public key cryptographic algorithm to verify that the user who directed the transaction to write is really the owner of the account. Let's take a closer look:

relationship.png

Public-key cryptography consists of two key pairs: * private key * and * public key *. In the case of Monacoin, the private key is a 256-bit sequence and the public key is a 512-bit sequence. The private key is used to prove that the person who directed the transaction to write is A. Think of something like a seal or signature in the real world. By signing the transaction with the private key, you can prove that the person who directed the transaction to write is A. This information should never be leaked to the outside, as anyone can spoof A and direct remittances from A's account if the private key is leaked online.

The private key is generally expressed in hexadecimal, but as it is, it has 64 characters, so it is a little redundant to carry. You'll also want a checksum to indicate if this is really a string representing Monacoin's private key. For this reason, Monacoin also provides a format called * Wallet Import Format (WIF) *, which is a more concise representation of the private key. The word "private key" in Monacoin generally refers to WIF rather than the raw private key. Since the raw private key and WIF represent the same information, you can get the raw private key from WIF and vice versa.

Next, let's move on to the explanation of public keys. The public key is the public information entered in the blockchain and is used to verify the signature with the private key. All users connected to the Monacoin network verify that the writer of the transaction is A by comparing this public key with the digital signature. Note that you can generate a public key from a private key, but not vice versa.

Since the size of the public key is 512 bits, it is a little too huge to paste it on a blog or bulletin board as it is. To address this issue, Monacoin offers a shorter public key representation. This is the commonly known "Monacoin wallet address". Keep in mind that while it is easy to generate a wallet address from a public key, you cannot generate a public key from a wallet address.

Conversion method

Now let's see how to generate a specific private and public key. Generating a Monacoin address takes three major steps: (1) Generating a private key (2) Generating a public key from a private key (3) Generating an address from a public key. In addition, the operation mentioned in the above figure (A) Generating WIF from private key (B) Generating private key from WIF is also important, so we will explain how to do it.

(1) Generate a private key

There is no particular rule for being a private key, and any 256bit key will do. Generally, we use true random numbers obtained from random number generators such as / dev / random /. For security reasons, it is desirable to avoid using pseudo-random numbers that are not cryptographically secure, such as Mersenne Twister.

def make_private_key():
    return os.urandom(32)  # 32 = 256/8

The result of the execution is as follows:

>>> private_key = make_private_key()
>>> print(private_key.encode("hex_codec"))
3954e0c9a3ce58a8dca793e214232e569ff0cb9da79689ca56d0af614227d540

(2) Generate a public key from the private key

Monacoin uses an algorithm called * [Elliptic Curve DSA](http://ja.wikipedia.org/wiki/Elliptic Curve DSA) * for the digital signature algorithm (parameter is Secp256k1). It's difficult to understand the detailed mechanism, but if you just want to use it, you only have to hit a standard library such as OpenSSL, so it's best to use it.

This time we will use a Python library called [ʻecdsa](https://pypi.python.org/pypi/ecdsa). I think it's easy to install using pip`.

$ pip install ecdsa

The Python code that generates the public key from the private key looks like this:

def private_to_public_key(private_key):
    signing_key = ecdsa.SigningKey.from_string(
        private_key, curve=ecdsa.SECP256k1)
    verifying_key = signing_key.verifying_key
    return verifying_key.to_string()

The result of the execution is as follows:

>>> public_key = private_to_public_key(private_key)
>>> print(public_key.encode("hex_codec"))
47f272a8dad703f809489dfc9ea3606e206ba6a16ecbde314186a03b68326284eaecd034af5300bb6991ac5897c8163ed67894205bc1b7dd5dac8080dba2fe69

(3) Generate an address from the public key

This process is a bit more complicated than it used to be, but it's not difficult, so let's break it down one by one. First of all, add \ x04 to the beginning of the given public key (for unknown reasons). Please note that this prefix is not a unique value for Monacoin, but a common value for Bitcoin and Litecoin.

pk_with_prefix = "\x04" + public_key

Next, apply two one-way functions sha256 and ripemd160 to this public key to convert it to a 160-bit hash.

ripemd160 = hashlib.new('ripemd160')
ripemd160.update(hashlib.sha256(pk_with_prefix).digest())
hash160 = ripemd160.digest()

Then prefix this hash with \ x32. This will make Monacoin's wallet address start with M, making it easier to identify the type of wallet address.

vhash160 = "\x32" + hash160  # monacoin addresses start with M

The value of the prefix depends on the cryptocurrency. For example, Bitcoin takes the value \ x00 and Litecoin takes the value \ x30. If you want to know the prefix of other derived currencies, please refer to PUBKEY_ADDRESS in src / base58.h. For example, for Monacoin, the source code for src / base58.h looks like this:

src/base58.h


class CBitcoinAddress : public CBase58Data
{
public:
    enum
    {
        PUBKEY_ADDRESS = 50, // Monacoin addresses start with M or N
        SCRIPT_ADDRESS = 5,
        PUBKEY_ADDRESS_TEST = 111,
        SCRIPT_ADDRESS_TEST = 196,
    };
...

The source code says start with M or N, but with List of address prefixes, \ x32 always points to M. , Probably the source code is incorrect.

Next, after the hash of the (8 + 160) bits with this \ x32, add a checksum used to verify the address. Many cryptocurrencies treat the value obtained by cutting out 32 bits from the beginning of the sequence to which the hash function sha256 is applied twice as a checksum.

def _make_checksum_for_address(data):
    code = hashlib.sha256(hashlib.sha256(data).digest()).digest()
    return code[:4]

Finally, the value of the hash of (8 + 160) bits with a checksum, excluding confusing characters such as Base58 (0, O), It is encoded in a coding format that expresses data with 58 types of characters.

checksum = _make_checksum_for_address(vhash160)
raw_address = vhash160 + checksum
return base58_encode(raw_address)

It's been long, but the final Python code looks like this:

def _make_checksum_for_address(data):
    code = hashlib.sha256(hashlib.sha256(data).digest()).digest()
    return code[:4]

def public_key_to_address(public_key):
    pk_with_prefix = "\x04" + public_key
    ripemd160 = hashlib.new('ripemd160')
    ripemd160.update(hashlib.sha256(pk_with_prefix).digest())
    hash160 = ripemd160.digest()
    vhash160 = "\x32" + hash160  # monacoin addresses start with M
    checksum = _make_checksum_for_address(vhash160)
    raw_address = vhash160 + checksum
    return base58_encode(raw_address)

The result of the execution is as follows:

>>> public_key_to_address(public_key)
MB3D45ngvaWRcACUmAFUf6fzcdXR8bVM6k

(A) Generate WIF from private key

The following describes how to generate WIF from the private key. Follow the steps below to generate WIF. First of all, Monacoin prefixes the private key with the prefix \ xb2. The value of the prefix depends on the cryptocurrency. For example, Bitcoin takes the value \ x80 and Litecoin takes the value \ xb0.

The specific value of the prefix depends on the PUBKEY_ADDRESS in src / base58.h. Specifically, the value of PUBKEY_ADDRESS plus 128 is the value of the prefix PRIVKEY_ADDRESS:

src/base58.h


class CBitcoinSecret : public CBase58Data
{
public:
    enum
    {
        PRIVKEY_ADDRESS = CBitcoinAddress::PUBKEY_ADDRESS + 128,
        PRIVKEY_ADDRESS_TEST = CBitcoinAddress::PUBKEY_ADDRESS_TEST + 128,
    };
...

Then, after the value of the private key prefixed with this prefix, add a checksum to verify the private key. Many cryptocurrencies treat the value obtained by cutting out 32 bits from the beginning of the sequence to which the hash function sha256 is applied twice as a checksum.

def _make_checksum_for_wif(code):
    return hashlib.sha256(
        hashlib.sha256(code).digest()).digest()[:4]

Finally, the value with the checksum is encoded in Base58. The final Python code looks like this:

def _make_checksum_for_wif(code):
    return hashlib.sha256(
        hashlib.sha256(code).digest()).digest()[:4]


def private_key_to_wif(private_key):
    assert(len(private_key) == 32)
    checksum = _make_checksum_for_wif("\xb2" + private_key)
    return base58_encode("\xb2" + private_key + checksum)

The result of the execution is as follows:

>>> private_key_to_wif(private_key)
6ySkrpLpwm6gKsWo2aS6EL1SZxidZNdJkKqsKRNjXzv9WSrpHjR

(B) Generate a private key from WIF

Similarly, for WIF to generate a private key, just reverse the steps above. It's verbose to explain this step again, so it's enough to look at the Python code below:

def wif_to_private_key(wif):
    code = base58_decode(wif)
    prefix, private_key, checksum = code[0], code[1:33], code[33:]
    checksum_from_hex = _make_checksum_for_wif(prefix + private_key)
    assert(checksum == checksum_from_hex)
    return private_key

Exercises

With the explanation so far, it is now possible to convert the private key to WIF format. All you have to do now is use this WIF format to get your private key into your Monacoin client. Please refer to the method of Bitcoin wiki for the specific import method. Be sure to make a backup of wallet.dat.

Finally, here is a brief exercise as a review of the past. The first person to solve it has the privilege of stealing the prize :)

Monacoin wallet address MPKWCip9CLawFKwwMBDTTp2ZWJcrkDf7rX Private key leaked by computer virus 9a833fd68f30459bd6f7b718818668c5c6d20b5a2b491558cea08be63937f847 Turned out to be. Use this private key to steal the full amount stored at the above address.

Recommended Posts

Understand cryptocurrency (Bitcoin, Monacoin) protocols: public and private keys
Create private and public keys using ssh-keygen (difference between Windows 10 and Linux)