椭圆曲线有关知识_IT分享知识网

大家好，欢迎来到IT知识分享网。

1. 实数域上的椭圆曲线

椭圆曲线并不是椭圆，称其为椭圆曲线的原因是，它们与用来计算椭圆周长的方程相似，都由三次方程描述。一般来说，椭圆曲线的三次方程为：

式中，a、b、c、d、e均为实数，x和y在实数集上取值。对我们而言，将方程限制为如下形式是足够的：

椭圆曲线的定义中还包含一个称为无穷远点或零点的元素，记为。对于给定的a值和b值，曲线由每个x值对应的正y值和负y值组成。于是，每条曲线都关于y=0对称。

加法的几何描述 可以证明，若限制后的方程中的参数a和b满足条件

$4a^3+27b^2\neq 0$

则可基于集合E(a,b)定义一个群。要在E(a,b)中定义一个群，必须定义一个称为加法的运算，并用+表示，其中a和b的取值需要满足上述条件。采用几何术语，可按如下方式定义加法的运算规则：若椭圆曲线上的三个点都在一条直线上，则它们的和为。从这个定义出发，可将椭圆曲线上加法的运算规则定义如下：

1. 是加法的单位元。于是有 O=-O ；对椭圆曲线上的任意点，有 P+O=P 。下面假设 $P\neq Q$ 且 $Q\neq O$ 。

2. 点的负元是具有相同x坐标和相反y坐标的点，即若 P=(x,y) ，则。注意这两个点可用一条垂线连接起来，且。

3. 要计算x坐标不同的两点和之和，可在和之间画一条直线并找到第三个交点。显然存在唯一的交点（除非这条直线在或处与椭圆曲线相切，此时分别取 R=P 或 R=Q ）。为了形成群结构，需要在这三个点上定义加法： P+Q=-R 。也就是说，定义 P+Q 为第三个交点（相对于x轴）的镜像。

4. 上述各项的集合说明也适用于具有相同x坐标的两个点和。两点由一条垂线连接，也可视为在无穷远点处与曲线相交，因此有，这与上述步骤2一致。

5. 要加倍点，可画一条切线并找到另一个交点。于是，。

利用上述运算规则，可以证明集合 E(a,b) 是交换群。

加法的代数描述 对于彼此非负元的两个不同点和，连接它们的虚线的斜率 $\Delta =(y_Q-y_P)/(x_Q-x_P)$ 。恰好与椭圆曲线相交于另一点，即与之和的负元。经过某些代数运算后，可将 R=P+Q 表示为：

$x_R=\Delta ^2-x_P-x_Q,\;y_R=-y_P+\Delta (x_P-x_R)$

我们还需要将一个点与自身相加：，当 $y_P\neq 0$ 时，上式可变为:

$x_R=(\frac{3x_P^2+a}{2y_p})^2-2x_P,\;y_R=(\frac{3x_P^2+a}{2y_p}) (x_P-x_R)-y_P$

2. 上的椭圆曲线

椭圆曲线密码学使用的是其变量和系数均为有限域的元素的椭圆曲线。

对有限域上的椭圆曲线运算来说，不存在显而易见的几何解释，但可以使用实数域上的椭圆曲线运算的代数解释。

对 Z_p 上的椭圆曲线，如同实数那样，只讨论限制形式的方程，但此时变量和系数均限制在 Z_p 上：

$y^2mod\;p=(x^3+ax+b)mod\;p$

例如，时，上式成立：

$7^2mod\;23=(9^3+9+1)mod\;23,\;49mod\;23=739mod\;23,\;3=3$

下面考虑所有满足上式的整数对(x，y)和无穷远点组成的集合。系数a和b，变量x和y都是 Z_p 的元素。

例如，令p=23并考虑椭圆曲线，其中 a=b=1 。对于集合 $E_{23}(1,1)$ ，我们只对满足如下条件的非负整数感兴趣，即满足方程模运算且位于 (0,0) 到的象限中的非负整数。

可以证明，若 $(x^3+ax+b)mod\;p$ 无重复因子，则根据集合可以定义一个有限交换群。这等价于下列条件：

$(4a^3+27b^2)mod\;p\neq 0\;mod\;p$

定义在上的加法运算规则，与定义在实数域上的椭圆曲线的运算规则一致。对任何点 $P,Q\;\epsilon \;E_p(a,b)$ ：

1. P+O=P

2. 若，则。点是的负元，记为。例如，对 $E_{23}(1,1)$ 中的点，有，而 $-7mod\;23=16$ 。因此，，该点也在 $E_{23}(1,1)$ 中。

3. 若，，且 $P\neq -Q$ ，则由下列规则确定:

$x_R=(\lambda ^2-x_p-x_Q)mod\;p,\;y_R=(\lambda (x_p-x_R)-y_p)mod\;p$

式中，

$\lambda =\left\{\begin{matrix} (\frac{y_Q-y_p}{x_Q-x_p})mod\;p & P\neq Q\\ (\frac{3x_P^2+a}{2y_p})mod\;p & P=Q \end{matrix}\right.$

4. 将乘法定义为重复相加，如4P=P+P+P+P。

例如，令 $E_{23}(1,1)$ 中的。

计算 P+Q 则有

$\lambda =(\frac{7-10}{9-3})mod\;23=(\frac{-3}{6})mod\;23=(\frac{-1}{2})mod\;23\\. \;=((-1)*2^{-1}mod\;23)mod\;23=(-1*(12))mod\;23\\.\;=11$

（-1除以2就等于-1乘以2在 $Z_{23}$ 中的乘法逆元）

$x_R=(11^2-3-9)mod\;23=17,\;y_R=(11 (3-17)-10)mod\;23=20$

所以。

要计算，先求

$\lambda =(\frac{3(3^2+1)}{2\times 10})mod\;23=(\frac{5}{20})mod\;23=(\frac{1}{4})mod\;23\\ .\;=(1*(4^{-1}mod\;23))mod\;23\\ .\;=6$

$x_R=(6^2-3-3)mod\;23=7,\;y_R=(6 (3-7)-10)mod\;23=12$

即。

3. 上的椭圆曲线

给定某个m，对 GF(2^m) 上的椭圆曲线，使用变量和系数均在 GF(2^m) 上取值的三次方程，并使用 GF(2^m) 上的算数运算规则来进行运算。

业已证明， GF(2^m) 上适合于椭圆曲线密码应用的三次方程与 Z_p 上的三次方程不同，其形式为：

式中，变量x和y及系数a和b是 GF(2^m) 中的元素，且所有计算均在 GF(2^m) 中执行。

接下来考虑满足上式的所有整数对(x，y)和无穷远点组成的集合 $E_{2^m}(a,b)$ 。

例如，对使用不可约多项式定义的有限域 GF(2^4) ，其生成元满足 f(g)=0 ，即 g^4=g+1 或二进制数 g=0010 。我们可以按如下方式求出的各次方：

			$g^{12}=1111$
			$g^{13}=1101$
		$g^{10}=0111$	$g^{14}=1001$
		$g^{11}=1110$	$g^{15}=0001$

例如，。

下面考虑椭圆曲线。此时。满足该方程的一个点为：

$(g^3)^2+g^5(g^3)=(g^5)^3+(g^4)(g^5)^2\\ g^6+g^8=g^{15}+g^{14}+1\\ 1100+0101=0001+1001+0001\\ 1001=1001$

可以证明，只要 $b\neq 0$ ，即可根据集合 $E_{2^m}(a,b)$ 定义一个有限交换群。加法的运算规则如下所述。对所有点 $P,Q\;\epsilon \;E_{2^m}(a,b)$ ：

1. P+O=P

2. 若，则。点是的负元,记为。

3. 若，，且 $P\neq -Q$ ，则由下列规则确定:

$x_R=\lambda ^2+\lambda +x_p+x_Q+a,\;y_R=\lambda (x_p+x_R)+x_R+y_p$

式中，

$\lambda =\frac{y_Q+y_p}{x_Q+x_p}$

4. 若，则由下列规则确定：

$x_R=\lambda^2+ \lambda+a ,\;y_R=x_p^2+(\lambda +1)x_R$

式中，

$\lambda =x_p+\frac{y_p}{x_p}$

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/132389.html

椭圆曲线有关知识

1. 实数域上的椭圆曲线

相关推荐

发表回复