第4章公钥密码体系　.pptVIP

第4章 公钥密码系统 ;导读;公钥密码体制于1976年由W. Diffie和M. Hellman提出，同时，R. Merkle也独立提出了这一体制。 这种密码体制采用了一对密钥——加密密钥和解密密钥(且从解密密钥推出加密密钥是不可行的)，这一对密钥中，一个可以公开(称之为公钥)，另一个为用户专用(私钥)。 公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配(distribution)问题，另一是由于对数字签名的需求。 ;陷门单向函数; 公钥密码系统可用于以下三个方面： (1) 通信必威体育官网网址：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现必威体育官网网址通信。 ; (2) 数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。; (3) 密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。 ;公开密钥算法的特点如下所述。 （1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为： DSK(EPK(X))? X 解密密钥是接收者专用的秘密密钥，对其他人都必威体育官网网址。 此外，加密和解密的运算可以对调，即 EPK(DSK(X)) ? X。 （2）加密密钥是公开的，但不能用它来解密，即 DPK(EPK(X))? X （3）在计算机上可以容易地产生成对的PK和SK。 （4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。 （5）加密和解密算法都是公开的。 ; 公开密钥加密的第一个算法是由Ralph Merkle和Martin Hellman开发的背包算法，它只能用于加密。后来，Adi Shamir将其改进，使之能用于数字签名。背包算法的安全性不好，也不完善。随后不久就出现了第一个较完善的公开密钥算法RSA (根据其发明者命名，即R. Rivest, A. Shamir和L. Adleman)。 RSA密码系统的安全性基于大数分解的困难性。 求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，从而由一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。 公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等。; （1）加密算法 若用整数X表示明文，用整数Y表示密文(X和Y均小于n)，则加密和解密运算为： 加密：Y ? Xe mod n 解密：X ? Yd mod n ; （2）密钥的产生 现在讨论RSA公开密钥密码体制中每个参数是如何选择和计算的。 ① 计算n。用户秘密地选择两个大素数p和q，计算出n ? pq。n称为RSA算法的模数。 ② 计算φ(n)。用户再计算出n的欧拉函数φ(n)?(p ? 1)(q ? 1) 。 ③ 选择e。用户从[1, φ(n) ? 1]中选择一个与φ(n)互素的数e作为公开的加密指数。; ④ 计算d作为解密指数。用户计算出满足下式的d ed ?1 modφ(n) 即：(ed –1) modφ(n)=0 由此推出 ed =t φ(n)+1 (t 是大于等于1的正整数） ⑤ 得出所需要的公开密钥和秘密密钥： 公开密钥(即加密密钥)PK ? {e, n} 秘密密钥(即解密密钥)SK ? {d, n} 其中，p、q、φ?(n)和d就是秘密的陷门(四项并不是相互独立的)，这些信息不可以泄露。;RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成大小合适的数据分组，然后对分组分别进行加密。每个分组的大小应该比n小。 设ci为明文分组mi加密后的密文，则加密公式为 ci=mie (mod n) 解密时，对每一个密文分组进行如下运算： mi=cid (mod n) 例子:说明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来说，