椭圆曲线公钥密码体制ECC

1、椭圆曲线公钥密码体制椭圆曲线公钥密码体制(ecc)主讲人：赵永哲主讲人：赵永哲e_mail: yongzhe 电话：电话于椭圆曲线关于椭圆曲线椭圆曲线问题的研究有椭圆曲线问题的研究有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位于位于每个垂线上位于位于每个垂线上opq = p点点p和点和点-p相加的和为无穷远点相加的和为无穷远点点点p和点和点q相加相加pqp+qr设连接点设连接点p和和q的直线，交椭圆曲线于点的直线，交椭圆曲线于点r, 则点则点p和和q的和为点的和为点-r求点求点p的二倍的二倍p2*pr过过p点作切线点作切线通过点通过点p作曲线的切线，交曲线于另一点作曲线的切线，交曲线于另一点r, 则则2p=-r求点求点p的二倍的特例的二倍的特例p若点若点p

4、的切线的斜率是的切线的斜率是0，则，则2p=o, 3p=p,4p=o,5p=p有限域上的椭圆曲线有限域上的椭圆曲线 定义：定义：对于曲线对于曲线 y2 = x3 + ax + b(mod p)，a,ba,b为小于为小于p p的整数的整数当当4a3 + 27b2(mod p)不为零时构成有限域不为零时构成有限域fp上上的椭圆曲线群。记为的椭圆曲线群。记为ep(a,b)有限域上的椭圆曲线的点的构造有限域上的椭圆曲线的点的构造 1.1.对于每一个对于每一个x (0=x 3 q = p 3y y2 2 + + xyxy = x = x3 3 + ax + ax2 2 + b + b 对于对于 q =

5、2 q = 2m m 1 1基点基点 g = ( g = (x xg g,y,yg g) ) g g的阶的阶n n h = #e/n. h = #e/n. （#e #e 为椭圆曲线的阶）为椭圆曲线的阶）椭圆曲线的密钥的生成椭圆曲线的密钥的生成已知参数已知参数t: (q, a, b, g, n, h) ,椭圆曲线的公钥椭圆曲线的公钥 q = (xq,yq)是这样生成的是这样生成的:1. 在区间在区间 1,n-1选择一个随机数或伪随机数选择一个随机数或伪随机数d. 2. 计算计算 q = dg. 3. q为公钥为公钥; d为私钥为私钥. 椭圆曲线密钥对的验证椭圆曲线密钥对的验证 已知公钥已知公钥q

6、 = (xq,yq) 和参数和参数t:(q, a, b, g, n, h) 按照如下步骤检查公钥的有效性按照如下步骤检查公钥的有效性1. 检查检查 q o 2. 检查检查xq 和和 yq 是否属于是否属于gf(q). 3. 检查检查q 是否位于椭圆曲线上是否位于椭圆曲线上 4. 检查检查 nq = o. 密钥长度比较密钥长度比较安全级别安全级别对称密码对称密码ecc(n)dsa/rsa(模）模） 56561125128080160102411211222420481281282563072192192384768025625651215360具有具有128位安全强度的实例：位安全强度的实例：s

7、ecp256k1t = (p;a;b;g;n;h) :p = ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f = 2256 -232-29-28-27-26-24-1a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007g = 04 79be667e f9d

8、cbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798 483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8n = ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141h = 01具有具有128位安全强度的实例：位安全强度的实例： sect283k1t = (m; f (x);a;b;g;n;h):m=283 f (x) = x283+x12 +x7+x

9、5+1a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001g = 04 0503213f 78ca4488 3f1a3b81 62f188e5 53cd265f 23c1567a 16876913 b0c2ac24 58492836 01ccda38 0f1c9e31 8d90f95d 07e5426f e87e4

10、5c0 e8184698 e4596236 4e341161 77dd2259n = 01ffffff ffffffff ffffffff ffffffff ffffe9ae 2ed07577 265dff7f 94451e06 1e163c61h = 04公钥密码系统中公钥密码系统中ecc与与rsa的对比的对比 rsa算法的特点之一是数学原理简单、在工程应用算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全强度相对较低。中比较易于实现，但它的单位安全强度相对较低。一般数域筛一般数域筛( (nfs) )方法去破译和攻击方法去破译和攻击rsa算法，它算法，它的破译或求解难度是亚指数级的。的破译或求解难度是亚指数级的。 ecc算法的数学理论非常深奥和复杂，在工程应用算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它的单位安全强度相对较高。中比较难于实现，但它的单位安全强度相对较高。pollard rho方法去破译和攻击方法去破译和攻击ecc算法，它的破译算法，它的破译或求解难度基本上是指数级的。或求解难度基本上是指数级