楕円曲線

math crypto

定義

$p$: 素数, $>3$

$$E:Y^{2}Z=X^3+aX{Z}^2+b{Z}^3(a,b\in {\mathbb{F}}_{p^n},{\Delta }_{E:=}4a^3+27b^2\ne 0)$$

または, その比

$$\begin{array}{rl}E({\mathbb{F}}_{p^n}):& =\{(X:Y:Z)\mid Y^{2}Z=X^3+aX{Z}^2+b{Z}^3,(X,Y,Z)\in {\mathbb{F}}_{p^n}\backslash \mathcal{O}\}\\ & =\{(x,y)\in ({\mathbb{F}}_{p^n}{)}^2\mid y^2=x^3+ax+b\}\cup \{\mathcal{O}=(0,1,0)\}\end{array}$$

を ${\mathbb{F}}_p$ 上の楕円曲線, 元を $E$ の ${\mathbb{F}}_p$-有理点という.

• $\mathcal{O}$ を無限遠点ということもある

定義

点, $P,Q\in E$:楕円曲線 に対して, $P\ast Q:=$ 直線 $PQ$ と $E$ の交点 ($\ne P,\ne Q$).
このとき,

• $P+Q:=\mathcal{O}\ast (P\ast Q)$
• ${}^{\forall }R\ast P=\mathcal{O}$ になるような $-P:=R$

とする.

命題

EC:$E:y^2=x^3+ax+b$ on $K$: 体, $P(x_1,y_1),Q(x_2,y_2)$ に対する演算.

1. $-P=(x_1,-y_1)$
2. $P+Q=(m^2-x_1-x_2,m(x_1-x_2)-y_1)$, $m:=\frac{y_2-y_1}{x_2-x_1}$
3. $P+P=(m^2-2x_1,m(x_1-x_2)-y_1),m:=\frac{dy}{dx}(x_1,y_1)=\frac{{2x_1}^2+\alpha }{2y_1}$