椭圆曲线公钥密码体制(ECC).ppt

椭圆曲线公钥密码体制(ECC) 主讲人：赵永哲 e_mail: yongzhe @jlu.edu.cn 电话 关于椭圆曲线 椭圆曲线问题的研究有150多年的历史 1985年 Washington 大学的Neal Koblitz IBM 的Victor Miller 把椭圆曲线应用于密码领域 目前，椭圆曲线和RSA算法是使用最广泛的公钥加密算法 实数域上的椭圆曲线 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e 其中a，b，c，d，e是满足某些简单条件的实数。 典型椭圆曲线 椭圆曲线的加法 依据： 如果在椭圆曲线上有三个点存在于一条直线上，则它们的和为无穷远点。 其中无穷远点记为○ 点P和点-P相加 点P和点Q相加 求点P的二倍 求点P的二倍的特例 有限域上的椭圆曲线 定义： 对于曲线 y2 = x3 + ax + b(mod p)，a,b为小于p的整数 当4a3 + 27b2(mod p)不为零时构成有限域Fp上的椭圆曲线群。记为Ep(a,b) 有限域上的椭圆曲线的点的构造 1.对于每一个x (0=xp), 计算z=x3 + ax + b(mod p); 2.若z不是模p的平方根， 则没有具有x值的Ep(a,b)点； 若z是模p的平方根， 则存在满足条件的两个点。 椭圆曲线E23(1,0) 的点的构造 即y2 = x3 + x在有限域F23上的点的构造 椭圆曲线E23(1,0) 的点的构造 满足条件的23个点是: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17) 有限域上的两个点的加法 若 P = (xP , yP)，Q = (xQ , yQ). 若 P 和 Q 是不同的点且 Q 不是 -P, P + Q = R 按如下方法计算： λ = (yP - yQ) / (xP - xQ) mod p xR = λ2 - xP - xQ mod p yR = -yP + λ(xP - xR) mod p 例题 仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，求P+Q 所以P+Q=（17,20），仍为E23(1,1)中的点。 求点P的2倍 若 P = (xP , yP) 若 yP 不为 0 2P = R 按如下方法计算：? λ = (3xP2 + a) / (2yP ) mod p ? xR = λ2 - 2xP mod p ? yR = -yP + λ(xP - xR) mod p 例题 仍以E23(1,1)为例，设P=(3,10)，求2P 所以2P=(7,12)。 练习 1. Does the elliptic curve equation y2 = x3 + 10x + 5 define a group over F17? 2. Do the points P(2,0) and Q(6,3) lie on the elliptic curve y2 = x3 + x + 7 over F17?3. What are the negatives of the following elliptic curve points over F17? P(5,8) Q(3,0) R(0,6)4. In the elliptic curve group defined by y2 = x3 + x + 7 over F17, what is P + Q if P = (2,0) and Q = (1,3)? 5. In the elliptic curve group defined by y2 = x3 + x + 7