公开密钥密码系统

公开密钥密码系统

引言
随着计算机和电子通讯技术,包括因特网的迅猛发展,金融电子化的步伐大大加快,这 种电子化、数字化的趋势已经波及社会生活的几乎所有的方面。人与人之间的许多交往活 动,包括商业贸易、金融财务和其他经济活动中,不少已以数字化信息的方式在网上流动着 。"数字化经济"(Digital Economy)的图景已经浮现,电子商业、电子银行和电子货币的研 究、实施和标准化正在紧锣密鼓地进行中。许多传统上基于纸面的,常常需要签名盖章的 重要凭证,诸如纸币、存单、支票、股票、公函、合同、租约、遗嘱、选票、法律文书、 身份证件、学历证书等等,已陆续转化为数字电子媒体的形式出现。这种转化方兴未艾,前 景辉煌,虽然未必会有百分之百的转化,但对社会、经济、商业、金融乃至个人生活各方面 的影响将是深刻的。

然而,从基于纸面转化为基于数字电子媒体的形式后,在生成、传输、保存、验证和鉴 定等多方面出现了新的技术需求、问题和困难。无疑,其中最重要的是安全问题:怎样才能 确保原始信息不会被窃取、窃听?不能被伪造、篡改?怎样才能确认信息发送者的真实性? 怎样才能保证信息发送者无法抵赖?

必须注意,那些机密的、甚至价值连城的重要信息常常需要在公开的网络上传送。"公 开"和"机密"虽有其水火不相容的一面,在需要的场合,它们还是可以协调共存,相互补充的 。"公开密钥密码系统"(public-key cryptosystem,或称"公开密钥密码体制")的巧妙方法 比较成功地解决了上述问题,并已在业界得到了广泛的应用。

密码学
公开密钥密码体制是现代密码学的最重要的发明和进展。说起密码学(cryptography ,或称密码术),在大家的印象中,主题应该是保护信息传递的机密性。确实,保护敏感的通 讯一直是密码学多年来的重点。但是,这仅仅是当今密码学的主题的一个方面,对信息发送 人的身份的验证,正是密码学主题的另一方面。公开密钥密码体制为这两方面的问题都给 出了出色的答案,并正在继续产生许多新的思想和方案。

与"公开密钥密码体制"相对应的是"传统密码体制",又称"对称密钥密码体制",其中用 于加密的密钥与用于解密的密钥完全一样,如图1所示。

图1 对称密钥密码体制

在对称密钥密码体制中,加密运算与解密运算使用同样的密钥。通常,使用的加密算法 比较简便高效,密钥简短,破译极其困难。但是,在公开的计算机网络上安全地传送和保管 密钥是一个严峻的问题。1976年,Diffie和Hellman为解决密钥管理问题,在他们的奠基性 的工作"密码学的新方向"一文中,提出一种密钥交换协议,允许在不安全的媒体上通讯双方 交换信息,安全地达成一致的密钥。在此新思想的基础上,很快出现了"不对称密钥密码体 制",即"公开密钥密码体制",其中加密密钥不同于解密密钥,加密密钥公之于众,谁都可以 用,解密密钥只有解密人自己知道,分别称为"公开密钥"(public-key)和"秘密密钥"(priv ate-key),如图2所示。

图2 公开密钥密码体制

模算术
要了解公开密钥密码体制的基本原理,有必要简略地介绍一些初等数论的知识。先以 7日一循环的星期为例,我们有0,1,2,3,4,5,6这七个数,0代表星期日,或"0天",1代表星期 一,或"1天",依次类推。在这个"数系统"中,很容易得到加法表。如图3所示。

图3 模7加法表(mod 7)

这种加法就是所谓"模"计算,7是"模"值,可以写出:

5 4=2 mod 7(星期五加四天是星期二)

2 3=5 mod 7(星期二加三天是星期五)

3 4=0 mod 7(星期三加四天是星期日)等等。由于乘法是连加,乘幂是连乘,也就不难 写出模7乘法表和乘幂表。如图4,图5所示。这些特殊的运算,尤其是乘幂运算,再联系到" 星期几"已无多大意义。然而,在一些公开密钥密码系统中,同余乘幂运算有着重要的地位 ,不过"模"值远远超过7,是很大的数,往往是几百位的十进制数(或上千位的二进制数)。

图4 模7乘法表(mod 7)

图5 模7乘幂表(mod 7)

仔细观察一下图5中的模7乘幂表,可见对a=3而言,31、32、33、34、35、36正好填满 了1、2、3、4、5、6六个非零值,对a=5也有此性质,而对a=1、2、4、6则不然。我们称具 有这种性质的值为"生成元"。大家知道,乘幂运算的逆运算是对数运算,现在,图5中同余式 乘幂的逆运算结果如图6所示,有确切意义的仅有a=3和a=5两个"生成元"值。这种对数被称 为"离散对数",也可用log表示,如图6所示。离散对数的概念在公开密钥密码系统中,也有 着重要的地位。

图6 离散对数表(mod 7)

RSA公开密钥密码系统
RSA公开密钥密码系统是由R.Rivest、A.Shamir和L.Adleman于1977年提出的。RSA的 取名就是来自于这三位发明者的姓的第一个字母,后来,他们在1982年创办了以RSA命名的 公司RSA Data Security Inc.和RSA实验室,该公司和实验室在公开密钥密码系统的研究和 商业应用推广方面具有举足轻重的地位。

现在,用一个简单的例子来说明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难以找出它的两个巨大的质数因子。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有