ECCNotes2

huangx607087学习ECC的笔记2

0. About

这一系列笔记主要介绍椭圆曲线密码学的知识,接着笔记1继续扩展。

这一笔记本来2.22就创建开始写了,咕到了3月4日才勉强提交,哎(准备补充笔记3了。笔记3不会接着笔记2继续讲。。。。。

6.椭圆曲线上的双线性对

在线性代数中,向量空间$R^n$中两个向量$\vec v,\vec w$,它们的数量积就是它们对应分量的积之和。

现在有两个$n$维行向量$\vec v,\vec w$和一个$n$阶方阵$A$,那么我们可以定义一个函数$\beta(\vec v,\vec w)=\vec vA\vec w^T$。其中$\vec w^T$中的上标$T$表示转置,将行向量化为列向量以满足矩阵乘法的规则。当然有
$$
\beta(a_1\vec v_1+a_2\vec v_2,\vec w)=a_1\beta(\vec v_1,\vec w)+a_2\beta(\vec v_2,\vec w)
$$

$$
\beta(\vec v,b_1\vec w_1+b_2\vec w_2)=b_1\beta(\vec v,\vec w_1)+a_2\beta(\vec v,\vec w_2)
$$

还有一种双线性配对是$R^2$上的行列式映射。 因此,如果$\vec v=(v_1,v_2)$和$\vec w=(w_1,w_2)$,那么有$\delta(\vec v,\vec w)=v_1w_2-v_2w_1$,也就是将这两个行向量构造出的矩阵的行列式的值。

我们在本节中讨论的双线性对是相似的,因为它们以椭圆曲线上的两个点作为输入,并给出一个数字作为输出。 然而,双线性条件略有不同,因为输出值是有限场的非零元素,所以用乘积代替刚才最上面两个线性组合右边的和。

椭圆曲线上的双线性对具有许多重要的密码学应用。 对于这些应用程序中的大多数,有必要使用有限域的素数阶$GF(p^k)$。

6x01 椭圆曲线上的有限阶点

我们首先简要描述椭圆曲线上的有限阶点

定义:当椭圆曲线$E$上的一点$P$,满足$mP=O$的时候,那么这个点的阶就是$m$。$E$上所有阶为$m$的点记为$E[m]$。这类点称为有限阶点或扭转点。

很显然,如果$P,Q\in E[m]$,那么$P+Q,-P \in E[m]$。故$E[m]$是$E$的一个子群。当然,定义域是$GF(49)$的椭圆曲线$E$上所有阶为$10$的点的集合记为$E(GF(49))[10]$。其他的情况可以此类推。

当椭圆曲线的定义域为$Q,R,C$时,那么$E(C)[m]=\dfrac{Z}{mZ}×\dfrac{Z}{mZ}$。

当椭圆曲线在$GF(p)$上时,如果$p$不是$m$的因数,那么对于任意的$j$,都存在$k$使得$E(GF(P^{jk}))[m]=\dfrac{Z}{mZ}×\dfrac{Z}{mZ}$。

如果$l$为素数,曲线的定义域为$K$,那么有$E(K)[l]=\dfrac{Z}{lZ}×\dfrac{Z}{lZ}$,那么我们可以认为$E[l]$是在$\dfrac{Z}{lZ}×\dfrac{Z}{lZ}$上的一个向量空间。当然,对于合数$m$,$E(K)[m]$中也会有两个点$P_1,P_2$,使得$E[m]$中的任意一个点$P$,都可以用$P_1,P_2$线性表示成$P=aP_1+bP_2$。对于系数$a,b∈\dfrac{Z}{mZ}$的唯一选择。 当然,如果$m$很大,可能很难找到$a$和$b$。 实际上,如果$P$是$P_1$的倍数,那么求$a$的值与解$P$和$P1$的ECDLP是相同的。

6x02 椭圆曲线上的有理数函数和约数

为了定义Weil和Tate对,我们需要解释椭圆曲线上的有理函数如何与其零点和极点相关。 我们从一个变量的有理函数的简单情况开始。 有理数函数是多项式的比值
$$
f(x)=\dfrac{\sum_{i=0}^{n}a_ix^i}{\sum_{i=0}^{n}b_ix^i}
$$
根据代数基本定理,在复数范围内,于$n$次方程有$n$个根,那么$f(x)$还可以写成这样的形式,其中所有的$\alpha$和所有的$\beta$都不相同。
$$
f(x)=\dfrac{a\prod_{i=1}^r (x-\alpha_i)^{e_i}}{b\prod_{i=1}^s (x-\beta_i)^{d_i}}
$$
由于$\alpha$与$\beta$中的值没有交集,因此,我们得到所有的$\alpha$值都是$f(x)$的零点,所有的$\beta$值都是$f(x)$的极点。我们通过定义$f(x)$的除数为形式和来跟踪$f(x)$的零点和极点及其倍数。定义:
$$
\mathrm{div} (f(x))=\sum_{i=1}^r e_i\alpha_i-\sum_{i=1}^sd_i\beta_i
$$
在椭圆曲线$E:y^2=x^3+Ax+B$中,如果把$x,y$都看成是某个变量的有理函数$x(t),y(t)$,那么椭圆曲线$E$上面的$f$的有些零点和极点会消失。此外,可以将倍数分配给零点和极点,因此 $f$ 有一个相关的除数
$$
\mathrm{div}(f)=\sum_{P\in E} n_P[P]
$$
在这个形式和中,系数$n_P$是整数,只有有限的$n_P$是非零的,所以$\mathrm{div}(f)$是有限和。

下面我们假设一个椭圆曲线方程$y^2=x^3+Ax+B$,那么我们可以有
$$
x^3+Ax+B=(x-\alpha_1)(x-\alpha_2)(x-\alpha_3)
$$
那么很显然,$(\alpha_i,0)$都是椭圆曲线上阶数为$2$的点,设$P_i=(\alpha_i,0)$,那么我们可以有$2P_1=2P_2=2P_3=O$。那么$y$就会在这三个点上消失,然后我们就有
$$
\mathrm{div}(Y)=[P_1]+[P_2]+[P_3]-3[O]
$$
并且可以推出,$P_1,P_2,P_3$都是不同的点。

更一般地,我们可以定义椭圆曲线$E$上的除数定义成$D=\sum_{P\in E}n_P[P]$,其中$n_p\in Z$并且$n_P=0$对所有但是有限个点$P\in E$。

其中,除数的度数就是它的系数之和:$\deg D =\deg \sum_{P\in E}n_P[P]=\sum_{P \in E} n_p$。

我们也可以通过方括号来定义除数的和:$\mathrm{Sum}(D)=\mathrm{Sum}\sum_{P\in E}n_P[P]=\sum_{P\in E}n_PP$。

注意,$n_PP$意味着用加法法则把$P$加到自己的$n_P$次上在$E$上,很自然地会问哪些除数是函数的除数,哪些除数是函数的除数函数的除数决定函数的大小。这些问题是由下面的定理来回答。

定理1:设$f$和$g$是椭圆曲线上的有理函数,如果$\mathrm{div}(f)=\mathrm {div} (g)$,那么存在一个非零常数$c$使得$f=cg$。

定理2:设$D=\sum_{P\in E}n_P[P]$,为椭圆曲线$E$上的一个除数,则$D$是$E$上有理函数的除数当且仅当$\deg D=0 \text{ and Sum}(D)=O$。

特别地,如果$E$上的有理函数没有零或极点,那么它就是一个常数。

6x03 Weil配对

用$e_m$表示的Weil配对以一对点作为输入$P, Q∈E[m]$,并给出单位$e_m(P,Q)$的第$m$个根作为输出。双线性Weil对的性质用方程表示
$$
e_m(P_1+P_2,Q)=e_m(P_1,Q)e_m(P_2Q)
$$

$$
e_m(P,Q_1+Q_2)=e_m(P,Q_1)e_m(P,Q_2)
$$

定义:设$P,Q∈E[m]$,即$P$和$Q$是$m$阶点群$E$。设$f_P$和$f_Q$是$E$上的有理函数满足$\mathrm{div}(f_P)=m[P]−m[O]$和$\mathrm{div}(fQ)=m[Q]−m[O]$。$P$和$Q$的Weil配对值就是
$$
e_m(P,Q)=\dfrac{f_P(Q+S)f_Q(-S)}{f_P(S)f_Q(P-S)}
$$
其中$S\in E $且$S$不为$O,P,-Q,P-Q$。并且$e_m(P,Q)$的值与函数$f_P,f_Q$的选取无关。

Weil配对的值满足$e_m(P,Q)^m=1$、$e_m(P,Q)=e_m(Q,P)^{-1}$,其中$P,Q\in E[m]$且对于任何的$P\in E[m]$,都有$e_m(P,P)=1$。

并且,Weil配对是非退化的,也就是说,如果对于任意的$Q\in E[m]$,都有$e_m(P,Q)=1$,那么可以推出$P=O$。

我们选择一个基$P_1,P_2∈E[m]$。那么任意元素$P∈E[m]$都可以是在此基础上写成$P=a_PP_1+b_PP_2$。

因此我们可以又以下的式子:
$$
e_m(P,Q)=e_m(P_1,P_2)^{a_Pb_Q-a_Qb_P}
$$
Weil配对的优点是它可以非常有效地计算不必用$E[m]$的基来表示$P$和$Q$。

6x04 一种有效的算法来计算Weil配对

我们设椭圆曲线$E$上有两点$P,Q$,直线$P,Q$的斜率为$k$,$S(x,y)\in E$,那么我们设
$$
g_{P,Q}=\dfrac{y-y_P-k(x-x_P)}{x+x_P+x_Q-k^2}
$$
如果$x_P=x_Q$且$P \not =Q$,那么上式的值视为$x-x_P$。如果$P=Q$,那么$k$视为$P$点在椭圆曲线上对应点的切线的斜率,而切线的斜率可以用高等数学中隐函数求导法求出为$y’=\dfrac{3x^2+A}{2y}$

因此,我们还可以获得这样一个式子:$\mathrm{div}(g_{P,Q})=[P]+[Q]-[P+Q]-[O]$。

下面的算法返回一个除数满足$\mathrm{div}(f_P ) = m[P] − [mP] − (m − 1)[O]$。

已知$P(36,60)$和$Q(121,387)$均为有限域上椭圆曲线$y^2\equiv x^3+30x+34\pmod{631} $上的$5$阶点,设$S(x,y)=(19,186)$为椭圆曲线上符合条件的任意一点,通过下面的代码,我们可以求出$e_5(P.Q)$的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
o1=GF(631)
A,B=30,34
E=EllipticCurve(o1,[A,B])
m=5
def g(P,Q,S):
if(P[0]==Q[0] and P!=Q):
return S[0]-P[0]
if P[0]==Q[0]:
k=(3*P[0]*P[0]+A)/(2*P[1])
else:
k=(P[1]-Q[1])/(P[0]-Q[0])
return (S[1]-P[1]-k*(S[0]-P[0]))/(S[0]+P[0]+Q[0]-k*k)
def F(P,S):
T,f=P,1
n=bin(m)[2:]
for i in range(1,len(n)):
f=f*f*g(T,T,S)
T=2*T
if int(n[i]):
f=f*g(T,P,S)
T=T+P
return f
P,Q,S=E(36,60),E(121,387),E(19,186)
tmp1=F(P,Q+S)/F(P,S)
tmp2=F(Q,P-S)/F(Q,-S)
ePQ=tmp1/tmp2
print(tmp1,tmp2,ePQ)
#198 345 242

可以看出:$242^5\equiv 1 \pmod {631}$

特别地,如果$P \in E[m]$,那么$\mathrm{div}(f_P)=m[P]-m[O]$。

6x05 Tate配对

Weil对是椭圆曲线上的非退化双线性形式在任何领域。对于有限域上的椭圆曲线还有另一对,我们称之为Tate配对在密码学中经常使用,因为它在计算上有点复杂比Weil配对更有效。在本节中,我们将简要介绍Tate配对。

设$E$是$GF(q)$上的一个椭圆曲线,$l$是一个素数,设$P\in E(GF(q))[l],Q \in E(GF(q))$,选择$E$上的有理函数$f_P$使得:
$$
\mathrm{div}(f_P)=l[P]-l[O]
$$
并且Tate对$P,Q$的值为
$$
τ (P,Q)=\dfrac{f_P(Q+S)}{f_P(S)}
$$
其中$S$是$E(GF(q))$上任一点,并且使得上式的分子分母不为$0$的点。

事实证明,Tate配对的值只有在乘以$GF(q)$元素的$l$次幂之后才有明确的定义。如果$q \equiv 1 \pmod l$,我们定义$P,Q$的Tate配对为
$$
τ’(P,Q)=τ’(P,Q)^{(q-1)/l}=(\dfrac{f_P(Q+S)}{f_P(S)})^{(q-1)/l}
$$
设$E$是$GF(q)$上的一个椭圆曲线,$l$是素数满足$q\equiv 1 \pmod l$且$E(GF(q))[L]=\dfrac{Z}{lZ}$。

那么我们可以得到这样一个映射:
$$
:E(GF(q))[l]×E(GF(q))[l] \rightarrow GF(q)
$$
并且这个$τ’$的性质也满足:
$$
τ’(P_1+P_2,Q)=τ’(P_1,Q)τ’(P_2Q)
$$

$$
τ’(P,Q_1+Q_2)=τ’(P,Q_1)τ’(P,Q_2)
$$

并且$τ’(P,P)$的值$x$满足$x^l\equiv 1 \pmod p$且$x \not =1$。

7.$GF(p^k)$上的Weil对

7x01 嵌入度和MOV算法

设$E$是$GF(p)$上的一个椭圆曲线,$m≥1$且$p$不整除$m$,为了能够获得非零的Weil配对值,我们需要用一个$E$上的独立的阶为$m$的点,一般情况下,阶为$m$的点一般有$m^2$个,但它们的坐标可能在一个更大的域中才能完全出现。

定义:嵌入度 设$E$是$GF(p)$上的椭圆曲线,$m≥1$且$p$不整除$m$,$E$对$m$的嵌入度的值为使得以下式子成立的最小$k$值:
$$
E(GF(p^k))[m] = (\dfrac Z{mZ})^2
$$
而在密码学的应用中,当$m$是一个大素数时,这一情况下嵌入度也可以这样理解:

设$E$是$GF(p)$上的一个椭圆曲线,$l$是一个与$p$不相等的素数,那么$E$对$l$的嵌入度可能是下面三种情况之一:

1.$E$的嵌入度为$1$,不过当$l>\sqrt p +1$的时候这张情况时不可能的
2.$p \equiv 1 \pmod l$时,$E$的嵌入度为$l$
3.$p \not \equiv 1 \pmod l$时,此时的嵌入度就是使得下面式子成立的最小$k(≥2)$值。
$$
p^k \equiv 1 \pmod l
$$
设$E$是$GF(p)$上的一个椭圆曲线,$P\in E$并且$P$的阶为$l$,$l$是一个大素数且$l>\sqrt p +1$。那么我们可以用下面的步骤来求解ECDLP,而这里求解ECDLP的问题就需要用到求解DLP的问题

1.计算$n=|E(GF(p^k))|$,其中$|E|$表示椭圆曲线内所含点数
2.随机选取一个点$T \in E(GF(p^k))$且$T\not \in E(GF(p))$
3.设$T’=(n/l)T$,如果$T’=O$,重新选择$T$
4.计算$\alpha=e_l(P,T’)$和$\beta =e_l(Q,T’)$
5.计算离散对数$\alpha^x\equiv \beta \pmod p$
6.那么我们可以求出$Q=xP$,ECDLP求解。

99.后记

ECC笔记2到这里暂时先结束,写的比较匆忙,书上5.8、5.9、5.10有很多比较晦涩难懂的东西,个人感觉在CTF中的应用不是很广泛,后期会对这一笔记进行更新补充(根本原因是因为自己太菜了,看不懂(


ECCNotes2
http://example.com/2021/03/04/ECCNotes2/
作者
huangx607087
发布于
2021年3月4日
许可协议