技術者向けビットコイン講座 第1回 楕円曲線を自分の手で扱う

Jonathan Underwood
2015-03-01
(
Sun
)
series_banner

はじめに

どうも初めまして、ビットバンク社にて技術顧問を勤めさせていただいておりますジョナサン・アンダーウッドと申します。宜しくお願いします。日本語ネイティブじゃないので、理解可能な文章作り頑張ります。

今日のお話しはビットコインの背骨とも言える暗号アルゴリズム、Elliptic Curve Cryptography (ECC) について説明をすると同時に、実際に楕円曲線の計算ができるパイソンのスクリプトを一緒に書いていきます。(次回からは、その背骨に色々と積み上げて行って、手作り (ビットコインのライブラリ無し) でビットコインのウォレットが作れるくらいまでやります。)

(注意:暗号アルゴリズムの計算はテストがしにくく、動いているように見えても、稀なケースにしか現れないバグは山ほどあります。よって、本気のビジネスや本物のビットコインを扱うソフトの開発に関わった場合、当講座で作る暗号アルゴリズムに関わるコードを使わず、世界中のシステムに試され、叩き固められたライブラリを使うことをオススメします。このコードを使用したことから発生した如何なる責任は負いかねます。予めご了承下さい。)

楕円曲線とはどういう仕組み?

loop_EC

secp256k1_EC

楕円曲線とは、上記のイメージのような (必ずしも楕円である必要が無い) グラフです。

必ず下記のようなフォーマットに従います。

ECC_equation

abを変えても、それで出来上がる曲線は必ず下記のことが言えます。

  • 曲線上に存在する2つの点を通過する直線は必ず3つ目の点を通過する。
  • 曲線上に存在する1つの点を通過し、接線となる場合、その接線は必ず2つ目の点を通過する。

(上記の線は唯一【縦線】を除きます。)

加法

この性質を活かして、擬似的な足し算を定義することができます。- 点Aと点Bを足し合わせて出来る点はその2つの点をつなぐ直線が通過する3つ目の点の反転

A + B = CA + A = 2A

EC_Add_ex
EC_Double_ex

これを計算するには上記の画像左と右では異なります。

P + Q = R の計算を (xp, yp) + (xq, yq) = (xr, yr) とそれぞれの点の座標で計算します。※ダブルの場合は P + P = R

足し算 (Point Addition)ダブル計算 (Point Doubling)

EC_Add_equation
EC_Double_equation

大切なことは、通常の足し算と同じようにA + (B + C) = (A + B) + CA + B = B + A上記の二つの常識が楕円曲線の擬似的な足し算でも通じます。

加法 - ソース

これをパイソンで書くと下記のようになります。

[code language="python"]# SECP256k1 curve a and p valuecA = 0cP = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

def inv_mod(a, p = cP): lim, him = 1, 0 low, high = a % p, p while low > 1: ratio = high / low nm = him - lim * ratio new = high - low * ratio him = lim high = low lim = nm low = new return lim % p

def EC_add(P, Q, Pcur = cP): Lamda = ((Q[1] - P[1]) * inv_mod(Q[0] - P[0])) % Pcur x = ((Lamda ** 2) - P[0] - Q[0]) % Pcur y = (Lamda * (P[0] - x) - P[1]) % Pcur return (x, y)

def EC_double(P, Acur = cA, Pcur = cP): Lamda = ((3 * (P[0] ** 2) + Acur) * inv_mod(2 * P[1])) % Pcur x = (Lamda ** 2 - 2 * P[0]) % Pcur y = (Lamda * (P[0] - x) - P[1]) % Pcur return (x, y)[/code]

このコードを含め、このシリーズで使われる定数はすべてビットコインが使用する「SECP256k1」という曲線をベースに使っているので、念頭に入れていただければ幸いです。(他の曲線と他の定数は存在します。)

cPとなっているものは大きな(256ビット)素数です。(方程式では「mod p」のpの部分です。)これを用いて楕円曲線が存在する平面の範囲を限定していて、一つの端を越えたら、向こう側の端が巻き戻って続きます。イメージは下記のようなものです。(p = 10 の場合)

secp256k1_EC_mod10

なお、合同算術を用いて「割り算」を行う場合、代わりに「拡張ユークリッド互除法」を使わなければいけませんので、inv_modも入れています。

乗法

P + P + P + P = 4P のようにPを複数回足し合わせると擬似的な掛け算もできます。これによって、公開鍵暗号に応用できる部分が見えてきます。

足し算はできても、引き算ができません。更に、合同算術によって限られた平面で大きな乱数と掛け算をすると、最終的にたどり着いた点を見るだけで何回足し合わされたか分かりません。

先ず、公開鍵を生成するために、起点となる点を定義します。これをGenerator PointのGで表します。

このGを自分に何回足し合わせたかの回数のことを秘密鍵とし、それで出来た点のことを公開鍵とします。

計算にDouble and Add手法を使います。下記の方程式にあるGを全て簡単な整数で置き換えてみてください。(例えば10)

(例:22 x G ⇒ 10110 (22の2進法))

double_add

では、楕円曲線の掛け算をパイソンで書くとどうなるか:

乗法 - ソース

[code language="python"]cN = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141cB = 7

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424Gpt = (Gx, Gy)

def EC_mult(Scalar, Point = Gpt): if Scalar == 0 or Scalar >= cN: raise Exception("Invalid Scalar/Private Key") ScalarB = str(bin(Scalar))[2:] Q = Point for i in range (1, len(ScalarB)): Q = EC_double(Q) if ScalarB[i] == "1": Q = EC_add(Q, Point) return (Q)[/code]

cN というのは、合同算術で限られた平面に存在する整数で出来た点の総数です。それだけの点が存在するということは、掛け数としてそれを超えた数字を入れても重複が出てきます。よって、楕円曲線の計算をする場合、整数の計算はNで限り、平面の座標を指す場合はPで限ります。

実践

さて、試しに、有名な鍵ペアでも作ってみましょう。

上記のスクリプトをすべてまとめて、「ecc.py」として保存します。(記事の最後にもまとめてあります。)同じパス内でパイソンのターミナルを開いて下記のコマンドを実行しましょう。

[code language="python"]>>> from ecc import EC_mult>>> from hashlib import sha256>>> hash = sha256("Satoshi Nakamoto").hexdigest()>>> hash'a0dc65ffca799873cbea0ac274015b9526505daaaed385155425f7337704883e'>>> scalar = int(hash, 16)>>> pt = EC_mult(scalar)>>> "04" + "%064x" % pt[0] + "%064x" % pt[1]'040791dc70b75aa995213244ad3f4886d74d61ccd3ef658243fcad14c9ccee2b0aa762fbc6ac0921b8f17025bb8458b92794ae87a133894d70d7995fc0b6b5ab90'[/code]

そうです!Brainwalletがビットコインの創設者「中本哲史」のものを計算しました。

この公開鍵のハッシュを取って、ビットコインアドレスにすると 1JryTePceSiWVpoNBU8SbwiT7J4ghzijzW になります。(秘密鍵が5K38ZKiJBMmsk9iLcaakHfMa6FoZpLKpmhyo9aZnjossPc49J7e)このアドレスはすごく有名なアドレスの一つです。ビットコインを送り込むとその内誰かに取られますので、ご注意を。

第1回 おしまい

では、今回はこれで終わりです。

ソースの結果はこちら:[code language="python" collapse="true"]# SECP256k1 curve p, n, a, b, and G valuescP = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1cN = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141cA = 0cB = 7

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424Gpt = (Gx, Gy)

def inv_mod(a, p = cP): lim, him = 1, 0 low, high = a % p, p while low > 1: ratio = high / low nm = him - lim * ratio new = high - low * ratio him = lim high = low lim = nm low = new return lim % p

def EC_add(P, Q, Pcur = cP): Lamda = ((Q[1] - P[1]) * inv_mod(Q[0] - P[0])) % Pcur x = ((Lamda ** 2) - P[0] - Q[0]) % Pcur y = (Lamda * (P[0] - x) - P[1]) % Pcur return (x, y)

def EC_double(P, Acur = cA, Pcur = cP): Lamda = ((3 * (P[0] ** 2) + Acur) * inv_mod(2 * P[1])) % Pcur x = (Lamda ** 2 - 2 * P[0]) % Pcur y = (Lamda * (P[0] - x) - P[1]) % Pcur return (x, y)

def EC_mult(Scalar, Point = Gpt): if Scalar == 0 or Scalar >= cN: raise Exception("Invalid Scalar/Private Key") ScalarB = str(bin(Scalar))[2:] Q = Point for i in range (1, len(ScalarB)): Q = EC_double(Q) if ScalarB[i] == "1": Q = EC_add(Q, Point) return (Q)[/code]

次回以降はもうちょっと手短にビットコインに関わる関数や扱い方を説明する記事を書こうと思っています。今回少し長くなってしまい申し訳ございません。

こちらの記事の内容と書いたソースを随時githubに挙げていきますので、皆さんも是非チェックしてみて下さい。Pull request や教えている内容に対する指摘は検討しますので、是非 issuepull request を下さい。https://github.com/junderw/btcnews/tree/master/第1回

単なるディスカッションについては下記のコメント欄にてどうぞ宜しくお願いします。

No items found.
Latest Post