公钥密码技术

-1-第三章公钥密码技术-2-第三章公钥密码技术11.公钥密码的概念2.公钥密码学的理论基础3.公钥密码算法4.密钥交换5.公钥密码算法的应用-3-提出公钥密码的动因1.密钥分配问题。使用对称加密算法的通信双方要进行加密通信时，需要通过秘密的安全信道协商加密密钥，而这种安全信道如何实现呢？机械阶段2.数字签名问题。信息的电子化对密码学提出了新的要求：电子报文和电子文件需要一种与书面材料中使用的签名等效的认证手段。-4-公钥密码的初始化阶段-5-加密通信阶段-6-1.公钥密码的概念2.公钥密码学的理论基础3.公钥密码算法4.密钥交换5.公钥密码算法的应用第三章公钥密码技术2-7-计算复杂度与公钥密码•计算复杂度•P问题和NP完全问题•密码与计算复杂度的关系-8-单向陷门函数一个单向陷门函数()fX要满足下面的条件：它将一个定义域映射到一个值域，使得每一个函数值都有一个唯一的原象；同时，函数值计算很容易而逆计算是困难的，但是如果知道某个陷门t后，逆计算是容易的。即()YfX容易1()XfY困难知道陷门t后，1()tXfY容易-9-单向陷门函数的数学问题1.分解整数问题。2.离散对数问题。3.RSA问题。-10-1.公钥密码的概念2.公钥密码学的理论基础3.公钥密码算法4.密钥交换5.公钥密码算法的应用第三章公钥密码技术3-11-公开密钥算法公钥算法的种类很多，具有代表性的三种密码：基于离散对数难题（DLP）的算法体制，例如Diffie-Hellman密钥交换算法；基于整数分解难题（IFP）的算法体制，例如RSA算法；基于椭圆曲线离散对数难题（ECDLP）的算法体制；-12-RSA算法麻省理工学院的RonRivest,AdiShamir和LenAdleman于1977年研制，并于1978年首次发表；RSA是一种分组密码，其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；既可用于加密，又可用于数字签名，已得到广泛采用；RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；RSA-155(512bit),RSA-140于1999年分别被分解；-13-Euler函数欧拉函数(Euler’stotientfunction)，记为φ(n)，表示小于n而且与n互素的正整数个数；对于任一素数p，φ(p)=p-1;对于两个不同的素数p和q，若n=p×q，则φ(n)=φ(p×q)＝φ(p)×φ(q)＝(p-1)×(q-1)；-14-Euler函数举例设p=3,q=5,那么n=p×q=15；1）小于15而且与15互素的正整数是：{1，2，4，7，8，11，13，14}因此，φ（15）＝8；2）φ（15）=（3-1）*（5-1）=8-15-欧拉定理对于任何互素的整数a和n，(modn)，或者写作a(modn)给定两个素数p和q，以及整数n=p×q，和m，其中0mn，则modnmodn1)(na1)(nammmqpn1)1)(1(1)(mmmqpknk1)1)(1(1)(-16-RSA算法的描述对于明文分组M和密文分组C，加密解密形式分别为：C=MemodnM=Cdmodn=(Me)dmodn=Medmodn因此，公钥KU={e,n},私钥KR={d,n},公钥算法必须满足:1）有可能找到e、d、n的值，使得对所有Mn有Med=Mmodn；2）对于所有Mn，要计算Me和Cd相对简单；3）给定e和n时，判断出d是不可行的；-17-RSA算法的描述如何找到：？参考欧拉定理可以得到：ed=k×φ(n)+1也就是说：nMMMqpknkmod1)1)(1(1)()(mod1ned)(mod1nednMMedmod-18-RSA算法的实现实现的步骤如下：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-1modφ(n)(5)Bob在目录中公开n和e作为公钥密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=p×q，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d-19-RSA算法举例设p=7,q=17,n=7*17=119;参数T={n=119};φ(n)=(7-1)(17-1)=96;选择e=5,gcd(5,96)=1;计算d,d*e=1mod96;d=77;因为77×5＝385＝4×96＋1设:明文m=19加密：（19）5mod119=66解密：（66）77mod119=19-20-RSA算法的安全性分析密码分析者攻击RSA体制的关键在于分解n,若分解成功使n=p×q，则可以算出φ(n)＝（p-1)×(q-1)，然后由公开的e，解出秘密的d;若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来,建议选择p和q大约是100位的十进制素数,模n的长度要求至少是512比特;-21-RSA算法的安全性分析EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数;国际数字签名标准ISO/IEC9796中规定n的长度位512比特位;为了提高加密速度，通常取e为特定的小整数,如EDI国际标准中规定e＝216＋1;ISO/IEC9796中甚至允许取e＝3;这时加密速度一般比解密速度快10倍以上;-22-RSA算法的安全性分析为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1分别含有大素因子p1和q1；(3)P1-1和q1-1分别含有大素因子p2和q2；(4)p+1和q+1分别含有大素因子p3和q3；-23-椭圆曲线密码编码学ECC1985年Miller,Koblitz独立提出y2+axy+by=x3+cx2+dx+e表示曲线上的点连同无穷远点O的集合加法:若曲线三点在一条直线上,则其和为O；倍数:一个点的两倍是它的切线与曲线的另一个交点；-24-椭圆曲线上的加法规则加法公式:O作为加法的单元，O=-O，P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P,而且(x,-y)也在EP(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则P+Q=(x3,y3)为x3=2-x1-x2(modp)y3=(x1-x3)-y1(modp)其中，如果PQ，则=(y2-y1)/(x2-x1)如果P=Q，则=(3x12+a)/(2y1)-25-椭圆曲线示例椭圆曲线上的加法:P+Q=-R椭圆曲线上一点的2倍:Q+Q=-S-26-有限域上的椭圆曲线有限域上的椭圆曲线定义如下：y2x3+ax+b(modp)p是素数,a,b为非负整数，且满足4a3+27b2(modp)0针对所有的0=xp，可以求出有效的y，得到曲线上的点(x,y)，其中x,yp。曲线记为EP(a,b),EP(a,b)中也包括O点例如，令P=23，a=b=1，椭圆曲线为y2＝x3+x+1，4×13＋27×12(mod23)=80满足模23椭圆群的条件-27-椭圆曲线上的密钥交换1）双方选择EP(a,b)以及EP(a,b)的一个元素G,使得nG=0的最小n值是一个非常大的素数；2）A选择私钥Xn,计算公钥PA=XG；3）B选择私钥Yn,计算公钥PB=YG；4）A计算秘密密钥:K=X(PB)=XYG5）B计算秘密密钥:K=Y(PA)=YXG=XYG因此，双方获得了一个共享会话密钥(XYG)-28-椭圆曲线上的密钥交换攻击双方选择EP(a,b)以及EP(a,b)的一个元素G,使得G的阶n是一个大素数A选择私钥Xn,计算公钥PA=XG,AB:PAE截获PA,选私钥Z,计算PE=ZG,冒充AB:PEB选择私钥Yn,计算公钥PB=YG,BA:PBE截获PB,冒充BA:PEA计算:XPE=XZGB计算:YPE=YZGE计算:ZPA=ZXG,ZPB=ZYGE无法计算出XYGE永远必须实时截获并冒充转发,否则会被发现.-29-椭圆曲线加密/解密1）双方选择椭圆群EP(a,b)以及EP(a,b)的一个元素G,使得nG=0的最小n值是一个非常大的素数；2）A选择私钥Xn,计算公钥PA=XG；3）B选择私钥Yn,计算公钥PB=YG；4）A若想加密和发送报文Pm给B，选择随机数k，并产生一对点组成的密文Cm={kG,Pm+kPB}；5）B解密密文，Pm+kPB-Y×kG＝Pm+k×YG-Y×k×G=Pm除了A，无人知道k，因此无法破译-30-两类加密算法比较保密密钥算法RSA算法椭圆曲线算法40位————56位400位——64位512位——80位768位——90位1024位160位112位1792位195位120位2048位210位128位2304位256位-31-1.公钥密码的概念2.公钥密码学的理论基础3.公钥密码算法4.密钥交换5.公钥密码算法的应用第三章公钥密码技术4-32-Diffie-Hellman密钥交换算法若用户A和用户B希望交换一个密钥，如何进行？1）全局公开参数：一个素数q和其一个原根a；2）用户A选择一个随机数XAq，计算YA=aXAmodq，YA公开；3）用户B选择一个随机数XBq，计算YB=aXBmodq，YB公开；4）用户A计算密钥K=(YB)XA×modq;5）用户B计算密钥K=(YA)XB×modq;-33-Diffie-Hellman密钥交换算法证明：K=(YB)XAmodq=(aXBmodq)XAmodq=(aXB)XAmodq=aXBXAmodq=(aXA)XBmodq=(aXAmodq)XBmodq=(YA)XBmodq攻击分析：公开数据q，a，YA和YB，若想攻击用户B的秘密密钥，攻击者必须计算XB=inda,q(YB)；安全性分析：计算模一个素数的指数相对容易，计算离散对数却很难；-34-Diffie-Hellman密钥交换算法举例1）密钥交换基于素数q=97和q的一个原根a=5；2）A和B分别选择密钥XA=36和XB=58，并分别计算其公开密钥YA=536=50mod97YB=558=44mod973）交换了公开密钥后，每人计算共享的秘密密钥如下K=(YB)XAmod97=4436=75mod97K=(YA)XBmod97=5058=75mod97-35-ECC密钥交换算法类似Diffie－Hellman密钥交换，思考如何用ECC来实现密钥交换。-36-1.公钥密码的概念2.公钥密码学的理论基础3.公钥密码算法4.密钥交换5.公钥密码算法的应用第三章公钥密码技术5-37-公钥密码的典型应用•使用RSA和DES对信息加密•使用散列函数和RSA进行数字签名-38-进阶阅读和习题