网络,信息,安全 第四章-公钥密码系统.ppt

第二部分 信息加密与信息隐藏 第4章 公钥密码系统 导读 本章我们将讨论解密密钥与加密密钥不同的情况。非对称密码系统的解密密钥与加密密钥是不同的，一个称为公开密钥，另一个称为私人密钥（或秘密密钥），因此这种密码体系也称为公钥密码体系。公钥密码除可用于加密外，还可用于数字签名。《中华人民共和国电子签名法》已于2005年4月1日实行。 Contents 公钥密码概述 公钥的起源 公钥密码体制于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）加密和解密算法都是公开的。 Contents RSA密码系统 公开密钥算法RSA (根据其发明者命名，即R. Rivest, A. Shamir和L. Adleman)。 RSA密码系统的安全性基于大数分解的困难性。 求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，从而由一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。 公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等。 RSA密码系统 （1）加密算法 若用整数X表示明文，用整数Y表示密文(X和Y均小于n)，则加密和解密运算为： 加密：Y ? Xe mod n 解密：X ? Yd mod n RSA密码系统 （2）密钥的产生 现在讨论RSA公开密钥密码体制中每个参数是如何选择和计算的。 ① 计算n。用户秘密地选择两个大素数p和q，计 算出n ? pq。n称为RSA算法的模数。 ② 计算φ(n)。用户再计算出n的欧拉函数 φ(n)?(p ? 1)(q ? 1) 。 ③ 选择e。用户从[1, φ(n) ? 1]中选择一个与 φ(n)互素的数e作为公开的加密指数。 RSA密码系统 ④ 计算d作为解密指数。用户计算出满足下式的d ed?1modφ(n) 即：(ed –1) modφ(n)=0由此推出 ed =t φ(n)+1 (t 是大于等于1的正整数） ⑤ 得出所需要的公开密钥和秘密密钥： 公开密钥(即加密密钥)PK ? {e, n} 秘密密钥(即解密密钥)SK ? {d, n} 其中，p、q、φ?(n)和d就是秘密的陷门(四项 并不是相互独立的)，这些信息不可以泄露。 RSA密码系统 RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成大小合适的数据分组，然后对分组分别进行加密。每个分组的大小应该比n小。 设ci为明文分组mi加密后的密文，则加密公式为 ci=mie (mod n) 解密时，对每一个密文分组进行如下运