楕円曲線暗号がどのように使われるのかをざっくりと理解する

楕円曲線とは下のような滑らかな3次の曲線を表します。この楕円曲線を用いることで秘密鍵から公開鍵が生成されています。

楕円曲線

secp256k1

ビットコインのブロックチェーンにはsecp256k1という楕円曲線が使われています。secp256k1は下の方程式で表される曲線を指します。

secp256k1: $y^2=x^3+7$

楕円曲線暗号では楕円曲線の式に少し手を加えた下の式が用いられます。

$y^2 = x^3+7 \bmod p$

modを見慣れない方もいると思いますが、$a = b \bmod p$は「aとbはpで割った余りが等しい」ということを表します。例えば$1= 13 \bmod 4$です。

この式は$y^2$と$x^3+7$をpで割った余りが等しくなる点の集合を表します。例えばp=30だと下のようなグラフとなります。

楕円曲線暗号を使った公開鍵の生成では上のグラフのある1点(x,y)のペアが公開鍵となります。それでは秘密鍵からどのように公開鍵を生成するかをみていきます。

公開鍵を生成する

秘密鍵から公開鍵の生成は次の方法を行います。

楕円曲線上の基準点$G(x,y)$に対し秘密鍵の値$k$をかけた$kG$を求める

非常にシンプルです。ただし注意しなくてはいけないのは、k倍とは「楕円曲線上でk倍」という意味です。つまり$kG(x,y) = G(kx,ky)$ではありません。

では楕円曲線上でk倍とはどういう意味か説明します。ここで掛け算は足し算の繰り返しとも考えることができるのでここでは足し算について説明します。

楕円曲線上の足し算

楕円曲線上で足し算は次のように定義されます。

  • 曲線上の点$G(x,y)$に対する接線と曲線との交点を見つける
  • 交点においてx軸と対称な点をG+G=2Gとする

秘密鍵は基準点$G(x,y)$を$k$倍すれば求まるので今の足し算を$k$回繰り返します。すると最終的に点$kG(x,y)$を求めることができ、この点の座標$x,y$のペアが公開鍵となります。

なぜこのような手法がとられているかというと、楕円曲線暗号は離散対数問題という性質を持っているからです。

離散対数問題とは素数$p$と定数$g$が与えられたとき、$y=g^x \bmod p$を求めることは容易だが$y$から$x$を求めることは困難であるという性質です。

例えば$p=3$、$g=4$の場合を考えます。

$x=3$のとき$y=4^3=64=1 \bmod 3$とすぐに求めることができます。

しかし$y=1$のとき$x$を求めるには$x$を一つ一つ計算する必要があり$p$が大きい場合には非常に計算に手間がかかることとなります。

楕円曲線では上の例が応用されて、公開鍵$kG$と基準点$G$がわかっていても秘密鍵$k$を求めるのは非常に困難であるというハッシュ関数と同様の一方向の性質を持つため暗号として用いられています。

(補足)楕円曲線の足し算

楕円曲線上の足し算の計算を数学を使って追っていきます。補足となるので上の話がよくわからない方は飛ばして大丈夫です。

一般に楕円曲線の足し算$R(x_r, y_r) = P(x_p, y_p) + Q(x_q, y_q)$は、2点P,Qが与えられているときRはP,Qを通る直線と曲線の交点においてx軸に対称な点となります。公開鍵の計算ではある点の2倍を求めたいのでP=Qとなり直線は曲線の接線となっていました。

まずは実際に点Rを求めましょう。

P,Qを通る直線は傾きを$\lambda=(y_q – y_p)/(x_q – x_p)$で$P(x_p, y_p)$を通る直線なので

$y-y_p = \lambda (x-x_p)$

と表すことができます。この式を$\beta = y_p + \lambda x_p$とおいて変形して下のように書きます。

$y = \lambda x + \beta$

この直線と楕円曲線の交点(R’とおきます)は下の二つの方程式を満たします。

$y_r = \lambda x_r + \beta$
$y_r^2 = x_r^3 + ax + b$

したがってR’は3次方程式$x^3 – \lambda^2 x^2 – 2\lambda \beta x – \beta^2 + ax + b = 0$の解となります。ここでこの3次方程式を満たす解は直線と楕円曲線の3つの交点P,Q,R’であるため

$x^3 – \lambda^2 x^2 – 2\lambda \beta x – \beta^2 + ax + b = (x_x_p)(x-x_q)(x-x_r)=0$

と表すことができます。したがって解と係数の関係より

$x_r = \lambda^2 – x_p – x_q$

と求めることができます。RはR’をx軸に対して折り返した点なので

$y_r = \lambda(x_p – x_r) – y_p$

と求めることができます。

なぜこのように直線の交点や折り返しから足し算を求めているかというと、この計算方法は足し算が満たすべき条件を満たすからです。細かい数学の話になるので割愛しますが、例えば足し算として成り立つためには結合法則を満たすことが必要条件となります。結合法則とはA+(B+C)=(A+B)+Cのように足す順番に計算結果がよらない性質です。

上の計算はP,Q,Rの順番を変えても成り立つため結合法則を満たしていると言えます。

コメント

タイトルとURLをコピーしました