椭圆曲线加密算法(ECC).ppt

椭圆曲线加密算法（ECC）假如平行线在很远很远的地方相交了？即平行线相交于无穷远点P∞：

无穷远点与平常点
与无穷远点相区别把原来平面上的点叫做平常点

由此出现了射影坐标系

射影平面坐标系是对普通平面直角坐标系的扩展：
增加无穷远点P∞
构造方法：
对普通平面直角坐标系上的点A的坐标（x,y）做如下改造：令x=X/Z，y=Y/Z（Z≠0）；则A点可以表示为（X:Y:Z）。变成了有三个参量的坐标点，这就对平面上的点建立了一个射影平面坐标体系。一条椭圆曲线是在射影平面上满足方程：

的所有点的集合，且曲线上的每个点都是非奇异的
椭圆曲线上有一个无穷远点O∞（0:1:0）（满足方程）
椭圆曲线的形状不是椭圆的：

设x=X/Z，y=Y/Z代入方程得到：

上述方程加上无穷远点O∞构成了平面上的椭圆曲线

椭圆曲线上的切线斜率

运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点，过做y轴的平行线交于R。规定:
前面所述的椭圆曲线是连续的，并不适合用于加密；必须把椭圆曲线变成离散的点
有限域Fp上：
有限域Fp中只有p（p为素数）个元素0,1,2……p-2,p-1；
加法(a+b)法则：a+b≡c(modp)
乘法(a×b)法则是：a×b≡c(modp)
除法(a÷b)法则：a/b≡c(modp)
单位元是1，零元是0
将椭圆曲线定义到有限域Fp上就变成了离散的椭圆曲线将这条曲线定义在Fp上：
选择两个满足下列条件的小于p(p为素数)的非负整数a、b
则满足下列方程的所有点(x,y)，再加上无穷远点O∞构成一条椭圆曲线:
其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)的图像：对于椭圆曲线上的某个点P，存在一个最小的数n，使得，那么n就是P点的阶。
终于进入正题了…加密/解密

签名&生成软件序列号公开密钥算法总是要基于一个数学上的难题。
RSA：给定两个素数p、q很容易相乘得到n，而对n进行因式分解却相对困难。
那椭圆曲线上有什么难题呢？
考虑K=kG，其中K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数。
给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。
点G：基点（basepoint）
k（k<n，n为基点G的阶）：私有密钥（privatekey）
K：公有密钥（publickey)
用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
用户A选择一个私有密钥k，并生成公开密钥。
用户A将Ep(a,b)和点K，G传给用户B。
用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）。
用户B计算点。
用户B将C1、C2传给用户A。
用户A接到信息后，计算，结果就是点M。
再对点M进行解码就可以得到明文。上图是ECC加密/解密的图示，从中可以看到如果有一个偷窥者H，他只能看到Ep(a,b)、K、G、C1、C2而通过K、G求k或通过C2、G求r都是相对困难的。因此，H无法得到A、B间传送的明文信息。描述一条Fp上的椭圆曲线，常用到六个参量：
T=(p,a,b,G,n,h)
p、a、b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的整数部分
参量值一般要求满足以下几个条件：
p越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求

签名过程：
选择一条椭圆曲线Ep(a,b)，和基点G；
选择私有密钥k（k<n，n为G的阶），利用基点G计算公开密钥；
产生一个随机整数r（r<n），计算点；
计算SHA值，即；
计算；
将sn和Hash作为用户名username的序列号验证过程（软件中存有椭圆曲线Ep(a,b)，和基点G，公开密钥K）：
从用户输入的序列号中，提取sn以及Hash；
计算点，如果sn、Hash正确，其值等于软件作者签名过程中点R(x,y)的坐标，因为所以
计算；
如果H=Hash则注册成功。如果H≠Hash，则注册失败。
简单对比一下两个过程：
作者签名用到了：椭圆曲线Ep(a,b)，基点G，私有密钥k，及随机数r。
软件验证用到了：椭圆曲线Ep(a,b)，基点G，公开密钥K。Microsoft的产品安装Key为25位字符，这25位字符是如何得出来的呢？下面将一一叙述…Base24：这25个字符实际是114bits的数据用Base24进行UUCode后的结果，做为安装Key，这个Base必须绝对避免误认，所以Microsoft选择了以下这24个字符做为UUCode的Base：BCDFGHJKMPQRTVWXY2346789上页所述的114位数据按Intel高位在后