2017-06-27

curve25519とed25519の同等性

ed25519

curve25519とは、
$\nu^{2} = \mu^{3} + 486662\mu^{2} + \mu$
のことであり、
ed25519とは、
$x^{2} + y^{2} = 1 +\frac {121665}{121666} x^{2}y^{2}$
のことである。これは単純な変数の置き換えで同等性が示せる。
ただし、ed25519の方が加法定義で場合分けをする必要がなく、扱いやすい。

$d = 486662$ とし、 $\frac {d - 2}{d + 2} = \frac {121665} {121666}$ とする。

$\nu = \sqrt{d} \frac {\mu} {x}$
$\mu = \frac {1+y} {1-y}$
を代入して計算すると、
$(2+d)x^{2} + dy^{2} = d + (d-2)x^{2}y^{2}$
となる。
xを $x \sqrt{ \frac {d}{d+2}}$ で置き換えると。 $x^{2} + y^{2} = 1 + \frac {d-2} {d+2}x^{2}y^{2}$
が得られる。

2017-06-22

RSA暗号の原理を理解するための数学知識

暗号

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、
色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

まずモジュラー演算記号(mod)を覚えましょう。
$a = b \mod n$
これは整数aを整数nで割った余りとbを整数nで割った余りが等しいことを表します。
例:
$9 \mod 4 = 1$
$107 \mod 10 = 7$

モジュラー演算には以下の性質があります。

$a = b \mod n, \\ c = d \mod n$ 　

のとき、

$a + c = b + d \mod n$

$a * c = b * d \mod n$

$a^{m} = b^{m} \mod n$

である。

$ef = eg \mod n$ で gcd(e, n) = 1 ならば
$f = g \mod n$
である。
ここで gcd(a, b) は整数a,bの最大公約数(Greatest Common Divisor)を表します。

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、 $a^{\phi(n)} = 1 \mod n$ である。
$\phi(n)$ は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 $\phi(p) = p-1$ となる。

また、p, qが素数の場合、２つをかけた合成数 pq に対して $\phi(pq) = (p-1)(q-1)$ が成り立つ。

RSA暗号の世界 – まいとう情報通信研究会

ＲＳＡのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
$m = n \mod p$
$m = n \mod q$
であれば
$m = n \mod pq$ 　　である。

中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語

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}$ が残る。あとは自明である。