《-公钥密码体制精讲ppt课件.ppt》由会员分享，可在线阅读，更多相关《-公钥密码体制精讲ppt课件.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章章非对称密码体制非对称密码体制1为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l学习要点：学习要点：l了解非对称密码体制的提出背景、基本思想了解非对称密码体制的提出背景、基本思想l了解非对称密码体制的基本应用方向了解非对称密码体制的基本应用方向l了解三种典型的公钥密码体制了解三种典型的公钥密码体制l DH密钥交换算法密钥交换算法lRSA2为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益61概述概述l问题的提出：问题的提出：l密钥管理困难密钥管理困难l
2、传统密钥管理两两分别用一对密钥时，则传统密钥管理两两分别用一对密钥时，则n 个用户需要个用户需要C(n,2)=n(n-1)/2 个密钥，当个密钥，当用户量增大时用户量增大时密钥空间急剧增大密钥空间急剧增大。如。如:ln=100 时时C(100,2)=4,995ln=5000 时时C(5000,2)=12,497,500l陌生人间的保密通信问题陌生人间的保密通信问题 l数字签名的问题数字签名的问题l传统加密算法无法实现抗抵赖的需求传统加密算法无法实现抗抵赖的需求3为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益4为了规范事业单位
3、聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6.1.1 公钥密码体制公钥密码体制l公钥密码又称为双钥密码、非对称密码公钥密码又称为双钥密码、非对称密码l公钥密码体制提出的标志性文献：公钥密码体制提出的标志性文献：lW.Diffie and M.E.Hellman,New Directions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-6545为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作
4、人员聘用制度，保障用人单位和职工的合法权益6为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6.1.2 对公钥密码体制的要求对公钥密码体制的要求（1）参参与与方方B容容易易通通过过计计算算产产生生一一对对密密钥钥（公公开密钥开密钥KUb和私有密钥和私有密钥KRb）。）。（2）在在知知道道公公开开密密钥钥和和待待加加密密报报文文M的的情情况况下下，对对于于发发送送方方A，很很容容易易通通过过计计算算产产生生对对应应的的密密文：文：CEKUb（M）（3）接接收收方方B使使用用私私有有密密钥钥容容易易通通过过计计算算解解密密所所得得
5、的的密密文文以以便便恢恢复复原原来来的的报报文文：MDKRb（C）DKRb（EKUb（M）7为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（4）敌敌对对方方即即使使知知道道公公开开密密钥钥KUb，要要确确定定私私有密钥有密钥KRb在计算上是不可行的。在计算上是不可行的。（5）敌敌对对方方即即使使知知道道公公开开密密钥钥KUb和和密密文文C，要要想想恢恢复复原原来来的的报报文文M在在计计算算上上也也是是不不可可行行的。的。（6）加加密密和和解解密密函函数数可可以以以以两两个个次次序序中中的的任任何何一一个个来来使使用用:(这这
6、条条不不是是所所有有公公开开密密钥钥体体系系都都适用，如适用，如DSA只用于数字签名只用于数字签名)M=DKRb（EKUb（M）M=EKUb（DKRb（M）8为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6.1.3 单向陷门函数单向陷门函数满足公钥密码体制，要设计一单向陷门函数满足公钥密码体制，要设计一单向陷门函数单向陷门函数是满足下列条件的函数单向陷门函数是满足下列条件的函数f f：(1)给定给定x，计算，计算y=fpk(x)是容易的是容易的(2)给定给定y,计算计算x使使x=f-1sk（y）是困难的）是困难的(3)知道密
7、钥知道密钥S Sk k的情况下，反向计算是容易的的情况下，反向计算是容易的 x=f-1sk（y）9注注：1 1 仅满足仅满足(1)(1)、(2)(2)两条的称为单向函数；第两条的称为单向函数；第(3)(3)条称为陷门性，条称为陷门性，S Sk k称为陷门信息。称为陷门信息。2 2 当用陷门函数当用陷门函数f f作为加密函数时，可将加密密作为加密函数时，可将加密密钥钥p pk k公开。公开。f f函数的设计者将函数的设计者将S Sk k保密，用作解密密钥。保密，用作解密密钥。由于加密函数是公开的，任何人都可以将信息由于加密函数是公开的，任何人都可以将信息X X加密加密成成y=fpk(x)，然后送
8、给函数的设计者（当然可以通，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有过不安全信道传送）；由于设计者拥有S Sk k，他自然，他自然可以解出可以解出x=f-1sk（y）。3 3 单向陷门函数的第单向陷门函数的第(2)(2)条性质表明窃听者由截条性质表明窃听者由截获的密文获的密文y=fpk(x)推测推测x x是不可行的。是不可行的。10为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益11为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l生
9、活中的例子生活中的例子l将挤出的牙膏弄回管子里比把牙膏挤出来困难将挤出的牙膏弄回管子里比把牙膏挤出来困难得多；得多；l燃烧一张纸要比使它从灰烬中再生容易得多燃烧一张纸要比使它从灰烬中再生容易得多l把盘子打碎成数千片碎片很容易，把所有这些把盘子打碎成数千片碎片很容易，把所有这些碎片再拼成为一个完整的盘子则很难。碎片再拼成为一个完整的盘子则很难。12为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l数学上数学上(有很多函数看起来和感觉像单向函数，能够有很多函数看起来和感觉像单向函数，能够有效地计算它们，但我们至今未找到有效的求有效
10、地计算它们，但我们至今未找到有效的求逆算法。逆算法。)l将许多大素数相乘要比将其乘积因式分解容易将许多大素数相乘要比将其乘积因式分解容易得多。得多。l我们把离散对数函数、我们把离散对数函数、RSA函数作为单向函数函数作为单向函数来使用，但是，目前还没有严格的数学证明表来使用，但是，目前还没有严格的数学证明表明所谓这些单向函数真正难以求逆，即单向函明所谓这些单向函数真正难以求逆，即单向函数是否存在还是未知的数是否存在还是未知的 13为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l单向函数不能用作加密。因为用单向函单向函数不能用
11、作加密。因为用单向函数加密的信息是无人能解开它的。但我数加密的信息是无人能解开它的。但我们可以利用具有陷门信息的单向函数构们可以利用具有陷门信息的单向函数构造公开密钥密码。造公开密钥密码。14为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6.1.4 公开密钥密码系统的公开密钥密码系统的分析方法分析方法l强行攻击强行攻击(对密钥对密钥)。l公开密钥算法本身可能被攻破。公开密钥算法本身可能被攻破。l可能报文攻击可能报文攻击(对报文本身的强行攻击对报文本身的强行攻击)。15为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体
12、制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6.1.5 公钥密码系统的应用公钥密码系统的应用l加密加密/解密解密l数字签名数字签名l会话密钥交换会话密钥交换16为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益17为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益18为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益6-2 Diffie-Hellman密钥交换算法密钥交换算法lDiff
13、ie-Hellman密钥交换算法的有效性依赖于密钥交换算法的有效性依赖于计算有限域中离散对数的困难性。计算有限域中离散对数的困难性。l本原元本原元l离散对数离散对数19为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益本原元（原根）本原元（原根）l对于一个素数对于一个素数q，如果数值：，如果数值：，是各不相，是各不相同的整数，并且以某种排列方式组成了同的整数，并且以某种排列方式组成了从从1到到q-1的所有整数的所有整数l则称整数则称整数a是素数是素数q的一个本原元的一个本原元20为了规范事业单位聘用关系，建立和完善适应社会主义市
14、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 离散对数离散对数l对于一个整数对于一个整数b和素数和素数q的一个本原元的一个本原元a，可以找到一个唯一的指数可以找到一个唯一的指数i，使得：，使得：b=ai mod q (0 i q-1)成立，则指数成立，则指数i称为称为b的以的以a为底数的模为底数的模q的的离散对数离散对数。21为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益22为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l一个素数一个
15、素数q和一个整数和一个整数a（均公开），（均公开），a是是q的一个的一个原根原根l用户用户A选择一个随机数选择一个随机数XAq，计算，计算 l用户用户B选择一个随机数选择一个随机数XBq，计算，计算 l每一方都对每一方都对X的值保密存放而使得的值保密存放而使得Y的值对于另一方可以公的值对于另一方可以公开得到开得到l用户用户A计算密钥：计算密钥：l用户用户B计算密钥：计算密钥：l双方以双方以K作为加、解密密钥，以对称密钥算法进行保密通作为加、解密密钥，以对称密钥算法进行保密通信信Diffie-Hellman密钥交换算法密钥交换算法23为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的
16、事业单位工作人员聘用制度，保障用人单位和职工的合法权益DH例子例子l素数素数q=97,它的一个本原元它的一个本原元a=5lA和和B分别选择随机数分别选择随机数Xa=36和和Xb=58lA计算公开密钥：计算公开密钥：Ya=536 mod 97=50 mod 97 lB计算公开密钥：计算公开密钥：Yb=558 mod 97=44 mod 97 lA计算会话密钥：计算会话密钥：K=4436 mod 97=75 mod 97lB计算会话密钥：计算会话密钥：K=5058 mod 97=75 mod 9724为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单
17、位和职工的合法权益63RSAl由由Rivest,Shamir和和Adleman在在1978年年提出来的提出来的l数学基础数学基础:Euler定理，并建立在大整数定理，并建立在大整数因子分解的困难性之上因子分解的困难性之上25为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l明文空间明文空间P 密文空间密文空间C =Zn(剩余类集合剩余类集合)l密钥的生成密钥的生成l为了产生两个密钥，选取两个大素数，为了产生两个密钥，选取两个大素数，p和和q。为。为了获得最大程度的安全性，两数的长度一样。计了获得最大程度的安全性，两数的长度一样
18、。计算乘积：算乘积：n=pqRSA密码体制描述密码体制描述26为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l然后随机选取加密密钥然后随机选取加密密钥e，使，使e和和(p-1)(q-1)互互素。最后用欧几里德扩展算法计算解密密钥素。最后用欧几里德扩展算法计算解密密钥d，以满足：，以满足：ed1 mod(p-1)(q-1)l则则 d=e-1 mod(p-1)(q-1)l注意：注意：le和和n是公开的，公钥是公开的，公钥KU=e,nlp和和q不再需要，但不可泄露不再需要，但不可泄露 私钥私钥KR=d,n27为了规范事业单位聘用关
19、系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l加密加密(用用e,n)l明文：明文：Mn 密文：密文：C=Me(mod n)l解密解密(用用d,n)l密文：密文：C 明文：明文：M=Cd (mod n)28为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA加密加密/解密解密29为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益算法分析算法分析l密钥生成时，要求密钥生成时，要求n很大，攻击者要将其成功的很大，攻击
20、者要将其成功的分解为分解为p*q是困难的。是困难的。(大因子分解困难性大因子分解困难性)lRSA的加密函数的加密函数 C=Me mod n 是一个单向函数是一个单向函数l接收方，拥有私钥，解密容易接收方，拥有私钥，解密容易证明：证明：M=Cd mod n=(Me mod n)d mod n=M 在在ed=1 mod(n)条件下成立条件下成立M=Cd mod n=(Me mod n)d mod n=Med mod n=M1+k (n)mod n=M (M(n)k mod n=M (M(n)mod n)k mod n (根据欧拉定理注根据欧拉定理注5)=M 1k mod n=M (Mn)ed=1
21、mod (n),k为整为整数数 ed-1=k (n)ed=k (n)+130为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l若若Bob选择了选择了p=7和和q17l则则n=119,(n)=61696253，一个正，一个正整数整数e能用作加密指数，当且仅当能用作加密指数，当且仅当e不能被不能被2，3所整除所整除l假设假设Bob选择选择e=5，那么用辗转相除法将求得：，那么用辗转相除法将求得：d=e-1 77(mod 96)lBob的解密密钥的解密密钥d=77,119，公开，公开5,119 l现假设现假设Alice想发送明文想发
22、送明文19给给BobRSA的例子的例子31为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Alice能否直接发送能否直接发送1234给给Bob?32例例2：p=47,q=61,(n)=(47-1)(61-1)=2760时，时，SK=167是否为是否为秘密密秘密密钥的候选者？钥的候选者？用欧氏算法计算：用欧氏算法计算：gcd(2760,167)=1即可证明。即可证明。33用用RSA算法加密与解密的过程：算法加密与解密的过程：例：明文例：明文=“RSA ALGORITHM”(1)明文用数字表示明文用数字表示 空白空白=00，A=0
23、1,B=02,Z=26(两位十进制两位十进制数表示数表示)1819 0100 0112 0715 1809 2008 1300(2)利用加密变换公式利用加密变换公式 C=mPK mod r,即即C=18191223 mod 2867=2756PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod 2867)=18191024 1819128 181964 18194 18192 18191(mod 2867)=27562756 2001 0542 0669 2347 0408 181534为了规范事业单
24、位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益步骤步骤：Bob为实现者为实现者lBob寻找出两个大素数寻找出两个大素数p和和qlBob计算出计算出n=pq和和 (n)=(p-1)(q-1).lBob选择一个随机数选择一个随机数e(0e (n)，满足，满足（e，(n)）1lBob使用辗转相除法计算使用辗转相除法计算d=e-1(mod (n)l Bob在目录中公开在目录中公开n和和e作为她的公开密钥作为她的公开密钥RSA密码体制描述密码体制描述35为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人
25、单位和职工的合法权益 密码分析者攻击密码分析者攻击RSA体制的关键点在体制的关键点在于如何分解于如何分解n。若分解成功使。若分解成功使n=pq，则可，则可以算出以算出(n)（p-1)(q-1)，然后由公开的，然后由公开的e，解出秘密的，解出秘密的d。36为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益要求要求：若使：若使RSA安全，安全，p与与q必为足够大的必为足够大的素数，使分析者没有办法在有效时间内素数，使分析者没有办法在有效时间内将将n分解出来。建议选择分解出来。建议选择p和和q大约是大约是100位的十进制素数。位的十进
26、制素数。模模n的长度要求至少的长度要求至少是是512比特。比特。37为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 为了抵抗现有的整数分解算法，为了抵抗现有的整数分解算法，对对RSA模模n的素因子的素因子p和和q还有如下要求：还有如下要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1(3)gcd(p1-1,q1-1)应该很小。应该很小。为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小为特定的小整数，如整数，如EDI国际标
27、准中规定国际标准中规定 e2161，ISO/IEC9796中甚至允许取中甚至允许取e3。这时加密速。这时加密速度一般比解密速度快度一般比解密速度快10倍以上。倍以上。38为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益39为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益选择两个大素数选择两个大素数p和和q，通常要求每个均大于，通常要求每个均大于10100。u计算计算npq和和(n)(p1)(q1)。u选择一与选择一与(n)互素的数、令其为互素的数、令其为d。u
28、找到一个找到一个e满足满足ed1(mod(n)。选好这些参数后，将明文划分成块，使得每个明文报文选好这些参数后，将明文划分成块，使得每个明文报文P长度长度m满足满足0mn。加密加密P时，计算时，计算CPe(mod n)，解密解密C时计算时计算PCd(mod n)。由于模运算的对称性，可以证明，由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开为实现加密，需要公开(e,n)，为实现解密需要为实现解密需要(d,n)。RSA算法归纳算法归纳40为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员
29、聘用制度，保障用人单位和职工的合法权益RSA的速度的速度l硬件实现时，硬件实现时，RSA比比DES慢大约慢大约1000倍。倍。l软件实现时，软件实现时，DES 比比RSA快大约快大约100倍。倍。聪明地选择一个聪明地选择一个e值，值，RSA加密速度将快得多加密速度将快得多41为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益如何计算如何计算a ab b mod n mod n？如何判定一个给定的整数是素数？如何判定一个给定的整数是素数？如何找到足够大的素数如何找到足够大的素数p p和和q?q?问题问题42为了规范事业单位聘用关系
30、，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 要点要点1：(a b)mod n=(a mod n)(b mod n)mod n 执行乘法操作之前先用模的方法降阶执行乘法操作之前先用模的方法降阶要点要点2：m的二进制表示为的二进制表示为bkbk-1b0,则则 计算计算am mod nam mod n=a(2i)mod n =a(2i)mod nbi 0bi 0如何计算如何计算ab mod n？43为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益快速取模指数算法计算快速取模指数算法计
31、算ab mod n c 0;d 1for i k downto 0do c 2c d (d d)mod n if bi=1 then c c+1 d (d a)mod nreturn d44为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益快速取模指数算法：例子快速取模指数算法：例子7 560mod 561=1a=7,n=561,m=560=(1000110000)245Miller and Rabin,WITNESS算法算法WITNESS(a,n)判定判定n 是否为素数，是否为素数，a是某是某个个小于小于n的整数的整数1.令令
32、bkbk-1b0 为为(n-1)的二进制表示，的二进制表示，2.d 13.for i k downto 04.do x d5.d (d d)mod n6.if d=1 and x 1 and x n-17.then return TRUE8.if bi=19.then d (d a)mod n10.if d 111.then return TRUE12.return FALSE 返回值：返回值：TRUE:n一定一定不是素数不是素数FALSE:n可能是素数可能是素数应用：应用：随机选择随机选择a n,计算计算s次，次，如果每次都返回如果每次都返回FALSE，则这时则这时n是素数的概率为是素数的概
33、率为(1-1/2s)如何判定一个给定的整数是素数？如何判定一个给定的整数是素数？46为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益1.随机选一个奇数随机选一个奇数n(伪随机数发生器伪随机数发生器)2.随机选择一个整数随机选择一个整数a n3.执行概率素数判定测试执行概率素数判定测试,如果如果n 未测试通过未测试通过,则则 拒绝数值拒绝数值n,转向步骤转向步骤14.如果如果n已通过足够的测试已通过足够的测试,则接受则接受n,否则转向步骤否则转向步骤2;说明：说明：随机选取大约用随机选取大约用 ln(N)/2的次数，如的次数，如
34、ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。好在生成密钥对时才用到，慢一点还可忍受。确定素数确定素数p和和q以后，只需选取以后，只需选取e,满足满足gcd(e,(n)=1,计算计算d=e-1 mod (n)（扩展的欧拉算法）（扩展的欧拉算法）如何找到足够大的素数如何找到足够大的素数p和和q?47为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益p和和q在长度上应仅差几个数位，即在长度上应仅差几个数位，即p和和q应是应是1075 到到10100（p-1）和（和（q-1）都应包含一个较大的素数因子都应包含一个
35、较大的素数因子gcd(p-1,q-1)应比较小应比较小如果如果en 且且 dn1/4,则则d可以很容易确定可以很容易确定建议建议 48为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益DES和和RSA性能比较（同等强度）性能比较（同等强度）49为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA的数字签名应用将在第八章介绍的数字签名应用将在第八章介绍！50为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工
36、的合法权益64椭圆曲线密码体制ECCl椭圆曲线密码体制以高效性著称椭圆曲线密码体制以高效性著称l由由Neal Koblitz和和Victor Miller在在1985年年分别提出分别提出lECC的安全性基于椭圆曲线离散对数问的安全性基于椭圆曲线离散对数问题的难解性题的难解性l密钥长度大大地减小密钥长度大大地减小l是目前已知公钥密码体制中每位提供加是目前已知公钥密码体制中每位提供加密强度最高的一种体制密强度最高的一种体制55为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线的概念和分类 定义：定义：椭圆曲线是一个具有两个变
37、元椭圆曲线是一个具有两个变元x和和y的三的三次方程，它是满足：次方程，它是满足：Y2+aXY+bY=X3+cX2+dX+e 的所有点的所有点(X,Y)的集合，外加一个零点或无穷远的集合，外加一个零点或无穷远点点O57为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益1、实数域上的椭圆曲线l实数域上的椭圆曲线是对于固定的实数域上的椭圆曲线是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2=X3+aX+b 的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b是实数，是实数，X和和Y在实
38、数域上取值在实数域上取值58为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2、有限域GF(p)上的椭圆曲线 lGF(p)域上的椭圆曲线是对于固定的域上的椭圆曲线是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2=X3+aX+b mod(p)的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b，X和和Y在在GF(p)域上取值域上取值59为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Hasse定理定理 l如果如果
39、E是定义在是定义在GF(p)域上的椭圆曲线，域上的椭圆曲线，N是是E上的点的个数，则：上的点的个数，则：60为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例子例子61为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3、有限域GF(2m)上的椭圆曲线 l是对于固定的是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2+XY=X3+aX2+b 的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b，X和和Y在在GF(2
40、m)域上取值域上取值lGF(2m)域上的元素是域上的元素是m位的串位的串 62为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例子例子l由多项式由多项式 定义的域定义的域GF（24）l基元为基元为g=(0010)，g的各幂分别是的各幂分别是 63为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例子（续）例子（续）l考虑椭圆曲线：考虑椭圆曲线：l点点(g5,g3)满足该方程满足该方程 l(g3)2+g5 g3=(g5)3+g4(g5)2+1 g6+g8=g15+
41、g14+1(1100)+(0101)=(0001)+(1001)+(0001)(1001)=(1001)64为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益满足该方程的点集满足该方程的点集65为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线的加法规则椭圆曲线的加法规则lAbel群群：l加法规则加法规则1：l加法规则加法规则2：l加法规则加法规则3：互逆点：互逆点l加法规则加法规则4：加法交换律：加法交换律l加法规则加法规则5：加法结合律：加法结合律 l
42、加法规则加法规则6：l加法规则加法规则7：66为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线的加法规则（续）椭圆曲线的加法规则（续）lGF（2m)域域l加法规则加法规则3：如果如果 ，则，则l加法规则加法规则6：l加法规则加法规则7：67为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益加法规则的几何描述加法规则的几何描述68为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益两个定义两个
43、定义l标量乘标量乘l阶阶lP是椭圆曲线是椭圆曲线E上的一点，若存在最小的上的一点，若存在最小的正整数正整数n，使得，使得nP=O，则称，则称n是点是点P的阶的阶 69为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例子例子lGF（23）上椭圆曲线）上椭圆曲线：l设：设：l求求P1P2和和2P170为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线密码体制 l椭圆曲线离散对数问题椭圆曲线离散对数问题l已知椭圆曲线已知椭圆曲线E和点和点P，随机生成一个整，随
44、机生成一个整数数d，容易计算，容易计算:Q=d*P，但给定，但给定Q和和P,计计算算d就相对困难就相对困难 71为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益1、系统的建立 l选取选取:l一个基域一个基域GF(p)l定义在该基域上的椭圆曲线定义在该基域上的椭圆曲线Ep(a,b)lE上的一个拥有素数阶上的一个拥有素数阶n的点的点Pl其中有限域其中有限域GF(p)，椭圆曲线参数，椭圆曲线参数a,b，点点P和阶和阶n都是公开信息都是公开信息72为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，
45、保障用人单位和职工的合法权益2、密钥的生成l在区间在区间1,n-1中随机选取一个整数中随机选取一个整数dl计算计算:Q=dPl实体的实体的l公开密钥公开密钥:点点Ql实体的私钥实体的私钥:整数整数d 73为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3、加密过程 l待发送消息：待发送消息：AB：M查找查找B的公开密钥：的公开密钥：Q将消息将消息M表示成一个域元素表示成一个域元素:m在区间在区间1,n-1中随机选取一个整数中随机选取一个整数k计算点计算点:(x1,y1)=kG计算点计算点:(x2,y2)=kQ，如果如果x2=0
46、，则返回第则返回第步步计算计算:c=mx2传送加密数据传送加密数据(x1,y1,c)给给B 74为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益4、解密过程 l当实体当实体B解密从解密从A收到的密文收到的密文(x1,y1,c)时，时，执行步骤：执行步骤：l使用私钥使用私钥d，计算点，计算点:(x2,y2)=d(x1,y1)l因为因为:(x2,y2)=kQ=kdG=d(x1,y1)l计算计算 ，恢复出消息，恢复出消息m 75为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线密码体制的主要优点椭圆曲线密码体制的主要优点 l安全性高 l密钥长度小l算法灵活性好76为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益椭圆曲线密码体制与离散对数密码体椭圆曲线密码体制与离散对数密码体制的比较制的比较77为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益l l 78