1 椭圆曲线密码体制椭圆曲线密码体制 主讲人：裴士辉主讲人：裴士辉 e_mail: shihui_pei 电话：电话：13694302598 关于椭圆曲线关于椭圆曲线 ?椭圆曲线问题的研究有椭圆曲线问题的研究有150多年的历史多年的历史 ?1985年年 Washington 大学的大学的Neal Koblitz IBM 的的Victor Miller 把椭圆曲线应用于密码领域把椭圆曲线应用于密码领域 ?目前，椭圆曲线和目前，椭圆曲线和RSA算法是使用最广泛的公钥加 密算法 算法是使用最广泛的公钥加 密算法 2 实数域上的椭圆曲线实数域上的椭圆曲线 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为 它的曲线方程与计算椭圆周长的方程类似。一般 来讲，椭圆曲线的曲线方程是以下形式的三次方 程： 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为 它的曲线方程与计算椭圆周长的方程类似。一般 来讲，椭圆曲线的曲线方程是以下形式的三次方 程： y2+axy+by=x3+cx2+dx+e 其中其中a，b，c，d，e是满足某些简单条件的实数 。 是满足某些简单条件的实数 。 典型椭圆曲线典型椭圆曲线 E : Y2= X3 5X + 8 - 4 - 特点特点: 可以应用几何学使椭圆曲线上的点形成一个群. 特点特点: 可以应用几何学使椭圆曲线上的点形成一个群. 3 椭圆曲线的加法椭圆曲线的加法 ?依据：依据： 如果在椭圆曲线上有三个点存在于一条直线上，则 它们的和为无穷远点 如果在椭圆曲线上有三个点存在于一条直线上，则 它们的和为无穷远点。 ?其中无穷远点记为其中无穷远点记为 点点P和点和点-P相加相加 垂直直线没有第三个交点垂直直线没有第三个交点 Q 在无限远处增加点在无限远处增加点 O 点点 O位于位于每个垂线上位于位于每个垂线上 O P Q = P 点点P和点和点-P相加的和为无穷远点相加的和为无穷远点 4 点点P和点和点Q相加相加 P Q P+Q R 设连接点设连接点P和和Q的直线，交椭圆曲线于点的直线，交椭圆曲线于点R, 则点则点P和和Q的和为点的和为点-R 求点求点P的二倍的二倍 P 2*P R 过过P点作切线点作切线 通过点通过点P作曲线的切线，交曲线于另一点作曲线的切线，交曲线于另一点R, 则则2P=-R 5 求点求点P的二倍的特例的二倍的特例 P 若点若点P的切线的斜率是的切线的斜率是0，则，则2P=O, 3P=P,4P=O,5P=P 有限域上的椭圆曲线有限域上的椭圆曲线 定义： 对于曲线 定义： 对于曲线 y2= x3 + ax + b(mod p)，a,b为小于p的整数 当 ，a,b为小于p的整数 当4a3+ 27b2(mod p)不为零时构成有限域不为零时构成有限域Fp上 的椭圆曲线群。记为 上 的椭圆曲线群。记为Ep(a,b) 6 有限域上的椭圆曲线的点的构造有限域上的椭圆曲线的点的构造 1.对于每一个1.对于每一个x (0=xp), 计算 , 计算z=x3 + ax + b(mod p); 2.若 ; 2.若z不是模不是模p的平方根， 则没有具有 的平方根， 则没有具有x值的值的Ep(a,b)点； 若 点； 若z是模是模p的平方根， 则存在满足条件的两个点。 的平方根， 则存在满足条件的两个点。 椭圆曲线椭圆曲线E23(1,0) 的点的构造的点的构造 即即y2= x3 + x在有限域在有限域F23上的点的构造上的点的构造 7 椭圆曲线椭圆曲线E23(1,0) 的点的构造的点的构造 满足条件的23个点是: 满足条件的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) 8 有限域上的两个点的加法有限域上的两个点的加法 若若P = (xP, yP)，Q = (xQ, yQ). 若若P和和Q是不同的点且是不同的点且Q不是不是-P, P + Q = R按如下方法计算：按如下方法计算： s = (yP- yQ) / (xP- xQ) mod p xR= s2- xP- xQmod p yR= -yP+ s(xP- xR) mod p 例题例题 仍以仍以E23(1,1)为例，设为例，设P=(3,10)，Q=(9,7)，求，求P+Q 所以所以P+Q=（17,20），仍为），仍为E23(1,1)中的点。中的点。 2 3 3 7 1031 11mod23 9362 113910917mod23 11(3 17) 1016420mod23 x y = = = = 9 求点求点P的的2倍倍 若若P = (xP, yP) 若若yP不为不为0 2P = R按如下方法计算：按如下方法计算： s = (3xP2+ a) / (2yP) mod p xR= s2- 2xPmod p yR= -yP+ s(xP- xR) mod p 例题例题 仍以仍以E23(1,1)为例，设为例，设P=(3,10)，求，求2P 所以所以2P=(7,12)。 2 2 3 3 3 3151 6mod23 2 10204 633307mod23 6(37) 103412mod23 x y + = = = = 10 练习练习 1. 如下方程如下方程 y2= x3+ 10x + 5 是否是是否是F17上的椭圆曲线方程上的椭圆曲线方程? 2. 点点 P(2,0)和和 Q(6,3) 是否是是否是 F17上的椭圆曲线方程上的椭圆曲线方程y2= x3+ x + 7上的点上的点 ? 3. 求如下点在求如下点在F17上的椭圆曲线方程的负点上的椭圆曲线方程的负点? P(5,8) Q(3,0) R(0,6) 4. F17上的椭圆曲线方程上的椭圆曲线方程y2= x3+ x + 7 已知已知 P = (2,0)， Q = (1,3) ，求，求P + Q ? 5. F17上的椭圆曲线方程上的椭圆曲线方程y2= x3+ x + 7 已知已知P = (1, 3)，求，求 2P? 椭圆曲线群椭圆曲线群 椭圆曲线椭圆曲线E(Fq)和椭圆曲线和椭圆曲线E(F2m)对于点的加法运算 形成一个 对于点的加法运算 形成一个Abel群群 11 阶阶(order) 椭圆曲线的阶是指椭圆曲线的点个数 椭圆曲线中的点 椭圆曲线的阶是指椭圆曲线的点个数 椭圆曲线中的点P的阶是指满足的阶是指满足kP=O的最小的整数的最小的整数k 椭圆曲线的离散对数问题椭圆曲线的离散对数问题 ?给定椭圆曲线上的点给定椭圆曲线上的点P和点和点Q, 寻找数寻找数k使得使得kP = Q， 其中 ， 其中k称为称为Q基于基于P的离散对数。的离散对数。 ?例如例如: 对于椭圆曲线：对于椭圆曲线： y2= x3+ 9x + 17 over F23, 求点求点Q = (4,5)基于点基于点P = (16,5)的离散对数的离散对数k 12 椭圆曲线的离散对数问题的遍历求法椭圆曲线的离散对数问题的遍历求法 计算计算kP, 直到的到直到的到Q为止为止 P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5) 离散对数为离散对数为k = 9. ECElGamal加密体制加密体制 主要参数：主要参数： 1. 选取有限域选取有限域Fp、椭圆曲线、椭圆曲线Ep及基点及基点PE(p) (这些参数可由一组用户公用这些参数可由一组用户公用). 2. 选取随机数选取随机数a, 计算计算Q=aP. 3. Q作为公钥作为公钥, a作为私钥作为私钥 13 ECElGamal加密体制的加/解密过程加密体制的加/解密过程 ? 加密：加密： Bob发送秘密消息发送秘密消息m给给Alice：: 1.将消息 ：: 1.将消息m转化为椭圆曲线上的点转化为椭圆曲线上的点M; 2.随机选取正整数 ; 2.随机选取正整数k. 3.计算 . 3.计算kP, , kQ=(x, y),若,若x=0或或y=0返回第2步,直到返回第2步,直到 x0,y0. 发送 . 发送C=(kP,M+kQ)给给Alice. . ? 解密： 收到密文 解密： 收到密文C后后, Alice计算计算a(kP)=kQ,得到得到M,进而的到明文进而的到明文m 举例举例 取取p=751，Ep(-1,188)， 即椭圆曲线为 ， 即椭圆曲线为y2x3-x+188, Ep(-1,188)的一个生成元是的一个生成元是G=(0,376)， A的公开钥为的公开钥为PA=(201,5)。 假定 。 假定B已将欲发往已将欲发往A的消息嵌入到椭圆曲线上的点的消息嵌入到椭圆曲线上的点 Pm=(562,201)， B选取随机数选取随机数k=386，由，由kG=386(0,376)=(676,558)， Pm+kPA=(562，201)+386(201,5)=(385,328)， 得密文为 ， 得密文为(676,558),(385,328)。 14 密钥长度比较密钥长度比较 15360512256256 7680384192192 3072256128128 2048224112112 10241608080 5121125656 DSA/RSA(模）模）ECC(n)对称密码安全级别对称密码安全级别 公钥密码系统中公钥密码系统中ECC与与RSA的对比的对比 ?RSA算法的特点之一是数学原理简单、在工程应用 中比较易于实现，但它的单位安全强度相对较低。 算法的特点之一是数学原理简单、在工程应用 中比较易于实现，但它的单位安全强度相对较低。 ?一般数域筛(一般数域筛(NFS)方法去破译和攻击)方法去破译和攻击RSA算法，它 的破译或求解难度是亚指数级的。 算法，它 的破译或求解难度是亚指数级的。 ?ECC算法的数学理论非常深奥和复杂，在工程应用 中比较难于实现，但它的单位安全强度相对较高。 算法的数学理论非常深奥和复杂，在工程应用 中比较难于实现，但它的单位安全强度相对较高。 ?Pollard rho方法去破译和攻击方法去破译和攻击ECC算法，它的破译或 求解难度基本上是指数级的。 算法，它的破译或 求解难度基本上是指数级的。 15 16 17 公钥密码现状公钥密码现状 ?大素数的因式分解大素数的因式分解 ?离散对数离散对数 ?椭圆曲线椭圆曲线 公钥密码方案的实际应用公钥密码方案的实际应用 ?实现速度实现速度 ?通常用于交换对称算法的加密密钥通常用于交换对称算法的加密密钥 ?数字签名算法数字签名算法 18 下次课内容下次课内容 数字签名与密钥管理数字签名与密钥管理 下次课再见！下次课再见！