密码学sec-chap08.ppt

1、第八讲 公钥密码续,2020/8/2,公钥密码,2,第8讲的主要内容,椭圆曲线密码的基本概念 (ECC) 椭圆曲线密码算法 椭圆曲线密码算法的性能,2020/8/2,公钥密码,3,ECC曲线的定义,满足如下方程的点，加上一个无穷远点，构成了椭圆曲线。,椭圆曲线的形状不是椭圆的。只是这个方程类似计算椭圆周长的方程而得名。,2020/8/2,公钥密码,4,ECC曲线的定义,椭圆曲线方程： 曲线上的每个点都是非奇异（或光滑）的 ,即曲线上任意点的偏导数不能同时为0。 对任何域上都有效的定义。（我们只关心有限域）,2020/8/2,公钥密码,5,ECC曲线的定义,2020/8/2,公钥密码,6,ECC

2、曲线的定义,Fq上的椭圆曲线方程:,F2m上的椭圆曲线方程:,2020/8/2,公钥密码,7,ECC曲线的定义,无穷远点： 平行线，永不相交? 平行线是不是在很远的地方相交？ 射影平面(上面的点（x,y,z）) 平行直线的交点为无穷远点，记做P。 直线上出现P点，所带来的好处是所有的直线都相交了，且只有一个交点。 与无穷远点相区别把原来平面上的点叫做平常点。,2020/8/2,公钥密码,8,ECC曲线的定义,无穷远点的性质： 直线L上的无穷远点只能有一个。 平面上一组相互平行的直线有公共的无穷远点。 平面上任何相交的两直线L1,L2有不同的无穷远点。 平面上全体无穷远点构成一条无穷远直线。（想

3、象一下） 平面上全体无穷远点与全体平常点构成射影平面。,2020/8/2,公钥密码,9,ECC曲线的定义,椭圆曲线上的无穷远点在哪里？ （0, ）,2020/8/2,公钥密码,10,ECC曲线上定义的运算:加法,这是抽象的定义,O是P ，P和Q是椭圆曲线上的两点。,2020/8/2,公钥密码,11,ECC曲线上定义的运算:加法,2020/8/2,公钥密码,12,ECC曲线上定义的运算:加法,性质： 3个交点？3次方程，有3个交点。 交换律？ 结合律？,2020/8/2,公钥密码,13,ECC曲线上定义的运算:加法,8个点相同，第9个点就是 (P+Q)+R, P+(Q+R)相等,2020/8/2

4、,公钥密码,14,ECC曲线上定义的运算,如何求解？ 过点P，Q的直线设为,代入方程得：,2020/8/2,公钥密码,15,ECC曲线上定义的运算,P(x1,y1),Q(x2,y2),-R(x3,y3) 根据根与系数的关系,可以解得：,2020/8/2,公钥密码,16,ECC曲线上定义的运算,注意当PQ时，即是求2P。 求曲线斜率K 的时候，注意。,2020/8/2,公钥密码,17,Fq上的椭圆曲线：,当q=23时：a=1,b=1时的曲线,看图： 本质上是一样的。,2020/8/2,公钥密码,18,Fq上的椭圆曲线：,已知E23(1,1)上两点P(3,10)，Q(9,7)， 求1)-P，2)P

5、+Q，3) 2P。 解 1) P的值为(3,-10) 2) k=(7-10)/(9-3)=-1/2，2的乘法逆元为12 因为2*121 (mod 23) k-1*12 (mod 23) 故 k=11。 x=112-3-9=10917 (mod 23); y=113-17-10=8920 (mod 23)故P+Q的坐标为(17,20) 3) k=3(9)+1/(2*10)=1/46 (mod 23) x=62-3-3=3020 (mod 23) y=6(3-7)-10=-3412 (mod 23) 故2P的坐标为(7,12),2020/8/2,公钥密码,19,Fq上的椭圆曲线：困难问题,椭圆曲线

6、上的点的阶 ： 如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O，则将n称为P的 阶，若n不存在，我们说P是无限阶的。 结论:在有限域上定义的椭圆曲线上所有的点的阶n都是存在的,2020/8/2,公钥密码,20,Fq上的椭圆曲线：困难问题,考虑如下等式： K=kG 其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数 给定k和G，根据加法法则，计算K很容易 但给定K和G，求k就相对困难了。 这就是椭圆曲线加密算法采用的难题。我们把点G称为基点（base point）,2020/8/2,公钥密码,21,Fq上的椭圆曲线加密算法,1、用户A选定一条椭圆曲线Ep(a,b)，

7、并取椭圆曲线上一点，作为基点G。 2、用户A选择一个私有密钥k，并生成公开密钥K=kG。 3、用户A将Ep(a,b)和点K，G公开。 4、用户B将待传输的明文编码到Ep(a,b)上一点M，并产生一个随机整数r，用户B计算点C1=M+rK；C2=rG。(密文是两个点) 6、用户B将C1、C2传给用户A。 7、用户A接到信息后，计算C1-kC2，结果就是点M。因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M,2020/8/2,公钥密码,22,椭圆曲线实现密钥交换,公开基点P。 A随机选择PA=nAP，将PA传给B B随机选择PB=nBP，将PB传给A 则A计算PAB=nAPB=nAnBP B也