SSブログ

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

前回より続く)

前回の No.316「高校数学で理解する楕円曲線暗号の数理(1)」では「有限体上の楕円曲線で定義された加法群」までの説明をしました。楕円曲線暗号はこの加法群で構成します。今回はその説明ですが、まず、加法群の点をどうやって見い出すか、またこの加法群の点の総数はどうなっているのかです。


16. 楕円曲線上の点


F p の元 xy のぺア xy の集合を F p  2 と記述します。集合 F p  2 の元で楕円曲線上の "点" はどれだけあるでしょうか。まず、楕円曲線の式を満たす F p  2 の元がどのように計算できるかを調べます。

 平方数と平方根 

楕円曲線の式を、

{ y2 = z z = x3 + ax + b

と書くとき、z z0 )が F p での平方数なら、y の解が2つ求まります。ここで、次の命題が成立します。

16.1  平方数である条件

z0 ではない F p の元とする。

z p-1 2 = 1

であるとき(かつ、そのときに限り)z は平方数である(= オイラーの規準)。


F p で考えているので「平方数」と書きましたが、整数の世界では「平方剰余」です。つまり、 x2 = a modn となるような x が存在する a が平方剰余です。16.1 の証明ですが、 F p から 0 を除いた乗法群 F p で考えます。12.1(No.313)により、z F p の生成元(の一つ)を g として、

z = gk

と表現できます。つまり、命題の条件は、

g k p-1 2 = 1

です。このとき k は偶数のはずです。なぜなら、もし k が奇数だとすると、 k p-1 2 p-1 で割り切れないので、

k p-1 2 = sp-1+t 1 t < p-1

と表現できます。すると、

g k p-1 2 = g sp-1+t = gp-1 s · gt = gt

となり、 gt = 1 1 t < p-1 になりますが、これは g が生成元であることと矛盾します。従って k は偶数です。そうすると k=2m とおいて、

z = g m 2

となり、z は平方数になります。



z は平方数だとわかったとき、実際に F p y(= z の平方根)を求める手段が必要になります。整数であれば平方数の平方根を求めるのは容易ですが、 F p ではそうはいきません。特に、楕円曲線暗号で使われる p は10進数で数10桁以上の巨大素数なので、総当たりで求めたり、解の存在範囲を限定していって求めるわけにはいかないのです。ただ、もし p 3 mod4 なら求めるのは容易で、

y = z p+1 4

が解の一つとなります(もう一つの解は -y で、つまり p-y )。確認してみると、

y2 = z p+1 4 2 = z p+1 2 = z p-1 2 · z = z

となって、確かに y が解であることがわかります。しかし、 p 1 mod4 なら、このような簡便な式では求まりません。この場合は「トネリ - シャンクスのアルゴリズム」で解を求めます(Tonelli は19世紀イタリア、Shanks は20世紀米国の数学者)。なお、このアルゴリズムは説明が長くなるので割愛します。



いま、 F p において z0 から p-1 まで振ったときの y2 = z の解の総数を求めてみます。z を、 F p の生成元 g を使って、

z = 0 gk k = 1 2  ⋯  p-1

と表すと、

・  z = 0 のとき、解は1個
・ k が偶数のとき、解は2個
・ k が奇数のとき、解は無し

となり、 F p  2 における解、 zy の総数は p となります。では、 F p  2 における楕円曲線上の点、 xy の総数はどうなるでしょうか。x F p の全ての元に渡るとき、z F p で均等にバラつくとは限りません。しかし xy の総数は「だいたい p に近い値」だと考えられます。

つまり、群 Eabp の元で、零元 O 以外の F p  2 に属するものは、だいたい p 個あると考えられる。群 Eabp の元の数を #E と書くと、 #E は 零元 O を含んで p+1 に近い値だと考えられます。

Eabp の元の数を評価する式があります。「ハッセの定理」です(Helmut Hasse は20世紀ドイツの数学者)。この定理にによると、

p+1-2p #E p+1+2p

であり、想定どおり #E p+1 の周辺であることが分かります。 #E を具体的に求めるアルゴリズムは、1985年にオランダ出身の数学者、レネ・ショーフ( Rene Schoof。英語読みでスクーフとも書かれる)が開発しました。その「ショーフのアルゴリズム」は、数学用語で言うと最初の「決定論的多項式時間アルゴリズム」です。平たく言うと「計算結果が100%正しいと数学的に保証される(=決定論的)計算可能な(=多項式時間)アルゴリズム」です。「ショーフのアルゴリズム」の具体的内容は、ここでは割愛します。


17. 位数


楕円曲線暗号を構成する上で必要になるのが、有限群における「位数」の概念です。以下の位数の話はすべての有限群に共通するので、群の演算を乗法的に書くことにします(掛け算、冪乗、単位元 e、などの記法を使います)。演算を加法と考えても全く同じことになります。

元の数が有限個の群 G を「有限群」といい、その元の個数を「群位数(group order)」と呼びます。群位数を |G| と表します。群の演算則だけから次のことが言えます。

単位元 e でない群 G の元を a とします。a の冪乗 an 1n n を増やしていくと、ある時点で an = e となります。その理由ですが、

a1 a2  ⋯  a |G|

という |G| 個の元を考えてみます。もし |G| 個が全て相異なると、どれかが e のはずです。全てが相異なる元ではないとき、

aj = ai 1 i < j |G|

となったとすると、 ai の逆元を右から掛けて、

aj-i = e

が得られます。 1 j-i < |G| なので、この範囲に e があります。そこで、つぎのように元 a位数を定義できます。

17.1  位数の定義

有限群 G の任意の元 a について、

a d = e

となる最小の da の "位数(order)" と言う。



さらに、元の位数については次の命題が成り立ちます。

17.2  位数と群位数

有限群 G の任意の元 a の位数を d とすると、d は群位数 |G| の約数である。


この命題が成り立つ理由は次の通りです。有限群 G の任意の元を a とし、集合 A を、

A = a1 a2  ⋯  ad = e

とします。集合 A の元は全て相異なります。なぜなら、もし、

aj = ai 1 i < j d

となったとすると、

aj-i = e

であり、d ad = e となる最小の数であるという位数の定義に反するからです。さらに、集合 A の任意の元の逆元は集合 A に含まれます。つまり、 ad = e なので aj 1j<d に対して ad-j 1d-j<d が逆元です(ということは集合 A もまた群であり、これを G の部分群と言います)。

集合 AG の全ての元を尽くしているなら 17.2 は成立します。そこで、集合 A に含まれない G の元があったとし、それを b1 とします。集合 A の全ての元に左から b1 を掛けて、集合 B1 を作ります。つまり、

B1 = b1 a1 b1 a2  ⋯  b1 ad

です。集合 A の元は全て相異なるので、集合 B1 の元も全て相異なります。さらに、集合 B1 の元で集合 A の元と同じものはありません。なぜなら、もし、

b1 ai = aj 1 i < j d

だとすると、 ai の逆元、 ad-i を右から掛けて、

b1ad = ad-i+j b1 = ad-i+j = aj-i

となりますが、 1 j-i < d なので、これは b1 が集合 A の元であることを意味していて仮定に反します。つまり、集合 B1 の元で集合 A の元と同じものはありません。

集合 A B1 G の元の全てを尽くしているなら、 2d = |G| となって 17.2 は証明できたことになります。そうではない場合、集合 A B1 に含まれない G の元の一つを b2 として、集合 B2 を、

B2 = b2a1 b2a2  ⋯  b2ad

と定義します。そうすると先ほど同じように、集合 B2 の元は全て相異なり、かつ、集合 A との重複はありません。さらに、集合 B2 の元は集合 B1 の元とも重複しません。なぜなら、もし、

b2ai = b1aj 1 i < j d

だとすると、 ai の逆元、 ad-i を右から掛けて、

b2 = b1 ad-i+j = b1 aj-i

となりますが、 1 j-i < d なので、 b2 が 集合 B1 の元という意味になり仮定に反します。つまり、集合 B2 の元は集合 B1 の元と重複しません。

以上の操作は G の元が残っている限り B3 B4  ⋯  と続けられます。そしてある時点で 残っている G の元がちょうど切りのよいところで無くなるはずです。 Bn-1 まで作ったときに G の元の全てを尽くしたとしたら、 nd = |G| です。これで 17.2 が証明できました。17.2 から直ちに次の2つが結論づけられます。

17.3  

有限群 G の任意の元 a について、

a |G| = e

である。


これは、群位数 |G| が 元 a の位数の倍数なのでそうなります。p を素数とし、Gp 未満の自然数からなる乗法群 F p だとすると、 |G| = p-1 なので、フェルマの小定理( 3.1 )そのものになります。


17.4  群位数が素数の群

有限群 G の群位数 |G| が素数だとすると、

単位元 e を除く G の全ての元の位数は |G|

である。


素数の約数は 1 と素数自身しかないので、単位元以外の元の位数は群位数に等しくなります。従って、群位数が素数の群では任意の元 a の冪乗が群全体に "バラける" ことになります。


楕円曲線暗号の構成:スカラー倍と離散対数


ここから具体的な楕円曲線暗号のしくみに入ります。楕円曲線上の F p  2 の点と零元 O が作る加法群を Eabp とし、その群位数を #E と書きます。楕円曲線暗号では Eabp における「スカラー倍」の演算を利用します。

楕円曲線上の F p  2 の点の一つを B = Bx By とし、dB の位数、n 1 n d とします。Bn 倍(=スカラー倍)を nB と書き、

nB = B + B +  ⋯  + B n

と定義します。そして、

nB = A

と書くことにすると、A を求める計算は、 Eabp の2倍式と加法式を使って可能です。例として 133 B の場合だと、 133 = 27 + 22 + 1 なので、

133 B = 27 B + 22 B + B

となります。つまり、 Eabp の2倍式を7回使って、

21 B ,   22 B ,    ⋯  ,   26 B ,   27 B

と順次計算し、加法式を2回使うと A が求まります。これは n がたとえ巨大数であっても可能です。 2256 は10進数で約80桁(256ビット)の巨大数ですが、それでも256回程度の2倍算と最大で256回程度の加算をすれば A が求まります。このあたりは 4.2 の「冪剰余の計算アルゴリズム」と同じです。もちろん冪剰余と違って、2倍算も加算も単純な掛け算ではありません。 Eabp の群演算は、定義式どおりの少々ややこしい式です。しかし計算が可能なことは確かです。

スカラー倍の計算は可能ですが、その逆、つまり AB を知って n 求めるのは困難になります。この n を求める問題を、加法群 Eabp における「離散対数問題」と呼びます。離散対数問題を解くのが不可能になるのは、B の位数 d が10進数で数10桁以上といった巨大数の場合です。その場合、Ad 種のバリエーションをとるので、n を求めるのは不可能になります。

位数 d が巨大数である B を求める方法の一つは、p を巨大な素数とし、群位数 #E も素数であるような Eabp を選ぶことです。そうすると 17.4 により、零元 O 以外の Eabp の全ての元の位数 d #E になり、その #E p+1 の近辺にあるので、B をどのように選ぼうとも位数 d は巨大数になります。

#E が素数である Eabp では、任意の元 AB について、 nB = A となる n が唯一存在することになります。このことを、

logB A = n

と書くと、B は実数における通常の対数の "底(base)" に相当します。B Eabp の元 = F p  2 の元なので、B を「ベースポイント(base point)」と呼びます。このペースポイントを含め、楕円曲線暗号では、

・  Eabp
・  #E
・  B = Bx By
・ dB の位数)

が公開されます。そして暗号化通信では、d より小さい数 k をランダムに選び

・ 公開鍵 : kB  
・ 秘密鍵 : k

とします。公開鍵だけを知っても秘密鍵は計算できない。これが楕円曲線暗号の原理です。



スカラー倍のイメージをつかむため、p がごく小さい数の場合で実験してみます。計算してみると、 p=29 ,   a=-1 = 28 ,   b=1 のとき #E = 37 となって、群位数が素数になります。 y2 = x3 - x + 1 の解の一つは 01 なので、これをベースポイント B としてスカラー倍を順次計算してみると次の通りとなります。

 B=(01 )   2B=(2210 )   3B=(2713 )   4B=(924 )   5B=(1418 )   6B=(1125 )   7B=(2320 )   8B=(128 )   9B=(268 )   10B=(223 )   11B=(324 )   12B=(11 )   13B=(2828 )   14B=(518 )   15B=(175 )   16B=(2517 )   17B=(2021 )   18B=(1018 )   19B=(1011 )   20B=(208 )   21B=(2512 )   22B=(1724 )   23B=(511 )   24B=(281 )   25B=(128 )   26B=(35 )   27B=(26 )   28B=(2621 )   29B=(1221 )   30B=(239 )   31B=(114 )   32B=(1411 )   33B=(95 )   34B=(2716 )   35B=(2219 )   36B=(028 )   37B=(O    

群位数が素数なので B の位数は 37 となり、群位数と一致します。この計算を F p  2 の平面に表示すると次の通りです。B 36B は赤丸、 2B 35B は黒丸です。矢印は加算を示し、赤矢印は B+B 35B+B の加算です。

スカラー倍.jpg
図15: E -1 1 29 (零元を除く) #E = 37 ,   B = 01 ,   d=37  

スカラー倍を繰り返すごとに "楕円曲線" 上の合計36点を通り、それが乱雑に変化することが分かります。



振り返ってみると、RSA暗号(No.311)の安全性は巨大数の因数分解の困難性に依存しているのでした。またディフィー・ヘルマンの鍵交換(No.313)は、乗法群 F p における離散対数問題を解くことの困難性に依存しています。これらに使われる演算はいずれも整数の乗除算です。それに対して楕円曲線暗号に使われるのは、整数の乗除算よりは遙かに複雑な、楕円曲線上の加法群における「加算」です。ここに楕円曲線暗号の解読しにくさの要因があります。



実用的な楕円曲線暗号で公開するパラメータをどうやって作るか、その一例をあげます。


① 素数の大きさを決め(たとえば10進数で50~100桁程度)、素数判定法によってその大きさの素数 p を求める。

②  p より小さい数、ab をランダムに決め、加法群 Eabp の群位数 #E を計算する。

③  #E が素数なら次へ。素数でなければ ② に戻る。

④  p より小さい数、 Bx をランダムに選び、 Bx が平方数ならその平方根 By を求めてベースポイント B = Bx By とする。


#E が素数なので、B の位数 d #E に等しくなります。なお、 #E がたまたま p と一致すると離散対数問題が解けることが分かっているので、③ でそのようなケースを排除しておきます。

この決め方では、群位数 #E の計算と素数判定を繰り返すことになり、多大な計算時間がかかることは想像に難くありません。しかしパラメータは1度計算すれば暗号通信の仕様として公開し、皆がそれを使えばいいわけです。最初の1回だけの計算時間より、その後の通信の安全性の方が重要です。

楕円曲線暗号のパラメータの一例を次に掲げます。secp160r1 という名称で公開されているパラメータです。

secp160r1
 
p= 1461501637330902918203684 832716283019653785059327 = 2 160 - 231 - 1 a= 1461501637330902918203684 832716283019653785059324 = p - 3 b= 1632357913061681105466049 19403271579530548345413 #E= 1461501637330902918203687 197606826779884643492439 Bx = 4258262317238883504465415 92701409065913635568770 By = 2035201141629041078739914 57957346892027982641970 d= 1461501637330902918203687 197606826779884643492439 =#E


楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)


ディフィー・ヘルマンの鍵共有(No.313)を、楕円曲線暗号を使って実現できます(ECDH と略称される)。鍵共有のプロセスは次のように進みます。しかるべき「公開鍵センター」が、皆が使う公開鍵として、

・  Eabp
・  #E
・  B = Bx By
・ dB の位数)

をオープンにして(暗号通信の仕様書として公開して)おきます。以下のスカラー倍演算はすべて F p で行います。AliceBob が秘密鍵を共有したい場合、

暗号文による通信の開始にあたって、Alice 0 < kA < d である乱数 kA を発生させ、 kA B Alice の公開鍵として(盗聴されている通信路を介して) Bob に送付

します。乱数 kA Alice の秘密鍵として秘匿します。次に同様に、

Bob 0 < kB < d である乱数 kB を発生させ、 kB B Bob の公開鍵として(盗聴されている通信路を介して) Alice に送付

します。もちろん kB は秘匿します。そして、

Alice KA = kA kB B を共有の秘密鍵

Bob KB = kB kA B を共有の秘密鍵

とします。この作り方から KA = KB = K となるので、秘密鍵 K を共有できたことになり、以降はこれを使って暗号化通信(公開鍵ではない、高速な暗号化通信)を行います。使った秘密鍵は通信が終わったら捨てます。

原理は、オリジナルのディフィー・ヘルマンの鍵交換(DH)と全く同じです。ただ、オリジナルが F p での離散対数問題を利用していたのに対し、ECDH は Eabp での離散対数問題を利用した暗号であることが違います。


18. 結合則が成り立つことの証明


楕円曲線論入門.jpg
J.H.シルヴァーマン、J.テイト
「楕円曲線論入門」
楕円曲線暗号が暗号として成立するのは、楕円曲線上の加法群 Eabp が "群" として定義できるからです。群であるための条件は「単位元の存在」「逆元の存在」「結合則の成立」の3つです。このうち単位元の存在と逆元の存在は、そもそもそれが成り立つように群の演算を定義したのでした。

しかし結合則は自明ではありません。前回 No.315 の「楕円曲線上の有理点が作る加法群」のところで結合則が成り立つことの証明を後回しにしたので、ここに書くことにします。結合則が成り立つのは、楕円曲線上の有理点の加法を「3次曲線と直線の交点」で決めていることに理由があります。その理由を説明したいと思います。

前回で引用した、シルヴァーマン、テイト著「楕円曲線論入門」には、結合則が成り立つことを示した次の図があります。加法群の零元 O を楕円曲線上にとった場合の図です。

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

楕円曲線上に点 PQR をとったとき、

P+Q + R = P + Q+R

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

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

です。ここで の記号は、 A B と書くと AB を結ぶ直線が楕円曲線と交わる点(で AB 以外の点)の意味です。O は零元でした。従って、結合則を証明するためには、

P+Q R = P Q+R

が証明できればよいことになります。言葉で書くと、


P+Q R を通る直線が楕円曲線と交わる点を T1 とし、P Q+R を通る直線が楕円曲線と交わる点を T2 とすると、 T1 T2 は同じ点である


となります。上の図はそれを表しています。以下の証明では同じことですが、次を示します。

18.1  結合則

P+Q R を結ぶ直線と、 Q+R P を結ぶ直線の交点を T とすると、楕円曲線は T を通る。


これは楕円曲線上の2点、 P+Q R P Q+R が等しい(= 図11)ことと同じなので、以降は 18.1 が成り立つことを示します。そのためにまず、次の命題 18.2 を証明します。この証明の筋道は「楕円曲線論入門」に書かれているものです。

18.2  3つの3次曲線の交差

2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする。

別の3次曲線 D が 9点のうちの8点、 P1 ,   P2  ⋯  ,   P8 を通るとき、D P9 も通る。


これは「ケーレー - バカラック(Cayley-Bacharach)の定理」と呼ばれるものの特別な場合です(Cayleyは英国、Bacharachはドイツの数学者。いずれも19世紀)。ここで言う「3次曲線」とは、次の一般形で表される "3次曲線のすべて" であり、楕円曲線もその一部です。

[3次曲線の一般形]
ax3 + bx2y + cxy2 + dy3 + ex2 + fxy + gy2 + hx + iy + j = 0

10個の係数(=パラメータ)、 a b  ⋯  i j を決めると3次曲線が一つ決まります。もちろん、各係数を定数倍した曲線は同じ曲線です。つまり、この形の3次曲線の係数は実質的に "9次元" と言えます。3次曲線なので a b c d のうち少なくとも一つは 0 でないものがあります。その係数で全体を割れば、係数の数は9個になることからもわかります。

従って、一般には相異なる9点を通る3次曲線は一意に決まります。これは、直線の方程式を ax + by + c = 0 で表したとき、この式には3つのパラメータがあるものの実質的に2次元であって、相異なる2点を通る直線が一意に決まるのと同じことです。このことを踏まえると、命題 18.2 の前半である、

2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする

のところについては、 P1 ,   P2  ⋯  ,   P9 何らかの制約条件がついているからこそ、2つの3次曲線が2つとも9点目の点を通るわけです。以上のことの裏返しは、

相異なる8点、 P1 ,   P2  ⋯  ,   P8 を通る3次曲線は一意に定まらず、無数にある

ということです。そして、さきほどの「相異なる8点を通る2つの3次曲線が2つとも9点目の点を通る」ということは、9点目が8点から決まる特別な点であることを示唆しています。そこで、相異なる8点を通る3次曲線が一般的にどういう式で表現できるかを考えます。8点の座標を、

P1 = x1 y1 P2 = x2 y2 P8 = x8 y8

とします。まず、3次曲線が P1 を通るということは、10個のパラメータは次の制約条件を満足しなければなりません。

x1 3 a + x1 2 y1 b + x1 y1 2 c + y1 3 d + x1 2 e + x1 y1 f + y1 2 g + x1 h +y1 i + j = 0

これは 10個の変数 aj についての線型方程式(1次方程式)なので、係数を変数の前に記述しました。同様にして、3次曲線が P2 から P8 を通ることから7個の制約条件が得られます。これらをまとめると、

{ x1 3 a + x1 2 y1 b +  ⋯  + y1 i + j = 0 x2 3 a + x2 2 y2 b +  ⋯  + y2 i + j = 0   ⋮ x8 3 a + x8 2 y8 b +  ⋯  + y8 i + j = 0  

の、合計8つの制約条件が得られます。8個の点を通る3次曲線の10個のパラメータは、この8つの制約条件(連立1次方程式)を満たさなければなりません。ということは、 10 - 8 = 2 で、これらのパラメータは、制約条件のない自由な2つのパラメータで表現できることになります。

たとえば ab を "2つのパラメータ" に選ぶと、残りの cj は、 αn a + βn b n=c  ⋯  j という「ab の1次式」で表現できます( αn βn は連立1次方程式の係数で決まる値)。しかしこれでは a=0 かつ b=0 のときに、すべてのパラメータが 0 という自明な解しか得られません。 x3 の項と x2y の項がない3次曲線はいくらでもありうるので、自明ではない解の中に a=0 b=0 となるものは当然あるはずです。つまり、 αn a + βn b の形は連立1次方程式の解の全部は表していません。

では、上記の連立1次方程式の「自明ではない解すべてを表す一般解」はどういう形でしょうか。それには8つの方程式を満たす独立な数値の組(=連立1次方程式の解)を2組用意します。つまり無数にある解の中から2つをピックアップし、それをベクトル表現で、

V 1 = a1 b1  ⋯  j1 V 2 = a2 b2  ⋯  j2

とします。"独立" とはこの場合、2つの数値群が異なった3次曲線を表現しているということです。そして、同時に 0 にはならない新たな2つのパラメータを導入します。それを λ1 ,   λ2 とすると、

λ1 V 1 + λ2 V 2

が連立1次方程式の一般解(不定解)になります。自由な2つのパラメータの1次式で表現されていて、8つの方程式を満たすことが明らかだからです。この一般解をもとに3次曲線の方程式を表現します。そこで、

f1 = a1 x3 + b1 x2y +  ⋯   ⋯  + h1 x + i1 y + j1

f2 = a2 x3 + b2 x2y +  ⋯   ⋯  + h2 x + i2 y + j2

の2つの関数を考えると、 f1 = 0 の3次曲線と f1 = 0 の3次曲線は、共に8点を通ります。従って、

λ1 f1 + λ2 f2 = 0

8点を通り、2つの自由なパラメータで表現された3次曲線群です。従って、これが P1 ,   P2  ⋯  ,   P8 を通るすべての3次曲線を表す一般形です。



以上を踏まえて命題 18.2 を検討します。命題を再掲すると、


2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする。

別の3次曲線 D が 9点のうちの8点、 P1 ,   P2  ⋯  ,   P8 を通るとき、D P9 も通る。


でした。この前半の2つの3次曲線の関数式を

C1  :  F1 = 0 C2  :  F2 = 0

とします。 F1 = 0 F2 = 0 も9点、 P1 ,   P2  ⋯  ,   P9 を通る3次曲線です。従って F1 = 0 F2 = 0 P1 ,   P2  ⋯  ,   P8 8点を通る2つの3次曲線でもある。ということは、 P1 ,   P2  ⋯  ,   P8 の8点を通るすべての3次曲線は、

F = λ1 F1 + λ2 F2 = 0

で表されます。従って、命題の後半に出てくる別の3次曲線 D P1 ,   P2  ⋯  ,   P8 の8点を通るとすると、D F = λ1 F1 + λ2 F2 = 0 で表現できます。

ここでよく考えてみると、3次曲線 F = 0 は9点目の P9 を通るのでした。従って D P9 を通ります。これで 18.2 が成り立つことが証明できました。以上を振り返ってまとめると次のようになります。


・ 9つの点を通る3次曲線は一意に決まる。
・ 8つの点を通る3次曲線なら無数に存在する。
・ 8つの点を通る2つの3次曲線が、2つとも9つ目のある(特別な)点 P を通るとしたら、8点を通るすべての3次曲線は P を通る。



18.2 を踏まえて、楕円曲線の加法群で結合則が成り立つことを証明します。ポイントは「相異なる3つの直線を "3次曲線" として扱う」ことです。この扱いがなぜ可能かと言うと、3つの直線を、

f1 = a1x + b1y + c1 = 0 f2 = a2x + b2y + c2 = 0 f3 = a3x + b3y + c3 = 0

としたとき、

FL = f1 · f2 · f3 = 0 で表される2次元平面上の点の集合は3つの直線を表しているが、3次曲線の一般形である

からです。もちろん、 FL = 0 の3次曲線の一般形は、係数 a b  ⋯  i j に特別の関係があります。だからこそ3つの直線を表現しているわけです(数学用語で言うと "退化した" 3次曲線)。しかし特別の関係があるとしても 18.2 を証明した議論の筋道には全く影響しません。このことを踏まえて結合則を証明すべき図11を再掲します。

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


証明すべきことは 18.1 の、


P+Q R を結ぶ直線と、 Q+R P を結ぶ直線の交点を T とすると、楕円曲線は T を通る。


でした。図11で、

C1 : 点線の3直線から成る3次曲線
C2 : 実線の3直線から成る3次曲線

とすると、 C1 (点線) と C2 (実線)は次の9つの点を通ります。

P1 O
P2 P
P3 Q
P4 R
P5 P Q
P6 Q R
P7 P + Q
P8 Q + R
T P + Q R を結ぶ直線と、 Q + R P を結ぶ直線の交点

9つの点を通るのはそういう風に作図したからです。一方、楕円曲線は T 以外の P1 P8 の8点を通ります。8点は楕円曲線上の点として作ったからです。T だけは違って、楕円曲線上の点として作ったのではなく2直線の交点です。しかし 18.2 によって楕円曲線は T も通る。これで、楕円曲線上の有理点が作る加法群で結合則が成り立つことの証明が完成しました。



零元を無限遠点にとる加法群ではどうなるでしょうか。この場合は「射影平面での3次曲線」を考える必要があります。射影平面での3次曲線の一般形は、

[射影平面における3次曲線の一般形]
AX3 + BX2Y + CXY2 + DY3 + EX2Z + FXYZ + GY2Z + HXZ2 + IYZ2 + JZ3 = 0

ですが、証明の筋道は xy平面と全く同じです。というのも、証明のコアのところは「10変数の連立1次方程式(方程式数が8)の不定解が、一般形でどう表現できるか」であり、曲線方程式の未知数が xy の2つであっても XYZ の3つであっても証明の論理に影響がないからです。

というわけで、楕円曲線暗号で実際に使われる「無限遠点を零元にした加法群」においても結合則が成り立つのでした。


19. パスカルの定理


最後に余談ですが、18.2 から証明できる別の定理があります。「パスカルの定理」です。これはパスカルが16歳のときに発表した「円錐曲線試論」にあります。最も一般的な形で言うと次の通りです。

19.1  パスカルの定理

円錐曲線上に異なる6点、 P1 P6 をとる。

直線 P1 P2 P4 P5 の交点を Q1
直線 P2 P3 P5 P6 の交点を Q2
直線 P3 P4 P6 P1 の交点を Q3

とすると、 Q1 ,   Q2 ,   Q3 は同一直線上にある。


これは美しい定理です。どんな円錐曲線かを言っていないし(円、楕円、放物線、双曲線)、円錐曲線上の6点の位置も、その順序も何も言ってない。それにもかかわらず「同一直線上にある」という、シンプルで強い断定が結論にくる ・・・・・・。個人的経験を言うと、高校生時代にこの定理を知ってその "不思議さ" が印象的だったことを覚えています。

この定理の例を図15と図16、図17に示します。 Q1 P7 Q2 P8 Q3 T と書きました。円錐曲線が円か楕円であり、6点を円・楕円の周上に順に(= 一周するように)とった場合には、パスカルの定理は、

円・楕円に内接する6角形の対辺が作る2直線の交点3つは同一直線上にある

と簡潔に表現できます(図15)。

図O:パスカルの定理(1).jpg
図15 パスカルの定理(1)

図P:パスカルの定理(2).jpg
図16 パスカルの定理(2)
楕円上の点の位置は図15と同じだが名前付けが違う。しかし3点が同一線上に並ぶのは同じである。このように6点は楕円上のどの位置にどの順序で配置してもよい。

図Q:パスカルの定理(3).jpg
図17 パスカルの定理(3)

定理の証明は次の通りです。3次曲線、 C1 ,   C2 ,   D を、

C1 赤色の3次曲線
C2 青色の3次曲線
D P7 P8 を(T とは関係なく)結んだ直線と円錐曲線が作る、黒色の3次曲線

とします。 C1 C2 は 、 P1 P8 T を通ります。そういう風に作図したからです。一方、D P1 P8 を通ります。そうすると 18.2 より DT も通ります。D P7 P8 を通るように作図しましたが、T を通るようには作図していません。それでも T を通る。

その T は、D の円錐曲線部分にはありません。なぜなら、T は直線 P3 P4 上に(ないしは直線 P6 P1 上に)ありますが、円錐曲線と直線の交点は高々2つであり、 P3 ,   P4 が(ないしは P6 ,   P1 が)すでに円錐曲線上にあるからです。従って TD の直線部分にあるしかない。これで証明が終わりました。

パスカルの定理のよくある証明は、円の場合に補助円を用いて証明し、それを "斜めから見たら" 楕円でも成り立つ、とするものです。しかしこの定理は、すべての円錐曲線(=2次曲線の一般形、 ax2 + bxy + cy2 + dx + ey + f = 0 で表される曲線)で成り立つことが上の証明から分かります。



楕円曲線暗号は「楕円曲線上の有理点による加法群」の上に作られた暗号ですが、

楕円曲線上の有理点で加法群を構成できることと、パスカルの定理が成り立つことには、意外にも共通の数学的理由がある

のでした。




nice!(0) 

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)