三次射影曲线简介

mathe

现在开始，如果没有特别说明，我们提到椭圆曲线都是指其Weierstrass形式，而其中点$\infty$就是只对应群中的加法零元。
另外对于曲线上任意一点A,其自相加n次可以记为$nA$,如果$nA=\infty$，我们说点A的阶是n. 而椭圆曲线中的有限阶点称为Torsion点
另外，通常这个椭圆曲线的系数和所有的点的坐标都定义在某个数域$K$上，我们记它为椭圆曲线$E(K)$.而如果F是K的一个扩域，那么对应的必然有椭圆曲线$E(F)$它和$E(K)$有完全相同的参数。于是对应的，$E(K)$必然是$E(F)$的一个嵌入（自然是子群）。特别的如果F是K的代数闭包$\bar{K}$,我们有椭圆曲线$E(\bar{K})$.
现在给定域K上椭圆曲线$E(K)$我们查看集合$E(n)={A|A \in E(\bar{K}), nA=\infty}$，也就是椭圆曲线在其代数闭包中的所有n阶点构成的集合。
理论分析给出，如果K的特征为p,那么如果\(p\nmid n\),那么$E(n)$同构于群$Z_n \oplus Z_n$;而如果$p|n$,设$n=p^r n'$,那么$E(n)$同构于群$Z_{n'} \oplus Z_{n'}$或$Z_{n'} \oplus Z_n$,其中$Z_n$表示整数集的模n运算。特别的，如果K是有理数集Q,由于特征为0，那么$E(n)$必然同构于$Z_n \oplus Z_n$。

另外对于数域$K$,其代数闭包中所有n次单位元可以构成集合$\mu_n$,那么存在双线性函数Weil Paring \(e_n: E(n)\times E(n) \longrightarrow \mu_n\)。
所谓双线性就是$e_n(S_1+S_2,T)=e_n(S_1,T)e_n(S_2,T), e_n(S,T_1+T_2)=e_n(S,T_1)e_n(S,T_2)$等
而利用Weil Paring,可以得出一个比较有用的结论
定理: 如果\(E(n)\subset E(K)\)那么\(\mu_n\subset K\).
由此得出对于有理数集上椭圆曲线E(Q),$n>=3$,必然有\(E(n)\not\subset E(Q)\),也就是3重以上的点必然有在扩域上的（也就是坐标不是有理数）
而有理数集上的椭圆曲线E(Q)所有阶为有限的点构成一个群成为Torsion群，这个群必然有限而且阶不超过16
特别如果椭圆曲线系数$a_4,a_6$都是整数，那么对于Torsion群里每个点$(x,y)$,必然有$y^2|4p^3+27q^2$,由此我们知道Torsion群的计算非常简单。
Pari/Gp中函数elltors可以用来计算Torsion群。
另外E(Q)同构于$E_{"tor"} \oplus Z^r$,这就是说椭圆曲线群是有限生成的(Mordell-Weil定理),其中r成为这个椭圆曲线群的秩

mathe

在射影几何里，由于无穷远点的存在，直线在无穷远点处闭合，所以实数集同构于圆。同样复数集在引入无穷远点后从平面变成球面。
那么对于实数域上椭圆曲线，其图像同构于一个或两个圆。而复数域，椭圆曲线同构于轮胎。

mathe

现在还有有限域$F_q$上椭圆曲线群需要了解，其上群结构总是同构于$Z_{n_1}\oplus Z_{n_2}$,其中$n_1|n_2$,而且对于充分大的q,$n_2$唯一确定$n_1$.所以可以通过群上不超过两个点生成所有点

mathe

Hass定理说椭圆曲线群中元素数目同q+1的差的绝对值不超过$2\sqrt(q)$.
Pari/Gp中，我查了一下文档，发现函数ellap可以用来计算这个差值
(09:30) gp > E=ellinit([Mod(0,97),Mod(3,97)])
%1 = [Mod(0, 97), Mod(0, 97), Mod(0, 97), Mod(0, 97), Mod(3, 97), Mod(0, 97), Mo
d(0, 97), Mod(12, 97), Mod(0, 97), Mod(0, 97), Mod(27, 97), Mod(89, 97), Mod(0,
97), Vecsmall([3]), [97, [0, 94, [6, 0, 0, 0]]], [0, 0, 0, 0]]
(09:30) gp > ellap(E)
%2 = -19
所以曲线$y^2=x^3+3$模97得到曲线点的数目为97+1-(-19)=117
而函数ellcard(E)可以直接返回117
然后用ellgenerators(E)可以得到两个生成元
[[Mod(90, 97), Mod(40, 97)], [Mod(20, 97), Mod(90, 97)]]
然后用ellorder([Mod(90, 97), Mod(40, 97)])=39可以得知群的结果应该是同构于$Z_39\oplus Z_3$

mathe

$E(F_q)$点的数目为$q+1-a$而且$X^2-aX+q=(X-\alpha)(X-\beta)$.那么$E(F_{q^n})$点的数目为$q^n-\alpha^n-\beta^n+1$

mathe

在普通数域$F_q$中有离散对数问题，就是已知$a^n=b$,给出$n,b$求$a$.
同样在椭圆曲线群$E(F_q)$中也有离散对数问题，已经整数$n$和曲线上点$A,B$满足$nA=B$,给出$B,n$值求$A$就是离散对数问题。
对于椭圆曲线群上离散对数问题现在没有有效的方法
现在我们可以用DH作为例子来说明如何利用椭圆曲线来交换秘密数据。
比如现在mathe和wanye想通过emath中BBS来交换秘密数据，当然实际应用中我们需要选择一个很大的素数域，这里为了方便，还是用$F_97$作为例子，并且使用14#的曲线$y^2=x^3+3$,我们知道曲线上有点$G=[1,2]$,同样这个点的阶是39（实际应用中必须选择一个阶含有大素数因子的点来防御穷举攻击）。
mathe可以选择一个自己的密钥，比如是m=5（保密），然后计算M=mG, ellmul(E,[1,2],5)=[76,65],于是在BBS上公开M=[76,65]
wayne也可以选择自己的密钥，比如w=11(保密），然后计算W=wG, ellmul(E,[1,2],11)=[2,60],于是在BBS上公开W=[2,60]
在相互拿到对方的数据有，mathe可以计算S=mW, ellmul(E,[2,60],5)=[35,2]
wayne可以计算S=wM, ellmul(E,[76,65],11)=[35,2]
于是mathe和wayne拥有了公共的数据S,然后双方就可以通过用S作为密钥使用一些约定的对称加密算法任意交换数据了

mathe

  现在可以举一个实际一些的例子，比如还是选择如上面的曲线$y^2=x^3+3$,而我们选择$F_q$中$q=115792089237314936872688561244471742058375878355761205198700409522629664518163$
E=ellinit([Mod(0,q),Mod(3,q)]);
于是ellcard(E)=$p=
115792089237314936872688561244471742058035595988840268584488757999429535617037$
而显然点$G=[1,2]$在曲线上。
大家只要随机产生一个不超过p的大随机整数a就可以选择作为密钥，然后让计算机计算A=ellmul(E,G,a)就可以得到公钥了。由于得到点的阶是一个超大整数，所以现在的计算机还是没有能力破译的
在Pari/Gp下面可以用random(2^256)产生一个256比特的随机数，为了保证小于p而且平均分布可以产生一个512比特的随机数然后对p求余数，就可以得到密钥，然后产生公钥。
比如我可以产生一个公钥M=
(10:57) gp > ellmul(E,[1,2],%16)
%17 = [Mod(752266960737650656089684783495320312744914275427270152468098439736359
58756023, 1157920892373149368726885612444717420583758783557612051987004095226296
64518163), Mod(18912811488559598925677202750181765097108792769061852665781126322
72927302114, 1157920892373149368726885612444717420583758783557612051987004095226
29664518163)]
也就是得到点[75226696073765065608968478349532031274491427542727015246809843973635958756023,1891281148855959892567720275018176509710879276906185266578112632272927302114]