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

椭圆曲线公钥密码体制椭圆曲线公钥密码体制(ECC)主讲人：赵永哲主讲人：赵永哲e_mail: yongzhe @：：13180888761关于椭圆曲线关于椭圆曲线Ø椭圆曲线问题的研究有椭圆曲线问题的研究有150多年的历史多年的历史 Ø1985年年       Washington 大学的大学的Neal Koblitz        IBM 的的Victor Miller       把椭圆曲线应用于密码领域把椭圆曲线应用于密码领域Ø目前，椭圆曲线和目前，椭圆曲线和RSA算法是使用最广泛的公钥加算法是使用最广泛的公钥加密算法密算法实数域上的椭圆曲线实数域上的椭圆曲线 •椭椭圆圆曲曲线线并并非非椭椭圆圆，，之之所所以以称称为为椭椭圆圆曲曲线线是是因因为为它它的的曲曲线线方方程程与与计计算算椭椭圆圆周周长长的的方方程程类类似似一一般般来来讲讲，，椭椭圆圆曲曲线线的的曲曲线线方方程程是是以以下下形形式式的的三三次次方方程：程：•y2+axy+by=x3+cx2+dx+e•其中其中a，，b，，c，，d，，e是满足某些简单条件的实数是满足某些简单条件的实数典型椭圆曲线典型椭圆曲线E : Y2 = X3 – 5X + 8- 4 -特点特点: 可以应用几何学使椭圆曲线上的点形成一个群. 椭圆曲线的加法椭圆曲线的加法Ø依据：依据：  如如果果在在椭椭圆圆曲曲线线上上有有三三个个点点存存在在于于一一条条直直线线上上，，则则它们的和为无穷远点它们的和为无穷远点。

Ø其中无穷远点记为其中无穷远点记为○○ 点点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的切线的斜率是的切线的斜率是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

则存在满足条件的两个点 椭圆曲线椭圆曲线E23(1,0) 的点的构造的点的构造即即y2 = x3 + x在有限域在有限域F23上的点的构造上的点的构造椭圆曲线椭圆曲线E23(1,0) 的点的构造的点的构造满足条件的满足条件的2323个点是个点是: :    (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         over F17, what is 2P if P = (1, 3)?  上的椭圆曲线上的椭圆曲线 定义：定义：对于曲线对于曲线 y2 +xy= x3 + ax2 + b b不不为0 0，，a,b 属于属于的解的集合构成的解的集合构成 上的椭圆曲线群。

记为上的椭圆曲线群记为 上的椭圆曲线举例上的椭圆曲线举例 •作为一个简单的例子作为一个简单的例子, 考略考略         , 其上的不可约多项式为其上的不可约多项式为 f(x) = x4 + x + 1. •元素元素g = (0010)是生成元是生成元.•g的幂为的幂为:    g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000)   g4 = (0011) g5 = (0110) g6 = (1100) g7 = (1011)   g8 = (0101) g9 = (1010) g10 = (0111) g11 = (1110)    g12 = (1111) g13 = (1101) g14 = (1001) g15 = (0001)  上的椭圆曲线举例上的椭圆曲线举例 •对于椭圆曲线对于椭圆曲线 y2 + xy = x3 + g4x2 + 1. 其中其中 a = g4 ，，    b = g0 =1. •点点 (g5, g3) 满足椭圆曲线方程满足椭圆曲线方程 :               y2   +  xy      =  x3       +  g4x2         +  1         (g3)2    + g5g3    = (g5)3    + g4g10        +   1             g6     + g8        = g15       + g14          + 1          (1100) + (0101) = (0001) + (1001) + (0001)                         (1001) = (1001) 椭圆曲线椭圆曲线T=(m=4,f(x)=x4+x+1,g=0010,a=g4,b=g0)的点的构造的点的构造 (1, g13)     (g3, g13)     (g5, g11)  (1, g6)      (g3, g8)       (g5, g3)  (g6, g14)   (g9, g13)      (g10, g8)   (g12, g12)  (g6, g8)    (g9, g10)      (g10, g)     (g12, 0)  (0, 1)  上椭圆曲线的点的加法逆元上椭圆曲线的点的加法逆元 • P = (xP, yP)的加法逆元的加法逆元 -P = (xP, xP + yP)• P + (-P) = O• P + O = P  上椭圆曲线不同的点的加法运算上椭圆曲线不同的点的加法运算 P = (xP, yP) 。

如果如果 P和和 Q是不同的点并且是不同的点并且P不等于不等于 -Q, 则则P + Q = R s = (yP - yQ) / (xP + xQ) xR = s2 + s + xP + xQ + a yR = s(xP + xR) + xR + yP 例题例题椭圆曲线椭圆曲线T=(m=4,f(x)=xT=(m=4,f(x)=x4 4+x+1,g=0010,a=g+x+1,g=0010,a=g4 4,b=g,b=g0 0) )点点P=(gP=(g6 6,g,g8 8) )点点Q=(gQ=(g3 3,g,g1313) )求点求点R=P+QR=P+Q 上椭圆曲线的点上椭圆曲线的点P的的倍点运算倍点运算 若若 xP = 0, 那么那么 2P = O 假设假设 xP 不等于不等于 0 2P = R  s = xP + yP / xP xR = s2+ s + ayR = xP2 + (s + 1) * xR 例题例题椭圆曲线椭圆曲线T=(m=4,f(x)=xT=(m=4,f(x)=x4 4+x+1,g=0010,a=g+x+1,g=0010,a=g4 4,b=g,b=g0 0) )点点P=(gP=(g6 6,g,g8 8) )求点求点R=2PR=2P练习练习已知已知 F(23））. 不可约多项式不可约多项式x3 + x + 1. 生成元生成元 g = (010)并且并且g1 = (010) g2 = (100) g3 = (011) g4 = (110)         g5 = (111) g6 = (101) g7 = (001) = 1 1.方程方程 y2 + xy = x3 + g5x2 + g6是否定义了是否定义了F(23)上的上的 一个椭圆曲一个椭圆曲线线? 2. 问点问点 P(g3, g6)和和 Q(g5, g2) 是否位于是否位于F(23)上的椭圆曲线上的椭圆曲线 y2 + xy = x3 + g2 x2  + g6 之上之上? 3. 求求F(23)上的如下椭圆曲线的点的加法逆元上的如下椭圆曲线的点的加法逆元?     P(g3,g6) Q(g,0) R(0,g3) 4. F(23)上的椭圆曲线上的椭圆曲线 y2 + xy = x3 + g2x2 + g6 , P = (g2,g6)，， Q = (g5,g5)，求，求P+Q? 5. F(23)上的椭圆曲线上的椭圆曲线 y2 + xy = x3 + g2x2 + g6, P = (g3, g4),求求2P?群群群(G, *)是由集合是由集合G和集合上的二元运算和集合上的二元运算* 组成的代数系统，群应满足如组成的代数系统，群应满足如下的性质下的性质 :1、封闭性、封闭性 : 对于任意的对于任意的 x,y ∈ ∈G，满足，满足 x * y   G2、结合律、结合律 :对于任意的对于任意的 x,y, z ∈ ∈G，， 满足：满足： (x * y) * z = x * (y * z)3、有单位元素、有单位元素 : 存在单位元素存在单位元素 e ∈ ∈ G ，满足：，满足： 对于任意的对于任意的x∈ ∈G，有，有 x * e = e * x = x4: 有逆：有逆：对于任意的对于任意的x∈ ∈G ,都存在都存在y ∈ ∈ G ，满足：，满足： x * y = y * x = e另外，如果满足交换另外，如果满足交换律，即对于律，即对于x, y ∈ ∈ G ，满足，满足 x * y = y * x 则则称群为称群为 abelian group.举例举例1.   Z,+  其中Z表示整数集 2.  Z,×.3.   Z,—  4.  R,×其中Z表示实数集有限域有限域有限域是指由集合有限域是指由集合 F 和和F上的二元运算上的二元运算+ 和和 * 组成的代数系统，有限域组成的代数系统，有限域应满足如下性质应满足如下性质:1.F 对于对于 +运算是运算是abelian群群.2.F \ {0}对于对于*运算是运算是abelian群群.3. 分配律对任意的分配律对任意的 x ,y , z ∈ ∈ F，满足，满足: x * ( y + z) = (x * y) + (x * z) (x + y) * z = (x * z) + (y * z)有限域的阶有限域的阶(order of the finite field)是指有限域的元素的个是指有限域的元素的个数数有限域也称为有限域也称为Galois域域有限域 F(p)其中集合为整数集其中集合为整数集 {0,1,2,3….p-1} ，， p是素数是素数.另外满足如下性质另外满足如下性质 :1.加法加法 : 对于对于 a, b   F(p), 有有a + b ≡ r mod p 2. 为模加法为模加法 2.乘法乘法 :对于对于a, b   F(p), 有有 a . b = s mod p                  为模乘法为模乘法有限域有限域 GF(2m)二元有限域二元有限域. 其中的集合为其中的集合为m个元素的集合个元素的集合 { m-1, …, 1,  0}，每个，每个  i   {0,1} ，都与任意的，都与任意的a   GF(2m) a =  m-1xm-1 + … +  1x +  0同时满足如下性质同时满足如下性质 :a = {am-1,..a1,a0} 和和 b = {bm-1,..b1,b0}   GF(2m) •加法加法 : a + b = c = {cm-1,..c1,c0} 其中其中 ci = (ai + bi) mod 2. c   GF(2m) •乘法乘法 : a . b = c = {cm-1,..c1,c0} 其中其中 c 是是 a(x) . b(x) 除以一个除以一个m阶不可约多项式的余式，阶不可约多项式的余式， 同时同时c   GF(2m) 椭圆曲线群椭圆曲线群椭圆曲线椭圆曲线E：：F(q)和椭圆曲线和椭圆曲线E:F(2m)对于点的加法运对于点的加法运算形成一个算形成一个Abel群群阶阶(order)椭圆曲线的阶是指椭圆曲线的点个数椭圆曲线的阶是指椭圆曲线的点个数椭圆曲线中的点椭圆曲线中的点P的阶是指满足的阶是指满足kP=O的最小的整数的最小的整数k练习练习确定椭圆曲线确定椭圆曲线T：：( q=7, a=0, b=2 )的阶。

的阶确定椭圆曲线确定椭圆曲线T：：( q=7, a=0, b=2 )的点的点(3, 6)的阶椭圆曲线的离散对数问题椭圆曲线的离散对数问题 Ø    给定椭圆曲线上的点给定椭圆曲线上的点 P 和点和点 Q ,        寻找数寻找数 k 使得使得 kP = Q，，        其中其中k称为称为Q基于基于P的离散对数的离散对数Ø例如例如:       对于椭圆曲线：对于椭圆曲线：       y2 = x3 + 9x + 17 over F23,       求点求点Q = (4,5) 基于点基于点 P = (16,5)的离散对数的离散对数k椭圆曲线的离散对数问题的遍历求法椭圆曲线的离散对数问题的遍历求法   计算计算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. 群群 Zp* 和和E(Fp) 的比较的比较群群Zp*E(Fp)群元素群元素整数整数{1, 2, …, p-1}坐标属于坐标属于Fp 的椭圆曲线上的点的椭圆曲线上的点的集合加上的集合加上O群上的运算群上的运算模模 p乘法乘法点的加法点的加法表示表示元素元素：：g, h乘法乘法：：g•h逆逆：：g-1除法除法：： g / h 幂幂：： ga元素元素：：P, Q加法加法：：P+Q逆逆：：-P减法减法：：P-Q乘乘：：aP离散对数问题离散对数问题已知已知 g  Zp*和和 h = ga mod p,求求 a已知已知 P  E(Zp)和和 Q = aP,求求 aECElGamal加密体制加密体制 主要参数：主要参数：1. 选取有限域选取有限域Fp、、椭圆曲线椭圆曲线Ep及基点及基点P∈∈E(p) (这些参数可由一组用户公用这些参数可由一组用户公用).2. 选取随机数选取随机数a, 计算计算Q=aP.3. Q作为公钥作为公钥, a作为私钥作为私钥 ECElGamal加密体制的加加密体制的加/ /解密过程解密过程Ø加密：加密： Bob发送秘密消息发送秘密消息m给给Alice：：: : 1. 1.将消息将消息m转化为椭圆曲线上的点转化为椭圆曲线上的点M; ; 2. 2.随机选取正整数随机选取正整数k. . 3. 3.计算计算kP, , kQ=(x, y), ,若若x=0或或y=0返回第返回第2 2步步, ,直到直到 x≠0,y≠0. . 发送发送C=(kP,M+kQ)给给Alice. .Ø解密：解密： 收到密文收到密文C后后,    Alice计算计算a(kP)=kQ,得到得到M,进而的到明文进而的到明文m 举例举例取取p=751，，Ep(-1,188)，，即椭圆曲线为即椭圆曲线为y2≡x3-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)}练习练习已知已知ECElGamal加密算法中加密算法中的椭圆曲线为的椭圆曲线为T ： (q=11, a=1, b=6, G=(2，7)) B的私钥为的私钥为nB=71. 确定确定B的公钥的公钥2. A要加密消息要加密消息Pm=(10,9), 并且选择了随机数并且选择了随机数K=3,    确定确定A发送给发送给B的密文的密文练习练习已知已知 F(23）：）： 不可约多项式不可约多项式x３３ + x + 1. 生成元生成元 g = (010)并且并且g1 = (010) g2 = (100) g3 = (011) g4 = (110)         g5 = (111) g6 = (101) g7 = (001) = 1ECElGamal加密算法中加密算法中椭圆曲线为椭圆曲线为T ： (m=3, f(x)= x３３ + x + 1 , a=100, b=101) B的私钥为的私钥为nB=3B收到的密文为（（收到的密文为（（100，，101）（）（111，，111））））求其解密后的明文求其解密后的明文椭圆曲线的参数椭圆曲线的参数GF(qGF(q) )下的下的椭圆曲曲线的参数是一个的参数是一个6 6元数元数组：：   T = (q, a, b, G, n, h) T = (q, a, b, G, n, h) •q = p q = p 或或 q = 2q = 2m m•a a 和和 b b   GF(qGF(q) )y y2 2   x x3 3 + ax + b (mod p) + ax + b (mod p) 对于于 q = p > 3 q = p > 3y y2 2 + + xyxy = x = x3 3 + ax + ax2 2 + b + b 对于于 q = 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 = (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位安全强度的实例：位安全强度的实例：secp256k1T = (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   F9DCBBAC  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+x5+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 E87E45C0                      E8184698 E4596236 4E341161 77DD2259n = 01FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFE9AE        2ED07577 265DFF7F 94451E06 1E163C61h = 04公钥密码系统中公钥密码系统中ECC与与RSA的对比的对比 ØRSA算法的特点之一是数学原理简单、在工程应用算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全强度相对较低。

中比较易于实现，但它的单位安全强度相对较低Ø一般数域筛一般数域筛( (NFS) )方法去破译和攻击方法去破译和攻击RSA算法，它的算法，它的破译或求解难度是亚指数级的破译或求解难度是亚指数级的  ØECC算法的数学理论非常深奥和复杂，在工程应用算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它的单位安全强度相对较高中比较难于实现，但它的单位安全强度相对较高ØPollard rho方法去破译和攻击方法去破译和攻击ECC算法，它的破译或算法，它的破译或求解难度基本上是指数级的求解难度基本上是指数级的 公钥密码现状公钥密码现状Ø大素数的因式分解大素数的因式分解Ø离散对数离散对数Ø椭圆曲线椭圆曲线 公钥密码方案的实际应用公钥密码方案的实际应用Ø实现速度实现速度 Ø通常用于交换对称算法的加密密钥通常用于交换对称算法的加密密钥Ø数字签名算法数字签名算法下次课内容下次课内容流密码和分组密码加密模式流密码和分组密码加密模式下次课再见！下次课再见！。