第4章公钥密码系统.ppt

第4章公钥密码系统4.1RSA密码系统公钥密码系统是基于陷门单向函数的概念。在第3章中，我们介绍了单向函数的概念。单向函数是易于计算但求逆困难的函数，而陷门单向函数是在不知道陷门信息情况下求逆困难，而在知道陷门信息时易于求逆的函数。公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文分析出明文或私钥是不可行的。如图4-1所示，Bob拥有多个人的公钥，当他需要向Alice发送机密消息时，他用Alice公布的公钥对明文消息加密，当Alice接收到后用她的私钥解密。由于私钥只有Alice本人知道，所以能实现通信保密。图4-1通信保密(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。如图4-2所示，Bob用私钥对明文进行加密并发布，Alice收到密文后用Bob公布的公钥解密。由于Bob的私钥只有Bob本人知道，因此，Alice看到的明文肯定是Bob发出的，从而实现了数字签名。(3)密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。本章将先讨论RSA密码系统和Diffie-Hellman密钥交换，最后介绍数字签名。图4-2数字签名公开密钥加密的第一个算法是由RalphMerkle和MartinHellman开发的背包算法[2]，它只能用于加密。后来，AdiShamir将其改进，使之能用于数字签名。背包算法的安全性不好，也不完善。随后不久就出现了第一个较完善的公开密钥算法RSA[3](根据其发明者命名，即R.Rivest,A.Shamir和L.Adleman)。RSA密码系统的安全性基于大数分解的困难性。我们知道，求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等，这在许多密码学教材中都有所论述，本书不作讨论。下面介绍RSA密码系统的细节。选择两个不同的大素数p和q(一般都为100位左右的十进制数字)，计算乘积：n=pq和欧拉函数值：φ (n)=(p−1)(q−1)随机取一整数e，1＜e＜φ (n)，且e和φ (n)互素。此时可求得d以满足：ed1mod φ(n)则d=e–1mod φ(n)这样可以把e和n作为公开密钥，d作为私人密钥。其中，p、q、φ (n)和d就是秘密的陷门(四项并不是相互独立的)，这些信息不可以泄露。RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成大小合适的数据分组，然后对分组分别进行加密。每个分组的大小应该比n小。设ci为明文分组mi加密后的密文，则加密公式为ci=mie(modn)解密时，对每一个密文分组进行如下运算：mi=cid(modn)这种加/解密方案的可行性证明可以参考本章参考资料[13]。这里将举一个简单的例子来说明RSA的加/解密过程。选p=5，q=11，则n=pq=55，φ (n)=(p−1)(q−1)=40于是明文空间为在闭区间[1,54]内且不能被5和11整除的数。(如果明文m同n不是互为素数，就有可能出现消息暴露情况，即，这样我们就可能通过计算n与加密以后的m的最大公约数来分解出n。通常，一个明文同n有公约数的概率小于1/p+1/q，因此，对于大的p和q来说，这种概率是非常小的。)选择e=7，则d=23。由加/解密公式可以得到加密表如表4-1所示。表4-1加密表4.2Diffie-Hellman密钥交换Diffie-Hellman算法的安全性在于在有限域上计算离散对数非常困难。在此先简单介绍一下离散对数的概念。定义素数p的本原根(PrimitiveRoot)为一种能生成1～p−1所有数的一个数，即如果a为p的本原根，则amodp，a2modp，…，ap−1modp两两互不相同，构成1～p−1的全体数的一个排列(例如p=11，a=2)。对于任意数b及素数p的本原根a，可以找到一个惟一的指数i，满足：b=aimodp,0≤i≤p−1称指数i为以a为底模p的b的离散对数。如果Alice和Bob想在不安全的信道上交换密钥，他们可以采用如下步骤：(1) Alice和Bob协商一个大素数p及p的本原根a，a和p可以公开；(2) Alice秘密产生一个随机数x，计算X=axmodp，然后把X发送给Bob；(3) Bob秘密产生一个随机数y，计算Y=aymodp，然后把Y发送给Alice；(4) Alice计算k=Yxmodp；(5) Bob计算k'=Xymodp。k和k'是恒等