密码学学习笔记——筑基篇·卷五（椭圆曲线）

椭圆曲线

椭圆曲线(elliptic curve)

定义：椭圆曲线是一条由方程$y^2=x^3+ax+b$给定的曲线，其中 $a,b\in F,char(F)\neq 2,3$，，并满足 $\Delta=4a^3+27b^2\neq0$ 。
丢番图曲线：$y^2=x^3-x+9$ ($a=-1,b=9)$, ($x,y)\in\mathbb{Q}^2$

$\Delta\neq0$:非奇异(non-singular),光滑，$x^3+ax+b$无重根
$\Delta=0$:奇异 (singular),不光滑，$x^3+ax+b$有重根(奇异点)

补充：有重根说明多项式和它的导数存在公共根

前两个叫结点(node)，第三个叫尖点(cusp)

奇异点：

该点处曲线不可微分，即奇异点处无法作切线(切线值无定义)

只要椭圆曲线是奇异的，奇异点就一定在x轴上

当点的集合包含奇异点时无法构成群，因为奇异点处无法作切线，故讨论椭圆曲线时排除奇异的情况

奇异点到原点的距离是左根到原点的距离的一半

判别式:

$\Delta<0$时：

图像有一个组成部分

$x^3+ax+b=0$只有唯一的实数根

$\Delta>0$时：

图像有两个组成部分

$x^3+ax+b=0$有三个不同的实数根

椭圆曲线：魏尔斯特拉斯方程 $y^2=x^3+ax+b$定义在域上的一条光滑射影亏格(genus)为1的曲线。

椭圆：亏格为0的曲线。

椭圆曲线上的点

$E=\{(x,y)|y^2=x^3+ax+b\}\cup\{O\}$

椭圆曲线上的点通常用P、Q或R表示
O:无穷远点(point at infinity)

加法

几何表示

群：$(E,+)$
加法运算+: $E$里点和点之间的加法(并非简单的坐标间加法，而是一种几何的方法)

$(E,+)$加法阿贝尔群对于$\forall P,Q,R\in E$,都有

封闭性：$P+Q\in E$
结合律：$(P+Q)+R=P+(Q+R)$
单位元：$P+O=O+P=P$ (无穷远点$O$是单位元)
逆元：$P+(-P)=O$ ($P=(x_1,y_1),-P=(x_1,-y_1)$)
交换律：$P+Q=Q+P$

椭圆曲线三个点在一条直线上时，三个相加等于无穷远点

4种情况:

$nP:=P+P+\cdots+P$
$0P=O,\quad(-n)P=-(nP)$

点P的阶：$\text{满足 }nP=O\text{的最小正整数}n$

坐标表示

$P=(x_1,y_1),Q=(x_2,y_2)$,则$P+Q$ 有四种情况:

$P\neq Q$ 且$x_1\neq x_2$
$P\neq Q$ 且$x_1 = x_2 : P+Q=O$
$P=Q$且$y_1\neq0$
$P=Q$且$y_1=0:P+P=2P=O$

$\text{设 }P=(x_1,y_1),Q=(x_2,y_2),\quad\text{直线 }L\text{方程为 }y=\lambda x+c,\text{ 则}\\\lambda=\begin{cases}\dfrac{y_2-y_1}{x_2-x_1},&P\neq Q\text{ 且 }x_1\neq x_2\\\dfrac{3x_1^2+a}{2y_1},&P=Q\text{ 且 }y_1\neq0(隐函数求导算斜率)\end{cases}$ $c=y_1-\lambda x_1=\begin{cases}\frac{y_1x_2-y_2x_1}{x_2-x_1},&\quad P\neq Q\text{ 且 }x_1\neq x_2\\\frac{-x_1^3+ax_1+2b}{2y_1},&\quad P=Q\text{ 且 }y_1\neq0\end{cases}$ $\begin{gathered} (\lambda x+c)^{2}=x^{3}+ax+b \\ f(x)=x^{3}+ax+b-(\lambda x+c)^{2} \\ \text{设 }R=(x_3,y_3),\text{则} \\ f(x)=(x-x_{1})(x-x_{2})(x-x_{3}) \\ x^3+ax+b-(\lambda x+c)^2=(x-x_1)(x-x_2)(x-x_3)\end{gathered}$ $\begin{aligned}&x^3-\lambda^2x^2-2\lambda cx+ax+b-c^2\\&=x^3-(x_1+x_2+x_3)x^2+(x_1x_2+x_1x_3+x_2x_3)x-x_1x_2x_3\\&\lambda^2=x_1+x_2+x_3\Longrightarrow x_3=\lambda^2-x_1-x_2\\&y_{3}=\lambda x_{3}+c\end{aligned}$ $\begin{aligned} P+Q=-R& =(x_3,-y_3)=(\lambda^2-x_1-x_2,-\lambda x_3-c) \\ &=\left(\lambda^2-x_1-x_2,-\lambda^3+(x_1+x_2)\lambda-c\right) \end{aligned}$

点的加法算法

$P=(x_1,y_1),Q=(x_2,y_2)$,椭圆曲线为$x^3+ax+b:$

if $\left(P\neq Q\mathrm{~and~}x_1=x_2\right)$or$\left(P=Q\mathrm{~and~}y_1=0\right)$

return $O$
if $P\neq Q$ and $x_1\neq x_2$， $\lambda=\frac{y_2-y_1}{x_2-x_1}\:,\:c=\frac{y_1x_2-y_2x_1}{x_2-x_1}$

else $\lambda=\frac{3x_{1}^{2}+a}{2y_{1}},c=\frac{-x_{1}^{3}+ax_{1}+2b}{2y_{1}}$$(即P=Q$ and $y_1\neq0)$
return $(x_3,-y_3)=(\lambda^2-x_1-x_2,-\lambda^3+(x_1+x_2)\lambda-c)$

定理 (Poincaré,约1900年):设$F$是域，椭圆曲线方程为
$x^3+ax+b,a,b\in F$,及$E=\begin{Bmatrix}(x,y)&x^3+ax+b\end{Bmatrix}\cup\begin{Bmatrix}0\end{Bmatrix}$
设$E(F)=\{(x,y)\in E\mid x,y\in F\}\cup\{O\}$,则$E(F)$是$E$的子群

无穷远点

仿射平面：仿射坐标$(x,y)\in A^2(F)$
射影平面：射影坐标$(X,Y,Z)\in P^2(F)$
$(0,0,0)\notin P^2(F)$
转换公式：$x=\frac{X}{Z},y=\frac{Y}{Z}$

例：仿射坐标 $(x,y)=(3,2)$
射影坐标 $(X{:}Y{:}Z)=(3{:}2{:}1)$ （X,Y,Z）=(3Z,2Z,Z)

仿射点：坐标形式为$(X:Y:1)$的点

无穷远点的坐标

$x=\frac X0,y=\frac Y0$

仿射坐标(无法表示)$\longleftarrow$射影坐标$(X:Y:0)$

无穷远线(line at infinity)

无穷远点$(X:Y:0)$
无穷远线：$(X:1:0)$和$(1:0:0)$形成的直线,嵌在射影平面用$P^1(F)$表示

有限域上的椭圆曲线

$Z_p:$ 椭圆曲线密码常用的有限域 $(p>3$是素数)

$F_p\cong Z_p$

定义在$F_p$上的椭圆曲线(坐标运算都是模$p$的)

方程：$y^2\equiv x^3+ax+b\pmod p$),其中$a,b\in F_p$是常数

满足：$\Delta=4a^3+27b^2\not\equiv0\pmod p$。

点：$(x,y)\in F_p\times F_p$
群：$E(F_p)$

$y^2\equiv x^3+ax+b\pmod p$

$|E(F_p)|\leq2p+1(\text{每个}x\text{对应两个}y\text{,而}x\text{的取值不超过}p\text{个},此处加上无穷远点)$

定理 (Hasse,1933): $p+1-2\sqrt{p}\leq\left|E(F_p)\right|\leq p+1+2\sqrt{p}$
Schoof 算法：计算 $|E(F_p)|$的大小
(时间复杂度：$O((logp)^8)$个比特运算和$\mathcal{O}((logp)^6)$个$\mathbb{Z}_p$中运算)

定理：$E(F_p)$是循环群或同构于两个循环群的笛卡尔乘积$(p>3)$
$E(F_p)\cong Z_{n_2}\times Z_{n_1}$

$E(F_p)\cong Z_{n_2}\times Z_{n_1}$
$n_2\mid n_1,n_2\mid(p-1)$

定理:$|E(F_p)|$是素数或两个不同素数乘积,则$E(F_p)$是循环群$(p>3)$

点压缩(point compress)

$(x,y)转为存储(x,y\ mod\ 2),即y是奇数存储(x,1),y是偶数存储(x,0),y是偶数$

点解压(point decompress)

$(x,y\ mod\ 2)$
$y^2=x^3+ax+b\ mod\ p$
$y=\pm\sqrt{x^3+ax+b}\:mod\:p\longrightarrow y_1=y，y_2=p-y$

同源(isogeny)

椭圆曲线的结构特点

几何结构(光滑射影曲线)
代数结构(点群$E$)

同源是一种保持椭圆曲线结构的映射

$\text{同源 }\phi{:}E(K)\to E^{\prime}(K)\text{ 是个群同态(满同态)(}K\text{是域)}$

$\phi(O)=O^{\prime}$

自同态 (endomorphism): 椭圆曲线到自身的同源
自同构 (automorphism): 同源是自同态，也是同构

注意：自同态未必是同源，比如：$\forall P\in E(K),\phi(P)=O$ ,是自同态，但不是同源(因为不是满同态)

例：$\phi{:}E(K)\to E(K)$，记$\phi:=[n]$
$P\mapsto nP$
自同态 $(n=0$时不是同源)
$n\neq0:$同源
$n=\pm1:$自同构

对于大多数椭圆曲线，唯一的自同态就是这种形式的同源

同源的标准形式

设 $\phi{:}E(K)\to E^{\prime}(K)$ 是同源 $(K$是域),点$P=(x,y)\in E(K)$,
则仿射坐标下，$\phi$具有以下标准形式(standard form):

$\phi(x,y)=(\frac{u(x)}{v(x)},\frac{s(x)}{t(x)}y)$

其中$u(x),v(x),s(x),t(x)\in K[X],u(x),v(x)$互素，$s(x),t(x)$互素。

推论：设$E(K)$ 的方程为 $y^2= x^3+ ax+ b$, $f( x) = x^3+ ax+b$,则：
$v^3(x)\mid t^2(x)$
$t^2(x)\mid v^3(x)f(x)$
同源$\phi{:}E(K)\to E^{\prime}(K)$是同源 (K是域)
$\phi(x,y)=(\frac{u(x)}{v(x)},\frac{s(x)}{t(x)}y)$

弗罗贝尼乌斯自同态(Frobenius endomorphism)

$\pi{:}E(F_q)\to E(F_q)$
$(X{:}Y{:}Z)\mapsto(X^q:Y^q:Z^q)$

$E(F_q)$的方程$y^2=x^3+ax+b,a,b\in F_q,(x,y)\in F_q^2$
$\pi(x,y)=(x^q,\:(x^3+ax+b)^{\frac{q-1}2}y)$

$u(x)=x^q，v(x)=e，s(x)=(x^3+ax+b)^{\frac{q-1}2}，t(x)=e$

注：若$F_q$的特征是素数$p$
$\boldsymbol{\pi}^{\prime}:E(F_q)\to E^{\prime}(F_q)$
$(X{:}Y{:}Z)\mapsto(X^p{:}Y^p{:}Z^p)$
同源(未必是自同态)

定理 (Sato-Tate定理)：$\left|E(F_q)\right|=\left|E^{\prime}(F_q)\right|,当且仅当,这两个椭圆曲线同源。$

同源的度(degree of isogeny)

定义(同源的度): $\phi(x,y)=(\frac {u(x)}{v(x)},\frac{s(x)}{t(x)}y)$是标准形式，同源$\phi$的度是
$deg(\phi):=\max(deg(u(x)),deg(v(x)))。$

同源的可分性(separability)

定义(可分性): $\phi(x,y)=(\frac {u(x)}{v(x)},\frac{s(x)}{t(x)}y)$是标准形式，
如果 $(\frac{u(x)}{v(x)})^{\prime}\neq\theta$,则称$\phi$是可分的(separable);
如果 ($\frac{u(x)}{v(x)})^{\prime}=\theta$,则称$\phi$是不可分的 (inseparable)。

同源的分解

任何特征大于0的同源都可以分解成可分同源和不可分同源的复合

引理1：域$K$的特征是$p$。设多项式 $u(x),v(x)\in K[X]$互素，则
$(\frac{u(x)}{v(x)})^{\prime}=\theta\Leftrightarrow u^{\prime}(x)=v^{\prime}(x)=\theta$
$\Leftrightarrow u(x)=f(x^{p}),v(x)=g(x^{p})\:,$
其中$f(x)$,g$(x)\in K[X]$

引理2：$\phi{:}E(K)\to E^{\prime}(K)$是不可分同源，$K$ 的特征是$p$ 。则标准形式下，有

$\phi(x,y)=\phi(a(x^p),b(x^p)y^p)\:,$

其中$a(x),b(x)\in K[X]$

性质：同源$\phi{:}E(K)\to E^{\prime}(K)$,$K$的特征是$p>0$,则有
$\phi=\alpha\circ(\pi^{\prime})^n,$
其中 $\alpha$是可分同源，$\pi^{\prime}$是$p$ -power 弗罗贝尼乌斯映射，$n\geq0$。
注：$\pi^\prime:(X{:}Y{:}Z)\mapsto(X^p{:}Y^p{:}Z^p)$

$\begin{aligned}&&&\bullet\phi 是可分同演:设n=0,\alpha=\alpha,\phi,则满足\phi=\alpha\circ(\pi^{\prime})^{n},\\&&&\bullet\phi 是不可分同源:根据引理2。有\phi(x,y)=\phi(a(x^p),b(x^p)y^p)。\\&&&\text{设 }\alpha_1(x,y):=(a(x),b(x)y),\text{ 有 }\phi=\alpha_1\circ\pi^{\prime}。\\&&&\text{如果 }\alpha_1\text{是可分同源,则满足 }\phi=\alpha\circ(\pi^{\prime})^n\quad(n=1,\alpha:=\alpha_1);\\&&&\text{如果 }\alpha_1\text{ 是不可分同源,根据引理2, 有}\\&&&\alpha_1(x,y)=\alpha_1(a_1(x^p),b_1(x^p))y^n)。\\&&&\text{设 }\alpha_2(x,y)=(\alpha_1(x),b_1(x)),\text{ 有 }\alpha_1=\alpha_2\circ\pi^{\prime},\\&&&\text{则 }\phi(x,y)=\alpha_1\circ\pi^{\prime}=\alpha_2\circ\pi^{\prime}\circ\pi^{\prime}=\alpha_2\circ(\pi^{\prime})^2。\\&&&\text{依此类推,有 }\phi=\alpha_n\circ(\pi^{\prime})^n\text{。令}\alpha:=\alpha_n,\text{ 有}\phi=\alpha\circ(\pi^{\prime})^n\text{。}\end{aligned}$

度的分解

定义(度的分解):对于同源的分解 $\phi=\alpha\circ(\pi^{\prime})^n$,设$deg_s\phi$是其可
分度 (separable degree), $deg_i\phi$是其不可分度 (inseparable
degree),则
$deg_s\phi:=deg\alpha,\:deg_i\phi:=p^n,$
而且总是有
$deg\phi=(deg_s\phi)\cdot(deg_i\phi)=deg\ \alpha\cdot p^n$

例： $\begin{aligned}&\phi=(\pi^{\prime})^n\\&(\pi^{\prime})^n\text{的特征大于0,是可分解的。}\\&\text{设 }(\pi^{\prime})^n=\alpha\circ(\pi^{\prime})^n\text{,则有 }\alpha:P\mapsto P。\\&\text{所以,}deg\alpha=1\text{。故而,}deg_s\pi^{\prime}=1。\end{aligned}$

定义(纯不可分同源):可分度是1的同源,叫纯不可分的(purely inseparable)

性质:纯不可分同源的度必然是$p^n$的形式(反之,未必成立)。

$deg\phi=1$ (同构)时，则$\phi$具有如下性质：

$\phi$是可分的(即$(\frac u(x){v(x)})^{\prime}\neq0)$
$\phi$也是纯不可分的 (即$deg_s\not\phi=1)$

代数闭包(algebraic closure)

同源 $\phi{:}E(K)\to E^{\prime}(K)$诱导了一个$E(\overline{K})\to E^{\prime}(\overline{K})$的群同态。

例：$E(F_q)$上的弗罗贝尼乌斯自同态$\pi{:}\left(X{:}Y{:}Z\right)\mapsto\left(X^q{:}Y^q{:}Z^q\right)$,
诱导了一个$E(\overline{F}_q)\to E^{\prime}(\overline{F}_q)$的群同构。

同源核(isogeny kernel)

本质上是同源的同态核

第一同源核定理(First isogeny-kernel theorem)

定理：同源$\phi=\alpha$ o$(\pi^{\prime})^n$,则$|\ker\phi|=deg(\alpha)$
(同源核的阶等于其可分度)

$|\mathrm{Ker~}\phi|=|\mathrm{Ker~}\alpha|=|S|=deg\left(g\right)=deg\left(\alpha\right)$

例：$deg(\alpha)=3$,则$|\ker\phi|=3$

第二同源核定理(Second isogeny-kernel theorem)

定理：设$E(K)$是椭圆曲线，$G$是$E(\bar{K})$的有限子群，则存在椭圆曲线$E^\prime$,以及可分同源$\phi:E\to E^{\prime}$,使得 $Ker \phi=G$,且$E^\prime$和$\phi$在同构意义下是唯一的。

推论:度是合数的同源可以被分解成一系列度是素数的同源。

椭圆曲线的自同态环

同态群(groups of homomorphisms)

设椭圆曲线$E$和$E^{\prime}$定义在域$K$上，定义集合

$Hom(E,E^{\prime}):=\{\text{所有同源}\alpha{:}E\to E^{\prime}\}\cup\{[0]\}$

$Hom(E,E^{\prime})$上的加法运算：对于任意 $\alpha,\beta\in Hom(E,E^{\prime})$,任意点
$P\in E(\overline{K}),\alpha+\beta$定义为$(\alpha+\beta)(P):=\alpha(P)+\beta(P)$

构成加法阿贝尔群，加法单位元：$[0]:P\mapsto 0P(=O)$

引理1

设 $\alpha, \beta \in Hom(E,E’)$，对于所有点 $P \in E(\overline{K})$，如果 $\alpha(P) = \beta(P)$，则 $\alpha = \beta$

引理2

对于所有 $n \in Z$ 和 $\alpha \in Hom(E,E’)$，有 $[n] \circ \alpha = n\alpha = \alpha \circ [n].$

分配律

对于$\alpha,\beta\in Ho\boldsymbol{m}(E,E^{\prime}),\phi\in Ho\boldsymbol{m}(E^{\prime},E^{\prime\prime})$,有
$\phi\circ(\alpha+\beta)=\phi\circ\alpha+\phi\circ\beta$

对于$\phi\in Ho\boldsymbol{m}(E,E^{\prime}),\boldsymbol{\alpha},\beta\in H\boldsymbol{om}(E^{\prime},E^{\prime\prime})$,有
$(\alpha+\beta)\circ\phi=\alpha\circ\phi+\beta\circ\phi$

消去律

消去律：设 $\boldsymbol{\alpha},\boldsymbol{\beta}{:}E\to E^{\prime},\boldsymbol{\phi}{:}E^{\prime}\to E^{\prime\prime}$是同源，有

$\phi\circ\alpha=\phi\circ\beta\quad\Longrightarrow\quad\alpha=\beta$

设 $\phi{:}E\longrightarrow E^{\prime},\boldsymbol{\alpha},\boldsymbol{\beta}{:}E^{\prime}\to E^{\prime\prime}$是同源，有

$\alpha\circ\phi=\beta\circ\phi\Rightarrow\alpha=\beta$

对偶同源

定义(对偶同源):

设同源 $\phi:E \rightarrow E’$ , 其度为 $deg(\phi)$ , 则 $\phi$ 唯一的对偶同源为 $\widehat{\phi}$ , 满足

$\widehat{\phi} \circ \phi = [deg(\phi)]$

$\text{另外,定义}[\widehat0]:=[0]$

例: 设 $deg(\phi) = 3$, 则 $\widehat{\phi} \circ \phi = [deg(\phi)] = [3]$, 即对于任意点 $P \in E$, 有 $\widehat{\phi} \circ \phi(P) = \widehat{\phi}(\phi(P)) = [3](P) = 3P$

性质1：如果 $\widehat{\phi} \circ \phi = [\deg(\phi)]$，那么 $\phi \circ \widehat{\phi} = [\deg(\phi)]$，也即 $\widehat{\widehat{\phi}} = \phi$

证明：$(\phi \circ \widehat{\phi}) \circ \phi = \phi \circ (\widehat{\phi} \circ \phi)$ （结合律）

$= \phi \circ [\deg(\phi)]$ （对偶同源定义）

$= [\deg(\phi)] \circ \phi$ （《同态群》引理2）

则 $\phi \circ \widehat{\phi} = [\deg(\phi)]$ （消去律）

性质2：对于任意 $n\in\mathbb{Z}$,有$[\widehat n]=[n]$
证明：

$\begin{aligned}[n]\circ[n]&=[n^2]\\&=[deg([n])]\end{aligned}$

性质3：对于任意 $\alpha, \beta \in Hom(E,E’)$，有 $\widehat{\alpha + \beta} = \widehat{\alpha} + \widehat{\beta}$

性质4：对于任意$\alpha\in Hom(E^{\prime},E^{\prime\prime}),\beta\in Hom(E,E^{\prime})$,有

$\widehat{\alpha\circ\beta}=\widehat{\beta}\circ\widehat{\alpha}$

$\alpha\circ\beta$相当于$\phi$
$\widehat{\beta}\circ\widehat{\alpha}$相当于$\widehat{\phi}$
$[deg(\alpha\circ\beta)]$相当于$[deg(\phi)]$

筑基篇·椭圆曲线