非对称密码体制杨秋伟湖南大学 计算机与通信学院2021/3/10Page: 1非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/102非对称密码基本概念：对称密码面临的困难对称密码面临的困难o密钥管理密钥管理：若N个人相互保密通信，每人必须拥有(N-1)个私钥，N很大时，需要保存的私钥很多。如何解决？o可信中心分发可信中心分发：共需要发N*(N-1)/2个私钥：例如N =1000时, 999 *1000/2 = 499500o双方事先约定双方事先约定：用户之间自己秘密会面(第一次远距离通信如何办第一次远距离通信如何办？)加密器EK解密器DK密文密文明文明文明文明文K密钥产生器K2021/3/103非对称密码基本概念：非对称密码的提出非对称密码的提出o对称密码的局限性对称密码的局限性n密钥管理的困难性问题n陌生人间的保密通信问题n数字签名问题p非对称密码非对称密码(1976年由W. Diffie和M. Hellman提出)与对称密码的几与对称密码的几点区别点区别：n双钥双钥密码、公钥密码n基于数学函数，而非替换和换位n解决了对称密码的诸多局限性2021/3/104非对称密码基本概念：非对称密码体制非对称密码体制o密钥密钥(PK,SK)nPK：俗称公钥(Public Key)，通常公钥是公开的，可以被任何实体通过有效渠道获取；nSK：俗称私钥(Secret Key)，通常私钥是保密的，不能被任何实体通过非法渠道获取；加密器EK解密器DK密文密文明文明文明文明文PK密钥产生器SK2021/3/105非对称密码基本概念：设计要求设计要求o参与方B容易通过计算产生一对密钥；o在知道公开密钥和待加密消息的情况下，发送方A容易产生密文；o接受方B使用私有密钥容易通过计算解密所得密文，以便恢复原来的消息；o敌手在知道公开密钥的情况下，确定私有密钥计算上不可行；o敌手在知道公开密钥和密文的情况下，恢复消息计算上不可行；o两个密钥中的任何一个可以用来加密，对应的另一个用来解密。2021/3/106非对称密码基本概念：非对称密码的算法组非对称密码的算法组成成p密钥生成密钥生成KG()n根据输入的安全参数 ，输出公钥和私钥对(PK, SK)o加密加密E()n根据输入的公钥和消息，输出密文。o解密解密D()n根据输入的解密私钥和密文，算法输出消息或输出表示密文不合法的特殊符号“?”2021/3/107非对称密码基本概念：非对称密码的原理非对称密码的原理o非对称密码体制：非对称密码体制：加密密钥与解密密钥不同o非对称密码、认证系统的的安全性主要取决于构造非对称算法所依赖的数学问题。要求加密函数具有单单向向性性，即求求逆逆的的困困难难性性。因此，设计双钥体制的关键是先要寻求一个合适的单向函数。加密器EK解密器DK密文密文明文明文明文明文PK密钥产生器SK2021/3/108非对称密码基本概念：单向函数单向函数o令函数f是集A到集B的映射，以f：AB表示。若对任意x1x2，x1, x2A，有f(x1)f(x2)，则称f为单射单射，或1-1映射映射，或可逆的函数可逆的函数。nf为可逆的充要条件是：存在函数g:BA，使对任意xA有gf(x)=x。p一个可逆函数f：AB，若它满足：n对所有xA，易于计算f(x)；n对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单单向(One-way)函数函数。p定义中的“极为困难”是对现有的计算资源和算法而言。2021/3/109非对称密码基本概念：单向函数单向函数p例例一一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即 y = f(x) = ax。式中，xGF(p)，x为满足0 xp1的整数，其逆运算是GF(p)中定义的对数运算，即 x=logay (0 xp1)n由x求y：即使当p很大，也不难实现。为方便计算令a=2。例如p=2100时，需作100乘法。利用高速计算机由x计算ax可在0.1毫秒内完成。n从ax计算x：当p=2100时，以平均速度的计算机进行计算需时约1010.7秒(1年=107.5秒，故约为1600年！其中假定存储量的要求能够满足)。2021/3/1010非对称密码基本概念：单向陷门函数单向陷门函数o满足下列条件的函数f称为单向陷门函数单向陷门函数：n给定x，计算y = f(x)是容易的；n给定y，计算x使y = f(x)是困难的；n存在z，已知z时, 对给定的任何y，若相应的x存在，则计算x使y = f(x)是容易的。p两个难题两个难题n陷门函数其实就不是单向函数，因为单向函数是在任何条件下求逆都是困难的；n陷门可能不止一个，通过试验,一个陷门就可容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。2021/3/1011非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/1012非对称密码体制：Diffie-Hellman密码体制密码体制oDiffie和Hellman在密码学新方向一文中给出了非对称密码算法的思想n它不是真正意义上的非对称密码实例，仅仅是一个单向函数；n算法的目的是使得两个用户安全地交换一个会话密钥。o密钥交换密钥交换(秘密共享秘密共享)n发送方和接受方基于公钥密码体制交换会话密钥；n会话密钥采用对称加密体制加密需要保密传输的消息。2021/3/1013Diffie-Hellman密码体制：密钥交换系统工作密钥交换系统工作原理原理发送者接收者接收者的公钥加密接收者的私钥解密加密解密会话密钥交换阶段会话密钥交换阶段保密信息交换阶段保密信息交换阶段2021/3/1014Diffie-Hellman密码体制：本原元和离散对数本原元和离散对数o本原元本原元：对于一个素数qn如果数值amodq, a2modq,aq-1modq是各不相同的整数；n并且以某种排列方式组成了从1到q-1的所有整数；则称整数a是素数q的一个本原元本原元。o离离散散对对数数：对于一个整数b和素数q的一个本原元a，可以找到一个唯一的指数i，使得b aimodq (0i q-1) 成立，则指数i称为b的以a为基数的模q的离散对数离散对数。2021/3/1015Diffie-Hellman密码体制：算法算法o用户A和用户B之间安全交换会话密钥，已知一个素数q和一个整数a，其中整数a是素数q的一个本原元。n用户A随机选择一个数xA q ，计算 yA axA modq；n用户B随机选择一个数xB q ，计算 yB axB modq；n用户A和用户B分别公开yA、yB；n用户A计算k1 (yB)xA modq，用户B计算k2 (yA)xB modq ，k即为共享的会话密钥。pk1 (yB)xA modq (a)xAxB modq (axA)xB modq (yA)xB modq k22021/3/1016Diffie-Hellman密码体制：实例实例o例例一一：令p = 43，3作为mod43的本原根。令Alice和Bob知道公共参数(p, a)=(43, 3)，Alice和Bob试图协商一个会话密钥。nAlice随机选取她的秘密指数8，计算38 25 mod43，并将结果发送给Bob；nBob随机选取她的秘密指数37，计算337 20 mod43，并将结果发送给Alice；nAlice和Bob分别计算会话密钥 9 208 2537 mod43。2021/3/1017Diffie-Hellman密码体制：算法安全性算法安全性oDeffie-Hellman密钥交换算法安全性源于在有有限限域域上上计计算算离离散散对对数数，它比计算指数更为困难。n攻击者只知道a、q、yA、yB，除非计算离散对数，恢复xA、 xB，否则无济于事。oa和和q的选取的选取n(q-1)/2应该是一个素数，并且q应该足够大：系系统统的的安安全全性性取取决于与决于与q同样长度的数的因子分解的难度同样长度的数的因子分解的难度；n可以选择任何模n的本原元a，通常选择最小的a(一般是一位数)。2021/3/1018Diffie-Hellman密码体制：中间人攻击中间人攻击AliceBob12AliceBob12Malice122021/3/1019Diffie-Hellman密码体制：中间人攻击中间人攻击o用户Alice和用户Bob之间安全交换会话密钥，已知一个素数q和一个整数a，其中整数a是素数q的一个本原元。n1Alice随机选择一个数xA q ，计算 yA axA modq，发送给Malice(Bob)；n1Malice随机选择一个数m q ，计算 yM am modq，发送给Bob；n2Bob随机选择一个数xB q ，计算 yB axB modq，发送给Malice(Alice)；n2Malice将 yM am modq发送给Alice。DH密钥交换协议不支持认证功能，需要额外的身份认证机制来保证安全性。2021/3/1020非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/1021非对称密码体制：背包密码体制背包密码体制oRalph Merkle和Martin Hellman开发了第一个非对称密码算法背背包算法包算法。(背包算法只能用于加密背包算法只能用于加密)o背包问题的描述背包问题的描述：给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中，使之等于一个给定的重量？n给定一系列值m1,m2,mn和一个和s，计算bi使之满足s = b1m1 + b2m2 + + bimio背包密码体制的安全性基于背包难题，它证明了如何将一个NP完全问题应用到非对称密码学，后来被证明是不安全的。2021/3/1022背包密码体制：背包算法的基本思想背包算法的基本思想o背包算法的思想是将消息编码为背包问题的解背包算法的思想是将消息编码为背包问题的解n明文分组长度等于堆中物品的个数，且明文位与bi的值相对应；n密文是计算得到的和值。明文1 1 1 0 0 10 1 0 1 1 00 0 0 0 0 00 1 1 0 0 0背包1 5 6 11 14 201 5 6 11 14 201 5 6 11 14 201 5 6 11 14 20密文1+5+6+20=325+11+14=300=05+6=112021/3/1023背包密码体制：超递增背包序列超递增背包序列o背包密码体制的奥秘：超递增背包序列超递增背包序列n超递增序列超递增序列：它的每一项都大于它之前所有项之和；n例一例一：1, 3, 6, 13, 27, 52o超递增背包问题的解超递增背包问题的解n计算其总重量并与序列中最大的数比较p如果总重量小于这个数，则它不在背包中；p反之，则它在背包中，背包重量减去这个数。n考查数列下一个最大的数，重复直到结束p如果总重量减为零，那么有一个解；p反之无解。2021/3/1024背包密码体制：背包问题易与难之间的转化背包问题易与难之间的转化o问题的转化问题的转化n超递增背包问题的解很容易找到；n非超递增背包问题是困难问题，没有快速解法。o超递增背包问题向非超递增背包问题的转化n取一个超递增序列，比如2, 3, 6, 13, 27, 52；n分别选取n和m，用n去乘所有的项，m作为模数进行模运。比如n = 31, m = 105, 231mod105 625231mod105 37 n得到一个非超递增序列，比如62, 93, 81, 88, 102, 37；n超递增序列作为私人密钥，得到的非超递增序列作为公钥。2021/3/1025背包密码体制：加密加密o加密加密n首先将明文分成长度等于背包序列中项数的多个分组；n用1表示存在，用0表示该项不在其中，计算背包的总重量；n所有分组重复第二步的操作。p例一：例一：明文 “011000110101101110”，背包序列62,93,81,88,102,37n明文分组 = 011000 110101 101110n计算背包总重量，第一组 011000对应 93 + 81 = 174，其它类似n密文 = 174，280，3332021/3/1026背包密码体制：解密解密o解密解密解密者知道私人密钥“超递增背包序列超递增背包序列”n首先计算出n-1以满足n-1n modm 1；n用n-1模m乘密文值的每项；n用私人背包对它进行划分可获得明文。p例一例一：密文 174，280，333，私人密钥2,3,6,13,27,52nn = 31，m = 105，则n-1 = 61；n所有密文值乘61模105，例17461mod105 93+6对应011000；n恢复出的明文为“011000 110101 101110”。2021/3/1027背包密码体制：实现及安全性实现及安全性o背包密码方案实现的限制背包密码方案实现的限制n超递增序列至少要包含250项，每一项的值应在200400位之间；n模数一般在100200位之间。o背包密码方案的安全性背包密码方案的安全性n采用穷举法攻击：一台每秒运行百万次的计算机，要1046年，即使100万台计算机并行处理，太阳毁灭之前也解决不了这个问题；nShamir和Zippel发现了背包问题易与难之间转化的缺陷，可以从非超递增背包序列中重构出超递增背包序列。2021/3/1028非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/1029非对称密码体制：RSA密码体制密码体制o由Rivest、Shamir、Adleman三位密码学家1978年发明的RSA算法是一种用数论构造的，迄今为止最为成熟完善的一个可逆的公钥密码体制，问题难度基于大整数分解。oRSA体制的几个组成部分n密钥生成密钥生成n加密加密n解密解密2021/3/1030RSA密码体制：密钥生成密钥生成o首先选取两个大素数p和q，计算n = pq；o随机选取加密密钥e，使e和(p - 1)(q - 1)互素；o用扩展欧几里德算法计算解密密钥d，以满足：ed = 1mod(p - 1)(q - 1)，即 d = e-1mod(p - 1)(q - 1)；o公开钥为(e, n)，秘密钥为(d, n)。2021/3/1031RSA密码体制：加加/解密解密o加密过程加密过程n加密的数学变换：C = Memodno解密过程解密过程n解密的数学变换： M = Cd modnp正确性验证正确性验证 Cdmodn = (Me)dmodn = Medmodn = Mk(p-1)(q-1)+1modn = MMk(p-1)(q-1)modn (欧拉定理？欧拉定理？)2021/3/1032RSA密码体制：加加/解密解密oM. Mk(p-1)(q-1)modn (欧拉定理？欧拉定理？)nM与n互素，则由欧拉定理Mk(p-1)(q-1)modn 1modn得MMk(p-1)(q-1)modn Mmodn ngcd(M,n) 1，由于n = pq，且p和q都是素数，则M是p或q的倍数。设M = tp，其中t为一正整数， 而gcd(M,q) =1(m n)。由欧拉定理Mq-1modq 1modq得1) Mk(p-1)(q-1)modq1modq Mk(p-1)(q-1) = 1 + rq(两边同时乘以M = tp)2) MMk(p-1)(q-1) =(1 + rq) tp = tp + rtpq = M + rtn3) MMk(p-1)(q-1)modn (M + rtn)modn M modn 2021/3/1033RSA密码体制：举例举例o选p = 7，q = 17。求n = pq = 119， 。取e = 5，满足1 e 0*z=0;for(;m!=1;m=1)if(m%2=0)*(link+*z)=0;else*(link+*z) =1;(*z)+; *(link+*z)=1;快速幂计算快速幂计算intPowerCompute(inta,int*link,intz,intn)inty=1;for(;z0;z-)if(*(link+z)!=0)y=(y*a)%n)*(y*a)%n)%n;elsey=(y*y)%n;if(*link!=0)y=(y*a)%n;returny;2021/3/1036RSA密码体制：RSA密码的密码的安全性安全性oRSA的安全性完全依赖于分解大数的难度的安全性完全依赖于分解大数的难度n从数学上从未证明过需要分解n才能从c和e中计算出m；n可通过猜测(p-1)(q-1)的值来攻击RSA，但这种攻击没有分解n容易；n可尝试每一种可能的d，直到获得正确的一个，这种穷穷举举攻攻击击还没有试图分解n更有效；n129位十进制数字的模数是能分解的临界数，n应该大于这个数。2021/3/1037RSA密码体制：对对RSA的选择密文攻击的选择密文攻击o例一例一(对协议的攻击对协议的攻击)：Eve在Alice的通信过程中进行窃听，设法成功选取了一个用她的公开密钥加密的密文c。Eve想读出信息m，m = cd。nEve选取一个随机数r，满足r小于n。她得到Alice的公钥e：x re modn y xc modn t r-1 modnnEve让Alice用她的私人密钥对y签名，以便解密y：u yd modnnEve计算：tu modn r-1yd modn r-1xdcd modn cd modn m2021/3/1038RSA密码体制：对对RSA的选择密文攻击的选择密文攻击o例例二二(对对协协议议的的攻攻击击)：Trend是一个公开的计算机公证人，Mallory想让Trend对一个本来不愿意签名的消息签名，例如m1。nMallory计算(如果可能的话)：m1 m2m3 modnnEve让Alice用她的私人密钥对m2和m3分别签名；nEve计算：m1d (m2d modn) (m3d modn)利用的缺陷利用的缺陷：指数运算保持了输入的乘法结构(xm)d modn = xdmd modn2021/3/1039RSA密码体制：对对RSA的的公共模数攻击公共模数攻击o不同的使用者采用相同模数n，即使e和d不同，假如两个公钥互素，则无需任何的解密技术就可以恢复明文。n设m位明文，两个公钥为e1和e2，模数为n，两个密文为：c1 me1 modn c2 me2 modnn由于e1和e2互素，根据扩展欧几里德算法找出r和s，满足：re1 + se2 = 1n假定r是负数(r或或s中有一个必须是负数中有一个必须是负数)，用欧几里德算法可计算c1-1：(c1-1)-r c2s = m modn2021/3/1040RSA密码体制：对对RSA的的低加低加/解密指数攻击解密指数攻击o对对RSA的低加密指数攻击的低加密指数攻击n选取较低的e值可以加快计算速度；n采用不同的RSA公钥及相同的e值，对e(e+1)/2个线形相关的消息加密，则存在一种能攻击该系统的方法阻止该攻击的方法是用独立随机值填充消息，使得m和n大小一样。o对对RSA的低解密指数攻击的低解密指数攻击n如果d达到n的1/4大小，且e比n小，那么存在一种攻击能够恢复d；假如e和d随机选择，该攻击很少发生；假如e的值很小，则d的值会比较大，该攻击不可能发生。消息比较短，则md和ce都小于n保证memodn me2021/3/1041RSA密码体制：实现实现RSA密码方案的限制密码方案的限制o根据前面成功的攻击，Jadith Moore列出了使用RSA的一些限制n知道了对于一个给定模数的一个加/解密密钥指数对，攻击者就能分解这个模数；n知道了对于一个给定模数的一个加/解密密钥指数对，攻击者无需分解n就可以计算出别的加/解密对；n在通信网络中，利用RSA的协议不应该使用公共模数；n消息应用随机数填充以避免对加密指数的攻击；n解密指数应该大。2021/3/1042非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/1043非对称密码体制：ElGamal密码体制密码体制oElgamal是一种可应用于加密和签名的密码算法n安全性依赖于有限域上离散对数的难度2021/3/1044ElGamal密码体制：工作原理工作原理o选择一个素数p，两个随机数g和x(gp,xp)，计算ygxmodp。公开密钥是y、g和p，私钥是x。设待加密消息为m：n加密加密p首先选择随机数r，只要r与p-1互素；p计算：a grmodp 和 b yrm modp，a和b作为密文对，密文的长度是明文的两倍；n解密解密p计算： m b/ax modp；n验证验证：axgrx modp，b/ax yrm/axgxrm/gxr mmodp。2021/3/1045ElGamal密码体制：实例实例o密钥生成密钥生成n选取素数p = 2357及Z*2357的生成元2，选取私钥x = 1751并计算gx modp 21751 mod2357 1185公钥是p = 2357, g = 2, gx = 1185。o加密加密n为加密信息m = 2053，选一个随机整数k = 1520，并计算 a 21520mod2357 1430，b 118515202053 mod2357 697。o解密解密na-x 1430-1751mod2357 872，m b/ax modp 697872 2053 2021/3/1046非对称密码体制组成o非对称密码体制的基本概念非对称密码体制的基本概念oDiffie-Hellman密码体制密码体制o背包密码体制背包密码体制oRSA密码体制密码体制oElgamal密码体制密码体制o椭圆曲线密码体制椭圆曲线密码体制2021/3/1047非对称密码体制：椭圆曲线密码体制椭圆曲线密码体制(ECC)oNeal Koblitz和Victor Miller在1985年分别提出了椭圆曲线密码体制(ECC)，它是迄今为止被实践证明安全有效的三类公钥密码体制之一。nECC的安全性基于椭圆曲线离散对数问题的难解性p比整数分解问题和模p离散对数问题难解；p密钥长度大大减少，256比特的ECC密钥达到128比特对称密钥的安全水平；对比RSA，用少得多的比特大小取得同等强度的安全性。p1998年被ISO/IEC定为数字签名标准，2000年2月定为IEEE标准。2021/3/1048非对称密码体制：椭圆曲线密码体制椭圆曲线密码体制(ECC)o椭圆曲线公钥系统是代替椭圆曲线公钥系统是代替RSA的强有力的竞争者有以下的优点的强有力的竞争者有以下的优点n安安全全性性能能更更高高：如160位ECC与1024位RSA、DSA有相同的安全强度；n计计算算量量小小、处处理理速速度度快快：在私钥的处理速度上(解密和签名)，ECC远比RSA、DSA快得多；n存存储储空空间间占占用用小小：ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，所以占用的存储空间小得多；n应应用用前前景景：带宽要求低使得ECC具有广泛得应用前景(比如研究者已把它作为下一代SET协议中缺省的公钥密码算法 )。 2021/3/1049椭圆曲线密码体制：椭圆曲线椭圆曲线o实数域上的椭圆曲线实数域上的椭圆曲线n对于固定的实数a,b，满足方程：y2=x3+ax+b的所有点的集合，外加一个零点和无穷远点O，其中x和y是实数域上取值。o有限域有限域GF(p)上的椭圆曲线上的椭圆曲线n对于固定的a,b，满足方程：y2x3+ax+b(modp)的所有点的集合，外加一个零点和无穷远点O，其中a,b,x,y是有限域GF(p)上取值，p是素数。o有限域有限域GF(2m)上的椭圆曲线上的椭圆曲线n对于固定的实数a,b，满足方程：y2+xy=x3+ax2+b的所有点的集合，外加一个零点和无穷远点O，其中a,b,x,y是有限域GF(2m)上取值。域GF(2m)上的元素是m位的串。2021/3/1050椭圆曲线密码体制：运算规则运算规则o只要非负整数a和b满足：4a3+27b2(modp) 0，那么Ep(a,b)表示模p的椭圆群，这个群中的元素和一个称为无穷远点的O共同组成椭圆群Abel群群(单位元、逆元、交换律、结合律单位元、逆元、交换律、结合律)。n两个互不为逆的点P(x1,y1)和Q(x2,y2)的加法规则加法规则P(x1,y1) + Q(x2,y2) = S(x3,y3) 其中x3=2-x1-x2, y3=(x1-x3)-y1, =(y2-y1)/(x2-x1)n对任意点P(x1,y1)的倍点规则倍点规则 P(x1,y1)+ P(x1,y1)=2P(x1,y1)=Q(x3,y3) 其中，x3=2-2x1, y3=(x1-x3)-y1, =(3x12+a)/2y12021/3/1051椭圆曲线密码体制：关于运算的两个定义关于运算的两个定义o定义一定义一：mP = P + P + P (m个P)o定义二定义二：P是椭圆曲线E上的一个点，若存在最小的正整数n，使得nP = O，其中O是无穷远点，则称n是P的阶数。PQRS = P + Q2021/3/1052椭圆曲线密码体制：系统初始化系统初始化o系统的建立系统的建立n选取一个有限域GF(p)和定义在该域上的椭圆曲线E(a,b)和E(a,b)上的一个阶为n的点P(xp, yp)；nGF(p)、a、b、P(xp, yp)和n都是公开信息。o密钥的生成密钥的生成n在区间1, n-1中随机选取一个整数d；n计算Q = dP；n实体的公开密钥是Q，私钥是证书d。2021/3/1053椭圆曲线密码体制：加密加密oBob试图将消息M发送给Alice时，执行下列操作n查找Alice的公钥Q；n将消息M表示成一个域元素mGF(p)；n在区间1, n-1中随机选取一个整数k；n计算点(x1, y1) = kP；n计算点(x2, y2) = kQ，如果x2 = 0，则返回到第三步；n计算c = mx2；n传送加密数据(x1, y1, c)给Alice。数据类型的转换2021/3/1054椭圆曲线密码体制：解密解密o当Alice解密从Bob收到的密文(x1, y1, c)时，执行下列操作n使用她的私钥d，计算点(x2, y2) = d(x1, y1)；n计算x2-1；n计算c x2-1，而 c x2-1 = mx2 x2-1 = m，即恢复出明文。2021/3/1055椭圆曲线密码体制：整数到域元素的转换整数到域元素的转换o平方剩余平方剩余n如果p是素数，且a小于p，如果 x2 a modp对于一些x成立，则称a是对模p的平方剩余。n例如例如：p = 7, 4 22 52 mod7 (2和5称为平方根)o整数到域元素的转换整数到域元素的转换(设明文消息是设明文消息是m,0mM)n取一个足够大的整数k30,50；n不妨取k = 30，计算一系列的xmk+jj =0,1,2，直到x3+ax+b(modp)是模p的平方剩余；n(x, (x3+ax+b)1/2)即为椭圆曲线上的点。2021/3/1056椭圆曲线密码体制：软件注册保护的应用软件注册保护的应用o注册机的制作注册机的制作(也可称为签名过程)n选择一条椭圆曲线Ep(a,b) 和基点G；n选择私有密钥k(k n,n为G的阶)，计算公开密钥K = kG；n产生一个随机整数r(rn)，计算点R=rG；n将用户名和点R的坐标值x,y作为参数，计算SHA值，即Hash = SHA(username,x,y)；n计算sn r - Hash * k (mod n) n将sn和Hash作为用户名username的序列号2021/3/1057椭圆曲线密码体制：软件注册保护的应用软件注册保护的应用o软件注册的验证软件注册的验证(已知椭圆曲线Ep(a,b)、基点G和公开密钥K)n从用户输入的序列号中，提取sn以及Hash；n计算R sn * G + Hash * K(mod p)，如果sn、Hash正确，其值等于签名过程中点R(x,y)的坐标，因为sn r Hash * k(mod n) sn*G + Hash*K = (r - Hash*k)*G + Hash*K =rG - Hash*kG + Hash*K = rG - Hash*K + Hash*K = rG = R； n计算H = SHA(username,x,y)；n如果“H = Hash”则注册成功。如果“HHash” 则注册失败(为什么？提示注意点R与Hash的关联性)。2021/3/1058椭圆曲线密码体制：软件注册保护的应用软件注册保护的应用o基于椭圆曲线密码的软件注册机的分析基于椭圆曲线密码的软件注册机的分析n软件注册软件注册：椭圆曲线Ep(a,b)、基点G、私有密钥k和随机数r；n软件验证软件验证：椭圆曲线Ep(a,b)、基点G和公开密钥K； nCracker要想制作注册机，只能通过软件中的Ep(a,b)、基点G和公开密钥K，并利用K = kG这个关系获得k后才可以，而求k是很困难的Cracker很难通过跟踪验证算法得到注册机！2021/3/1059