2017-06-19

edward曲線における加法

ed25519

Edward曲線 $x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}$

において、曲線上の２つの点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ の加算後の点を次のように定義する。

$\displaystyle X = \frac {1} {a} \cdot \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + x_{1} x_{2} y_{1} y_{2}}$

$\displaystyle Y = \frac {1} {a} \cdot \frac {y_{1} y_{2} - x_{1} x_{2}} {1 - x_{1} x_{2} y_{1} y_{2}}$

この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。　　

$A = X^{2} + Y^{2} - a^{2}X^{2}Y^{2}$ を計算し、 $a^{2}$ に等しくなることを示す方針で行く。

代入すると $\displaystyle a^{2} A = \frac {1} {(1 + x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ (x_{1}y_{2} + x_{2}y_{1})^{2}(1- x_{1}x_{2}y_{1}y_{2})^{2} \\ + (y_{1}y_{2} - x_{1}x_{2})^{2} (1 + x_{1} x_{2} y_{1} y_{2})^{2} \\ - (x_{1}y_{2} + x_{2}y_{1})^{2} (y_{1}y_{2} - x_{1}x_{2})^{2})$

ここで、

$\displaystyle a^{2}A(1 - x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2})^{2} = B + C + D$ と置く。

B + C + Dを全て展開し、 $x_{1}, x_{2}, y_{1}, y_{2}$ の順番で並べると、７つほどペアが消える。

$B + C + D = x_{1}^{2}y_{2}^{2} + x_{2}^{2}y_{1}^{2} + x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} + x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} \\ + y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2} - 4 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} + x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} \\ - x_{1}^{2}y_{1}^{2}y_{2}^{4} - x_{2}^{2}y_{1}^{4}y_{2}^{2} - x_{1}^{4}x_{2}^{2}y_{2}^{2} - x_{1}^{2}x_{2}^{4}y_{1}^{2} \\ = E_{4} + E_{8} + E_{12}$

ここで $E_{i}$ はx,yの個数を表すが、それぞれ別々に計算してゆくと、 $E_{4}, E_{8}, E_{12}$ には、 $x_{1}^{2} + y_{1}^{2}$ , $x_{2}^{2} + y_{2}^{2}$ が２つ以上出てくるので、 $x_{1}^{2} + y_{1}^{2} = a^{2} ( 1 + x_{1}^2 y_{1}^2)$
$x_{2}^{2} + y_{2}^{2} = a^{2} ( 1 + x_{2}^2 y_{2}^2)$ に置き換える。

ここで、 $\frac {1} {a^{4}} (E_{4} + E_{8} + E_{12})$ を計算すると、５つほどペアが消え、 $1 - 2 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}$ が残る。あとは自明である。

2017-06-18

エドワード曲線とツイストエドワード曲線の形

ed25519

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf)

から、エドワード曲線と名付けられた

$x^{2} + y^{2} = a^{2}(1 + x^{2} y^{2})$

がどのような形をしているのか見てみましょう。

まずはa=1.0
$x^{2} + y ^{2} = 1 + x^{2} y^{2}$

2本の直線になってしまいました。。

次にa=1.1
$x^{2} + y^{2} = {1.1}^{2}(1 + x^{2} y^{2})$

次にa=0.9
$x^{2} + y^{2} = {0.9}^{2}(1 + x^{2} y^{2})$

おっと丸くなりました。

次に、ツイストエドワード曲線(http://eprint.iacr.org/2008/013.pdf)

$a x^{2} + y^{2} = 1 + d x^{2} y^{2}$

をみてみましょう。

a=1, d= -50
$x^{2} + y^{2} = 1 - 50 x^{2} y^{2}$

a=-1, d=-50
$- x^{2} + y^{2} = 1 - 50 x^{2} y^{2}$

a=-1, d=5
$- x^{2} + y^{2} = 1 + 5 x^{2} y^{2}$

$a=-1, d = - 0.7$
$- x^{2} + y^{2} = 1 -0.7 x^{2} y^{2}$

2017-06-18

楕円曲線の形

暗号

楕円曲線の一般的な形は以下のように表せます。

$y^{2} = x^{3} + ax^{2} + bx + c$

暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。
特異でない形のものは２つのパターンに分けられます。
1) yが0の時のxの値が３つある場合
2) yが0の時のxの値が１つだけしかない場合
それぞれの例を挙げます。

1) $y^{2} = x^{3} + x^{2} - x$

これは、左の曲線が閉じているパターンです。

2) $y^{2} = x^{3} + x^{2} + 1$

これは開いているパターン。

このグラフのイメージを掴んでおくと、楕円曲線の理論がとても理解しやすくなります。

a) この曲線上の２つの点を結ぶ直線を引くと、曲線と交わる３番目の点は必ず存在します。
b) xをプラスの無限大に持っていくと、yがプラスの無限大とマイナスの無限大に近づきます。

楕円曲線論入門

作者: J. H.シルヴァーマン,J.テイト,Joseph H. Silverman,John Tate,足立恒雄,木田雅成,小松啓一,田谷久雄
出版社/メーカー: 丸善出版
発売日: 2012/08/25
メディア: 単行本
この商品を含むブログを見る

2017-06-17

群、体、有限体の定義

群環体

群(group)の定義

ある要素の集まりに対して、一つの演算規則 f を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, c を要素とします。

1) 全ての要素に対して、結合法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
2) 全ての要素に対して、単位元が存在する
3) 全ての要素に対して、逆元が存在する

体(field)の定義

ある要素の集まりに対して、加算 f と乗算 g を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, cを要素とします。
1) 加算について可換群(単位元と逆元が存在する)
2) 乗算について可換群(単位元と逆元が存在する)
3) 加算、乗算について分配法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
g(f(a, b), c) = g(a, g(b, c))

体の元の数を位数と呼びます。

例1:

整数の集合は体ではありません。
なぜなら 3 を乗算する演算の逆元は 1/3 だが、これは整数ではなく有理数になってしまうから。

例2:

有理数の集合は体です。

有限体

整数の集合に対して、
加算を「整数の加算後に素数pで割った余り」
乗算を「整数の乗算後に素数pで割った余り」と定義した場合、体となります。
つまり、全ての要素に対して逆元が存在します。
元の数は p となります。
この体を $F_{p}$ と書きます。

2017-06-10

離散対数問題(Discrete Logarithm Problem)とは

暗号

RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、
楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。

離散対数問題(DLP)をここで解説してみます。

p : 素数

これは説明不要ですね。 2,3,5,7,11,...のように自分自身の値未満の数で割り切れる値が1だけな正の整数値です。

mod : モジュラ演算

a mod b = c

整数aを整数bで割った余りがcであることを表します。例えば、

7を3で割った余りは1
7 mod 3 = 1

8を3で割った余りは2
8 mod 3 = 2

9を3で割った余りは0
9 mod 3 = 0

余りは必ず、0からb-1の値のどれかになる性質があります。

原始根

3以上の素数 p と 1 以上 p-1 以下の整数 r が以下の性質を満たすとき r を mod p の原始根と呼びます。
「 $r, r^{2}, ⋯, r^{p−2}$ のいずれもが p で割って余り 1 でない。」

p=13の場合、原始根は2,6,7,11であることが知られていますが、原始根2の場合で計算してみます。

$2 \bmod 13 = 2$

$2^{2} \bmod 13 = 4$

$2^{3} \bmod 13 = 8$

$2^{4} \bmod 13 = 16 \bmod 13 = 3$

$2^{5} \bmod 13 = 32 \bmod 13 = 6$

$2^{6} \bmod 13 = 64 \bmod 13 = 12$

$2^{7} \bmod 13 = 128 \bmod 13 = 11$

$2^{8} \bmod 13 = 256 \bmod 13 = 9$

$2^{9} \bmod 13 = 512 \bmod 13 = 5$

$2^{10} \bmod 13 = 1024 \bmod 13 =10$

$2^{11} \bmod 13 = 2048 \bmod 13 = 7$

余りがいずれも1ではないことは確認できましたが、それ以外に何か気がついたでしょうか？
右辺の計算結果が2から12までの数字になっていて重複がないですね。
さらに、対応に規則性はないように見えますね。

同様に、原始根6の場合でも試してみましょう。

$6 \bmod 13 = 6$

$6^{2} \bmod 13 = 36 \bmod 13 = 10$

$6^{3} \bmod 13 = 216 \bmod 13 = 8$

$6^{4} \bmod 13 = 1296 \bmod 13 = 9$

$6^{5} \bmod 13 = 7776 \bmod 13 = 2$

$6^{6} \bmod 13 = 46656 \bmod 13 = 12$

$6^{7} \bmod 13 = 279936 \bmod 13 = 7$

$6^{8} \bmod 13 = 1679616 \bmod 13 = 3$

$6^{9} \bmod 13 = 10077696 \bmod 13 = 5$

$6^{10} \bmod 13 = 60466176 \bmod 13 = 4$

$6^{11} \bmod 13 = 362797056 \bmod 13 = 11$

原始根6の場合もやはり重複していませんし、対応に規則性も見えません。

原始根を使うと、この数式の右辺の値(=2からp-1までの値)と、左辺のべき乗の値が一対一対応させられるという性質があります。つまり、

p:素数、g:原始根、A: { 2, 3, 4, ..., p-1 }(右辺値)、r: { 1, 2, 3, ..., p-2 } (べき乗値)
$g^{r} \bmod p = A$

と書いた時に、rとAが一対一対応するということになります。

ここで計算したように、Aの値を与えた時に、対応するrの値を求めるには、べき乗計算とモジュラ計算を、
(計算量が少なくなるように)次数の少ない方から順番に計算し、余りがAになるまで繰り返す必要があります。
これを簡単に計算する一般的な方法は見つかっていないそうです。
これが、離散対数問題と呼ばれるものです。

Aの値を与えた時に、べき乗の値を返す関数を一般に対数関数と呼びますが、
ここで、rのことを底gについてのAの離散対数と呼びます。

一対一対応する値のペアがあり、計算が難しいということは、暗号に使えそうな気がしてきますね。

ここでやった単純なモジュラ演算の部分を楕円曲線上の演算に置き換えたものが、楕円曲線上のDLPというものです。

楕円曲線における離散対数問題(ECDLP)についてはこちら

楕円曲線における離散対数問題 - Pebble Coding

参考:
原始根の定義と具体例（高校生向け） | 高校数学の美しい物語