第五章公钥密码学与典型算法

1、第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法1第第5 5章非对称密码体制与典型算法章非对称密码体制与典型算法本章内容本章内容 公钥密码体制概述公钥密码体制概述 RSARSA算法算法 EIGamalEIGamal算法算法 椭圆曲线密码体制椭圆曲线密码体制第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法2教学要求教学要求 掌握公钥密码体制的基本思想掌握公钥密码体制的基本思想 掌握掌握RSARSA公钥密码算法公钥密码算法 了解了解EIGamalEIGamal密码算法密码算法 掌握椭圆曲线域的计算方法掌握椭圆曲线域的计算方法 了解椭圆曲线密码体制的基本原理了解椭圆曲

2、线密码体制的基本原理第第5 5章非对称密码体制与典型算法章非对称密码体制与典型算法第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法35.15.1公钥密码体制概述公钥密码体制概述一、对称密码体制的问题一、对称密码体制的问题密钥管理困难密钥管理困难 n用户保密通信网，用户彼此间进行用户保密通信网，用户彼此间进行保密通信需要保密通信需要 个密钥。个密钥。 n=1000：499500个密钥个密钥 n=5000：12497500个密钥个密钥陌生人间不便进行保密通信陌生人间不便进行保密通信无法实现抗抵赖的数字签名无法实现抗抵赖的数字签名2(1)/ 2nCn n第第5 5章章 非对称密码体制

3、与典型算法非对称密码体制与典型算法4二、非对称密码体制二、非对称密码体制 别名：别名： 公钥密码体制，双钥密码体制公钥密码体制，双钥密码体制 两个密钥：两个密钥： 公开密钥（公钥）：用于加密公开密钥（公钥）：用于加密 秘密密钥（私钥）：用于解密。秘密密钥（私钥）：用于解密。 安全性基础：安全性基础： 基于数学难题基于数学难题 标志性文献标志性文献 W.Diffie and M.E.HellmanW.Diffie and M.E.Hellman, New Directions in , New Directions in Cryptography, IEEE Transaction on Inf

4、ormation Theory, Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654V.IT-22.No.6, Nov 1976, PP.644-654第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法5公钥密码体制的数学模型公钥密码体制的数学模型 由于速度比对称密码算法要慢几个数量级，因此公钥密由于速度比对称密码算法要慢几个数量级，因此公钥密码算法至今主要用于数据安全，或用于短数据和密钥的加密。码算法至今主要用于数据安全，或用于短数据和密钥的加密。第第5

5、 5章章 非对称密码体制与典型算法非对称密码体制与典型算法6对公钥密码体制的要求对公钥密码体制的要求（1 1）参与方）参与方B B容易通过计算产生一对密钥（公开密钥容易通过计算产生一对密钥（公开密钥P PUbUb和私有和私有密钥密钥P PRbRb）。）。（2 2）发送方）发送方A A容易通过计算产生密文：容易通过计算产生密文：c ce ePUbPUb（m m）（3 3）接收方）接收方B B容易通过计算解密密文：容易通过计算解密密文：m md dPRbPRbd dPRbPRb(e(ePUbPUb(m(m)（4 4）他人即使知道公开密钥）他人即使知道公开密钥P PUbUb，要确定私有密钥，要确定私

6、有密钥P PRbRb在计算上在计算上是不可行的。是不可行的。（5 5）他人即使知道公开密钥）他人即使知道公开密钥P PUbUb和密文和密文c c，要想恢复报文，要想恢复报文m m在计在计算上也是不可行的。算上也是不可行的。（6 6）加密和解密函数可以以两个次序中的任何一个来使用）加密和解密函数可以以两个次序中的任何一个来使用: : m md dPRbPRb(e(ePUbPUb(m(m) ) m=em=ePUbPUb(d(dPRbPRb(m(m)第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法7满足下列条件满足下列条件： 给定给定x，容易计算，容易计算y=f(x) 给定给定y =

7、f(x), 难以计算出难以计算出x 存在存在陷门陷门，已知，已知 时时,对给定的对给定的任何任何y，若相应的，若相应的x存在，则计存在，则计算算x使使y=f(x)是容易的是容易的三、陷门单向函数三、陷门单向函数陷门单向函数是公钥密码的核心陷门单向函数是公钥密码的核心Trap-Door One-Way Function实践证明安全的实践证明安全的3 3类公钥密码体制类公钥密码体制 大整数因式分解困难性：大整数因式分解困难性：RSARSA 离散对数难解性：离散对数难解性：DHDH，DSADSA 椭圆曲线离散对数难解性：椭圆曲线离散对数难解性：ECCECC第第5 5章章 非对称密码体制与典型算法非对

8、称密码体制与典型算法8四、公钥密码系统的分析方法四、公钥密码系统的分析方法 强力攻击强力攻击(对密钥对密钥) 密钥不能太短，防止密钥穷举密钥不能太短，防止密钥穷举 但也不能太长，以免影响速度但也不能太长，以免影响速度 公开密钥算法本身可能被攻破公开密钥算法本身可能被攻破 赖以安全的基石赖以安全的基石-数学难题被破解数学难题被破解 可能报文攻击可能报文攻击(对报文本身的强力攻击对报文本身的强力攻击) 对所有可能报文加密，直到与截获密文相同对所有可能报文加密，直到与截获密文相同第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法95.2 RSA算法算法由由Rivest, Shamir和

9、和 Adleman在在1978年提出年提出数学基础数学基础: 大整数因子分解的困难性，大整数因子分解的困难性，Euler定理定理陷门陷门第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法10 明文空间明文空间P密文空间密文空间C=Zn 密钥的生成密钥的生成 选择互异素数选择互异素数p,q，计算，计算n=pq, (n)=(p-1)(q-1)；选择整；选择整数数e使使 gcd(e, (n)=1, 1e (n), 计算计算d=e-1 mod (n) 公钥公钥PU=e,n 公开公开 私钥私钥PR=d,n 中中d保密保密 加密加密 (用用e,n) 明文：明文：mn 密文：密文：c=me m

10、od n 解密解密 (用用d,n) 密文：密文：c 明文：明文：m=cd mod n 一、一、RSA算法描述算法描述 为了安全，为了安全，p p、q q至少为至少为150150位十进制数以上位十进制数以上1 1、算法描述、算法描述第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法11位十进制位十进制 数数位十进制位十进制 数数位十进制位十进制 数数位十进制位十进制 数数位十进制位十进制 数数位十进制位十进制 数数第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法122、RSA要求要求p p、q q应为应为150150位以上的十进制数，但数值不应很接近，长度最位以上的

11、十进制数，但数值不应很接近，长度最好相差几位。好相差几位。 应该很小。应该很小。（p-1p-1）和（）和（q-1q-1）、（）、（p+1p+1）和（）和（q+1q+1）都应有一个大的素因子。）都应有一个大的素因子。 p/qp/q不应是一个接近于带有小分子或小分母的有理数。不应是一个接近于带有小分子或小分母的有理数。模模n n不能共享。不能共享。 公钥公钥e e的值应使计算得到的私钥的值应使计算得到的私钥 。为了满足这个要求，。为了满足这个要求，通常是先选私钥通常是先选私钥d d，满足，满足 且且 ，然后再，然后再由私钥由私钥d d计算公钥计算公钥e e： 。一旦私钥一旦私钥d d暴露，应立即改

12、变暴露，应立即改变p p、q q和和e e、d d。 gcd(1,1)pq4dn4( )ndngcd( , ( )1dn1mod( )edn第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法13互异素数互异素数p,q，n=pq, (n)=(p-1)(q-1), 选择整数选择整数e使使 gcd(e, (n)=1, 1e (n), 计算计算d=e-1 mod (n) 加密加密 (用用e,n) 明文：明文：mn 密文：密文：c=me mod n 解密解密 (用用d,n) 密文：密文：c 明文：明文： m=cd mod n 3、RSA算法证明算法证明m=cd mod n = (me mo

13、d n) d mod n = med mod n = m1+k (n)(n) mod n=(m.m k (n)(n) mod n= =m.(m (n)(n)k mod n=m.(m (n)(n)mod n)k mod n = m. 1k mod n (扩展欧拉定理扩展欧拉定理) =meded =1 mod =1 mod (n)(n)eded = k = k (n)+1(n)+1第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法144 4、RSARSA算法实例算法实例例例5-1 假设假设Alice和和Bob 使用使用RSA密码体制进密码体制进行全英文字符的保密通信。假设行全英文字符

14、的保密通信。假设Alice 选选择择 、 、 ，Bob选选择择 、 ，并采用双字母加、解密方式。，并采用双字母加、解密方式。（1 1）说明）说明AliceAlice和和BobBob建立建立RSARSA密码体制的方法。密码体制的方法。（2 2）若）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给出加密和解密过程。试给出加密和解密过程。 41Ap 67Aq 17Ae 43Bp 59Bq13Be第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法154 4、RSARSA算法实例算法实例例例5-1（1 1）说明）说明AliceAlice

15、和和BobBob建立建立RSARSA密码体制的方法。密码体制的方法。41Ap 67Aq 17Ae 43Bp 59Bq13Be解解 Alice Alice计算：计算：第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法164 4、RSARSA算法实例算法实例例例5-1（1 1）说明）说明AliceAlice和和BobBob建立建立RSARSA密码体制的方法。密码体制的方法。41Ap 67Aq 17Ae 43Bp 59Bq13Be解解 Bob Bob计算计算 ：第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法174 4、RSARSA算法实例算法实例例例5-1（2 2）若

16、）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给出加密和解密过程。试给出加密和解密过程。 41Ap 67Aq 17Ae 43Bp 59Bq13Be解解 Alice Alice加密：加密：“public”public”代换为数字并按双字母分组：代换为数字并按双字母分组：1520 0111 0802 1520 0111 0802 1311mod1520mod 25370095BeBcmn1322mod0111mod 25371648BeBcmn1333mod0802mod 25371410BeBcmn第第5 5章章 非对称密码体制与典型算法非

17、对称密码体制与典型算法184 4、RSARSA算法实例算法实例例例5-1（2 2）若）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给出加密和解密过程。试给出加密和解密过程。 41Ap 67Aq 17Ae 43Bp 59Bq13Be解解 Bob Bob解密解密 ： 密文密文“0095 1649 1410” 0095 1649 1410” 93711mod0095mod 25371520BdBmcnpu93722mod1648mod 25370111BdBmcnbl93733mod1410mod 25370802BdBmcnic明文明文: p

18、ublic: public第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法19如何产生大素数如何产生大素数p p和和q ?q ?如何快速计算如何快速计算 a am m mod n mod n？二、二、RSARSA算法的实现问题算法的实现问题第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法201 1、产生大素数、产生大素数p p和和q q二、二、RSARSA算法的实现问题算法的实现问题WITNESS(a,n)； a 是基数，判断奇数是基数，判断奇数n是否为素数是否为素数将将(n-1) 表示为二进制形式表示为二进制形式bkbk-1b0;d 1; for i k do

19、wnto 0 do x d; d (d d) mod n; if (d = 1) and (x 1) and (x n -1) then return FALSE; if (bi = 1) then d (d a) mod n; if (d 1) then return FALSE; return TRUE; 返回值返回值FALSE：n n一定一定不是素数不是素数TRUE: n n可能是素数可能是素数第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法211 1、产生大素数、产生大素数p p和和q q二、二、RSARSA算法的实现问题算法的实现问题例例 判断判断n=97n=97是否

20、素数，选择是否素数，选择a=2a=2。解解 n-1=96=n-1=96=（11000001100000）2 2i bi x d d 6 1 1 1 2 5 1 2 44 0 8 643 0 64 222 0 22 961 0 96 10 0 1 1素数素数课堂练习课堂练习 判断判断n=57n=57是否素数，是否素数，选择选择a=2a=2。合数合数第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法222、快速计算模指数、快速计算模指数ab mod n要点要点1 1：(a (a b) mod n=(a mod n) b) mod n=(a mod n)(b(b mod n) mod

21、n mod n) mod n 降阶降阶要点要点2 2：a a1616=aaaaaaaaaaaaaaaa=aaaaaaaaaaaaaaaa 计算计算1515次乘法次乘法 a a2 2, a, a4 4,a,a8 8, a, a16 16 计算计算4 4次乘法次乘法启示启示：将：将a ab b的的b b表示为二进制形式表示为二进制形式b bk kb bk-1k-1b b0,0, 即即12012222mod(.() .)modkkkbbbbbbanaaaaan1101102222kkkkbbbbb例例: : 19= 19=（1001110011） 191 202021 21()aaaaaa第第5 5

22、章章 非对称密码体制与典型算法非对称密码体制与典型算法23快速模指数算法计算快速模指数算法计算y=ab mod nb=(bkbk-1b0 )2/y y2 (bi=0 )/y y2 a (bi=1)x 0; y 1for i k downto 0 do x 2x y (y y) mod n if bi=1 then x x+1 y (y a) mod nreturn y22(mod)0(mod)1;iiynbyyanb第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法24例例 计算计算 7560 mod 561x0;y 1for i k downto 0do x 2x y (y y

23、) mod n if bi=1 then x x+1 y (y a) mod nreturn y解解 560=560=（10001100001000110000）2 2i bi d(初值初值=1）9 1 127=7 mod 5618 0 72 =49 mod 5617 0 492 =2401=157 mod 5616 0 1572=24649=526 mod 5615 1 52627=1936732=160 mod 5614 1 1602 7=179200=241 mod 5613 0 2412=58081=298 mod 5612 0 2982=88804=166 mod 5611 0 16

24、62=27556=67 mod 5610 0 672 =4489=1 mod 5617 7560 560 mod 561 = 1mod 561 = 1本题利用欧拉定理本题利用欧拉定理可以直接得到结果可以直接得到结果12012222mod(.() .)modkkkbbbbbbanaaaaan第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法253 3167 167 mod 561 = 504mod 561 = 504x0;y 1for i k downto 0do x 2x y (y y)mod n if bi=1 then x x+1 y (y a)mod nreturn y课堂

25、练习：课堂练习： 计算计算 3 3167 167 mod 561mod 561解解 167=10100111167=10100111i bi d(初值初值=1）7 1 12 3=3 mod 5616 0 32 =9 mod 5615 1 92 3=243 mod 5614 0 2432 =59049=144 mod 5613 0 1442 =20736=540 mod 5612 1 5402 3 =874800=201 mod 5611 1 2012 3 =121203=27 mod 5610 1 272 3 =2187=504 mod 56112012222mod(.() .)modkkkb

26、bbbbbanaaaaan第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法26DESDES和和RSARSA性能比较（同等强度）性能比较（同等强度）美国目前允许出口到我国的密码产品为美国目前允许出口到我国的密码产品为512 bits RSA512 bits RSA和和40bits40bits的某些私钥密码，说明美国已经有了破解方法！的某些私钥密码，说明美国已经有了破解方法！第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法275.35.3EIGamalEIGamal算法算法 由由Taher EIGamal 于于1984年提出年提出 安全性基于安全性基于离散对数问题的

27、难解性离散对数问题的难解性 密文几乎是明文的密文几乎是明文的2倍倍 目前仅用于数字签名目前仅用于数字签名 DSS中采用中采用EIGamal第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法28一、离散对数问题一、离散对数问题 尤其是尤其是p p极大时，如何通过上式计算出极大时，如何通过上式计算出x x在数学在数学上还没有有效的解决方法。上还没有有效的解决方法。 ( )yGF p(mod)xygplog(mod)gxyp假设假设p p是素数，是素数，g g是素域是素域GF(pGF(p) )的一个生成元。如的一个生成元。如果给定一个正整数果给定一个正整数 ，要寻找一个正整，要寻找一个

28、正整数数x x， ，使得，使得 成立，则该成立，则该x x应为：应为：12xp容易计算容易计算难以计算难以计算离散对数问题的难解性！离散对数问题的难解性！第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法29二、二、EIGamal算法算法( )xGF p12xp(mod)xygp1 1、密钥生成、密钥生成 选取一个大素数选取一个大素数p p，满足，满足GF(pGF(p) )中的离散对数问题是中的离散对数问题是难处理的。难处理的。 寻找寻找GF(pGF(p) )的一个生成元的一个生成元g g，它能生成，它能生成GF(pGF(p) )中所有中所有的非的非0 0元素。元素。 选取私钥选

29、取私钥 ，满足，满足 。 计算公钥计算公钥y:y: 私钥私钥x x保密，公钥保密，公钥y y和和p p、g g公开。公开。 第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法30二、二、EIGamal算法算法1modrcgp( )rGF p12rp2 2、加密、加密随机选择一个正整数随机选择一个正整数 ，满足，满足计算明文计算明文 的密文的密文 和和 ： ( )mMGF p1c2c2modrcmyp3 3、解密、解密对于合法密文对于合法密文 和和 ， ，且，且 ，解密得到明文解密得到明文 ： 1c2c12( )ccGF p、10c m121()modxmc cp数据扩展！数据扩展

30、！正确接收时，正确接收时，C10！第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法31二、二、EIGamal算法算法1modrcgp解密公式证明：解密公式证明：2modrcmyp121()modxmc cp112111()mod()() mod () () mod()()modmodxrrxxrrxxrxrc cpmygpm ggpm ggpmp接收方不知道接收方不知道r r，也可正确解密。，也可正确解密。密文的结果与密文的结果与r有关，将不再是惟一。有关，将不再是惟一。素数素数p p应为应为300300位十进制数以上，每次加密应选不同的位十进制数以上，每次加密应选不同的r 。

31、模数相同的模数相同的EIGamalEIGamal算法与算法与RSARSA算法的安全性大致相当。算法的安全性大致相当。 (mod)xygp第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法32EIGamal算法举例算法举例 例例5-45-4 假设假设 BobBob采用采用EIGamalEIGamal密码体制，并选密码体制，并选择素数择素数p=2579p=2579，私钥，私钥x=765x=765，且已知，且已知GF(pGF(p) )的一个生的一个生成元成元g=2g=2。 （1 1） 计算计算BobBob的公钥的公钥y y。（2 2） 若若AliceAlice想秘密发送消息想秘密发送消

32、息m=1299m=1299给给BobBob，且她，且她选择的随机数选择的随机数r=853r=853，试给出，试给出AliceAlice和和BobBob的加密和的加密和解密过程。解密过程。 第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法33EIGamal算法举例算法举例 例例5-45-4 假设假设 BobBob采用采用EIGamalEIGamal密码体制，并选密码体制，并选择素数择素数p=2579p=2579，私钥，私钥x=765x=765，且已知，且已知GF(pGF(p) )的一个生的一个生成元成元g=2g=2。 （1 1） 计算计算BobBob的公钥的公钥y:y:765mo

33、d2mod 2579949xygp(mod)xygp第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法34EIGamal算法举例算法举例 例例5-45-4 假设假设 BobBob采用采用EIGamalEIGamal密码体制，并选密码体制，并选择素数择素数p=2579p=2579，私钥，私钥x=765x=765，且已知，且已知GF(pGF(p) )的一个生的一个生成元成元g=2g=2。 （2 2） 若若AliceAlice想秘密发送消息想秘密发送消息m=1299m=1299给给BobBob，且她，且她选择的随机数选择的随机数r=853r=853，试给出，试给出AliceAlice和

34、和BobBob的加密和的加密和解密过程。解密过程。 949y AliceAlice加密加密: : 8531mod2mod 2579435rcgp8532mod1299 949mod 25792396rcmyp1modrcgp2modrcmyp第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法35EIGamal算法举例算法举例 例例5-45-4 假设假设 BobBob采用采用EIGamalEIGamal密码体制，并选密码体制，并选择素数择素数p=2579p=2579，私钥，私钥x=765x=765，且已知，且已知GF(pGF(p) )的一个生的一个生成元成元g=2g=2。 （2 2

35、） 若若AliceAlice想秘密发送消息想秘密发送消息m=1299m=1299给给BobBob，且她，且她选择的随机数选择的随机数r=853r=853，试给出，试给出AliceAlice和和BobBob的加密和的加密和解密过程。解密过程。 949y BobBob解密解密: : 1435c 22396c 1765121()mod2396 (435)mod 2579 1299xmc cp765435mod 2579242476511(435)mod 25792424mod 25791980121()modxmc cp第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法365.45.4

36、椭圆曲线密码体制椭圆曲线密码体制 由由Neal Koblitz和和Victor Miller在在1985年分别提出年分别提出 安全性基于安全性基于椭圆曲线域离散对数问椭圆曲线域离散对数问题的难解性题的难解性 是目前已知公钥密码体制中每位提是目前已知公钥密码体制中每位提供加密强度最高的一种体制供加密强度最高的一种体制第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法37ECC与与RSA和分组密码的密钥比较和分组密码的密钥比较在安全性能大致相当的情况下在安全性能大致相当的情况下 第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法38一、椭圆曲线及其运算一、椭圆曲线及其运

37、算定义定义 椭圆曲线是两个变元椭圆曲线是两个变元x、y满足形如满足形如三次方程三次方程 y2+axy+by=x3+cx2+dx+e 的所有点的所有点(x,y)的集合，外加一个的集合，外加一个零点零点或或无穷远点无穷远点O。 Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those calculating the circumference of an ellipse. 第第5 5章章 非对称密码体制与典型算法非对称密码体制

38、与典型算法391 1、实数域上的椭圆曲线、实数域上的椭圆曲线 实数域上的椭圆曲线实数域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、b值，满足形如三次方程值，满足形如三次方程 y2=x3+ax+b 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b是实数，是实数，x和和y在实数域上取值在实数域上取值324270ab构成阿贝尔群构成阿贝尔群 第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法40E（-1,0） E（1,1） 实数域椭圆曲线的几何图形实数域椭圆曲线的几何图形互逆点互逆点互逆点互逆点第第5 5章章 非对称密码体制与典型算

39、法非对称密码体制与典型算法41几何定义几何定义 如果椭圆曲线上的三个点位于一条直线上，如果椭圆曲线上的三个点位于一条直线上，那么它们的和为那么它们的和为O。 实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则()()PQPQO互逆点互逆点()()PQPQ点和点基本运算为加法运算基本运算为加法运算第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法42加法单位元为加法单位元为O O，满足，满足实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则互逆点互逆点P、Q，满足，满足OOPOPPQPQO ,),),)PPQQRRP xyQ xyR xy（、（、（PQPQxxyy 且且第第5 5章章

40、非对称密码体制与典型算法非对称密码体制与典型算法43实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则非互逆点非互逆点P、Q的加法规则的加法规则,),),)PPQQRRP xyQ xyR xy（、（、（,),),)PPQQRRP xyQ xyR xy（2RPQxxx()RPRPyxxyQPQPyyxx若若=，则，则R为为无穷远点无穷远点O第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法44实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（,),)2,),)PPPPPPRRP xyP xyP xyR xy（22RPxx()RP

41、RPyxxy232PPxay倍点规则倍点规则若若=，则，则R为为无穷远点无穷远点O第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法45实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则交换律交换律,),),)PPQQRRP xyQ xyR xy（、（、（PQQP结合律结合律PQRPQR（）（）标量乘法标量乘法mPPPPm m个个0 PO()()mPmP 第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法46实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例5-5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ，其上的两个点分别为，其上的两个点分别为 和

42、和 。（1） 计算计算 。（2） 计算计算 。（3） 计算计算 。（4） U点和点和R点是什么关系？点是什么关系？23yxx(1,0)P (2,6)Q PQR2QSPQU第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法47实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例5-5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（1） 计算计算 。23yxx(1,0)P (2,6)Q PQR6062 1QPQPyyxx22( 6)1 23RPQxxx ()6(1 3)02 6RPRPyxxy (1,0)(2, 6)(3, 2 6)PQR第第5 5章章 非对

43、称密码体制与典型算法非对称密码体制与典型算法48实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例5-5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（2） 计算计算 。23yxx(1,0)P (2,6)Q 2QS2233 21112262 6QQxay2211121252()2 2424242 6SQxx 1125112335()(2)66624242882 62 6SQRQyxxy 25352 (2, 6)(,6)24288QS第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法49实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例5-5 已知实数域

44、的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（3） 计算计算 。23yxx(1,0)P (2,6)Q PQU()PQUPQ (,)(2,6)QQQxy6062 1QPQPyyxx 22(6)1 23UPQxxx ()6(1 3)02 6UPUPyxxy (1,0)(2,6)(3,2 6)PQU第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法50实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例5-5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（4） U点和点和R点是什么关系？点是什么关系？23yxx(1,0)P (2,6)Q (1

45、,0)(2,6)(3,2 6)PQU(1,0)(2,6)(3, 2 6)PQRURxxURyy 互逆点关系互逆点关系 结论无普遍意义！结论无普遍意义！第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法512、素域素域GF(pGF(p) )上的椭圆曲线上的椭圆曲线 GF(p)域上的椭圆曲线域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、b值，满足形如三次方程值，满足形如三次方程y2=x3+ax+b (mod p) 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b、x和和y在在GF(p)域上取值域上取值 这类椭圆曲线通常也用这类椭圆

46、曲线通常也用 来表示来表示 构成椭圆群),(mod0)274(23baEpbap( , )pEa b第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法52HasseHasse定理定理 如果如果 是定义在是定义在GF(p)域上的椭域上的椭圆曲线，圆曲线，N是是 上的点的个数，上的点的个数，则：则： ppN2) 1( , )pEa b( , )pEa b第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法53 图图5-3 5-3 椭圆曲线上点的分布椭圆曲线上点的分布第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法54与实数域相同，但所有的运算都是与实数域相

47、同，但所有的运算都是 mod p 运算的结果。运算的结果。分数运算时，既可以进行分数约简，分数运算时，既可以进行分数约简，也可以对分子、分母进行模运算，以也可以对分子、分母进行模运算，以便整除。便整除。 素域素域GF(p) 上椭圆曲线的运算规则上椭圆曲线的运算规则第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法55素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例5-6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ，其上的两个点分别为，其上的两个点分别为 和和 。（1） 计算计算 。（2） 计算计算 。（3） 计算计算 。（4） U点和点和R点是否互逆点

48、？点是否互逆点？231yxx(3,10)P (9,7)Q PQR2PSPQU23(1,1)E第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法56素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例5-6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（1） 计算计算 。231yxx(3,10)P (9,7)Q PQR23(1,1)E7 10320103311 (mod 23)936633QPQPyyxx22(11)3 9121 1210917 (mod 23)RPQxxx ()11 (3 17) 1016420 (mod 23)RPRPyxxy

49、(3,10)(9,7)(17,20)PQR第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法57素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例5-6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（2） 计算计算 。231yxx(3,10)P (9,7)Q 2PS23(1,1)E2233 312851246 (mod 23)22 10202044PPxay222(6)2 3366307 (mod 23)SPxx ()6 (37) 103412 (mod 23)SPRPyxxy 2 (3,10)(7,12)PS第第5 5章章 非对称密码体制与典

50、型算法非对称密码体制与典型算法58素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例5-6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（3） 计算计算 。231yxx(3,10)P (9,7)Q PQU23(1,1)E()PQUPQ (,)(9, 7)(9,16) (mod 23)QQQxy16 1061936QPQPyyxx2213 911 12 (mod 23)UPQxxx ()1 (3 12) 10194 (mod 23)UPUPyxxy (3,10)(9,7)(12,4)PQU第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法59素域

51、素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例5-6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（4） U点和点和R点是否互逆点？点是否互逆点？231yxx(3,10)P (9,7)Q 23(1,1)E(3,10)(9,7)(12,4)PQU(3,10)(9,7)(17,20)PQRURxxURyy U点和点和R点不是互逆点点不是互逆点第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法603 3、有限域、有限域GF(2GF(2n n) )上的椭圆曲线上的椭圆曲线 是对于固定的是对于固定的a、b值，满足形如三次方程值，满足形如三次方程 y2+x

52、y=x3+ax2+b 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b、x和和y在在GF(2n)域上取值域上取值 GF(2n)域上的元素是域上的元素是n位的串，共位的串，共2n个元素个元素 常用常用 表示，表示，b0时构成阿贝尔群时构成阿贝尔群 实际应用中，实际应用中，n n必须足够大，至少必须足够大，至少n=160(n=160(相当于相当于1024 bits RSA)1024 bits RSA)2( , )nEa b第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法61例子例子 例例5-7 由不可约多项式由不可约多项式 定义定义的有

53、限域的有限域 有一个生成元有一个生成元 。（1）列出）列出 上所有的非上所有的非0元素，表明它们与元素，表明它们与生成元生成元 的关系，并验证的关系，并验证 。（2）若椭圆曲线是）若椭圆曲线是 即即 ，检验，检验 是否为是否为 上的点，并列出上的点，并列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。4( )1m xxx (0010)gx4(2 )GFg14(1001)g4402(,)Egg23421yxyxg x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF第第5 5章章 非对称密码体制与典型算法非对称密码体制与

54、典型算法62例子例子 例例5-7 由不可约多项式由不可约多项式 定义定义的有限域的有限域 有一个生成元有一个生成元 。（1）列出）列出 上所有的非上所有的非0元素，元素，表明它们与表明它们与生成元生成元 的关系，并验证的关系，并验证 。4( )1m xxx (0010)gx4(2 )GFg14(1001)gg0=(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) g1

55、5=(0001)4(2 )GF第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法63例子例子 例例5-7 （1）验证）验证 。4( )1m xxx (0010)gx14(1001)g1414gx14(1001)g第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法64例子例子 例例5-7 由不可约多项式由不可约多项式 定义定义的有限域的有限域 有一个生成元有一个生成元 。（2）若椭圆曲线是）若椭圆曲线是 即即 ，检验检验 是否为是否为 上的点，并列出上的点，并列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。4( )1m xxx (

56、0010)gx4402(,)Egg23421yxyxg x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg211ngmod (21)nxxgg213 29132622117()(1110)(1011)(0101)yxyggggggg3429 349227221271()()111(1111)(1011)(0001)(0101)xg xggggggg 是是4(2 )GF第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法65例子例子 例例5-7 由不可约多项式由不可约多项式 定义定义的有限域的有限域 有一个生成元有一个生成元 。（2）若椭圆曲线是）若椭圆曲

57、线是 即即 ，检验，检验 是否为是否为 上的点，并上的点，并列出列出 上所有非上所有非0点的点的坐标值坐标值，画出，画出 上点的上点的分布图分布图。4( )1m xxx (0010)gx4402(,)Egg23421yxyxg x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法66第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法67十进制十进制描述描述例例5-7的坐标的坐标值值第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法68GF(2GF(2n n) )域

58、上椭圆曲线的运算规则域上椭圆曲线的运算规则在在n次不可约多项式次不可约多项式m(x)定义的有限域中定义的有限域中进行进行运算要点：运算要点：加法：按位模加法：按位模2加加乘法、除法：使用生成元乘法、除法：使用生成元注意注意 ， mod (21)nxxgg2101ngg第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法692( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（加法单位元为加法单位元为 ，满足，满足 OOOPOP互逆点互逆点P、Q，满足，满足 PQPQO PQPPQxxx

59、yy且且第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法702( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（非互逆点非互逆点 的加法规则的加法规则PQ、,),),)PPQQRRP xyQ xyR xy（2RPQxxxa()RPRRPyxxxyQPQPyyxx若若=，则，则R为无穷远点为无穷远点O第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法712( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQR

60、RP xyQ xyR xy（、（、（0)Py （倍点规则倍点规则,),)2,),)PPPPPPRRP xyP xyP xyR xy（2Rxa2(1)RPRyxx2PPPxyx若若=，则，则R为无穷远点为无穷远点O第第5 5章章 非对称密码体制与典型算法非对称密码体制与典型算法722( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（0)Py （交换律交换律PQQP结合律结合律PQRPQR（）（）标量乘法标量乘法mPPPPm个0 PO()()mPmP 第第5 5章章 非对称密码体制与典型算法非对称密