非对称密码体制.ppt

4.3.2背包密码算法RalphMerkle和MartinHellman开发了第一个非对称密码算法——背包算法。(背包算法只能用于加密)背包问题的描述：给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中，使之等于一个给定的重量？？？给定一系列值m1,m2,…,mn和一个和s，计算bi使之满足s=b1m1+b2m2+…+bimi背包密码体制的安全性基于背包难题，它证明了如何将一个NP完全问题应用到非对称密码学，后来被证明是不安全的。**4.3.3ElGamal密码算法ElGamal密码算法由T.ElGamal在1985年提出ElGamal的安全性基于求解离散对数问题的困难性ElGamal算法描述所有的用户都共享一个素数p以及一个Zp的生成元a，系统中每一个用户U都随机挑选一个整数mu，并计算Cu=amumodp，然后用户U公开Cu作为公开密钥，并保存整数mu作为自己的私钥。**4.3.3ElGamal密码算法密钥对产生办法首先选择一个素数p，两个随机数g和x(g,xp)，计算y=g^x(modp)，则其公钥为g和p，私钥是x。g和p可由一组用户共享。ElGamal加解密过程被加密信息为m，首先选择一个随机数k，k与p-1互质，计算a=g^k(modp)，b=m*y^k(modp)(a,b)为密文，是明文的两倍长。解密时计算m=b/a^x(modp)**4.3.3ElGamal密码算法ElGamal密码算法最大的特点是非确定性由于密文依赖于执行加密过程所选择的随机数k，所以加密相同的明文可能会产生不同的密文。ElGamal密码算法的安全性依赖于乘法群上的离散对数计算复杂度。一般素数p要仔细地选取，且是k模p的本原元。为了防止已知攻击，p应该至少有300个十进制数位，p-1应该至少具有一个较“大”的素因数。ElGamal密码算法可以在任何离散对数问题难以处理的有限群中实现。**4.3.4椭圆曲线密码算法1985年，N.Koblitz及V.S.Miller分别提出了椭圆曲线密码算法椭圆曲线密码算法的优点(1)密钥尺度较小；(2)参数选择比较灵活；(3)具有由数学难题保证的安全性；(4)实现速度较快。****选择一个素数和椭圆曲线的参数a和b，共同定义椭圆曲线群E；其次，在E中按照前面的要求选择一个基点G。E与G是整个系统共同的参数，系统中每个用户都可以获得E与G。另外，系统中每一个用户U都将选择一个随机数rU，并计算，以PU为用户U的公钥，加以公开；以rU作为用户U的私钥（秘密密钥）加以保存，不能泄露。(1)加密算法假设某一Bob需要发送一个报文m给Elice，Bob将采用如下算法加密消息m：第一步：Bob将需要发送的明文编码嵌入到E上的一个点；第二步：Bob随机选择一个整数r，计算R=rG；第三步：Bob计算，其中PB是Elice的公开密钥；第四步：Bob将二元组（R，S）作为密文传送给Elice。4.3.4椭圆曲线密码算法**(2)解密算法Elice接收到二元组（R，S）后，计算：进行解密(其中rB是Elice的秘密密钥)。由于这样，Elice便可以对二元组（R，S）解密得到Pm，进而逆向译码获得明文m。4.3.4椭圆曲线密码算法**作业P74:8(d=37,y=58)**信息安全概论电子科技大学出版社2007年8月第4章非对称密码体制4.1概述4.2RSA密码算法4.3其它密码算法**4.1概述4.1.1对称密码面临的困难4.1.2非对称密码的产生4.1.3非对称密码体制4.1.4单向函数**4.1.1对称密码面临的困难密钥的管理、分发与协商假设某个系统有N个用户相互进行保密通信，任意两个用户使用互不相同的密钥。密钥管理问题：每个用户需要保存N-1个密钥。（如果N非常大，如何解决？）密钥分发问题：系统总共需要N*(N-1)/2个密钥：例如N=1000时,999*1000/2=499500。密钥协商问题：第一次协商好密钥后，以后可以通过当前密钥秘密发送新密钥。但第一次如何协商密钥？（用户秘密会面协商？陌生人怎么办？远距离怎么办？）消息发送者的身份确认问题**4.1.2非