椭圆曲线在有限域上存在标准的点压缩技术,使得仅需原本一半的比特数来表示ECC中的点,F2n上的椭圆曲线具备更优的性质;在使用点压缩后传输仅需更少的比特或存储时仅需更少的空间具体应用在内存和带宽受限的情形下如无线网络或智能卡椭圆曲线在有限域上存在标准的点压缩技术,使得仅需原本一半的比特数来表示ECC中的点,\\在F_{2^n}上的椭圆曲线具备更优的性质;在使用点压缩后传输仅需更少的比特或存储时仅需更少的空间\\ 具体应用在内存和带宽受限的情形下如无线网络或智能卡

​ 为了能让压缩后的坐标完全恢复,与原来相比,需要增加一定的计算量。总而言之就是以一定量的运算换取较多的空间资源。

在 F_p 上的点压缩

​ 在椭圆曲线密码体制中,需要将 G 点的 x、y 坐标都传送给对方,但是加密信息却只是坐标中的一小部分,存在很大的空间剩余问题,如何合理地分配空间资源,这就让 "点压缩" 技术就此诞生。

设加密系统所用基域是Fp,定义在其之上的椭圆曲线:E:Y2=X3+aX+ba,bFp设加密系统所用基域是F_p,定义在其之上的椭圆曲线: \\ E:Y^2=X^3+aX+b \quad a,b \in F_p

对一个点R=xR,yRE(Fp),yR1(mod2),将R记为[xR,1],否则记为[xR,0].对一个点R=(x_R,y_R)\in E(F_p),当y_R \equiv1(mod2),将R记为[x_R,1],否则记为[x_R,0].

​ 对这点不太明白,为什么是 1mod2 呢??翻看一些点压缩的论文,里面是这样描述的:

对任给椭圆曲线上的点(x1,y1E,发送方和接收方双方约定:1.如果y1Fp,且满足p2y1<p1,则发送x11给对方2.如果y1Fp,且满足0<y1<p2,则发送x10给对方接收方收到x1后,代入Y2=X13+aX1+b(modp)解出y1y1由接收方收到的[1/0]来确定是y1还是y1.以上过程就是标准的"点压缩"对任给椭圆曲线上的点(x_1,y_1) \in E,发送方和接收方双方约定:\\ 1.如果y_1 \in F_p,且满足\frac p2 \leq y_1 <p-1,则发送x_1和1给对方\\ 2.如果y_1 \in F_p,且满足 0 < y_1 <\frac p2 ,则发送x_1和0给对方\\ 接收方收到x_1后,代入Y^2=X_1^3+aX_1+b(modp)\\ 解出y_1'和y_1''由接收方收到的[1/0]来确定是y_1' 还是y_1''.\\以上过程就是标准的"点压缩"

​ 个人理解 (1mod2) 是在下面讲到的 F_2^n 有限域里的情况 (也是最常用的情况下)

​ 当 p 较大时,采用 "点压缩" 后,传输通行量大大减少,但是其加密安全性却完全没有降低。原来需要传送 2lnp 位 / 点,现在只需要 lnp+1 位 / 点,相较以前减少了一半左右。

在 F_2^n 上的点压缩

​ 在这种情形下有两种方法进行点压缩:

迹函数进行点压缩

​ 将与 ECC 相关的点的 x 坐标压缩 1 位,使得传送一个点仅需 n 位,其中 n 位用来表示 x,1 位用来确定 y 坐标

在有限扩张的素数域F上存在任意元素α=c1α1+...+cmαm在有限扩张的素数域F上存在任意元素 \alpha=c_1\alpha_1+... +c_m\alpha_m

对于αFqm,K=Fq,αK上的迹TrF/K(α)定义为TrF/K(α)=α+αq+...+αqm1KF的素子域,则TrF/K(α)称为α的绝对迹,简写位TrF(α)对于\alpha\in F_{q^m},K=F_q,\alpha在K上的迹Tr_{F/K(\alpha)}定义为\\ Tr_{F/K(\alpha)}=\alpha+\alpha^q+...+\alpha^{q^{m-1}}\\ 若K是F的素子域,则Tr_{F/K(\alpha)}称为\alpha的绝对迹,简写位Tr_{F(\alpha)}

​ 并且迹函数具有分配律、结合律的性质

特殊地,TrF/K(αq)=TrF/K(α)特殊地,Tr_{F/K(\alpha^q)}=Tr_{F/K(\alpha)}

半分点法进行点压缩

​ 半分点算法用来计算在 F_2(n)上的椭圆曲线的点乘([k] P)是特别有效的

更新于

请我喝[茶]~( ̄▽ ̄)~*

1sme 微信支付

微信支付