椭圆曲线密码学的一些具体的内容

椭圆曲线密码学的一些具体的内容

⑴ 无穷远元素（无穷远点，无穷远直线）
平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。
AB⊥L1， L2∥L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。
Q=∠BAP→p /2 AP → L2
可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。
直线L1上的无穷远点只能有一个。
（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）
结论：
1*. 平面上一组相互平行的直线，有公共的无穷远点。
（为与无穷远点相区别，把原来平面上的点叫做平常点）
2*.平面上任何相交的两直线L1,L2有不同的无穷远点。
原因：若否，则L1和L2有公共的无穷远点P∞，则过两相异点A和P ∞有相异两直线，与公理相矛盾。
3*. 全体无穷远点构成一条无穷远直线。
注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。
⑵ 齐次坐标
解析几何中引入坐标系，用代数的方法研究欧氏空
间。这样的坐标法也可推广至摄影平面上，建立平面摄影
坐标系。
牋 L1,L2
L1: a1x+b1y+c1=0
L2: a2x+b2y+c2=0
其中a1,b1不同时为0；a2,b2也不同时为0。
设
D= a1 b1 Dx= b1 c1 Dy= c1 a1
a2 b2 b2 c2 c2 a2
若D≠0，则两直线L1,L2相交于一平常点P(x,y），其坐标为x=Dx/D，y=Dy/D.
这组解可表为：x/Dx=y/Dy=1/D
（约定：分母Dx，Dy有为0时，对应的分子也要为0）
上述表示可抽象为（Dx，Dy，D).
若 D=0，则L1∥L2，此时L1和L2交于一个无穷远点P∞。
这个点P∞可用过原点O且平行于L2的一条直线L来指出他
的方向，而这条直线L的方程就是：a2x+b2y=0.
为把平常点和无穷远点的坐标统一起来，把点的坐标用
（X，Y，Z）表示，X，Y，Z不能同时为0，且对平常点
（x，y）来说，有Z≠0，x=X/Z，y=Y/Z，于是有：
i.e.
X / Dx = Y / Dy = Z / D，
有更好的坐标抽象，X,Y,Z），这样对于无穷远点则有Z=0，
也成立。
注：
a).若实数p≠0，则（pX,pY,pZ）与（X,Y,Z）表示同一个点。实质上用（X:Y:Z）表示。3个分量中，只有两个是独立的，

；具有这种特征的坐标就叫齐次坐标。
b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：
ax+by+c=0
则L上任一平常点（x,y）的齐次坐标为（X,Y,Z），Z≠0，代入得：
aX+bY+cZ=0
给L添加的无穷远点的坐标（X,Y,Z）应满足aX+bY=0，Z=0；平面上无穷远直线方程自然为：Z=0 !!
⑶任意域上的椭圆曲线
K为域，K上的摄影平面P2(K）是一些等价类的集合{(X:Y:Z)}。考虑下面的Weierstrass方程（次数为3的齐次方程）：
Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3
（其中系数ai∈K，或ai∈K为K的代数闭域）
Weierstrass方程被称为光滑的或非奇异的是指对所有适合
以下方程的射影点P=(X:Y:Z) ∈ P2(K）来说，
F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0
在P点的三个偏导数 之中至少有一个不为
0若否称这个方程为奇异的。
椭圆曲线E的定义：
椭圆曲线E是一个光滑的Weierstrass方程在P2(K）中的
全部解集合。
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
注：
a) 在椭圆曲线E上恰有一个点，称之为无穷远点。即（0:1:0）用θ表示。
b) 可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程：
设 x=X/Z，y=Y/Z，于是原方程转化为：
y2+a1xy+a3y=x3+a2x2+a4x+a6 ⑴
此时，椭圆曲线E就是方程⑴在射影平面P2(K）上的全部平常点解，外加一个无穷远点θ组成的集合。
c) 若a1,a2,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K--

；有理点集合表示为E(K），它为E中的全体有理坐标点的集合外加无穷远点θ.
⑷实域R上的椭圆曲线
设K=R，此时的椭圆曲线可表为平面上的通常曲线上
的点，外加无穷远点θ。
实域R上椭圆曲线的点的加法运算法则：
设L ∈ P2(R）为一条直线。因为E的方程是三次的，所以L可与E在P2(R）恰有三个交点，记为P,Q,R
（注意：如果L与E相切，那么P,Q,R可以不是相异的）。按下述方式定义E上运算⊙：
设P,Q ∈ E，L为联接P,Q的直线（若P=Q，则L取过P点的切线）；设R为L与E的另一个交点；
再取连接R与无穷远点的直线L′。则L′与E的另一个交点定义为P ⊙Q。
上页的实际图像为椭圆曲线y2=x3 - x的一般化。来自对具体曲线的抽象。对运算更具体一些：
设 P=(x1,y1），Q=(x2,y2），P⊙Q=(x3,y3），
由P Q的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：
α=(y2-y1）/(x2-x1），β=y1-αx1
易见，直线L上的一个点（x，αx+β）是在椭圆曲线E上，
当且仅当（αx+β）2= x3 - x。
P⊙Q=(x1,y1） (x2,y2）=(x3,y3） =(x3,-（αx3+β））
其中，x3= α2-x1-x2=((y2-y1） / (x2-x1））2-x1-x2；
y3=-y1+((y2-y1）/(x2-x1））（x1-x3）
当P=Q时：P⊙Q=（x3，y3）算得：
x3=（（3x12-1）/2y1）2-2x1; y3= -y1+（（3x12-1）/2y1）（x1-x3）
注：
a) 如果直线L与E相交与三点P,Q,R（不一定相异），那么 (P⊙Q)R=θ（从图中可见）。
b) 任给P∈E,P⊙θ =P （此时设Q= θ ，易见L=L′）
c) 任给P,Q∈E有：P⊙Q =Q⊙P
d) 设P∈E，那么可以找到 - P∈E使P -P= θ
e) 任给P,Q,R∈E，有（P⊙Q）⊙R= P⊙（Q⊙R)
综上所述，知E对 运算形成一个Abel群。
f) 上述规则可开拓到任意域上，特别是有限域上。假定
椭圆曲线是定义在有限域Fq上（q=pm），那么
E(Fq)={(x,y）∈Fq×Fq | y2+a1xy+a3y=x3+a2x2+a4x+a6} ∪{θ}
它对? 斝纬梢桓鋈海?狝bel群。 令Fq表示q个元素的有限域，用E(Fq）表示定义在Fq上
的一个椭圆曲线E。
定理1.(Hass定理） E(Fq）的点数用#E(Fq）表示，则
| #E(Fq)-q-1|≤2q1/2
⑴ Fp（素域，p为素数）上椭圆曲线
牋 p>3 a,b Fp 4a3+27b2 0 a b
义的Fp上的一个椭圆曲线方程为：
y2=x3+ax+b ⑵
它的所有解（x,y），（x Fp，y Fp），连同一个称为撑耷钤?
点敚?俏?龋┑脑?刈槌傻募?霞俏狤（Fp），由Hass定理
知：p+1-2p1/2≤#E(Fp) ≤ p+1+2p1/2
集合E(Fp）对应下面的加法规则，且对加法 形成
一个Abel群：
（i) θ⊙ θ=θ （单位元素）
（ii) (x,y）⊙ θ=(x,y），任给（x,y) ∈E(Fp)
（iii) (x,y）⊙ (x,-y)=θ，任给（x,y) ∈E(Fp），即点（x,y）的逆元
为（x,-y).
（iv) 令（x1,y1），（x2,y2）为E(Fp）中非互逆元，则
（x1,y1）⊙ (x2,y2）=(x3,y3），其中
x3=α2-2x1，y3= α（x1-x3）-y1
且α=(y2-y1）/(x2-x1） ⑶
（v）（倍点运算规则）
设（x1,y1） ∈E(Fp),y1≠0，则2(x1,y1）=(x3,y3），其中
x3= α2-2x1,y3=α（x1-x3）-y1
这里α=（3x12+a)/（2y1） ⑷
注：若#E(Fp)=p+1，曲线E(Fp）称为超奇异的，否则称为
非超奇异的。
例子：F23上的一个椭圆曲线
令y2=x3+x+1是F23上的一个方程（a=b=1），则该椭圆曲
线方程在F23上的解为（y2=x3+x+1的点）：
（0,1），（0,22），（1,7），（1,16），（3,10），（3,13），（4,0），（5,4），（5,19），（6,4），

；（6,19），（7,11），（7,12），（9,7），（9,16），（11,3），（11,20），（12,4），（12,19），（13,7），

；（13,16），（17,3），（17,20），（18,3），（18,20），（19,5），（19,18）；θ。
群E(F23）有28个点（包括无穷远点θ）。
2） F2m上的椭圆曲线
F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭
圆曲线E(F2m）是方程
y2+xy=x3+ax2+b ⑸
的解集合（x,y），其中x,y∈F2m，连同θ。
E(F2m）的加法规则如下：
（i) θ +θ= θ
（ii) 任给（x,y) ∈E(F2m），则（x,y）⊙ θ=(x,y)
（iii) 任给（x,y) ∈E(F2m），则（x,y)+(x,x+y)= θ，
即点（x,y）的逆为（x,x+y).
（iv) 两个相异且不互逆的点的加法规则：
令（x1,y1），（x2,y2） ∈E(F2m）且有x1≠x2则
（x1,y1） (x2,y2）=(x3,y3），其中
x3=α2+α+x1+x2+a；
y3=α（x1+x3）+x3+y1.
其中 α= (y2+y1）/(x2+x1）
（v) 倍点规则
令（x1,y1） ∈E(F2m），其中x1≠0。则
2(x1,y1）=(x3,y3），其中
x3= α 2+ α +a,y3=x12+（α +1）x3，这里α =(x1+y1/x1）
易见，群E(F2m）为Abel群。
例：F24上的一个椭圆曲线
f(x)=x4+x+1为F2上的一个不可约多项式，易见
F24=F2[x] / (f(x)) = {(k0,k1,k2,k3） | (k0,k1,k2,k3）=k0+k1α+k2α2+k3α3， 

；α为f(x)的零点，ki∈F2}
假定F24上的非超奇异椭圆曲线有下述方程定义：
y2+xy=x3+α4x2+1，注意f（α）=0。
方程应表为：
（1000)y2 + （1000)xy = （1000)x3 + （1100）x2 +（1000) 1985年，N. Koblitz和V. Miller分别独立提出了椭圆曲线密码体制（ECC），

；其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。
⑴知E(Fq）对点的?斣怂阈纬梢桓鯝bel群
设p∈E(Fq），若p的周期很大，即使
p⊙p⊙ …… ⊙p= θ （共有 t个p相加）
成立的最小正整数 t，希望 t 很大。
（t = p的周期，表示为∏（p)=t）。
并且对Q∈E(Fq），定有某个正整数m使
Q=m·p=p⊙ …… ⊙p （共有t个p相加）
定义
m=㏒pQ (m为以p为底Q的对数）。
椭圆曲线上的点形成的群E(Fq），相关它的离散对数
问题是难处理的。 选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。
在E(Fq）中选一个周期很大的点，如选了一个点P=(xp,yp），
它的周期为一个大的素数n，记∏ (P)=n（素数）。
注意：在这个密码体制中，具体的曲线及点P和它的n都
是公开信息。密码体制的形式采用EIGamal体制，是完全
类比过来。
a）密钥的生成
Bob（使用者）执行了下列计算：
i) 在区间[1,n-1]中随机选取一个整数d。
ii) 计算点Q:=dP (d个P相）
iii) Bob公开自己的公开密钥-- (E(Fq),p,n,Q)
iv) Bob的私钥为整数d！
Alice要发送消息m给Bob，Alice执行：
i) 查找Bob的公钥（E(Fq),p,n,Q),
ii) 将m表示成一个域元素m∈Fq,
iii) 在区间[1，n-1]内选取一个随机数k,
iv) 依据Bob的公钥计算点 (x1,y1）：=kP(k个P相）
v) 计算点（x2,y2）：=kQ，如果x2=0，则回到第iii）步
Ⅵ） 计算C:=m·x2
Ⅶ） 传送加密数据（x1,y1,C）给Bob
b) Bob的解密过程
Bob收到Alice的密文（x1,y1,C）后，执行
i) 使用私钥d，计算点（x2，y2）：=d(x1,y1），再计算Fq中x2-1=
通过计算m:=C·x2-1，恢复出明文数据

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息