第六章 - 指数与原根ppt课件

.,初等数论-第六章指数与原根,.,本章内容,.,1指数,.,1指数,.,.,.,.,.,.,.,.,.,.,.,.,.,2原根,.,.,.,.,3指标、二项同余方程,.,.,.,.,.,.,.,.,.,.,Diffie-Hellman密钥交换,Diffie和Hellman在1976年提出的Diffie-Hellman密钥交换协议，是一个典型的密钥协商协议;允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程;算法的安全性依赖于计算离散对数的难度.,Diffie-Hellman密钥交换,离散对数困难性回顾素数p的本原根定义：如果a是素数p的本原根，则数amodp,a2modp,ap-1modp是不同的并且包含1到p-1的整数的某种排列。对任意的整数b，我们可以找到唯一的幂I满足b=aimodp0=i=(p-1)i在离散对数算法中称为模p下以a为底b的离散对数（指标），记为i=inda,p(b)。离散对数的计算:Y=gXmodp已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的，当p很大时，该算法是不可行的。,Diffie-Hellman密钥交换,算法双方选择素数p以及p的一个原根a用户A选择一个随机数Xap，计算Ya=aXamodp用户B选择一个随机数Xbp，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方用户A计算出K=YbXamodp用户B计算出K=YaXbmodp双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方,K=YbXamodp=(aXbmodp)Xamodp=aXaXbmodp=(aXamodp)Xbmodp=YaXbmodp,Diffie-Hellman密钥交换,Diffie-Hellman密钥交换的攻击,中间人攻击图示,Diffie-Hellman密钥交换的攻击,中间人攻击1双方选择素数p以及p的一个原根a(假定O知道)2A选择Xap,计算Ya=aXamodp,AB:Ya3O截获Ya,选Xo,计算Yo=aXomodp,冒充AB:Yo4B选择Xbp,计算Yb=aXbmodp,BA:Yb5O截获Yb,冒充BA:Yo6A计算:(Xo)Xa(aXo)XaaXoXamodp7B计算:(Xo)Xb(aXo)XbaXoXbmodp8O计算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO无法计算出aXaXbmodpO永远必须实时截获并冒充转发,否则会被发现,Diffie-Hellman密钥交换,DiffieHellman密钥交换协议可以容易的推广到椭圆曲线上；为了防止这种中间人攻击，必须引入相应的认证机制；为此，Diffie等人于1992年提出了端到端协议（station-to-stationprotocol），该协议是对DiffieHellman密钥交换协议的一种修改，来抵抗中间人攻击。,ElGamal公钥系统,基本情况算法描述算法的安全性算法的应用,ElGamal公钥系统,基本情况ElGamal密码是除了RSA密码算法外，最具有代表性的公钥密码算法；Diffie-Hellmankeydistributionscheme的变形；加密的安全性建立在解离散对数的困难性上Publishedin1985byElGamal:T.ElGamal,APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985缺点：增加了传送信息长度（2倍）,ElGamal公钥系统,算法描述,ElGamal公钥系统,如果明文需要分组，则每个分块要有唯一的k,ElGamal公钥系统,ElGamal公钥系统,算法实例,ElGamal公钥系统,RSA与ElGamal比较,ElGamal公钥系统,ElGamal算法的安全性由于ElGamal密码的安全性建立在GF(p)离散对数的困难性之上，而目前尚无求解GF(p)离散对数的有效算法，所以p足够大时ElGamal密码是安全的.为了安全p应该为150位以上的十进制数，而且p-1应有大素因子.为了安全加密和签名所使用的k必须是一次性的.d和k都不能太小.,ElGamal公钥系统,ElGamal算法的安全性如果k不是一次性的，时间长了就可能被攻击者获得.又因为y是公开密钥，攻击者自然知道.于是攻击者就可以根据U=ykmodp计算出U,进而利用Euclid算法求出U-1.又因为攻击者可以获得密文C2,于是C2=UMmodp通过计算U-1C2得到明文M.设用同一个k加密两个不同的明文M和M,相应的密文为（C1,C2）和（C1,C2).因为C2/C2=M/M,如果攻击者知道M,则容易求出M.,ElGamal公钥系统,ElGamal算法的应用由于ElGamal密码的安全性得到世界公认,所以得到广泛的应用.著名的美国数字签名标准DSS,采用了ElGamal密码的一种变形;为适应不同的应用，人们在应用中总结出18种不同的ElGama