第6讲 公钥密码技术

1、2020/7/4,Ch4(2)-公钥加密技术,1,第4章公钥密码技术,主要知识点：公钥密码体制背包密码RSA密码公钥分配利用公钥密码分配对称密钥Diffie-Hellman密钥交换,2020/7/4,Ch4(2)-公钥加密技术,2,RSA算法的安全性,RSA密码体制的安全性是基于分解大整数的困难性假设RSA算法的加密函数c=memodn是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的对于接收方解密密文的陷门是分解n=pq，由于接收方知道这个分解，他可以计算(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。,2020/7/4,Ch4(2)-公钥加密技术,3,对

2、RSA算法的攻击有下面几个方法：穷举攻击，数学攻击，选择密文攻击，公共模数攻击，计时攻击最基本的攻击是穷举攻击，也就是尝试所有可能的私钥数学攻击的实质是试图对两个素数乘积的分解计时攻击也可以用于对RSA算法的攻击。计时攻击是攻击者通过监视系统解密消息所花费的时间来确定私钥。时间攻击方式比较独特，它是一种只用到密文的攻击方式,2020/7/4,Ch4(2)-公钥加密技术,4,公钥分配,公钥密码体制的密钥分配与对称密码体制的密钥分配有着本质的差别对称密码体制的密钥分配中必须同时确保密钥的秘密性、真实性和完整性,2020/7/4,Ch4(2)-公钥加密技术,5,公钥分配,公开密钥密码体制中有两个密钥

3、，私钥由自己保管，不需要进行分配公钥密码体制不需要保证公钥的秘密性,只需确保公钥的真实性和完整性，这样就能保证公钥没有被攻击者替换或篡改公钥的分配方法可归纳为四种：公开发布、公用目录表、公钥授权和公钥证书。,2020/7/4,Ch4(2)-公钥加密技术,6,1.公开发布,公开发布指用户将自己的公钥发给其他用户，或广播给某一团体这种方法虽然简单，但有一个较大的缺点，即任何人都可伪造这种公开发布如果某个用户假装是用户A并以A的名义向另一用户发送或广播自己的公开钥，则在A发现假冒者以前，这一假冒者可解读所有意欲发向A的加密消息，而且假冒者还能用伪造的密钥获得认证。,2020/7/4,Ch4(2)-公

4、钥加密技术,7,2.公用目录表,公用目录表指一个公用的公钥动态目录表公用目录表的建立、维护以及公钥的分布由某个可信的实体或组织承担，称这个实体或组织为公用目录的管理员与第一种分配方法相比，这种方法的安全性更高该方法有以下一些组成部分：,2020/7/4,Ch4(2)-公钥加密技术,8,管理员为每个用户在目录表中建立一个目录，目录中有两个数据项：一是用户名，二是用户的公开钥。每一用户都亲自或以某种安全的认证通信在管理者那里为自己的公开钥注册。用户可以随时用新密钥替换现有的密钥。这可能由于自己的公钥用过的次数太多或由于与公钥相关的私钥已泄漏。,公用目录表组成部分,2020/7/4,Ch4(2)-公

5、钥加密技术,9,管理员定期公布或定期更新目录表。例如，像电话号码本一样公布目录表或在发行量很大的报纸上公布目录表的更新。用户可通过电子手段访问目录表。此时，从管理员到用户必须有安全的认证通信。这种方案的安全性明显高于公开发布的安全性，但仍易受到攻击。如果敌手成功地获得管理员的私人密钥，就可伪造一个公钥目录表，以后既可以假冒任一用户又可以监听发往任一用户的消息。,公用目录表组成部分,2020/7/4,Ch4(2)-公钥加密技术,10,3.公钥授权,与公用目录表类似，假定有一个公钥管理机构来为用户建立、维护动态的公钥目录但同时对系统提出以下要求，即：每个用户都可靠地知道管理机构的公钥，而只有管理机

6、构自己知道相应的私钥图4.7是典型的公钥分配方案，在这个分配方案中完成了两个功能，一是获得需要的公钥；二是双方相互认证,2020/7/4,Ch4(2)-公钥加密技术,11,2020/7/4,Ch4(2)-公钥加密技术,12,4.公钥证书,公钥授权中的管理机构有可能成为系统的瓶颈，而且由管理机构维护的公钥目录表也易被攻击者篡改。分配公钥的另一方法是公钥证书用户通过交换公钥证书来互相交换自己的公钥公钥证书类似人们使用的纸类证书，如驾驶执照、毕业证等，两者都包括拥有者的属性，可以验证,2020/7/4,Ch4(2)-公钥加密技术,13,4.公钥证书,证书一般由第三方发行，这个第三方称为证书权威中心（

7、certificateauthority,CA）。证书由CA签名表明证书的拥有者所具有的公钥等信息。证书由CA用它的私钥签名，其他用户可以用CA的公钥验证证书的真假。,2020/7/4,Ch4(2)-公钥加密技术,14,使用公钥证书分配公钥过程非常简单事先由CA对用户的证书签名，证书中包含有与该用户的私钥相对应的公钥及用户的身份等信息所有的数据项经CA用自己的私钥签名后就形成证书用户可将自己的公钥通过公钥证书发给另一用户，接收方可用CA的公钥对证书加以验证，这样接收方就能知道发送方的公钥由于证书是由CA私钥加密，任何其他人不能伪造该证书。,2020/7/4,Ch4(2)-公钥加密技术,15,利

8、用公钥密码分配对称密钥,由于公钥算法速度很慢，在通信中一般不使用公钥加密消息，而是使用会话钥（对称密码密钥）因此一般的做法是用会话钥加密消息，用公钥来实现会话钥的分配。,2020/7/4,Ch4(2)-公钥加密技术,16,利用公钥密码分配对称密钥,一种简单的会话钥分配方法如下：A产生一对公私钥PUa和PRa，将公钥PUa和自己的身份标识IDA传给BB产生一个会话钥Ks，用A的公钥PUa加密后EPUa(Ks)传给A由于只有A有私钥PRa，所以A能够得到会话钥Ks。随后双方用会话钥Ks加密双方需要传输的消息。,2020/7/4,Ch4(2)-公钥加密技术,17,Diffie-Hellman密钥交换

9、,Diffie-Hellman密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公开密钥算法已在很多商业产品中得以应用算法的惟一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥算法本身不能用于加、解密该算法的安全性基于求离散对数的困难性。给定g,p,以及x=gk%p很难找到k,2020/7/4,Ch4(2)-公钥加密技术,18,Diffie-Hellman算法,算法的难度建立在离散对数问题(discretelog)上:给定g,p,以及x=gk%p很难找到k与对数问题相似，不同的是进行离散对数运算为被证实是NP完全问题，但与因子分解一样非常困难,2020/7/4,

10、Ch4(2)-公钥加密技术,19,Diffie-Hellman算法,设p是素数,g是生成元(generator)对任意x1,2,p-1我们能找到n满足x=gn%pAlice选择一个秘密的a值Bob选择一个秘密的b值Alice将ga%p发送给BobBob将gb%p发送给Alice两人的电脑共享秘密的gab%p共享的秘密可被用作对称密钥(公钥),2020/7/4,Ch4(2)-公钥加密技术,20,Diffie-Hellman算法,假设Bob和Alice使用gab%p作为对称密钥Trudy可以获得ga%p和gb%p注意(ga*gb)%p=ga+b%pgab%p如果Trudy能找到a或b,整个系统就被

11、破译了如果Trudy能解离散对数问题，那么她能够找到a或b,2020/7/4,Ch4(2)-公钥加密技术,21,Diffie-Hellman算法,公钥:gandp密钥:Alice的指数a,Bob的指数b,Alice,a,Bob,b,ga%p,gb%p,Alice计算(gb)a=gb*a=ga*b%pBob计算(ga)b=ga*b%p可以利用K=gab%p作为共有(对称)密钥,2020/7/4,Ch4(2)-公钥加密技术,22,Diffie-Hellman算法弱点,会遭受中级人(MiM)攻击（一种主动攻击）,Alice,a,Bob,b,gamodp,gbmodp,Trudy,t,gtmodp,gtmodp