第4讲 公钥密码体制

1、第4讲公钥密码体制,主讲：谢昕,2,课程主要内容,公钥密码体制概述,背包公钥密码,RSA公钥密码,椭圆曲线密码,概率加密等,1公钥密码体制概述,对称密钥密码体制问题：如何在网络上安全地传送和保管密钥？无法实现抗抵赖的需求等1976年，美国学者Diffie和Hellman发表了著名论文密码学的新方向，提出了建立“公开密钥密码体制”：若用户A有加密密钥PK(公开)，不同于解秘密钥SK(保密)，要求PK的公开不影响SK的安全。若B要向A保密送去明文m，可查A的公开密钥PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密钥SKA对x进行解密得到明文m。,公开密钥密码体制是现代密码

2、学最重要的发明,离散数学,尽人皆知的密钥叫做公开密钥(publickey)；只有密钥拥有者才知道的密钥：私有密钥(privatekey)这两种密钥合在一起称为密钥对；公开密钥可以解决安全分配密钥问题（不需要与保密密钥通信，所传输的只有公开密钥，它不需要保密），但对保证其真实性和完整性却非常重要。如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现保密的方法。如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法。,1公钥密码体制概述,离散数学,算法特点：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已选定的E和D，即使已知E的完整描述，也不可能推导出D。,1

3、公钥密码体制概述,离散数学,1公钥密码体制概述,数字签名必须保证做到以下3点：（1）接收者能够核实发送者对报文的签名；（2）发送者事后不能抵赖对报文的签名；（3）接收者不能伪造对报文的签名。,离散数学,RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）。公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。RSA得到了世界上的最广泛的应用，ISO

4、在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。,2RSA公钥密码体制,离散数学,整数n的因子分解的所需计算十进制位数运算次数时间501.4x10103.9小时759.0 x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0 x1015年5001.3x10394.2x1025年,（每微秒一次）,2RSA公钥密码体制,离散数学,RSA密钥体制的特点：（1）密钥配发十分方便，用户的公开密钥可以像电话本那样公开，使用方便，每个用户只需持有一对密钥即可实现与网络中任何一个用户的保密通信。（2）RSA加密原理基于单向函数，

5、非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥。RSA在用户确认和实现数字签名方面优于现有的其他加密机制。,2RSA公钥密码体制,离散数学,单向函数：给定一个函数f，若对任意给定的x，计算y，使得y=f(x)是容易的；但对任意给定的y，计算x，使得f(x)=y是难解的，即计算f-1(y)是困难的。则称f为单向函数。例：f(x)=ax（x、aGF(q)）为单向函数。,2RSA公钥密码体制,陷门单向函数：给定一个函数f，t为f相关的参数，任意给定的x，计算y=f(x)是容易的；当t未知时，计算逆函数f-1(y)难解，而当t已知时，计算f-1(y)容易。则称为f陷门单向函数。,离散数学,用于

6、构造双钥密码的单向函数：（1）多项式求根（2）离散对数（3）大整数分解（4）背包问题（5）Diffie-Hellman问题（6）二次剩余问题（7）模n的平方根问题,2RSA公钥密码体制,离散数学,2.1RSA公钥密码算法描述,（1）设计密钥A、在离线方式下，先产生两个足够大的强质数p、q；B、令n=pq。计算欧拉函数(n)=(p-1)(q-1)；C、选取一个与(n)互素的奇数e，称e为公开指数；D、根据ed=1mod(n)，找出d；E、舍弃p和q（但绝不能泄露），公开(n，e)，公钥；F、保密(n，d)私钥。,离散数学,（2）加密对于明文M，用公钥(n，e)加密可得到密文C。C=Memod(n

7、),2.1RSA公钥密码算法描述,（3）解密对于密文C，用私钥(n，d)解密可得到明文M。M=Cdmod(n),当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。,离散数学,举例1：选取p=3,q=5，则n=pq=15，(n)=(p-1)(q-1)=8选取e=11（大于p和q的质数）；由d11=1mod8，计算出d=3，得到公开密钥：（n，e）=（15，11）私有密钥：（n，d）=（15，3）假定明文M为整数13。则密文C=Memodn=1311mod15=(132)5*13mod15=(132mod15)5*13mod15=45*13mod15=7复原明文M为：

8、M=Cdmodn=73mod15=343mod15=13,2.1RSA公钥密码算法描述,离散数学,举例2：设p=43,q=59,n=pq=43*59=2537,(n)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d解方程de=1mod24362436=13187+5,13=25+3，5=3+2，3=2+1所以1=3-2，2=5-3，3=13-25，5=2436-13187所以，1=3-2=3-(5-3)=23-5=2(13-25)-5=213-55=213-5(2436-13187)=93713-52346即937131mod2436取e=13时，d=937,2.1RSA

9、公钥密码算法描述,13d=k*2436+1d=(k*2436+1)/13,试凑,离散数学,1、加密字串举例：若有明文publickeyencryptions2、先将明文分块为两个一组(此处为简化计算考虑)：publickeyencryptions3、将明文数字化令a,b,z分别为00,01,25得15200111080210042404130217241519081413184、利用加密可得密文00951648141012991365137923332132175113245、解密后又得到明文,2.1RSA公钥密码算法描述,离散数学,C=Memodn=152013mod2537=(15202)

10、6*1520mod2537152021730mod2537C=(1730)6*1520mod2537=(17302)3*1520mod2537173021777mod2537C=(1777)3*1520mod2537=(1777)2*1777*1520mod2537177721701mod2537C=1701*(1777*1520)mod2537=1701*1672mod2537=95（密文）,2.1RSA公钥密码算法描述,（2）加密,离散数学,M=Cdmodn=95937mod2537=(952)468*95mod2537=(1414)468*95mod2537=(14142)234*95m

11、od2537=(240)234*95mod2537=(625*25)*(341*788)*95mod2537=230*2323mod2537=1520mod2537=1520（明文）,2.1RSA公钥密码算法描述,（3）解密,离散数学,2.2RSA算法的优缺点,优点：是第一个能同时用于加密和数字签名的算法，也易于理解和操作，也是被研究得最广泛的公钥算法，二十年来经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。特别符合计算机网络环境。对于网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密

12、通信，只需从公钥簿上查出对方的加密密钥，用它对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息解密，了解报文的内容。,离散数学,缺点：（1）产生密钥很麻烦，难以做到一次一密。（2）RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。目前人们已能分解140多位十进制位的大素数，这就要求使用更长的密钥，速度更慢。而且目前人们正在积极寻找攻击RSA的方法。（3）速度太慢,RSA的分组长度太大。为了速度问题，目前人们广泛使用单、公钥密码结合使用的方法，优缺点互补：单钥密码加密速度快，用它来加密较长的文件，然后用RSA来给文件密钥加密，极好

13、的解决了单钥密码的密钥分发问题。,2.2RSA算法的优缺点,离散数学,2.3RSA密码体制的实现,实现的步骤如下：(Bob为实现者)(1)Bob寻找出两个大素数p和q；(2)Bob计算出n=p*q和(n)=(p-1)(q-1)；(3)Bob选择一个随机数e(0e(n)满足gcd(e,(n)=1；(4)Bob使用辗转相除法计算d=e-1(mod(n)；(5)Bob在目录中公开n和e作为他的公钥。,密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=p*q，则可以算出(n)=(p-1)(q-1)。然后由公开的e解出秘密的d。,离散数学,RSA密码系统设计要求：（1）p、q必须选择强素数

14、（2）p、q之差必须很大（3）p1、q1的最大公约数应尽量小（4）p、q选择应足够大（5）e不可以太小（6）e应选择使模(n)的阶最大,2.3RSA密码体制的实现,离散数学,美国斯坦福大学的Merkle和Hellman于1978年提出的。背包问题描述：已知一长度为b的背包及长度分别为a1,a2,an的n个物品。假定这些物品的直径与背包相同，若从这些物品中选出若干个正好装满这个背包，究竟是哪些物品。数学描述：已知b，求解a1x1+a2x2+anxn=b，其中a1,a2,an和b都是正整数。背包问题目前尚无有效求解算法。背包公钥密码：选取正整数a1,a2,an作为公钥，明文位串为m=m1m2mn，

15、利用公钥加密问题c=a1m1+a2m2+anmn。从密文c求明文m等价于背包问题。,3背包公钥密码体制,离散数学,MH公钥背包密码：其背包系列a1,a2,an是由超递增系列b1,b2,bn（）经过MH变换ak=wbk得到的。虽然a1,a2,an不具有超递增性，但可经变换后成为超递增系列求解。若超递增背包问题确实有解，则容易用所谓的贪心算法求出其解。例：超递增序列1，2，4，2n，若背包方程x1+2x2+4x3+8x4+16x5+32x6=47则x6=1，x5=0，x4=1，x3=1，x2=1，x1=1所以密文为：111101,3背包公钥密码体制,离散数学,MH公钥背包密码过程：（1）密钥生成用

16、户构造长度为n的超递增背包分量b1,b2,bn，选择两个正整数M、W，其中，WM且保证gcd(W,M)=1。则由WW-11modM，求出W-1（0W-1M)，计算ai=WbimodM，0in选择背包系统的公钥为Pk=(a1,a2,an)，私钥为Sk=(b1,b2,bn,M,W-1),3背包公钥密码体制,离散数学,（2）加密过程用户A给用户B发送秘密消息时，使用B的公钥PK，对明文m=（m1,m2,mn）进行加密变换：（3）解密过程用户收到密文C后，使用自己的私钥SK，计算,3背包公钥密码体制,离散数学,例：明文m=(m1,m2,m3,m4)=(11011,11010,11100,10110)，

17、选n=5，取a=(3,6,10,22,44)背包序列进行加解密。加密：c1=316110022144175c2=316110022144031c3=316110122044019c4=316010122144035得到密文c=(c1,c2,c3,c4)=(75,31,19,35)解密：取c1=75，求3x16x210 x322x444x575则x5=1，x4=1，x3=0，x2=1，x1=1对应明文m1=11011，其余明文类似可得。,3背包公钥密码体制,离散数学,设超递增背包序列为1,2,5,9,20,41,83,164，用MH背包算法进行加解密。,3背包公钥密码体制,1）因为1+2+5+9

18、+20+41+83+164=325，所以取M353，W233，用辗转相除法计算得W-150；2）a1=w.b1(mod353)=233*1(mod353)=233(mod353)a2=w.b2(mod353)=233*2(mod353)=113(mod353)a3=w.b3(mod353)=233*5(mod353)=106(mod353)a4=w.b4(mod353)=233*9(mod353)=332(mod353)a5=w.b5(mod353)=233*20(mod353)=71(mod353)a6=w.b6(mod353)=233*41(mod353)=22(mod353)a7=w.b

19、7(mod353)=233*83(mod353)=277(mod353)a8=w.b8(mod353)=233*164(mod353)=88(mod353),28,3背包公钥密码体制,3）得到背包序列233,113,106,332,71,22,277,88，作为公钥公布，而1,2,5,9,20,41,83,164作为么钥保存；4）假设要发送的明文是二进制信息：01011001110010101000100101011001对应的密文是a2a4a5a8113332718860411001010对应的密文是a1a1a5a72331137127769410001001对应的密文是a1a5a82337

20、188392故对应的密文：604,694,3925）接收方收到密文后其解密过程为用50密文模353：50604(mod353)=195(mod353)=164+20+9+2(mod353)其对应的明文是01011001，其余类推,29,ElGamal算法在密码协议中中有许多实际的应用，其安全性是基于求解离散对数问题的困难性。1984年提出的ElGamal密码体制也是一种双钥密码体制，既可以用于加密又可用于数字签名。,4ElGamal密码体制,定义1（本原元）：对于一个素数q，如果数值amodq,a2modq,.aq-1,modq是各不相同的数，并且以某种方式排列组成了从1到q-1的所有整数，则

21、整数a称素数q的一个本原元（生成元、基元、原根）。,离散数学,4ElGamal密码体制,定义2（离散对数）：对于一个整数b和素数q的本原元a，可以找到一个唯一的指数i，使得b=aimodq（0iq-1）成立，则指数i称为以a为底的模q的离散对数。对于给定的a、i、q，容易计算出b。但给定b、a、q，计算出i是非常困难的，这就是离散对数的难解性。,它是包括Diffie-Hellman密钥交换算法和DSA数字签名算法等在内的许多公钥密码算法的基础。,离散数学,Diffie-Hellman算法：让A和B两个陌生人之间建立共享秘密密钥的公开密钥算法。它的目的是使得两个用户安全地交换一个密钥以便用于以后

22、的报文加密，这个算法本身限于密钥交换的用途。许多商用产品都使用这种密钥交换技术。在Diffie-Hellman密钥交换算法中的单向函数是模指数运算。它的逆过程是离散对数问题，其Diffie-Hellman算法的保密性基于求modp解离散对数问题的困难。,Diffie-Hellman密钥交换方案,32,2.基本原理,用户A,用户B,公开,公开,秘密,秘密,会话秘密,会话秘密,密钥交换过程,Diffie-Hellman密钥交换方案,共享：素数P及本原元a,产生随机数XA,产生随机数XB,33,设P=47和47的一个原元，a=3。A选择秘密密钥XA=8，B选择秘密密钥XB=10，各自计算其公开密钥。

23、（1）双方各自计算A计算：YA=38mod47=6561mod47=28mod47B计算：YB=310mod47=59049mod47=17mod47（2）交换YA和YB；（3）交换密钥后，分别计算共享的秘密会话密钥KA、KB：A计算：KA=YBXAmod47=178mod47=4mod47B计算：KB=YAXBmod47=2810mod47=4mod47A和B双方独立地决定采用4作为会话密钥。,Diffie-Hellman密钥交换方案,3.交换示例,34,4ElGamal密码体制,ElGamal公钥体制的描述：,1）选取一个足够大的素数p，使求解离散对数问题在Zp上是困难的；2）在Zp*上选

24、择一个本原元g；3）随机选取整数k（0kp-2），并计算y=gk(modp);,密钥生成的准备：,离散数学,解密：Bob计算Dk(y1,y2)=y2(y1k)-1(modp)=m(gk)r(grk)-1=m,4ElGamal密码体制,加密：Alice取一个秘密随机数rZp-1，对明文m加密Ek(m,r)=(y1,y2)其中，y1=gr(modp)y2=m*yr(modp),公钥为：p,g,y私钥为：k,离散数学,4ElGamal密码体制,举例：设p=2579,如果选取g=2,k=765,则1）y=gk(modp)=2765(mod2579)=949；2）设A要发送的消息m=1299,则A选择随

25、机数r=853并计算y1=g853(mod2579)=435；及y2=1299*949853(mod2579)=2396。3）A发送密文y=(435,2399)给B；4）B收到后计算m=2399*(435765)-1(mod2579)=1299.,离散数学,EllipticCurveCryptosystem以高效性著称，由NealKoblitz和VictorMiller在1985年分别提出。ECC的安全性基于椭圆曲线离散对数问题的难解性，密钥长度大大地减小。ECC是目前已知公钥密码体制中每位提供加密强度最高的一种体制.,5椭圆曲线密码体制（ECC）,离散数学,椭圆曲线上的公钥密码体制的优点：速

26、度快、安全性高、密钥短、灵活性好。,5椭圆曲线密码体制（ECC）,离散数学,1、椭圆曲线的概念和分类,定义：椭圆曲线是一个具有两个变元x和y的三次方程，它是满足：Y2+aXY+bY=X3+cX2+dX+e的所有点(X,Y)的集合，外加一个零点或无穷远点O。注：它并非椭圆，只是其方程类似于计算椭圆周长的方程而得名的。,5椭圆曲线密码体制（ECC）,40,(1)无穷远元素（无穷远点，无穷远直线）平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，使两种不同关系统一。ABL1，L2L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。当Q=BAP/2时，APL2,5椭圆曲线密

27、码体制（ECC）,离散数学,可设想L1上有一点P，它为L2和L1的交点，称之为无穷远点。直线L1上的无穷远点只能有一个。(过A点只有一条平行于L1的直线L2，两直线的交点只有一个)结论：1)平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做平常点）2)平面上任何相交的两直线L1,L2有不同的无穷远点。(原因：否则L1和L2有公共的无穷远点P，则过两相异点A和P有相异两直线，与公理相矛盾)3)全体无穷远点构成一条无穷远直线。注：欧氏平面添加无穷远点和无穷远直线，构成射影平面。,5椭圆曲线密码体制（ECC）,离散数学,(2)齐次坐标解析几何中引入坐标系，用代数的

28、方法研究欧氏空间。这样的坐标法也可推广至射影平面上，建立平面射影坐标系。平面上两相异直线L1，L2，其方程分别为：L1：a1x+b1y+c1=0L2：a2x+b2y+c2=0其中a1、b1不同时为0，a2、b2也不同时为0。设若D0，则两直线L1，L2相交于一平常点P(x,y)，其坐标为x=Dx/D，y=Dy/D。,5椭圆曲线密码体制（ECC）,离散数学,这组解可表示为：x/Dx=y/Dy=1/D(约定：分母Dx，Dy有为0时，对应的分子也要为0)上述表示可抽象为(Dx，Dy，D)。若D=0，则L1L2，此时L1和L2交于一个无穷远点P。这个点P可用过原点O且平行于L2的一条直线L来指出它的方

29、向，这条直线L的方程就是：a2x+b2y=0。为把平常点和无穷远点的坐标统一起来，把点的坐标用(X，Y，Z)表示，X，Y，Z不能同时为0，且对平常点(x，y)来说，有Z0，x=X/Z，y=Y/Z，于是有：,5椭圆曲线密码体制（ECC）,离散数学,也即：X/Dx=Y/Dy=Z/D，这样对于无穷远点则有Z=0。注：1、若实数p0，则(pX,pY,pZ)与(X,Y,Z)表示同一个点。实质上用（X:Y:Z)表示。3个分量中，只有两个是独立的，具有这种特征的坐标就叫齐次坐标。2、设有欧氏直线L，它在平面直角坐标系上的方程为：ax+by+c=0则L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，Z0，代

30、入得：aX+bY+cZ=0给L添加的无穷远点的坐标(X,Y,Z)应满足aX+bY=0，Z=0；平面上无穷远直线方程即为：Z=0,5椭圆曲线密码体制（ECC）,离散数学,K为域，K上的射影平面P2(K)是一些等价类的集合(X:Y:Z)。如Weierstrass方程(三次齐次方程)：Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3(其中系数aiK，或aiK为K的代数闭域）Weierstrass方程被称为光滑的或非奇异的，是指对所有适合以下方程的射影点P=(X:Y:Z)P2(K)来说，F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在

31、P点的三个偏导数之中至少有一个不为0，否则称这个方程为奇异的。,5椭圆曲线密码体制（ECC）,离散数学,5椭圆曲线密码体制（ECC）,实数域上的椭圆曲线是对于固定的a、b值，满足方程：Y2=X3+aX+b的所有点的集合，外加一个零点或无穷远点，其中a、b是实数，X和Y在实数域上取值。,3、实数域R上的椭圆曲线,离散数学,椭圆曲线可表示为平面上的通常曲线上的点，另加一个无穷远点O。设LP2(R)为一条直线。因为E的方程是三次的，所以L可与E在P2(R)上恰有三个交点，记为P、Q、R(如果L与E相切，那么P、Q、R可以不相异)。按下述定义E上加法运算：设P、QE，L为联接P、Q的直线(若P=Q，则

32、L取过P点的切线)，设R为L与E的另一个交点，取连接R与无穷远点的直线L。则L与E的另一个交点定义为PQ。,5椭圆曲线密码体制（ECC）,离散数学,5椭圆曲线密码体制（ECC）,椭圆曲线y2=x3-x的一般化图像,离散数学,注：1、如果直线L与E相交于三点P、Q、R(不一定相异），那么(PQ)R=O(从图中可见）。2、任给PE，P=P(此时设Q=O，易见L=L)3、任给P,QE有：PQ=QP4、设PE，那么可以找到-PE使P-P=O5、任给P、Q、RE，有(PQ)R=P(QR)综上所述，知E对运算形成一个Abel群。6、上述规则可开拓到任意域上，特别是有限域上。,5椭圆曲线密码体制（ECC）,

33、离散数学,4、有限域上的椭圆曲线,5椭圆曲线密码体制（ECC）,GF(p)域上的椭圆曲线是对于固定的a、b值，满足形如方程：Y2=X3+aX+bmod(p)的所有点的集合，外加一个零点或无穷远点其中a、b，X和Y在GF(p)域上取值。,离散数学,例如：令Fp表示p个元素的有限域，p3为素数，a,bFp，满足4a3+27b20，由参数a和b定义Fp上的一个椭圆曲线：y2=x3+ax+b它的所有解(x,y)，(xFp，yFp)，连同一个称为“无穷远点”(记为或O)的元素组成的集合为定义在Fp上的一个椭圆曲线，记为E(Fp)。,5椭圆曲线密码体制（ECC）,离散数学,Hasse定理：如果E是定义在G

34、F(p)域上的椭圆曲线，N是E上的点的个数，则：,5椭圆曲线密码体制（ECC）,该椭圆曲线只有有限个点数N(称为椭圆曲线的阶，它包括无穷远点)，N越大，安全性越高。粗略估计，N近似p。,53,在GF(23)上的解为：（0，0）（1，5）（1，18）（9，5）（9，18）（11，10）（11，13）（13，15）（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）无穷远点O,5椭圆曲线密码体制（ECC）,例：在GF(23)上的一个椭圆曲线(即a=1，

35、b=0)y2x3+x(mod23),93+9(mod23)=738(mod23)=2(mod23)=y2(mod23)y2=23*n+2当n=1时，y=5；或当n=14时，y=18。,54,5椭圆曲线密码体制（ECC）,共有24个点，除(0，0)外，对应每一个x均有2个点，且它们是关于y=11.5对称的。注意：11.5=23/2,55,5、有限域GF(2m)上的椭圆曲线,对于固定的a、b值，满足方程：Y2+XY=X3+aX2+b的所有点的集合，外加一个零点或无穷远点O其中a、b，X和Y在GF(2m)域上取值。该类椭圆曲线通常用E2m(a,b)表示。显然GF(2m)域上的元素是m位的串。,5椭圆

36、曲线密码体制（ECC）,56,由多项式定义的域GF(24)基元为g=(0010)，g的各幂分别是：,5椭圆曲线密码体制（ECC）,57,考虑椭圆曲线：点(g5,g3)满足该方程(g3)2+g5g3=(g5)3+g4(g5)2+1g6+g8=g15+g14+1(1100)+(0101)=(0001)+(1001)+(0001)(1001)=(1001),5椭圆曲线密码体制（ECC）,58,满足该方程的点集:,5椭圆曲线密码体制（ECC）,(1,g13)(g3,g13)(g5,g11)(g6,g14)(g9,g13)(g10,g8)(g12,g12)(1,g6)(g3,g8)(g5,g3)(g6,

37、g8)(g9,g10)(g10,g1)(g12,0)(0,1),59,5椭圆曲线密码体制（ECC）,Abel群：加法规则1：加法规则2：加法规则3：互逆点加法规则4：加法交换律加法规则5：加法结合律,椭圆曲线的加法规则,60,5椭圆曲线密码体制（ECC）,加法规则6：加法规则7：,61,加法规则6：,5椭圆曲线密码体制（ECC）,对于GF（2m)域，加法规则3：,62,加法规则7：,5椭圆曲线密码体制（ECC）,63,定理：椭圆曲线E上的点及其无穷远点O形成一个Abel群。设P、Q是E上的任意两点，则其加法规则为：(1)OO=O，-O=O；（O是单位元）(2)若-P是P的逆元，则P-P=O；,

38、5椭圆曲线密码体制（ECC）,椭圆曲线的加法规则几何描述：,(3)对任意P(x,y)，有PO=P且OP=P，即O为恒元；,离散数学,5椭圆曲线密码体制（ECC）,(4)如果PO,QO,Q-P,R是P、Q连线与E的交点，或E在点P的切线交E所得的另一点R，则有：PQR；,离散数学,5椭圆曲线密码体制（ECC）,若P(xP,yP)、Q(xQ,yQ)是椭圆曲线E：y2=x3+ax+b上的任意两点，且PO,QO,Q-P,R(xR,yR)是P、Q连线与E的交点,如果沿x轴作关于R的对称点，将得到另一个对称点，该点称为：PQR；R(xR,-yR),一、点加公式,设：过P、Q的直线L为y=kx+b;则k=(

39、yQ-yP)/(xQ-xP),代入曲线方程。经比较得到：xR=k2-xP-xQ；-yR=-yP-k(xP-xR)；,离散数学,5椭圆曲线密码体制（ECC）,当PQ时，PQPP2P，称点2P为P的倍点。过P作E的切线，则必定与E相交于另一点R，作R关于x轴的对称点，得到另一点，也就是P的倍点2P。若过P的E地切线垂直于x轴，那么切线交E于无穷远点，则有PPO；（称P是一个阶为2的点）,二、倍点公式,对方程求导，得k=(3xP2+a)/2y,代入曲线方程得：xR=k2-2xP；-yR=-(kx+b)；,离散数学,5椭圆曲线密码体制（ECC）,倍点是将椭圆曲线上的点自身相加得到的点。若将E上的一个点

40、自身相加若干次，称之为点乘操作（标量乘）。,三、点乘操作,若P是椭圆曲线E上的一点，若存在最小的正整数n，使得nP=O，则称n是点P的阶。,离散数学,5椭圆曲线密码体制（ECC）,69,例题：GF（23）上椭圆曲线：设：P1=(3,10),P2=(9,7),求P1+P2、2P1和-P1。,5椭圆曲线密码体制（ECC）,计算P1P2：,70,5椭圆曲线密码体制（ECC）,计算2P1：,计算-P1：,71,5椭圆曲线密码体制（ECC）,补充：分数求模运算,方法1：测试法，用于模数较小时。先将分子分母分别取模，得到最简约分子式，如，然后求得使,方法2：标准法，适用所有情形。,72,5椭圆曲线密码体制

41、（ECC）,例1：313/10mod23,方法1：313+k*23=10*l，由于右边一定是10的倍数，左边也必须为10的倍数。所以试算当k=9时，左边为520，l=52。故：313/10mod23=52mod23=6mod23。,方法2：313/10mod23=313*10-1mod23=？10*10-11mod23（用辗转相除法得）23=10*2+310=3*3+11=10-3*3=10-3(23-10*2)=7*10-3*2310*7mod23=3*23+1mod23,即10*71mod23313*7mod23=2191mod23=6,73,5椭圆曲线密码体制（ECC）,解：在GF(24

42、)域共有16个元素值，其15个非0值如前例。其中a=g4=(0011)=3,b=1=(0001)=g0,计算P1P2：,74,5椭圆曲线密码体制（ECC）,75,ECC依据是定义在椭圆曲线点群上的离散对数问题的难解性。因为对已知E(Fq)对点的“”运算形成一个Abel群设pE(Fq)，若p的周期很大，即使ppp=O(共有t个p相加）成立的最小正整数t，希望t很大。(t=p的周期，表示为(p)=t)。并且对QE(Fq)，定有某个正整数m使Q=mp=pp(共有m个p相加),5椭圆曲线密码体制（ECC）,离散数学,定义m=logPQ(m为以p为底Q的对数）。椭圆曲线上的点形成的群E(Fq)，相关它的

43、离散对数问题是难处理的。建立椭圆曲线密码体制时，选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。在E(Fq)中选一个周期很大的点，如选了一个点P=(xp,yp)，它的周期为一个大的素数n，记(P)=n(素数)。注意：在这个密码体制中，具体的曲线及点P和它的n都是公开信息。,5椭圆曲线密码体制（ECC）,离散数学,例：对于F23的椭圆群y2=x3+9x+17，求R(4,5)对于Q(16,5)的离散对数，最直接的方法就是计算Q的倍数，直到找到满足条件的m值。,5椭圆曲线密码体制（ECC）,Q=(16,5),2Q=(20,20),3Q=(14,14),4Q=(19,20),5Q=(13,10),6

44、Q=(7,3),7Q=(8,7),8Q=(12,17),9Q=(4,5),因此R关于Q的离散对数是9。但对于大素数构成的群Fp，计算离散对数是不现实的。,离散数学,5椭圆曲线密码体制（ECC）,因此R关于Q的离散对数是9。但对于大素数构成的群Fp，计算离散对数是不现实的。已知椭圆曲线E和点P，随机生成一个整数d，容易计算:Q=d*P，但给定Q和P，计算d就十分困难！此为椭圆曲线离散对数问题的难解性。,离散数学,Bob(使用者）执行下列计算：在区间1,n-1中随机选取一个整数d；计算点Q=dP(d个P相加）；Bob公开自己的公开密钥：(E(Fq),p,n,Q)；Bob的私钥为整数d。,5椭圆曲线

45、密码体制（ECC）,一、密钥的生成,离散数学,Alice要发送消息m给Bob，Alice执行：查找Bob的公钥(E(Fq),p,n,Q)；将m表示成一个域元素（mFq）；在区间1，n-1内选取一个随机数k；依据Bob的公钥计算点(x1,y1)=kP；计算点(x2,y2)=kQ，如果x2=0,则回到第3步；计算C=mx2；传送加密数据(x1,y1,C)给Bob。,5椭圆曲线密码体制（ECC）,二、加密过程,离散数学,Bob收到Alice的密文(x1,y1,C)后，执行使用私钥d，计算点(x2,y2)=d(x1,y1)，再计算Fq中x2-1=?通过计算m:=Cx2-1，恢复出明文数据m。,5椭圆曲

46、线密码体制（ECC）,三、解密过程,离散数学,5椭圆曲线密码体制（ECC）,四、举例,ECELG椭圆曲线ElGamal密码体制,任务：BA：m用户A选取随机数（私钥）dA，产生公开密钥:PA=dA*G用户B选取随机数（私钥）dB，并计算公钥：PB=dB*GB计算并向A发送：(PB，m+dB*PA)用户A解密：(m+dB*PA)dA*PBm,离散数学,5椭圆曲线密码体制（ECC）,椭圆曲线设用户A的私钥为7，则公钥为7G：（是多少？）先计算2G，即2个G点，得：（16，5）；再计算4G，即2个2G点，得：（17，2）；再计算3G，即一个G点和一个2G点，得：（20，18）；最后计算7G，即3G与

47、4G两点，得：（17，21）；,离散数学,5椭圆曲线密码体制（ECC）,1)设用户B的消息m编码后为，且选取了随机数2)用户B计算：3）B向A发送消息：4)用户A计算：5)用户A计算：,离散数学,概率加密的本质是消除由公钥密码学引起的信息泄露。因为密码分析者总能用公开密钥加密一些随机消息，所以他能够得到一些信息。假设他已有密文C=Epk(M)，并企图恢复明文M，他可随机地选择一个消息M，并对M进行加密C=Epk(M)。如果C=C，那他猜到了那个正确的明文；如果CC，他可再次猜测。允许密码分析者使用你的公开密钥加密随机消息存在的潜在问题是：每当密码分析者加密一个消息时，就有一些信息泄露给他。概率加密试图消除这种泄露，目标是对密文或任何其他试验明文的任何计算都不能给密码分析者关于对应明文的任何信息。,6补充-概率加密,离散数学,在概率加密中，加密算法是概率性的而不是确定性的。即一个明文可能对应的密文不再是唯一的，因此从给定的密文要推测相应的明文就更加困难。例如，假定密码分析者有密文Ci=Epk(M)。即使他正确猜到M，但当他们加密Epk(M)时，结果将是完全不同的密文Cj。他无法比较Ci和Cj，所以他不可能知道他已经猜到消息M。在概率加密方案中，密文数目始终比明文多。因为许多密文解密成相同的明文。,6补充-概率加密,离散数学,实例：Manu