1 信息安全引论信息安全引论 第六讲第六讲 公开

《1 信息安全引论信息安全引论 第六讲第六讲 公开》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008-2009年度北京大学本科生课程讨论议题信息安全引论¾公开密钥密码算法第六讲−公开密钥密码算法的基本思想−公开密钥密码算法的数学基础−一些经典算法公开密钥密码算法陈钟教授北京大学信息科学技术学院软件研究所--信息安全研究室chen@infosec.pku.edu.cn2008/10/30NISC-06chenzhong©PKU公钥密码基于的数学难题离散对数难题•背包问题•离散对数的计算:•大整数分解问题（TheIntegerFactorizationy≡gxmodpProblem,RSA体制）–已知g,x,p

2、,计算y是容易的–已知y,g,p,计算x是困难的。•离散对数问题−有限域的乘法群上的离散对数问题(TheDiscrete•密码学中常用的主要有三个群的离散对数LogarithmProblem,ElGamal体制）−有限域GF（p）的乘法群−定义在有限域的椭圆曲线上的离散对数问题（The−有限域GF（2n）上的乘法群EllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）−有限域F上的椭圆曲线群讨论议题Diffie-Hellman密钥交换¾公开密钥密码经典算法–Diffie

3、-Hellman密钥交换算法•是第一个公钥方案•Diffie&Hellmanin1976–背包算法–nowknowthatJamesEllis(UKCESG)secretlyproposed–RSA算法theconceptin1970–EIGamal算法•使用在一些商业产品中•密钥交换方案–椭圆曲线密码算法ECC−不能用于交换任意信息−允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程−该秘密信息仅为两个参与者知道•算法的安全性依赖于有限域上计算离散对数的难度•在美国的专利1997年4月29日到期1Diffi

4、e-Hellman密钥交换•算法：UserAUserB–双方选择素数p以及p的一个原根a–用户A选择一个随机数Xa

5、Calculate•素数p以及p的原根a可由一方选择后发给对方K=(Yb)XamodpK=(Ya)XbmodpDiffie-HellmanKeyExchangeDiffie-HellmanExampleDiffie-Hellman密钥交换的攻击•用户Alice和Bob想交换密钥:YAYBP,a•约定素数P=353和a=3•replay攻击•随机选择密钥:BA–AchoosesxA=97,BchoosesxB=233•计算公钥:O97–yA=3mod353=40(Alice)233–yB=3mod353=248(Bob

6、)•中间人攻击图示•计算共享的会话密钥:K=yxAmod353=24897=160(Alice)AK=aXaXoK=aXbXoBABBOxB233KAB=yAmod353=40=160(Bob)Diffie-Hellman密钥交换的攻击讨论议题•中间人攻击–1双方选择素数p以及p的一个原根a(假定O知道)¾公开密钥密码经典算法–2A选择Xa

7、,计算Yb=aXbmodp,BÎA:Yb–RSA算法–5O截获Yb,冒充BÎA:Yo–6A计算:(Xo)Xa≡(aXo)Xa≡aXoXamodp–EIGamal算法–7B计算:(Xo)Xb≡(aXo)XXb≡aXoXbmodp–椭圆曲线密码算法ECC–8O计算:(Ya)Xo≡aXaXomodp,(Yb)Xo≡aXbXomodp•O无法计算出aXaXbmodp•O永远必须实时截获并冒充转发,否则会被发现2RSA算法讨论议题•RSA算法描述¾公钥密码经典算法•RSA实现中的问题–Diffie-Hellman密钥交换算法•

8、对RSA的攻击方法–背包算法–RSA算法–EIGamal算法–椭圆曲线密码算法ECCRSA算法RSA算法•1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布•是一种分组加密算法。–明文和密文在0~n-1之间,n是一个正整数•应用最广泛的公钥密码算法•只在美国申请专利，且已于2000年9月到期Rivest