公钥密码讲座new

《公钥密码讲座new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科生课程刘建伟2010-10-14第8讲：公钥密码技术（一）公钥密码体制的基本概念构造公钥密码的困难问题–离散对数、整数分解、椭圆曲线、…主要的几种公钥算法–RSA公钥算法–Diffie-Hellman密钥交换–ElGamal公钥算法–Rabin算法–椭圆曲线公钥算法(ECC)一、双钥密码体制的基本概念1、公钥密码的历史在对称密钥密码体制中，加密运算与解密运算使用同样的密钥。但是，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。1976年，Diffie和Hellman在奠基性论文“密码学的新方向”中提出公开密钥密码体制的概念：

2、使密钥交换、管理容易，并可实现数字签名。–NewDirectionsinCryptography,IEEEIT-22,1976公钥密码体制的基础，是计算复杂度理论。–单向函数/单向陷门函数–计算上困难问题/NP完全问题2、公钥密码学WhitefieldDiffie，MartinHellman，《NewDirectionsinCryptography》，1976。公钥密码学的出现使大规模的安全通信得以实现–解决了密钥分发问题；公钥密码学还可用于另外一些应用：数字签名、防抵赖等；公钥密码体制的基本原理–陷门单向函数(trapdoorone-w

3、ayfunction)公钥密码是密码学历史上一个伟大的革命性成果。3、理论基础——单向函数定义1：令函数f是集A到集B的映射，用f:A→B表示。若对于任意x≠x，x,x∈A，有f(x)≠f(x)，则称f为单射，121212或1-1映射，或可逆的函数。定义2：一个可逆函数f:A→B，若它满足：(1)对所有x∈A，易于计算f(x)；(()2)对“几乎所有x∈A”，由f(x)求x极为困难，以至于几乎是不可能的，则称f是一个单向函数。注意：定义中的“极为困难”是相对现有的计算机资源和算法而言。4、理论基础——陷门单向函数定义3：陷门单向函数是一类满足下述

4、条件的单向函数：f:A→B，z∈Z，Z是陷门信息集合。zzz(1)对所有z∈Z，在给定z下容易找到一对算法E和D，使对zz所有x∈A，易于计算f及其逆，即：zf(x)E(x)zzD(f(x))xzz(2)对所有z∈Z，当只给定E和D时，对所有x∈A，“很难zz”从y=f(x)计算出x。z区别：单向函数是求逆困难的函数，而陷门单向函数(trapdooronewayfunction)是在不知道陷门信息下求逆困难的函数。当知道陷门信息后，求逆易于实现。5、用于构造双钥密码的单向函数1.多项式求根2.离散对数DL(DiscreteLogarithm)3

5、.大整数分解FAC(FactorizationProblem)4.背背问包问题题((ppKnapsackproblem))5.Diffie-Hellman问题DHP6.二次剩余问题QR(QQR(QuadratiiRcResidue)7.模n的平方根问题(SQROOT)公钥密码体制的原理公钥密码技术，又称非对称密码技术或双钥密码技术（Public-key/Two-key/Asymmetric），其加密和解密数据使用不同的密钥。不同abc#@&abc加密器解密器明文密文明文公钥密钥体制的密钥管理公钥密钥体制解决了密钥的发布和管理问题，通信双方可以公开

6、其公开密钥，而保留私有密钥。发送方可以用人人皆知的接受方公开密钥对发送的信息进行加密，安全的传送给该接受方，然后由接受方用自己的私有密钥进行解密。公钥密码体制的特点包括两个密钥：–公开密钥(public-key)，可以被任何人知道，用于加密或验证签名–私钥(private-key)，只能被消息的接收者或签名者知道，用于解密或签名由私钥及其他密码信息容易计算出公开密钥；而由公钥及算法描述，计算私钥却非常困难。公钥加密方案公钥算法的用途用于公公分发钥分发（Public-KeyDistributionSchemes—PKDS）–用于交换秘密信息

7、，常用于交换对称加密算法的密钥用于公钥加密((yPublicKeyEncrypyption—PKE)–用于加密任何消息–任何人可以用公钥加密，私钥的拥有者可以解密–任何公钥加密方案能够用于密钥分配方案PKDS–许多公钥加密方案也是数字签名方案用于数字签名（SignatureSchemes）–用于生成对某消息的数字签名–私钥的拥有者生成数字签名–任何人可以用公钥验证签名公钥的安全性依赖于数学上足够大的困难性。类似与对称算法,穷搜索（exhaustivesearch）在理论上是能够破解公钥密码，但实际上，当密钥足够长(()>512bits)时，

8、破解极其困难。一般情况下，我们已经找到了一些已知的困难问题(hardproblem）目前，通常要求足够大的密钥长度(>