SSブログ

No.315 - 高校数学で理解する楕円曲線暗号の数理(1) [科学]

このブログでは、インターネットをはじめとする情報通信インフラで使われている「公開鍵暗号」について、今まで3回にわたって書きました。


の3つです。今回はその継続として、公開鍵暗号の一種で広く使われている「楕円曲線暗号」について、その数学的な背景を書きます。楕円曲線暗号は、1985年に米国 IBM の Victor Miller と米国 Washington 大学の Neal Koblitz によって独立に提案されました。暗号に限らず科学技術の世界では、同時期に同じアイディアが独立に考案されるというケースが見られます。

例によって高校レベルの数学知識だけを前提にし、証明なしに用いる定理や命題はないものとします。ただし、No.310、No.311、No.313 の内容やそこで証明した定理は既知とします。特にその中の、


です。なお、楕円曲線(Elliptic Curve)は、2次曲線である楕円(Ellipse)とは関係ありません。楕円の弧長を積分で求める時に出てくる数式なのでその名があるだけです。暗号の名を楕円暗号とするむきもありますが、誤解されるでしょう。楕円曲線暗号(Elliptic Curve Cryptography)が正しい言い方です。


15. 楕円曲線(Elliptic Curve)とは


楕円曲線とは、次の式で表される平面3次曲線です。

y2 = x3 + ax + b

係数の ab は有理数とします。楕円曲線の式の「標準形」と呼ばれるものは何種類かありますが、上式はその最も簡単な形です。楕円曲線暗号ではこの形を使うので、以降、楕円曲線といえばこの形で表される3次曲線とします。Wikipedia に非常にわかりやすい「楕円曲線のカタログ」が載っているのでそれを引用します。

b=-1 b=-0 b=-1 b=-2
a=-2 図A:楕円曲線のカタログ.jpg
a=-1
a= 0
a= 1
図1:楕円曲線のカタログ
Wikipediaより。楕円曲線には曲線の "成分" が1つのものと2つのものがある。なお、この図で a=b=0 だけは楕円曲線ではない。後述。

図でわかるように楕円曲線は成分(= ひとつながりの曲線)が1つのものと2つのもの(その1つは閉じた曲線)があります。この違いは何でしょうか。また、図の中にある a=0 b=0 の曲線は、実は楕円曲線ではありません。このあたりの説明は以降の通りです。楕円曲線の x の式を、

x3 + ax + b = f x

と書きます。 y = f x のグラフは少なくとも1回、x軸を横切るので、 f x = 0 の3次方程式は少なくとも1つの実数解を持ちます。この3次方程式が3つの異なる実数解を持つ条件を調べます。関数 f x が極値をとるとしたら、そのときの x は方程式、

f' x = 0

の解です。この解を x1 x2 とすると、

x1 =- -a 3 x2 =- -a 3

です。x がこの値をとるときの2つの極値がゼロでなく符号が逆であれば、 f x = 0 は3つの異なる実数解をもちます。つまりその条件は、

f x1 · f x2 < 0

です。 x1 x2 を入れて計算してみると、この条件は、

4a3 + 27b2 < 0

となります。不等号の向きが逆なら実数解は1つだけです。この不等号の左辺は「3次方程式の判別式」の符号を逆にしたものです。3次方程式の判別式 D は、いま扱っている楕円曲線の式の場合、

D = - 4a3 + 27b2

です。従って、

・  D > 0 のとき、 f x = 0 は3つの実数解をもち、楕円曲線で y=0 となる点は3つある。このとき楕円曲線の成分は2つになる(図2)。

・  D < 0 のとき、 f x = 0 の実数解は1つであり、楕円曲線で y=0 の点も1つである。このとき楕円曲線の成分は1つになる(図3)。

となります。この2つのケースで楕円曲線をを図示すると、図2( a=-2 b=1 )、図3( a=-2 b=2 )のようになります。

図B:成分が2つの楕円曲線.png
図2:成分が2つの楕円曲線 y2 = x3 - 2x + 1

図C:成分が1つの楕円曲線.jpg
図3:成分が1つの楕円曲線 y2 = x3 - 2x + 2

ここで D=0 のときにどうなるかを調べてみます。不定方程式、

4a3 + 27b2 = 0

の整数解を求めるために、 a = -3k2 0k と置くと、

a = -3k2 b = ±2k2

が解です。 k=0 1 とすると、

ab= 00 ,   -32 ,   -3-2

が解のうちの3組です。まず、 ab=00 のとき曲線の式は、

y2 = x3

となり、図4のように「尖点」をもつ曲線となります(Wikipedia の "楕円曲線のカタログ" にあったものです)。尖点では微係数が定まらず、曲線の接線が引けません。

図D:尖点をもつ3次曲線.jpg
図4:尖点をもつ3次曲線
y2 = x3

ab = -32 のときの曲線の式は、

y2 = x3 - 3x + 2 y2 = x+2 x-1 2

となり、図5のように「結節点」をもつ自己交差曲線となります。結節点において接線は引けますが、2種類あって一意に定まりません。

図E:結節点をもつ3次曲線.jpg
図5:結節点をもつ3次曲線 y2 = x3 - 3x + 2

ab=-3 -2 のときの曲線の式は、

y2 = x3 - 3x - 2 y2 = x-2 x+1 2

となり、図6のように -1 0 に「孤立点」が発生します。この孤立点でも接線は引けません。

図F:孤立点をもつ3次曲線.jpg
図6:孤立点をもつ3次曲線 y2 = x3 - 3x - 2

尖点、結節点、孤立点を曲線の「特異点」と言い、特異点をもつ3次曲線を特異3次曲線と言います。そして特異3次曲線は y2 = x3 + ax + b の形であっても楕円曲線とは言いません。つまり、楕円曲線の正確な定義は次の通りです。

15.1  楕円曲線の定義

次の式で表される平面曲線を楕円曲線と言う。

y2 = x3 + ax + b 4a3 + 27b2 0


この定義による楕円曲線は "なめらか" であり、曲線上の全ての点で唯一の接線が引けます。以降、この楕円曲線の性質を調べていきます。



楕円曲線暗号は「楕円曲線上の点の加法群」で構成する暗号です。そこでまず、No.313 でも触れた「群(group)」とは何かを復習します。


群の定義


群(G で表します)とは、何らかの2項演算 " " が定義された集合です。演算が定義されているとは、集合 G の任意の2つの元(同じ元であってもよい)、ab を演算した結果の ab G の元であることを意味します。この2項演算は次の3つの条件を満たす必要があります。この「条件を満たす2項演算が定義された集合」が群 G です。


(単位元) ae = ea = a となる元 e が存在
(逆元) ab = ba = e となる b が、任意の a について存在
(結合則) abc = abc


演算 " " を乗算と考えるとき、G を乗法群といいます。乗法群では2項演算を a×b a·b ab などと書きます。単位元は 1 と書くこともあります。また、逆元 b a-1 です。同一の n 個の元 a に対して演算 " " を n-1 回行った結果は an で「累乗(あるいは冪乗)」と呼びます。

演算 " " を加算と考えるとき、G を加法群といいます。加法群では2項演算を a+b と書きます。加法群の単位元を零元と呼び、0 と書くことがあります。また逆元 b -a です。同一の n 個の元 a に対して演算 を行った結果は na で「スカラー倍」と呼びます。

乗法群か加法群かは多分に "言葉の綾" の面があり、どちらがイメージしやすいかによります。但し、加法群と言った場合は暗黙に可換則、 ab = ba が成り立つ群を言います。可換則が成り立つ群を、ノルウェーの数学者 Abel の名前をとって「アーベル群」と呼びます。もちろん「乗法」や「加法」のイメージとは結びつきにくい群もたくさんあります。


楕円曲線上の有理点


楕円曲線上の有理点からなる加法群を構成することができます。有理点とは、楕円曲線上の点、 x0 y0 で、 x0 y0 も有理数の点です。一般に、楕円曲線が有理点を持つかどうかを有限回の手続きで決定する方法は知られていません。しかし、1個か2個の有理点があれば、次のような手続きで次々と有理点を見つけることができます。以下の記述では PQR などを有理点とし、

・ PQ を結ぶ直線がふたたび楕円曲線と交わる点を P Q (図7の左)

・ P 点における接線が楕円曲線と交わる点を P P (図7の右)

と定義します。ここでの " " は乗算の記号ではなく「" " の前後に書かれた楕円曲線上の点ではない、もう一つの直線と楕円曲線の交点」の意味です。

図G:楕円曲線上の有理点.jpg
図7:楕円曲線上の有理点
J.H.シルヴァーマン、J.テイト著「楕円曲線論入門」(シュプリンガー・フェアラーク東京 1995)より引用

楕円曲線論入門.jpg
J.H.シルヴァーマン、J.テイト
「楕円曲線論入門」
(シュプリンガー・
フェアラーク東京 1995)
図7で、 PQ PP も有理点です。なぜなら、係数が有理数の3次曲線と直線の交点を求める式は3次方程式になりますが、3次方程式の2つの異なる根が有理数なら(左図の PQ)、もうひとつの根 PQ も有理数だからです。もう1つが有理数でないと(=無理数や複素数)、3次曲線の係数が有理数という前提に反します。同じように3次方程式の重根(右図の P)が有理数だと、もう一つの根も有理数です。

つまり、楕円曲線上に1つ、ないしは2つの有理点があったとしたら、上記の操作で有理点を増やしていけます。そこで有理点の存在を前提として以下の議論を進めます。

なお、楕円曲線暗号で使う加法群は「有限体上の楕円曲線における加法群」であり、ここでは "有理点" が必ず存在し、それを見つけるアルゴリズムもあります(後述)


楕円曲線上の有理点が作る加法群


楕円曲線上の有理点を "群" にするためには、そこに何らかの演算を定義する必要がありますが、その定義を次のようにします。加法群なので演算を + と書きます。

 群演算 

・ 任意の有理点を零元(= O )とする。

・ PQ を楕円曲線上の有理点とするとき、点 PQ O を結ぶ直線が再び楕円曲線と交わる点を P+Q とする。つまり、

P+Q = P Q O

とする。

図H:楕円曲線上の群演算.jpg
図8:楕円曲線上の群演算
シルヴァーマン、テイト「楕円曲線論入門」より引用。零元の記号には、英大文字 O の筆記体が使ってある。以下同様

 零元 

この演算における零元 O が、群の零元の条件を満たしているかどうかを検証すると、

P+O = P O O = P

となって、零元の条件を満たしていることがわかります(図9)。もちろん、 O + P = P です。

図I:零元であることの検証.jpg
図9:O が零元であることの検証
「楕円曲線論入門」より引用

 逆元 

逆元は次のように定義します。零元 O における接線が楕円曲線と交わる点を S とします。まず、

S = O O

です。そして 点 QS を結ぶ直線が再び楕円曲線を交わる点を、 Q の逆元(= -Q )とします。つまり、

-Q = Q S

です。このように定義すると

Q + -Q = Q -Q O = S O = O

となり、群の逆元の条件を満たすことがわかります(図10)。SO を結ぶ直線は O で2回交差するので、 S O = O です。

図J:点の逆元.jpg
図10:点の逆元
「楕円曲線論入門」より引用

 結合則 

群を構成するためには、以上の群演算の定義が結合則を満たしていななければなりません。楕円曲線上に点 PQR をとったとき、

P+Q + R = P + Q+R

となるのが結合則ですが、

P+Q +R = P+Q R O P+ Q+R = P Q+R O

なので、

P+Q R = P Q+R

が示せればよいことになります。「楕円曲線論入門」にはこのことを示した図が載っています(図11)。

図K:結合則の検証.jpg
図11:結合則の検証
「楕円曲線論入門」より引用

P+Q R の点と P Q+R の点が、楕円曲線上で同一の点になることの証明は少々複雑なので「18. 結合則が成り立つことの証明」にまわします(後述)。



以上のように楕円曲線上の有理点は、直線との交点を使って加法と逆元をうまく定義することで "群" になることがわかりました。ここで注意すべきは、零元は楕円曲線上の任意の有理点でよいことです。これを利用し「零元=無限遠点」としたのが、実用的に使われる楕円曲線上の加法群です。


無限遠点を零元とする加法群


以下では「対称点」という言葉を使いますが、

P = xp yp とするとき、点 xp -yp P の対称点と呼ぶ

ことにします。楕円曲線は x軸について対称なので、点 Px軸で "折り返した" 点が P の対称点です。 y=0 となる点が楕円曲線上に1つ、または3つありますが、その点の対称点は同じ点です。

次に「y軸方向の無限遠点」を導入し、「楕円曲線上の有理点と無限遠点を合わせた集合」に群を定義します。ここからは無限遠点を O と書きます。

無限遠点は図に表せないのでイメージしにくいのですが、y軸方向の無限遠に O があると考えます。y 軸の正方向でも負の方向でもかまいません。

楕円曲線上の点 P P = xp yp とし、 xp をどんどん大きくすると、楕円曲線の式では x3 の項が支配的になるので、 yp 2 = xp 3 と近似できます。つまり yp = ± xp 3 2 となり、 xp が大きいと yp y軸の遙か上方(と下方)になります。この極限が無限遠点 O と考えます。さらに、

楕円曲線上の任意の点 P を通る y軸に平行な直線を引くと、その直線は P の対称点で楕円曲線と交差すると同時に、無限遠点 O でも交差する

と考えます。この y軸方向の無限遠点 O を零元とする群を構成します。

 群演算 

まず、群演算の加法ですが、

P + Q = P Q の対称点

と定義します(図12)。

図L:加法則.jpg
図12:加法則
「楕円曲線論入門」より引用

こうすると、 P Q P + Q を結ぶ直線は y軸と平行になり、それは無限遠点 O で楕円曲線と交差します。つまり、

P+Q = P Q O

です。この定義は 零元を楕円曲線上の点にとった図8と合致します。この加法の定義で O が群の零元の要件を満たしているかを検証すると、

P+O = P O O = P

となって要件を満たしていることがわかります。 P O P の対称点ですが、P の対称点と O を結ぶ直線が楕円曲線と交差する点は P なので上式が成立します。これは楕円曲線上に O をとった図9と同じです。さらに逆元ですが、Q が楕円曲線上にあったとき、

Q の対称点が Q の逆元( -Q と表記)

と定義します(図13)。

図M:逆元.jpg
図13:逆元
「楕円曲線論入門」より引用

こうすると、

Q + -Q = Q -Q O = O O

となりますが、 O O = O (=無限遠点の対称点は無限遠点)との自然な定義を行うと、

Q + -Q = O

となって逆元の要件を満たします。結合則についても零元を楕円曲線上にとった場合(図11)と同じ様に成立します。「18. 結合則が成り立つことの証明」でそのこと書きます。

 射影平面 

無限遠点は図で表現できず、何だか "怪しげな" 感じがしますが、数学的に厳密に定義できます。それには射影平面を使います。

平面 xy に対し、3つの数 XYZ で表される "平面" を射影平面と言います。3つの数がありますが3次元空間ではありません。ただし 000 の点は除きます。また、

λ0 とするとき
XYZ λ X λ Y λ Z は同じものである(同値である)

と定義します。 xy 平面から射影平面の対応は、

xy    xy1

とし、その逆の対応は、

Z0 のとき
XYZ    X Z Y Z

です。この対応からわかるように、射影平面には xy 平面にない点が含まれています( Z=0 の点)。

射影平面での楕円曲線の式は、 xy 平面の楕円曲線の式で、 x= X Z ,   y= Y Z とおき、全体に Z3 をかけて同時化(=変数項の合計次数をそろえる)します。その結果、

Y 2 Z = X 3 + aX Z 2 + b Z 3

の同時方程式が、射影平面での楕円曲線になります。ためしに、図2の楕円曲線( a=-2 b=1 )と y軸との交点を計算してみると、 xy 平面では、

{ y2 = x3 - 2x + 1 x=0

の連立方程式を解いて、 0 ±1 となります。一方、射影平面では、 x=0 X=0 なので、

{ Y 2 Z = X 3 - 2 X Z 2 + Z 3 X = 0

が、楕円曲線と直線の交点を求める連立式になります。この解は、αβ0 ではない数として、 0 α ±α 0 β 0 です。射影平面の同値関係を利用すると、

0 ±1 1 0 1 0

が楕円曲線と直線の交点になり、交点は3つあることになります。ここで xy 平面の交点には現れなかった 0 1 0 y軸方向の無限遠点です。無限遠点は楕円曲線の同時方程式を必ず満たします。つまり全ての楕円曲線は無限遠点を通ることになります。

楕円曲線の計算には現れませんが、無限遠点にもいろいろあって、 1 0 0 x軸方向の無限遠点、 α β 0 は任意方向の無限遠点です(αβ0 ではない数)。

xy 平面の2直線は、平行なときには交点がありませんが、射影平面の2直線は必ず1点で交わります。また射影平面の楕円曲線の1点を通る直線は、楕円曲線と必ず3点で交わります(直線が楕円曲線の接線の場合は、接点での交差数を2と数えます)。このように、交差を統一的に扱えるのが射影平面の特徴の一つです。

以上のような数学的裏付けのもとに導入したのが無限遠点です。これを xy 平面では、

・ y軸方向の無限遠のところに無限遠点 O がある
・ 楕円曲線は O を通る
・ y軸に平行な直線は O で楕円曲線と交わる

とイメージしてよいわけです。


加法式・2倍式


楕円曲線上の加法を計算式で表します。楕円曲線上の3点を次のように定義します。

P1 + P2 = P3 P1 = x1 y1 P2 = x2 y2 P3 = x3 y3

とします。 P1 P2 を結ぶ直線を y = λ x + μ とすると、連立方程式、

{ y2 = x3 + ax + b y = λ x + μ

の解が P1 P2 x3 - y3 です。この2つの式から y を消去すると、

x3 + ax + b - λ x + μ 2 = 0

が得られますが、この式は、

x - x1 x - x2 x - x3 = 0

と同一のはずです。そこで x2 の係数を比較すると、

- λ 2 = - x1 - x2 - x3

が得られます。つまり、

x3 = λ 2 - x1 - x2

となります。この x3 を直線の式に入れると、

- y3 = λ x3 + μ

ですが、 y1 = λ x1 + μ なので μ を消去すると、

y3 = - y1 + λ x1 - x3

となります。これが基本の加法式です。これを P1 P2 の配置パターンごとにまとめると、次の通りです。

  x1 x2 のとき 

{ x3 = λ 2 - x1 - x2 y3 = - y1 + λ x1 - x3 λ= y2 - y1 x2 - x1

  x1 = x2 y1 = y2 0 のとき 

この場合は P1 P2 を通る直線は P1 における楕円曲線の接線となり、直線の傾き λ は上の式のままでは計算できません。そこで y2 = x3 + ax + b x で微分すると

2y dy dx = 3 x2 + a

なので、

λ = 3 x1 2 + a 2 y1

となります。 x2 x1 に置き換えてまとめると、

{ x3 = λ 2 - 2 x1 y3 = - y1 + λ x1 - x3 λ= 3 x1 2 + a 2 y1

P1 + P1 の計算式です。これは P1 "2倍"(一般にはスカラー倍)であり、 2 P1 と書きます。

  x1 = x2 y1 y2 のとき、あるいは y1 = y2 = 0 のとき 

この場合、 P2 = - P1 なので、定義により

P1 + P2 = O

です。


有限体上の楕円曲線による加法群


以降に出てくる有限体 F p と 乗法群 F p については、No.313「高校数学で理解する公開鍵暗号の数理:10. 有限体と乗法群」 で定義したものです。

楕円曲線暗号に使われる楕円曲線は、有限体 F p で定義された "曲線" で、次の式を満たすものです。

y2 = x3 + ax + b 4a3 + 27b2 0

xyab は全て F p の元です。「この式を満たす全ての xy と 零点 O の集合」に対して演算を定義して群を構成します。演算を加法と考えて + と書きます。この "曲線" 上の3点を、

P1 + P2 = P3 P1 = x1 y1 P2 = x2 y2 P3 = x3 y3

とするとき、群の演算式は次のように定義されます。

  x1 x2 のとき 

{ x3 = λ 2 - x1 - x2 y3 = - y1 + λ x1 - x3 λ= y2 - y1 x2 - x1

  x1 = x2 y1 = y2 0 のとき 

{ x3 = λ 2 - 2 x1 y3 = - y1 + λ x1 - x3 λ= 3 x1 2 + a 2 y1

  x1 = x2 y1 y2 のとき、あるいは y1 = y2 = 0 のとき 

P1 + P2 = O

つまり、実数平面の有理点と無限遠点(=零元)で構成された群の演算式と全く同じです。もちろん加減乗除は F p で行います。これが群になる理由は、有理数体(有理数全体の集合)も有限体 F p も「体」であり、加減乗除は全く同一形式で記述できるからです。ただ、有理数体と違って F p の元の数は有限個であり、群の元の数も有限個(=有限群)です。以降、 F p 上の楕円曲線、 y2 = x3 + ax + b による有限群を Eabp と表記します。

F p 上の楕円曲線は、もはや "曲線" の形をしていませんが、これを可視化した図が Wikipedia にあるので、引用します。

図N:有限体上の楕円曲線(p=89,a=-1,b=0).jpg
図14:有限体上の楕円曲線
E-1 0 89  
F 89 ,   y2 = x3 - x  
赤丸が "楕円曲線上の点" を表し、計79個ある。零元(無限遠点)と合わせて、群の元の総数は 80 である。
(Wikipedia より)



以上が「有限体上の楕円曲線が作る加法群」で、楕円曲線暗号はこの加法群で構成されます。その話を次回にします。



nice!(0) 

nice! 0