ECC椭圆曲线详解(有具体实例)-白红宇

ECC椭圆曲线详解(有具体实例)

阅读量：5909 次

发布时间：2019-06-19

本文共 5972 字，大约阅读时间需要 19 分钟。

前言

ECC英文全称"Ellipse Curve Cryptography"

与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥

ECC164位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。

从射影平面讲起

古希腊数学家欧几里得的《几何原本》提出了五条公设。

1.由任意一点到任意一点可作直线。

2.一条有限直线可以继续延长。

3.以任意点为心及任意的距离可以画圆。

4.凡直角都相等。

5.同一平面内一条直线a和另外两条直线b.c相交，若在a某一侧的两个内角的和小于两直角，则b.c两直线经无限延长后在该侧相交。

《几何原本》只有在第29个命题

一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角

中才用到第五公设，即《几何原本》中可不依靠第五公设而推出前28命题。因此，一些数学家提出，第五公设能不能不作为公设，而作为定理？能不能依靠前四个公设来证明第五公设？这就是几何发展史上最著名的，争论了长达两千多年的关于“平行线理论”的讨论

1820年代，俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线，且都通过P点，并不与直线R相交”代替第五公设，然后与欧氏几何的前四个公设结合成一个公理系统，他经过细致深入的推理过程中，得出了一个又一个在直觉上匪夷所思，但在逻辑上毫无矛盾的几何体系。

这种几何学被称为罗巴切夫斯基几何，简称罗氏几何。从罗氏几何学中，可以得出这样一个结论：逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下：

1.坚持第五公设，引出欧几里得几何。

2.“可以引最少两条平行线”为公设，罗氏几何（双曲几何）。

3.“一条平行线也不能引”为公设，黎曼几何（椭圆几何）

左：双曲几何，即罗氏几何；中：欧几里德几何；右：椭圆几何，即黎曼几何

了解非欧式几何，就可以理解平行线的交点。

定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点

性质：

1.一条直线只有一个无穷远点；一对平行线有公共的无穷远点

2.任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）

3.平面上全体无穷远点构成一条无穷远直线

射影平面：平面上全体无穷远点与全体平常点构成射影平面

射影平面点的定义

对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z≠0，则投影为射影平面上的点(X:Y:Z)

求点（1,2）在新的坐标体系下的坐标

∵X/Z=1 ，Y/Z=2（Z≠0）

∴X=Z，Y=2Z ∴坐标为（Z:2Z:Z），Z≠0

即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0的坐标都是（1,2）在新的坐标体系下的坐标

(2) 求平行线L1：X+2Y+3Z=0 与L2：X+2Y+Z=0 相交的无穷远点

∵ L1∥L2 所以有Z=0， X+2Y=0

∴坐标为（-2Y:Y:0），Y≠0

即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0

椭圆曲线

一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合

\[ {Y^2}Z + {a_1}XYZ + {a_3}Y{Z^2} = {X^3} + {a_2}{X^2}Z + {a_4}X{Z^2} + {a_6}{Z^3} \]

1椭圆曲线方程是一个齐次方程

2曲线上的每个点都必须是非奇异的（光滑的），偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0

3圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程故得名

椭圆曲线示例

非椭圆曲线示例

这两个方程都不是椭圆曲线,因为他们在（0:0:1）点处（即原点）没有切线，不满足椭圆曲线每个点都必须是非奇异的（光滑的），

椭圆曲线普通方程

椭圆曲线普通方程：

\[ {y^2} + {a_1}xy + {a_3}y = {x^3} + {a_2}{x^2} + {a_4}x + {a_6} \]

无穷远点 (0, Y, 0)

平常点(x,y)斜率k：

\[ \begin{array}{l} {F_x}\left( {x,y} \right) = {a_1}y - 3{x^2} - 2{a_2}x - {a_4} \\ {F_y}\left( {x,y} \right) = 2y + {a_1}x + {a_3} \\ \end{array} \]

\[ \begin{array}{l} k = - \frac{

{

{F_x}\left( {x,y} \right)}}{

{

{F_y}\left( {x,y} \right)}} = \frac{

{3{x^2} + 2{a_2}x + {a_4} - {a_1}y}}{

{2y + {a_1}x + {a_3}}} \end{array} \]

椭圆曲线阿贝尔群

我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢？这就要定义椭圆曲线的加法群，这里需要用到近世代数中阿贝尔群。

在数学中，群是一种代数结构，由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求

封闭性：∀a,b∈G，a*b ∈ G

结合性： ∀a,b,c∈G ，有 (ab)c = a* (b*c)

单位元：ョe∈G， ∀a ∈G，有ea = ae = a

逆元： ∀a ∈G ，ョb∈G 使得 ab = ba = e

阿贝尔群除了上面的性质还满足交换律公理a * b = b * a

同样在椭圆曲线也可以定义阿贝尔群。

任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R'，过R'做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律

同点加法

若有k个相同的点P相加，记作kP

P+P+P=2P+P=3P

有限域椭圆曲线

椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。

我们给出一个有限域Fp

Fp中有p（p为质数）个元素0,1,2,…, p-2,p-1

Fp的加法是a+b≡c(mod p)

Fp的乘法是a×b≡c(mod p)

Fp的除法是a÷b≡c(mod p)，即 a×b^(-1)≡c (mod p)，b-1也是一个0到p-1之间的整数，但满足b×b-1≡1 (mod p)

Fp的单位元是1，零元是 0

Fp域内运算满足交换律、结合律、分配律

椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]

\[{y^2} = {x^3} + ax + b\left( {\bmod p} \right)\]

选择两个满足下列约束条件的小于p的非负整数a、b

\[4{a^3} + 27{b^2} \ne 0\left( {\bmod p} \right)\]

Fp上的椭圆曲线同样有加法

1.无穷远点 O∞是零元，有O∞+ O∞= O∞，O∞+P=P

2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ，有P+(-P)= O∞

3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系：

x3≡k2-x1-x2(mod p)

y3≡k(x1-x3)-y1(mod p)

若P=Q 则 k=(3x2+a)/2y1mod p

若P≠Q，则k=(y2-y1)/(x2-x1) mod p

例题椭圆曲线已知E23(1,1)上两点P(3,10)，Q(9,7)，求(1)-P，(2)P+Q，(3) 2P

\[\begin{array}{l} \left( 1 \right) - P = \left( {3, - 10\bmod 23} \right) = \left( {3,13} \right) \\ \\ \left( 2 \right)k = \frac{

{7 - 10}}{

{9 - 3}} = - {2^{ - 1}}\bmod 23 \\ 2 \cdot {2^{ - 1}} = 1\bmod 23 \Rightarrow {2^{ - 1}} = 12 \\ k = - 12\bmod 23 = 11 \\ P + Q = \left( {

{

{11}^2} - 3 - 9\bmod 23,11 \times \left( {3 - \left( { - 6} \right)} \right)\bmod 23} \right) = \left( {17,20} \right) \\ \\ \left( 3 \right)k = \frac{

{3 \times {3^2} + 1}}{

{2 \times 10}}\bmod 23 = 7 \cdot {5^{ - 1}}\bmod 23 \\ 5 \cdot {5^{ - 1}} = 1\bmod 23 \Rightarrow {5^{ - 1}} = 14 \\ k = 7 \cdot 14\bmod 23 = 6 \\ 2P = \left( {

{6^2} - 3 - 3\bmod 23,6 \times \left( {3 - 7} \right)\bmod 23} \right) = \left( {7,12} \right) \\ \end{array} \]

补充:

-2^(-1) mod 23 进行两部分计算

(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方，而是2的逆元

(2) 再算-A mod 23

(1) 计算第一步

根据有限域除法规则 2 * 2^(-1) = 1 mod 23

即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12

(2) 计算第二步

-A mod 23 ==> -12 mod 23 即 23 -12 = 11

所以有

-2^(-1) mod 23 = 11

有限域椭圆曲线点的阶

如果椭圆曲线上一点P，存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶

若n不存在，则P是无限阶的

计算可得27P=-P=(3,13)

所以28P=O ∞ P的阶为28

这些点做成了一个循环阿贝尔群，其中生成元为P，阶数为29。显然点的分布与顺序都是杂乱无章

椭圆曲线加密

考虑K=kG ，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶（nG=O∞ ），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据

点G称为基点（base point）

k（k<n）为私有密钥（privte key）

K为公开密钥（public key)