BIP32

2018-04-13

BIP32: Hierarchical Deterministic Wallets https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

Bitcoin 等で使われるアドレス=鍵ペアを多数扱いたい場合に、一個一個ランダムに生成すると全部きちんと管理しないとならない。 シード値とパラメータから、決定的な計算によって鍵を生成できる仕組みを用意すれば、

KeyX = f(Seed, X)

そのシード値とパラメータを扱うことで無数の鍵を管理することができて楽。

さらに諸々の工夫を加えて、鍵派生アルゴリズムを仕様化したものが BIP32.

Deterministic というのは、パラメータを与えれば鍵データが決定的に計算できるという意味。 Hierarchical というのは、そのパラメータが階層構造を成しているという意味。 Wallet というのは、この鍵群はウォレットへの利用を想定しているということであろう。

鍵派生アルゴリズム

準備

対称とする鍵は Bitcoin の CHECKSIG, つまり secp256k1 の公開鍵/秘密鍵ペア。 http://www.secg.org/sec2-v2.pdf

BIP32 の派生演算では、secp256k1 の鍵長 256bit に加えて、さらに chain code と呼ばれる 256bit の値を用意する。 鍵と chain code を合わせて拡張鍵(extended keys)と呼び、鍵 k と chain code c から成る拡張鍵を (k,c) と記述する。 鍵ペア k,K に対する拡張鍵は同一の chain code を用いる。

鍵ペア k,K
拡張秘密鍵 (k, c)
拡張公開鍵 (K, c)

拡張鍵から新たな拡張鍵を導出する演算 CKD(Child Key Derivation) を定義する。 CKD の入力は、派生元の拡張鍵と32bit整数のパラメータになる。 (k,c) とパラメータ i から生成した子拡張鍵を (ki,ci) とすると、

CKD((k,c), i) -> (ki, ci)

と記述できる。

CKD は、拡張秘密鍵から拡張秘密鍵を生成する演算 CKDpri と、拡張公開鍵から拡張公開鍵を生成する演算 CKDpub に分ける。 CKD で生成される子拡張鍵は、拡張鍵の制約を満たす必要がある。 つまり、

CKDpri((k,c), i) -> (ki,ci)
CKDpub((K,c), i) -> (Ki,Ci)

に対して、

Ki = point(ki)   //pointは楕円曲線の秘密鍵から公開鍵を計算する関数
ci == Ci

という関係が成り立つように CKD を定義する。

normal と hardened

鍵派生関数は 32bit整数のパラメータを受けとる。 このパラメータを半分にわけ、CKD の定義を二種類に分かれる。

0 から 2^31-1 までのパラメータで導出された子を normal child key, 2^31 から 2^32-1 で導出された子を hardened child key という。

normal child key

公開鍵 K の SEC1 圧縮表現 33byte に、パラメータ i の 4byte を連結したバイト列に対して、c を鍵として HMAC-SHA512 を取ったバイト列を I とする。

I = HMAC-SHA512(Key = c, Data = K || i)

I は HMAC-SHA512 の出力なので 512bit になる。 これを上位(左=IL)下位(右=IR)の 256bit ずつに分ける。

IL をビッグエンディアン整数として解釈した値(parse256)と k を足した値を、secp256k1 の定数 n (秘密鍵の最大値)で割った余りを ki とする。 ci は IR の値そのまま。

ki = parse256(IL) + k (mod n)
ci = IR

ここで、parse256(IL) >= n または ki = 0 となる場合、この CDKpri は無効とし、アプリケーション側でまた別の i を用いる。 // n は上位128bit が 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE で、256bit整数の最大値に近い

Ki は公開鍵であるから、秘密鍵 ki に point 関数を適用した値である。

  Ki = point(ki)
     = point( parse256(IL) + k  (mod n) )

楕円曲線暗号の公開鍵導出演算は楕円曲線のスカラー倍算であり、これは加法に対して準同型なので、

  Ki = point( parse256(IL) ) + point(k)
     = point( parse256(IL) ) + K

これを Ki の導出式とする。

まとめると、

IL || IR == HMAC-SHA512(Key = c, Data = K || i)
ki = parse256(IL) + k (mod n)
Ki = point( parse256(IL) ) + K
ci = IR

子拡張秘密鍵 (ki,ci) の導出

1. ki の計算には、IL,k が、ci の計算には IR が必要。
2. IL,IR を計算するためには K,c,i が必要。
3. K は k から計算可能。

よって、(ki,ci) の計算には k,c,i が必要。

親拡張秘密鍵は、k,c を知っている。i は外部から与えらえる。よって、親拡張秘密鍵から、子拡張秘密鍵を計算可能。

親拡張公開鍵は、k を知らない。よって、親拡張公開鍵から、子拡張秘密鍵を計算することはできない。

子拡張公開鍵 (Ki,ci) の導出

1. Ki の計算には、IL,K が、ci の計算には IR が必要。
2. IL,IR を計算するためには K,c,i が必要。

よって、(Ki,ci) の計算には K,c,i が必要。

親拡張秘密鍵は、k,c を知っている。i は外部から与えらえる。K は k から計算可能。よって、親拡張秘密鍵から、子拡張公開鍵を計算可能。

また、子拡張秘密鍵から子拡張公開鍵は計算可能なので、親拡張秘密鍵から子拡張秘密鍵を計算し、そこから子拡張公開鍵を計算することもできる。

CKDpub((K,c),i) = point(CKDpri((k,c),i))

親拡張公開鍵は、K,c を知っている。i は外部から与えられる。よって、親拡張公開鍵から、子拡張公開鍵を計算することができる。

まとめると、

親/子	private	public
private	可	可
public	不可	可

セキュリティ上の注意

ところで、子の秘密鍵導出の式

ki = parse256(IL) + k (mod n)

には親の秘密鍵k が使われている。

この演算は逆算が容易なので、IL と ki が分かると k が計算できてしまう。 また、IL は親の拡張公開鍵 (K,c) から計算できる。

つまり、親の拡張公開鍵(K,c)と子の秘密鍵ki から、親の秘密鍵k が計算できるということになる。 normal child key を使う際は、親の拡張公開鍵を公開してはならない。 たとえば、公開鍵 K を公開する際に、拡張公開鍵全体を公開しないように留意する。

hardened child key

0x00 の後に、秘密鍵 k の 32byte とパラメータ i の 4byte を連結したバイト列に対して、c を鍵として HMAC-SHA512 を取ったバイト列を I, I の上位下位半分をそれぞれ IL, IR とする。

IL || IR = HMAC-SHA512(Key = c, Data = 0x00 || k || i)

子の拡張秘密鍵を、

ki = parse256(IL) + k (mod n)
ci = IR

と定義する。 子の公開鍵は、子の秘密鍵に point 関数を適用したものである:

Ki = point(ki)
   = point(parse256(IL) + k)
   = point(parse256(IL)) + point(k)
   = point(parse256(IL)) + K

子拡張秘密鍵 (ki,ci) の導出

1. ki の計算には、IL,k が、ci の計算には IR が必要。
2. IL,IR を計算するためには k,c,i が必要。

よって、(ki,ci) の計算には k,c,i が必要。

親拡張秘密鍵は、k,c を知っている。i は外部から与えらえる。よって、親拡張秘密鍵から、子拡張秘密鍵を計算可能。

親拡張公開鍵は、k を知らない。よって、親拡張公開鍵から、子拡張秘密鍵を計算することはできない。

子拡張公開鍵 (Ki,ci) の導出

1. Ki の計算には、IL,K が、ci の計算には IR が必要。
2. IL,IR を計算するためには k,c,i が必要。
3. K は k から計算可能

よって、(Ki,ci) の計算には k,c,i が必要。

親拡張秘密鍵は、k,c を知っている。i は外部から与えらえる。 よって、親拡張秘密鍵から、子拡張公開鍵を計算可能。

また、子拡張秘密鍵から子拡張公開鍵は計算可能なので、親拡張秘密鍵から子拡張秘密鍵を計算し、そこから子拡張公開鍵を計算することもできる。

CKDpub((K,c),i) = point(CKDpri((k,c),i))

親拡張公開鍵は、k を知らない。 よって、親拡張公開鍵から、子拡張公開鍵を計算することはできない。

まとめると、

親/子	private	public
private	可	可
public	不可	不可

normal key derivation とは、拡張公開鍵から子拡張公開鍵を計算できない点が異なる。