第04章椭圆曲线密码体制ECCppt课件.pptxVIP

椭圆曲线密码（ECC）体制;ELGamal密码体制能够在任何离散对数难处理的有限群中实现。我们已经使用了乘法群Zp*，但其他群也是合适的候选者，如椭圆曲线群。

椭圆曲线在代数学和几何学上已广泛研究了150多年之久，有丰富而深厚的理论积累。椭圆曲线密码体制（EllipseCurveCryptosystem，ECC）在l985年由Koblitz和Miller提出，不过一直没有像RSA等密码系统一样受到重视。纵观目前的发展趋势，椭圆曲线已经逐渐被采用，很可能是一个重要的发展方向。;椭圆曲线并非椭圆，这么命名是因为它们是由三次方程描述的，而这些三次方程类似于计算椭圆周长的方程。一般的，描述椭圆曲线方程的形式是

y2+axy+by=x3+cx2+dx+e

其中a、b、c、d和e是满足一些简单条件的实数

一般来说，椭圆曲线还包含了一个特殊的点，即称为无穷远点(PointatInfinity)或零点(ZeroPoint)的O。;对于椭圆曲线上的点可以定义一种形式的加法：如果一个椭圆曲线上的三个点处于一条直线上，那么它们的和为O。从这个定义可以导出椭圆曲线上点的加法法则。

(1)O是加法的单位元，因而O＝－O；对于椭圆曲线上的任何一点P，有P+O＝P。

(2)一条与x轴垂直的线和曲线相交于两个x坐标相同的点P1=(x，y)和P2＝(x,－y)，同时它也和曲线相交于无穷远点，因此P1+P2+O＝O。因而一个点的负值是与其有着相同x坐标和相反的y坐标的点，如图4.1(a)所示。;(3)要对具有不同x坐标的两个点Q与R进行相加，先在它们之间画一条直线并求出第三个交点P1。容易看出这种交点是惟一的。

注意到Q+R+P1＝O，有Q+R＝－P。

特别地，当Q=R时，相当于对一个点Q加倍，只需画出一条切线并求出另一个交点S，那么Q+Q=2Q=－S。

显然，根据定义，此类加法满足交换率和结合率.而一个点的倍乘定义为

nP＝P+P+P+……+P

;椭圆曲线E23(1，1)上的点;Ep(a，b)上的加法规则;例子：;椭圆曲线群中的离散对数也属于难解问题。与通常理解的对数概念不同，由于椭圆曲线群中的运算是加法，加法的倍数对应于原来乘法的指数，因而椭圆曲线群中的离散对数问题是指已知群中的Q和R，求解方程：

R＝kQ中k值的问题。

;对基于F23的椭圆群y2＝x3+9x+17，求R=(4，5)对于Q=(16，5)的离散对数,最直接的方法就是计算Q的倍数，直到找到R。

Q＝(16，5)，2Q=(20，20)，3Q＝(14，14),

4Q=(19，20)，5Q＝(13，10)，6Q＝(7，3)，

7Q＝(8，7)，8Q＝(12，17)，9Q＝(4，5)

因此k关于Q的离散对数是9，对于大素数构成的群Fp，这样计算离散对数是不现实的，事实上现在也没有更好的(非指数级的)算法来解离散对数问题。

;4.4.3椭圆曲线密码算法

;发送者通过对Pm加上kPA来保护Pm。除了发送者之外没有人知道k的值，因此即便PA是公开密钥也没有人能去掉kPA，当然只有知道nA的人才可以去掉kPA。攻击者在不知道nA的情况下要想得到报文只能在知道G和kG的情况下计算出k，这归结为求解椭圆曲线离散对数问题，是非常困难的。

;1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

2、用户A选择一个私有密钥nA，并生成公开密钥PA=nAG。

3、用户A将Ep(a,b)和点PA，G传给用户B。

4、用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点Pm，并产生一个随机整数k（kn,n为基点G的阶）。

5、用户B计算点C1=Pm+kPA；C2=kG。

6、用户B将C1、C2传给用户A。

7、用户A接到信息后，计算C1-nAC2，结果就是点Pm。因为Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=Pm

再对点Pm进行解码就可以得到明文。;这个加密通信中，如果有一个偷窥者H，他只能看到Ep(a,b)、PA、G、C1、C2而通过K、G求nA或通过C2、G求k都是相对困难的。因此，H无法得到A、B间传送的明文信息。;注意到以上的过程并没有说明怎样将作为字符