公开密钥密码系统ThePublic-keycryptosystem
RSA公开密钥密码系统文字
公开密钥密码系统是由R.Rivest、A.Shamir和L.Adleman于1977年提出的。
RSA的 取名就是取自这三位发明者姓氏的第一个字母。后来,在1982年他们又创办了以RSA命名的公司（RSA Data Security Inc.和RSA实验室）,该公司和实验室在公开密钥密码系统的研发和商业应用推广方面具有划时代的意义，是全球公认的计算机网络安全的重要里程碑。
与"公开密钥密码体制"相对应的是"传统密码体制",又称"对称密钥密码体制",其中用 于加密的密钥与用于解密的密钥完全一样。
在对称密钥密码体制中,加密运算与解密运算使用同样的密钥。通常,使用的加密算法 比较简便高效,密钥简短,破译极其困难。但是,在公开的计算机网络上安全地传送和保管 密钥是一个严峻的问题。1976年,Diffie和Hellman为解决密钥管理问题,在他们的奠基性 的工作"密码学的新方向"一文中,提出一种密钥交换协议,允许在不安全的媒体上通讯双方 交换信息,安全地达成一致的密钥。在此新思想的基础上,很快出现了"不对称密钥密码体 制",即"公开密钥密码体制",其中加密密钥不同于解密密钥,加密密钥公之于众
现在,用一个简单的例子来说明RSA公开密钥密码系统的工作原理。
取两个质数p=11, q=13,p和q的乘积为n=p×q=143,算出另一个数z=(p-1)×(q-1)=120;再选取一个与z=120互 质的数,例如e=7(称为"公开指数"),对于这个e值,可以算出另一个值d=103(称为"秘密指数 ")满足e×d=1 mod z;其实7×103=721除以120确实余1。(n,e)和(n,d)这两组数分别为"公 开密钥"和"秘密密钥。"
设想张小姐需要发送机密信息(明文,即未加密的报文)s=85给李先生，她已经从公开媒体或网站上得到了李先生的公开密钥(n,e)=(143,7),于是她算出加密值
c=s[RUe] mod n=85[RU7] mod 143=123并发送给李先生。
李先生在收到"密文"(即经加密的报文)其中c=123，他就可利用只有他自己知道的秘密密钥(n,d)=(143,123)计算123123 mod 143,
得到的值就是明文(值)85,实现了解密。其中的计算用一般公式来表达,是
c[RUd] mod n=(s[RUe])[RUd] mod n=s[RUed] mod n
根据初等数论中的欧拉(Euler)定理,应用s[RUz]=1 mod n,所以
s[RUed]=s mod n
所以,李先生可以得到张小姐发给他的真正的信息s=85。
自然,我们要问,在李先生向公众提供了公开密钥,密文c又是通过公开的途径传送的, 其安全性何在?
回答是肯定的！只有当n足够大时, 例如,有512比特,或1024比特甚至2048比特,n=p×q中的p和q的 位数差不多大小,任何人只知道公开密钥(n,e),目前是无法算出秘密密钥(n,d)的。其困难在于从乘积n难以找出它的两个巨大的质数因子。
上面例子中的n=143,只是示意用的,用来说明RSA公开密钥密码系统的计算过程,从 143找出它的质数因子11和13是毫不困难的。对于巨大的质数p和q,计算乘积n=p×q非常简便,而其逆运算却是相当困难的事情。这是一种"单向性"。相应的函数称为"单向函数"。任何单向函数都可以作为某一种公开密钥密码系统的基础,而单向函数的安全性也就是这种公开密钥密 码系统的安全性。
公开密钥密码系统的一大优点是不仅可以用于信息的保密通讯,又可以用于信息发送者的身份验证(Authentication),或数字签名(Digital Signature),我们仍用下例来示意说明。
李先生要向张小姐发送信息m(表示他的身份,可以是他的身份证号码,或其名字的汉字 的某一种编码值),他必须让张小姐确信该信息是真实的,是由李先生本人所发的。为此,他使用自己的秘密密钥(n,d)计算
s=md mod n建立了一个"数字签名",通过公开的通讯途径发给张小姐。张小姐则使李先生的公开密钥(n,e)对收到的s值进行计算
s[RUe] mod n=(md)e mod n=m
这样,她经过验证,知道信息s确实代表了李先生的身份,只有他本人才能发出这一信息,因为只有他自己知道秘密密钥(n,d),其他任何人即使知道李先生的公开密钥(n,e),也无 法猜出或算出他的秘密密钥来冒充他的"签名"。
有两类基本的加密算法可供对文件加密者选择：保密密钥和公开/私有密钥。在保密密钥中，加密者和解密者使用相同的密钥，被称为对不对称密钥，这类算法有DES和IDEA。这种加密算法的问题是，用户必须让接收信息者知道自己所使用的密钥，这个密钥需要双方共同保密，任何一方的失误都会导致机密的泄露。而且在告诉收件人密钥过程中，还需要的防止任何人发现或窃取密钥，这个过程被称为密钥发布。有些认证系统在会话初期用明文传送密钥，这就存在密钥被截获的可能性。需要使用保密密钥对加密密钥的信息再加密。
另一类加密技术是公开/私有密钥，与非对称密钥体制不同的是，它使用相互关联的一对密钥，一个是公开的密钥，任何人都可以知道，另一个是私有密钥（专一密钥），只有拥有该对密钥的人才有，其他人并没有保管它。假如某甲发信给保存专一密钥的乙方，乙接收到加密信息后，就用他自己保存的密钥进行解密，而且只有乙方持有的私有密钥可以解密。这种加密方式的好处显而易见。密钥只有一个人持有，也就更加容易进行保密，因为不需在网络上传送私人密钥，也就不用担心别人在认证会话初期劫持密钥。下面把公开/私有密钥技术总结为以下几点：
1、公开钥/私有密钥有两个相互关联的密钥。
2、公开密钥加密的文件只有私有密钥能解开。
3、私有密钥加密的文件只有公开密钥能解开.这一特点被用于PGP（pretty good privacy）。
兰色雪狐 编篡于北京