Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

base58check フォーマットとビットコインアドレス

仮想通貨

bitcoinでは色々なところでbase58checkフォーマットが使われています。
base58checkフォーマットを行う関数をb58checkとして実装してみたのが以下です。
ここでは、公開鍵から、メインネットのビットコインアドレスを計算しています。
ビットコインアドレスは、versionに0x00、
ペイロードには、公開鍵をバイト列にしたものにsha256とripemd160を施したものになります。

#!/usr/bin/env python

import base58
import hashlib

# version: 1 bytes
# payload: bytes
def b58check(version, payload):
    d = version + payload
    h1digest = hashlib.sha256(d).digest()
    h2digest = hashlib.sha256(h1digest).digest()
    e = d + h2digest[0:4]
    return base58.b58encode(e)

ba = bytes.fromhex("037c3e90284927ea5a46cb7f4d8c91a5d6defd3827144b28ad2451b524becb9806")
d = hashlib.sha256(ba).digest()
m = hashlib.new('ripemd160')
m.update(d)
ba = m.digest()

r1 = b58check(bytes.fromhex("00"), ba)
print(r1)

b'1MQoLvLZ1DcC7BmKGkbkZWgKH2roYQjZLb'

一つ前の記事で bx コマンドで生成したものと一致していることが分かります。

macOS に bitcoin explorer をインストールする

仮想通貨 
$ brew install bx

秘密鍵を生成しファイルに出力(32バイトhex)

$ bx seed | bx ec-new > private_key
$ cat private_key
4a1bdbb5164f0b096ab56ec74399222e44d13b2a93d5ad7fe8a341bbfa197c46

秘密鍵から公開鍵を計算しファイルに出力(33バイトhex)
先頭が0x03なので、奇数の圧縮公開鍵であることが分かります。

$ cat private_key | bx ec-to-public > public_key
$ cat public_key
037c3e90284927ea5a46cb7f4d8c91a5d6defd3827144b28ad2451b524becb9806

公開鍵からビットコインアドレス形式に変換して出力する

$ cat public_key | bx ec-to-address
1MQoLvLZ1DcC7BmKGkbkZWgKH2roYQjZLb

ripemd160をpythonで試す

仮想通貨

ripemd160は160ビット(=20バイト)の値を返すハッシュ関数です。
pythonでは以下で計算できます。

#!/usr/bin/env python

import hashlib
h = hashlib.new('ripemd160')
h.update(b"abc")
r1 = h.hexdigest()

print(r1)
print("len "+str(len(r1)))

8eb208f7e05d987a9b044a8e98c6b087f15a0bfc
len 40

bitcoinではsha256とripemd160の２つのハッシュ関数が使われます。 sha256は有名なので分かりますが、なぜripemd160というマイナーなハッシュ関数が使われているのでしょうか？

明確な理由は不明ですが、256より少し小さいが、十分な強度で、かつsha256と組み合わせることで攻撃に対して少しでも強度を上げるためのようです。

https://en.wikipedia.org/wiki/RIPEMD

自作したい場合はこの辺りを参考にすればいいようです。

https://homes.esat.kuleuven.be/~bosselae/ripemd/rmd160.txt

またopensslコマンドにも実装されているのでそれで取ることも可能です。

$ openssl list-message-digest-commands
md4
md5
mdc2
rmd160
sha
sha1
$ echo -n "abc" |openssl rmd160
(stdin)= 8eb208f7e05d987a9b044a8e98c6b087f15a0bfc

base58をpythonで試す

仮想通貨

base58は大まかに言ってbase64を改良したものです。
base64は64個の文字とパディングに=(イコール)を使うものです。WEBプログラマなら説明は不要でしょう。

base58はbase64から小文字のl(エル),大文字のI(アイ),大文字のO(オー),0(数字のゼロ),+(プラス),/(スラッシュ)の6つの文字を取り除き,
さらに=(イコール)でパディングするのもやめたものです。

base58エンコードはバイト列をBigEndianの整数にしてから、58進数として、58個の文字でBigEndianで表現したものですが、
桁が少ない場合は先頭を0パディングします。
ただし、16進の場合とはパディングする桁数が違いますので、ご注意ください。

ここでは、pythonのbase58ライブラリを使って計算した場合と、
直に計算したもの２種類で値が一致しているか試しています。

$ pip install base58

#!/usr/bin/env python

# use library
import base58
r1 = base58.b58encode(b'\x00\x01\x02')
print(r1)

# not use library
alphabet = b'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
def b58encode(v):
    # パディング桁数を算出する
    nPad = len(v)
    v = v.lstrip(b'\0')
    nPad -= len(v)
    # バイト配列をBigEndianの数値と見なす
    p = 1
    s = 0
    # 右端から可算していく
    for c in reversed(v):
        s += p * c
        p = p << 8

    #   0 * 256 * 256 + 1 * 256 + 2
    # = 258
    print(s)

    output_ba = b''
    while s:
        # s に商, idx に余りが入る
        s, idx = divmod(s, 58)
        output_ba = alphabet[idx:idx+1] + output_ba

    # 先頭の0x0 の nPad バイト分ある場合は0(base58では1)を nPad バイト分パディングする
    return alphabet[0:1] * nPad + output_ba

r2 = b58encode(b'\x00\x01\x02')
print(r2)

b'15T'
258
b'15T'

参考
Base58Check encoding - Bitcoin Wiki

シュノア署名を楕円曲線secp256k1を使ってpythonで計算してみる

secp256k1

シュノア署名(Schnorr Signature)

シュノア署名を群の言葉で書きます。

秘密鍵と公開鍵の生成

STEP1
有限体 F_p と素数位数lのベースポイント g \in F_pを生成する。
STEP2
乱数 x \in {Z_l}^{*}を秘密鍵とし、 Y = {g} ^ {-x} mod pを公開鍵とする。
STEP3
H()をハッシュ関数とし公開する。

署名

STEP1
メッセージmに対して
乱数 r \in {Z_l}^{*}を生成し、以下を計算する。
u = {g}^{r} \mod p
e = H(u || m)
STEP2
v = r + xe \mod l
を計算する。v=0の場合はrを取り直す。
(e,v)が署名である。

署名検証

STEP1
e, vが {Z_l}^{*}の要素でなければ、NGとする。
STEP2
u' = {g}^{v} {y}^{e} \mod p
e' = H(u'||m) を計算する。
STEP3
e'= e ならOK、異なればNGとする。

pythonで確認する

シュノア署名(Schnorr Signature)を楕円曲線secp256k1を使って計算してみます。
ECDSAのように、ハッシュの取り方など、手続きが決まったRFCはなさそうなので、適当に実装してみました。
ソースと実行結果です。

#!/usr/bin/env python3
#
# secp256k1
# http://www.secg.org/SEC2-Ver-1.0.pdf
#  
import sys
import hashlib

sys.setrecursionlimit(1500)

b = 256
# q is prime
q = 2**256 - 2**32 - 977
# l (order of group) is prime
l = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# no depend q,l
def expmod(v,e,m):
    if e == 0: return 1
    t = expmod(v,e//2,m)**2 % m
    if e & 1: t = (t*v) % m
    return t

# no depend q,l
def inv(x, m):
    return expmod(x,m-2,m)

def double_pt(P):
    x = P[0]
    y = P[1]
    if y == 0: return [0, 0]
    nu = 3*expmod(x,2,q)*inv(2*y,q)
    x3 = expmod(nu,2,q)-2*x
    y3 = nu*(x-x3)-y
    return [x3 % q, y3 % q]

def add_pt(P, Q):
    x1 = P[0]
    y1 = P[1]
    x2 = Q[0]
    y2 = Q[1]
    if x1 == -1 and y1 == -1: return Q
    if x2 == -1 and y2 == -1: return P
    if x1 == x2:
        if (y1 + y2) % q == 0:
            return [-1, -1]
        else:
            return double_pt(P)

    lm = (y1-y2)*inv(x1-x2, q)
    x3 = expmod(lm,2,q)-(x1+x2)
    y3 = lm*(x1-x3)-y1
    return [x3 % q, y3 % q]

def scalarmult(P, e):
    if e == 0: return [-1, -1]
    if e < 0: e = e + l
    Q = scalarmult(P, e//2)
    Q = add_pt(Q, Q)
    if e & 1: Q = add_pt(Q, P)
    return Q

def isoncurve(P):
    x = P[0]
    y = P[1]
    return (y**2 - x**3 - 7) % q == 0

Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = [Gx, Gy]

# 32 byte array to big endian integer
def decodeint(s):
    assert(len(s) == 32)
    return int.from_bytes(s, 'big')

# big endian integer to 32 byte array
def encodeint(y):
  return y.to_bytes(32, byteorder='big')

print("q  = {}".format(q))
print("l  = {}".format(l))

# string to byte array
msg = str("0000").encode('utf-8')

# -- schnorr sign 
x = 5
print("x = {}".format(x))
Y = scalarmult(G, -x)
print("Y  = ({0}, {1})".format(Y[0], Y[1]))
r = 2
print("r  = {}".format(r))
U = scalarmult(G, r) 
u = U[0]

# int to byte array
u_ba = encodeint(u)
e_digest = hashlib.sha256(u_ba + msg).digest()
e = decodeint(e_digest)
v = (r + x * e) % l

print("e  = {}".format(e))
print("v  = {}".format(v))

# -- verify
UD = add_pt(scalarmult(G, v), scalarmult(Y, e))
ud = UD[0] % l
ud_ba = encodeint(ud)

ed_digest = hashlib.sha256(ud_ba + msg).digest()
ed = decodeint(ed_digest)
print("ed = {}".format(ed))

print("result {}".format(e == ed))

q  = 115792089237316195423570985008687907853269984665640564039457584007908834671663
l  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
x = 5
Y  = (21505829891763648114329055987619236494102133314575206970830385799158076338148, 17788380558553574189887744505607047724243097342766425233927699087598871091545)
r  = 2
e  = 5488091919336943623366459380250002739393051770454284273229695939919413862528
v  = 27440459596684718116832296901250013696965258852271421366148479699597069312642
ed = 5488091919336943623366459380250002739393051770454284273229695939919413862528
result True

eとedが一致しているのが分かります。

余談ですが、python3のバイト列とintを相互変換する組込関数めちゃ便利ですね。

参考:

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで