第十一讲 椭圆曲线

1、第十一讲 椭圆曲线 1984年，hendrik lenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。 椭圆曲线密码在1985年分别由neal koblitz 和victor miller提出。椭圆曲线密码方案为公钥机制，提供如同rsa一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ecdlp)。 我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ecdlp的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于rsa 短得多的密钥就可以达到与其相同的安全强度。例

2、如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特rsa密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。本讲提要q weierstrass方程q 实域上的椭圆曲线q 有限域上的椭圆曲线q 椭圆曲线密码q 椭圆曲线在分解中的应用 1 weierstrass方程是无穷远点。其中，：有理点的集合是上的的扩域，则是若。下：的判别式，具体定义如是，且，其中，由下述方程定义：上的椭圆曲线域0 ),( = )(4 42 49278 0 : 642233122423243162621862363144221264236348226432164223312axaxaxy

3、xy+a+ayll yxleleklaaaaaaaaaadaadaaadaaddddddddekaaaaax+a+ax+ay=xxy+a+ayeek定义1定义1有理点。上的的所有扩域，并认为无穷远点是点的属于和且坐标有理点是满足曲线方程的曲线远点。是曲线唯一的一个无穷点以上不同的切线。有点都没有两个或两个”的，即曲线的所确保椭圆曲线是“光滑条件的基础域。为的元素。均为域，为系数上的椭圆曲线，这是因是域我们称方程。中的方程称为llkyxlyxlee kkaaaaake) ,( (5) (4) 0 (3) (2)sweierstras (1)64321定义1定义1 评述.评述.2 实域上的椭圆曲线

4、2.1 简化weierstrass方程)274(16 :24124216336123),( :233232131122164223312ba+ax+b=xyeaaaaxayaaxyxx+a+ax+ay=xxy+a+aye这里，2.2 实域上的椭圆曲线73: (b) : )a (322321xyexxye；2.3 加法法则弦和切线法则。表示如上图点。这一几何轴的对称点就是则这个交点关于圆曲线相交于第三点，的直线，这条直线与椭和画一条连接按如下方法求出。首先的和与则上的两个不同的点。是椭圆曲线，和，法说明。令加法法则最好用几何方(a) )( = ) ( = (1)2211rxqprqpeyxqyx

5、p 2.3 加法法则(续)弦和切线法则(续)。何表示如上图点。这一几轴的对称点就是点，这个交点关于二线与椭圆曲线相交于第圆曲线的切线，这条切点做椭。首先，在的倍点按如下方法求出(b) (2)rxprp2.3 加法法则(续)。，。因此，。我们有的第三点有线相交是重根。椭圆曲线与直。得到的方程可以。代入是在这种情况下，直线。，因此，的方程求导数得到：对的斜率可以通过点的椭圆曲线。自加倍点假定我们做。，。因此，我们有。由于有线相交于第三点。因此，椭圆曲线与直得到的方程。代入是的直线和。通过，和，。令被定义为假定一条椭圆曲线)11672(61172473)3)4(8(3)4(882332 )( )3

6、4(374737)(7 10)(3q9) (273 32223232ryxxxexylyxdxdydxxydyeerrryxyxxxexylqppx ye例子1例子12.3 加法法则(续)共线。，。，也可以简化为相加两个点相减。，。因此，我们定义如同整数加法中的用起到了加法单位元的作，由于。gqpgqpqpqpyxyxyxyxpp )3() ( ) ()( )0( ) ()( )2( (1) 评述.评述.2.3 加法法则(续)代数公式 )2/()3( )/()()( )( )( )( 12112121313212333221132。，有任意点有一条附加法则：对于。如果如果并且这里，则。，确定并

7、令由方程令椭圆曲线pppqpyaxqpxxyymyxxmyxxmxyxrqpyxqyx pbaxxye 加法法则.加法法则.2.3 加法法则(续)上的点构成阿贝尔群。椭圆曲线。加法法则符合交换律。加法法则符合结合律：epqqprqprqp (3) : )2()( )( (1) 评述.评述.2.3 加法法则(续)3 有限域上的椭圆曲线3.1 模素数p的椭圆曲线，p2，3情形3.1.1 加法法则 。，这里应该被看成数曲线公式相同，除了实与前面给出的实域椭圆法法则的代数公式的椭圆曲线上的点的加模)1(mod 11pbbaba/bp。，上全部的点为：。，考虑椭圆曲线和令22) (24 13) (19

8、27) (15 6) (13 17) (6 10) (4 24) (17) (24 19) (17 2) (15 25) (10 12) (6 28) (3 5) (126) (20 10) (17 23) (14 4) (10 22) (5 1) (3 22) (027)(27 3) (20 27) (16 6) (14 19) (8 7) (5 23) (2 7) (02) (27 16) (19 2) (16 23) (13 10) (8 19) (4 6) (2 )29(mod204 : 204 32ex + + = xyeb=a=例例子子2 23.1.2 例子。，这意味着。因此，。斜

9、率是。如果需要计算。，这意味着。因此，。斜率是。，如果需要计算。被定义为假定1) (34) 2(1 )5(mod1)( )5(mod3 5) 0(mod4223 4) 2(1,0) (21) (34) (1 )5(mod0)( )5(mod2 5) 1(mod1341 3) (14) (1)5(mod32 131321231313212332yxxmy xxmxmyxxmy xxmxmxxye例子3例子33.1.2 例子(续)3.2 有限域gf(2n)上的椭圆曲线，这该如何处理？实际就是下，由于在模求导数是。例如，对的形式需要做一些修改下计算，椭圆曲线方程如果在模02202 2232yyyba

10、xxy3.2.1简化weierstrass方程。这里：，超奇异这里：，非超奇异：432212323123421311321164223312 )()( 0 )()( 0 c+ax+bcy=xyeyaxyxab+b+axxy=xyeaaaayaaaxayxax+a+ax+ay=xxy+a+aye。，最终，。，。，因此，我们需要得到。，我们有。，因此，第三个点应该是。，曲线方程，可以得到根代入椭圆。是。通过这两个点的直线，。让我们来计算，上的点：我们可以列出所有。：令) 1 0(1) (10) (0 ) 1 0( 0) (0 1) (10) (00) (0 0) (0 1(mod2) 0 0 1)

11、 (10) (0 1) (1 0) (1 1) (0 0) (0 )2(mod 32rrxxyexxyye例子4例子43.2.2 加法法则3.2.2 加法法则(续) ) ( )( / )()( )(2 )/()()( )( )( )( 211313233312121313212333221132。，有任意点有一条附加法则：对于。，对于任何。并且其中，。并且其中，则。，定义并令由方程令椭圆曲线pppcyxpyxpcaxmcyxxmymxyxpxxyymcyxxmyxxmxyxrqpyxqyx pbaxxcyye (超奇异).(超奇异). 加法法则加法法则3.2.2 加法法则(续) ) ,( )(

12、/ )(2 )/()()( )( )( )( 1113321321212333212113313212333221132。，有任意点有一条附加法则：对于。，有，对于任何。并且，。并且这里，则，定义并令由方程令椭圆曲线非pppyxxpyxpxyxmxmxxyxbxammxyxpxxyymyxxxmyaxxmmxyxrqpqpyxqyx pb axxxy ye超奇异).超奇异).( ( 加法法则加法法则3.2.2 加法法则(续)。，和，：椭圆曲线的点计算例子，上所有点如下：。上的非超奇异椭圆曲线考虑定义在。表示，例如，的二进制串为可表示为长度。元定义的有限域考虑由既约多项式0010) (1011

13、= 1111) 2(0010 0001) (0001 =1100) (1100+ 1111) (0010 1001) (1011 1100) (0111 1111) (0010 0010) (1011 1011) (0111 1101) (0010 1011) (1111 1111) (1001 0101) (0101 0001) (0001 0100) (1111 0110) (1001 0000) (0101 0000) (0001 1100) (1100 1001) (1000 1111) (0011 1011) (0000 0000) (1100 0001) (1000 1100) (

14、0011 ) 1( : )gf(21 (0101) )(4)gf(2 )gf(21= )( 32332420123401223344e+z+x+z+xy=xye+zaaaaz+a+az+aza+z +zzf例子5例子53.2.3 例子3.3 点的数量区间。称为，区间。上的椭圆曲线。则是令的阶。上也被称为，上点的数量定义为上的椭圆曲线。为有限域令hasse2121 2121 )gf( )()gf(# )gf(q+q +qq +q+q +#e qq +qeeqeeqehasse定理hasse定理定理1定理1 。的系数的阶上的椭圆曲线限域，下表给出了定义在有内的整数，区间对于每个定义在。令)，(#

15、: gf(37) 372137 372137hasse 37 = 32bae = n +ax +b = xyen+p例子6例子63.3 点的数量(续)3.4 椭圆曲线上的离散对数10) (17 = 31 7) (5 = 23 1) (3 =15 22) (24 = 77) (24 = 30 28) (3 = 22 22) (5 = 14 19) (17 = 619) (8 = 29 7) (0 = 21 27) (16 =13 12) (6 = 524) (1 = 36 6) (14 = 28 27) (27 = 20 13) (19 = 12 27) (15 = 410) (4 = 35 6

16、) (13 = 27 6) (2 = 19 25) (10 = 11 3) (20 = 326) (20 = 34 4) (10 = 26p 23) (2 = 18 23) (13 = 10 19) (4 = 22) (15 = 33 16) (19 = 25 2) (27 = 17 23) (14 = 9 5) (1 = 117) (6 = 32 2) (16 = 24 22) (0 = 16 10) (8 = 8 = 0 5)(1 = 37 =# 204gf(29) 32，上的点。产生的所有，下面给出了由点。的：上的椭圆曲线有限域p pp pppppp pp ppp pp pppp ppp

17、pppppp pppppp pepex + = xye例子7例子7生日攻击。指数索引。必须有大的素数因子。的最小整数。满足是为椭圆曲线并令攻击。令离散对数问题。就被称为椭圆曲线上的。找到这个满足个整数并且我们知道有某和假定有椭圆曲线上的点 (3) (2) hellman-pohlig (1)nnpnekpppkpbkbp 评述.评述.3.4 椭圆曲线上的离散对数(续)4 椭圆曲线密码4.1 明文表示。只需要简单计算恢复出明文消息，我们，为了从点。方根或程，直到我们发现了平我们可以重复上面的过。并尝试新的加我们就对否则，；则我们得到存在，的平方根。如果平方根并尝试计算计算，对于。里，这将可以表示

18、为。满足假定数。的大整作为失败率是可以接受是一个如果将轴，令可以嵌入一个点的。明文消息考虑kxmyxpkj xjyxpypbaxxbaxxkjkjjmkxmpkmmkxmpbaxxymmk )( (3)1 ),( )(mod 110 (2)0 ) 1( (1)21/ )(mod3332得以恢复。消息可以通过，。因此，而到，我们得。对于，的可选值就是，则。假定待加密的消息是我们要求，。由于，则可以令如果我们允许失败率为。：上的椭圆曲线定义在510/5111)(51)179(mod12111)179(mod12172 515951505160 179101/2 72 (179) 231032mpx

19、 +xxxmm kmkkx + = xyegfm例子8例子84.1 明文表示(续)4.2 椭圆曲线elgamal密码系统线上的点乘计算。将模幂计算变成椭圆曲线上的点加计算。将模乘计算变成椭圆曲曲线密码方案：成椭圆的离散对数密码方案变存在一般的方法将经典 (2) (1)。，秘密密钥是的公开密钥是。并计算选择做如下步骤：每个实体的阶。上的点曲线是椭圆对应秘密密钥，这里产生自己的公开密钥和下，开椭圆曲线参数摘要：每一个实体在公密钥对产生椭圆曲线dqadpq ndapennpe (2)11 (1)(elgamal 算法1算法14.2 椭圆曲线elgamal密码系统(续)。中提取明文消息，并从计算应该做

20、如下步骤：出明文消息，为了从密文消息中恢复。给，发送密文消息。和计算。任意选择一个。上的点表示为椭圆曲线将明文消息。公开密钥和，数真实的公开椭圆曲线参得到做如下步骤：解密之。，给实体加密一条消息摘要：实体加密椭圆曲线mmdccmaaccm +kqc = kpcnkmemqnpeabaamb122121 (1) )( (5)= )4(11 )3( (2) )( (1) elgamal 解密.解密. 加密.加密.算法2算法24.2 椭圆曲线elgamal密码系统(续)。，减掉这一部分得：，他从，之后，则首先计算。，和，。她计算并发送给并选择一个随机数下载。，想发送。假定，并公布随机选择。，系统产生

21、。：使用曲线)17435()146672()35766626( )35766626()146672()63215415(3 bob)35766626( )63215415(bob8alice 1743)(5alice)1808413(3bob )11 4()8831(mod453 12132mdckqmckpckqmdp qdpxxye 例子9例子94.2 椭圆曲线elgamal密码系统(续)4.3 椭圆曲线数字签名算法(ecdsa)。，的签名就是对对步。第，则转移到如果。和计算步。，则转移到第如果。和，计算。任意选择做如下步骤：实体。为，公开密钥的秘密密钥为素阶。是点，。假定椭圆曲线参数是的

22、公开密钥验证其签名通过可以任何实体签名。对一个任意长度的消息摘要：实体签名产生和认证) ( (4)(1)0 ) mod( )()( (3)(1)0 ) mod()( (2)11 (1) 11)( = ecdsa1111srmasnre+dksmhernxryxkpnkadpqndapnnpedabma签名产生.签名产生.算法3算法3 拒绝签名。接受签名；否则，返回返回，则。如果轴坐标计算的对，则返回拒绝签名。如果计算。，和，计算。失败，则返回拒绝签名上的整数。如果有任何，都是在区间和验证做如下步骤：，的签名对为了验证续签名产生和认证 ) (mod (4) )3() (mod) (mod) (m

23、od )( (2) 11 (1) )( )(ecdsa121211rvnxv xxx qupuxnwrunweunswmhens rbsrma认证.认证.算法3算法3 。因此，。的p = kpduuqp +uux nd +uudrwe+wrde+ss re+dsk)+ ( = = )mod()( 212121111 正确性证明.正确性证明.签名认证签名认证4.3 椭圆曲线数字签名算法(ecdsa)(续)5 椭圆曲线在分解中的应用5.1 椭圆曲线分解算法。进一步有，。因此，斜率：点的，我们实际需要计算在。可以计算。，和，：。令椭圆曲线令)2773(mod7053)17711 (2312 )277

24、3(mod1771112312 )2773 2312(mod2311767 )2773(mod67)43(2 3)(1 2 3)(1 )2773(mod442773 323232y xmdxdydxxydyppppxxyen例子10例子10。因此，。然而，我们发现的斜率为，和，。通过点。现在，继续计算，我们需要这里，。，因此，解答是续47592773592773) (1770702/17703) (1705)(17712 231)2773 (6 705)(17713)2(1 )(ppppp 例子10例子105.1 椭圆曲线分解算法(续)算法非常相似。的。这与点的情况出现或模这样的乘法使模，做点

25、乘法。希望通过数因子的整数，例如，通常与一个有大量小素在实践中，点。或最大公约数可以分解出了使用周期不相同。这就导致和模不断倍加过程中，模的点上，是希望对椭圆曲线使用椭圆曲线分解整数。不为模的情况，但另一个分母为分母模了一个。换句话，我们先发现，而的曲线。我们发现和曲线，也就是看作两条椭圆们可以把例子中的使用中国剩余定理，我1pollard1000! (3) ) (mod (2)04705947) (mod459) (mod347) (mod 59) (mod (1)pqppqpqpppqepqppe 评述.评述.5.1 椭圆曲线分解算法(续)。我们可以找到分解因子，因此，的倍数而不是是。由于

26、上满足在是最小的正整数，而上满足在是最小的正整数个点。进一步，有个点，而有。计算显示为我们可以分解，的逆。由于时需要计算但是计算都一切正常，这样做下去，到。，我们计算。假定我们设法计算。，和：选择。我们想分解599777640 8!761) (mod 777599) (mod 6403773777761) (mod 52640599) (mod 761599455839 599)(599) 599(mod8! 7! )3!(44!)2!(33! 2! !10 1) (1 55 455839 732mpemmpemeennpppppppppxx yen例子11例子115.1 椭圆曲线分解算法(续)是小素数的乘积。的整数或得条曲线使，则非常可能有至少一，这里多条曲线解因子。如果我们尝试解方法应该可以发现分况下，分着在选择这样曲线的情小素数的乘积。这意味是许多整数，则非常有机会可以使选择曲线如果随机的附近的整数。是一个在说明。数。因此，的倍有可能是并不是非常大的情况下在乘积，则是一组小素数的。如果，因此，有点的数量必然可以整除曲线上足最小正整数在曲线上满。形成的椭圆曲线一般情况下，考虑素数nqepeqpnnenpepnpbnbbnnpnmppep) (mod ) (mod