ビットガールズ埋蔵金を発掘した話 #Bitcoin

2016年秋期に「採掘！ビットガールズ」というバラエティー番組が放送された。まあ、何というか、色々とひどい番組だった。YouTubeに全話アップロードされている。

この番組では、放送の映像にBitcoinの秘密鍵が隠されていて、発見した人がBitcoinを手に入れられた。最初の1-2話は私も挑戦してみたけれど、番組終了後すぐにBitcoinが取り出されていて、とてもかなわないと諦めていた。が、後半は一気に難易度が上がって、今でもBitcoinが取り出されずに眠っているらしい。ということを最近知ったので、挑戦してみたところ、EP11のBitcoinの発掘に成功した。

ビットガールズ埋蔵金 | 半熟WEBLOG

発掘できたのはこのブログ記事のおかげなので、私も詳細と使ったプログラムを公開する。他の回のBitcoinの探索にも役に立つのではないかと思う。最初はSNS暗号の部分をこねくり回していたが、やはり上手く行かないので、SNS暗号分9文字（の一部）を全探索した。

映像内

5:57 rCiCswFy

7:38 L3JLGe5

10:58 HELHKU

14:07 UKrLZc38iGun

28:06 HULPk4aFFu

BitGirls EP11「採掘！ビットガールズ」#11 - YouTube

この探す作業は、出てくる時刻が分かっていてもつらい。よくこんなの全部見つけたな……。

Bitcoinの鍵のフォーマット

まず、WIF（Wallet import format）形式の秘密鍵KyrKViPURYnLRxjbDVPArACaHZ486k89eePRXkAQ6mGTJPP2faovや、対応するアドレス1DXVHZBsFoVHaxTy1rr7f2mgEZu6hMzfHkがどのような構造になっているのかを説明する。

元になるのは256ビットの乱数で、これが秘密鍵になる（厳密には、ごく一部の大きな整数は秘密鍵としては使えない）。例として、

priv = 4e81fc32b87c857cc280f06138dcc8ef9b546bb26cedf0ebc5c6ea0f68914094

とする。

Bitcoinでの電子署名には楕円曲線暗号が用いられている。パラメタはSecp256k1である。楕円曲線上の点は2個の整数の組で表される。点Gをpriv回足し合わせたものが、秘密鍵privに対応する公開鍵pubとなる。

pub = (pub_x, pub_y) = (79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

点が楕円曲線上にあるという制約から、pub_xの値とpub_yが偶数か奇数かが分かれば、pub_yを求められるため、pub_yが偶数ならば0x02を奇数ならば0x03をpub_xの前に付けたcompressed形式が通常は使われる。compressed形式の公開鍵は、

0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

となる。Bitcoinにはいくつかの送金方法があって、以前は公開鍵の160ビットのハッシュに対して送金する方法が良く使われていた。Bitcoinの160ビットハッシュは、SHA-256とRIPEMD-160をこの順に適用する。この公開鍵のハッシュは、

8965998906e0800616b59925a80f0f45e9a6b37b。

この前に公開鍵のハッシュであることを示す00を付けて、チェックサムとして全体の256ビットハッシュの先頭4バイトを末尾に付け、Base58でエンコードすると、アドレスとなる。Bitcoinで使われている256ビットハッシュはSHA-256を2回掛けたもの。

1DXVHZBsFoVHaxTy1rr7f2mgEZu6hMzfHk

WIF形式の秘密鍵は、対応する公開鍵をcompressed形式で扱っていることを末尾に01を付けて表す。さらに先頭に秘密鍵であることを示す80を付け、公開鍵と同様にチェックサムを付けてBase58エンコードすると、WIF形式の秘密鍵が得られる。

KyrKViPURYnLRxjbDVPArACaHZ486k89eePRXkAQ6mGTJPP2faov

探索

WIF形式の秘密鍵に付いているチェックサムで、秘密鍵が正しいかどうかを確かめることができる。最初は、Wikiを元にSNS暗号の部分を色々と変えて、それぞれでパーツの並び替えを試した。先頭が80で長さが37バイトのデータをBase58で符号化すると、先頭の文字はKかLになる。このことから、映像中の断片のうちL3JLGe5が先頭に来ることが分かる（SNS暗号の先頭の文字がKかLになって先頭にくる可能性もある）。

(n4,a4,a10) 1が2個あるのは何かのミスで、この部分が別の文字なんじゃねーの？
括弧の横の数字に1が多いのが怪しい。数字を無視して3文字からどれかを取ってみる
読む順番が合っているかが分からないので、9文字の並び替えを全部試す
アルファベット26文字から選ぶのではなく、Base58で使用されるものの中からだけ選ぶ
：

全部ダメだったので、SNS暗号部分を全探索することにしたが、$58^9=7,427,658,739,644,928$通りもある。

そこで、SNS暗号の9文字がWIF形式の秘密鍵の最後に来ると賭けることにした。WIF形式の秘密鍵の生成方法を見て分かるように、後半5バイトは秘密鍵には含まれていない。残り4個のパーツの並び替えを含めても16万通り程度を試すだけ済む。この場合はチェックサムで確認することができないので、秘密鍵から公開鍵のハッシュを生成して、アドレス19o9R48VyCCiqSNirCr1SJEWQaTS1BpEEtから取り出しものと一致するかを確認する。

search.py

# coding: utf-8

import hashlib, itertools

parts = [
    "L3JLGe5"
    "rCiCswFy",
    "HELHKU",
    "UKrLZc38iGun",
    "HULPk4aFFu",
]

addr = "19o9R48VyCCiqSNirCr1SJEWQaTS1BpEEt"

def hash256(data):
    data = hashlib.sha256(data).digest()
    data = hashlib.sha256(data).digest()
    return data

def hash160(data):
    data = hashlib.sha256(data).digest()
    h = hashlib.new("ripemd160")
    h.update(data)
    data = h.digest()
    return data

A = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

def base58enc(x):
    n0 = 0
    for i in range(len(x)):
        if x[i]=="\x00":
            n0 += 1
        else:
            break
    x = int(x.encode("hex"), 16)
    y = ""
    while x>0:
        y += A[x%58]
        x /= 58
    return "1"*n0 + y[::-1]

def base58dec(x):
    y = 0
    for t in x:
        y = y*58 + A.index(t)
    y = "%x"%y
    if len(y)%2!=0:
        y = "0"+y
    y = y.decode("hex")
    for i in xrange(len(x)):
        if x[i]!="1":
            break
        y = "\x00"+y
    return y

# アドレスから公開鍵のハッシュ値を取り出す
pub = base58dec(addr)
assert pub[0]=="\x00" and pub[-4:]==hash256(pub[:-4])[:4]
pubhash = pub[1:-4]
assert len(pubhash)==20
print "pub hash:", pubhash.encode("hex")

# 楕円曲線暗号
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
g = (
  0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
  0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
)

def add(a,b):
    if a==(0,0): return b
    if b==(0,0): return a
    x1,y1 = a
    x2,y2 = b
    if x1==x2 and (y1+y2)%p==0:
        return (0,0)
    if a!=b:
        t = (y2-y1)*pow(x2-x1,p-2,p)
    else:
        t = (3*x1*x1)*pow(2*y1,p-2,p)
    x3 = t*t-x1-x2
    y3 = t*(x1-x3)-y1
    return (x3%p,y3%p)


# 探索
snslen = 52-sum(map(len, parts))
# 2個目以降の部品を並び替え
for priv in itertools.permutations(parts[1:]):
    priv = parts[0]+"".join(priv)
    print priv
    # SNS暗号が全て1のときの秘密鍵が秘密鍵の最小値
    pmin = int(base58dec(priv+"1"*snslen)[1:-5].encode("hex"), 16)
    # SNS暗号が全てzのときの秘密鍵が秘密鍵の最大値
    pmax = int(base58dec(priv+"z"*snslen)[1:-5].encode("hex"), 16)

    # 最小の秘密鍵に対する公開鍵を求める
    priv = pmin
    pub = (0, 0)
    gg = g
    for i in range(256):
        if priv>>i&1:
            pub = add(pub, gg)
        gg = add(gg, gg)

    # 秘密鍵の値を増やしながら、公開鍵のハッシュ値が一致するかチェック
    while True:
        hash = hash160("\x02\x03"[pub[1]%2] + ("%064x"%pub[0]).decode("hex"))
        if hash==pubhash:
            # 正しい秘密鍵が見つかったので出力して終了
            priv = "\x80"+("%064x"%priv).decode("hex")+"\x01"
            priv = priv + hash256(priv)[:4]
            priv = base58enc(priv)
            print "Found!"
            print priv
            exit(0)

        if priv==pmax:
            break
        priv += 1
        pub = add(pub, g)

ラッキーなことに、本当にSNS暗号が最後だったので、答えが見つかった。実行時間は10秒ほど。

>python search.py
pub hash: 607b2a2e5b021e8067e93d368264ce4fdb7fb214
L3JLGe5rCiCswFyHELHKUUKrLZc38iGunHULPk4aFFu
L3JLGe5rCiCswFyHELHKUHULPk4aFFuUKrLZc38iGun
L3JLGe5rCiCswFyUKrLZc38iGunHELHKUHULPk4aFFu
L3JLGe5rCiCswFyUKrLZc38iGunHULPk4aFFuHELHKU
Found!
L3JLGe5rCiCswFyUKrLZc38iGunHULPk4aFFuHELHKUunt1Ke33Q

SNS暗号部分はunt1Ke33Qだった。写真の暗号と全く無関係でもなさそうだけど、結局写真の暗号はどう解読するのだろう？

秘密鍵からのBitcoinの取り出し

秘密鍵が分かったら、さっさと自分のアドレスにBitcoinを引き出さないと、誰かに先を越されてしまうかもしれない。本家のBitcoin Coreを使う。その方法も書いておく。他にもっと楽な方法もあるかもしれない。

一番オーソドックスな方法は、デバッグウィンドウを開いて、

importprivkey "L3JLGe5rCiCswFyUKrLZc38iGunHULPk4aFFuHELHKUunt1Ke33Q" "BitGirls EP11"

と打ち込むこと。これで、自分のウォレットでこの秘密鍵に紐付いた残高が見えるようになる。設定 → オプション → ウォレット → コインコントロール機能を有効化する　にチェックを入れると送金時にどのアドレスから送金するかを選べるようになるので、BitGirls EP11から他のアドレスに送れば良い。「残高」に入っている金額をそのままコピペして、「残高から料金を差し引く」にチェックを入れれば、送金手数料を除いた全額が送られる。

ただし、importprivkeyを実行した段階で全ブロックチェーンの再スキャンが走り、これがとても遅い。半日かかる。待っている間に誰かに先を越されるかもしれないので、手動で取引を作成して取り出した。

importprivkey "L3JLGe5rCiCswFyUKrLZc38iGunHULPk4aFFuHELHKUunt1Ke33Q" "BitGirls EP11" false
createrawtransaction "[{\"txid\": \"e0e1177ebc1262d5a21c81aa54b3cd40cd4c35de12d4775db7962af05b152a7a\", \"vout\":0}, {\"txid\": \"4b33cf21d2897d11fe1bab17053a83f0434e907296ea1e1438171bebe60f9fb5\", \"vout\": 1}]" "{\"3DFtVEjgiX917JKwUu4E6CTAtd3yDQWMgS\": 0.15151515}"
signrawtransaction "02000000027a2a155bf02a96b75d77d412de354ccd40cdb354aa811ca2d56212bc7e17e1e00000000000ffffffffb59f0fe6eb1b1738141eea9672904e43f0833a0517ab1bfe117d89d221cf334b0100000000ffffffff019b31e7000000000017a9147ee0e720815c7c036ad5aff3ccbdc0a54c67e9428700000000"
sendrawtransaction "02000000027a2a155bf02a96b75d77d412de354ccd40cdb354aa811ca2d56212bc7e17e1e0000000006b483045022100edb2598417b7f79299a4a05c9864f9e1047923ab8aee68e20bd7c32bc83d223802206ce35b9597a26254116e377b90d8a1be39dc920bf4b358300f841be3743baeaf012103a3894a8b4b571ce0c1c4ac2842791cc6c0c338563a2a238824ac4cd8efa61819ffffffffb59f0fe6eb1b1738141eea9672904e43f0833a0517ab1bfe117d89d221cf334b010000006b483045022100ca5b867721ebf230dde313ebc47e9cd701b7e9140ea8b688250a60c79d587fba02204d3b8738c9760a7a1ad0daa22fb1ee151ed7f6c295913c14916ceb02b120af07012103a3894a8b4b571ce0c1c4ac2842791cc6c0c338563a2a238824ac4cd8efa61819ffffffff019b31e7000000000017a9147ee0e720815c7c036ad5aff3ccbdc0a54c67e9428700000000"

importprivkeyの第3引数にfalseを指定すると、再スキャンが走らない。適当なブロックチェーンエクスプローラーでこのアドレスに送金しているトランザクションを調べて、そのIDと、そのうちの何番目の出力か（vout、0-index）を指定する。入力に指定した金額の合計と出力との差分が送金手数料としてマイナーに支払われるので、多くなりすぎないように注意。createrawtransactionの返り値の文字列をsignrawtransactionに指定すると電子署名をしてくれる。後はそれをsendrawtransactionで送信する。

しばらくBitcoin Coreを起動していなくて、同期がされていなかった。sendrawtransactionは同期が完了していないとネットワークに送信してくれないようなので、実際はBlockchain.infoからネットワークに送信した。

ブロードキャストトランザクション - Blockchain.info