公开密钥密码系统
引言
随着计算机和电子通讯技术,包括因特网的迅猛发展,金融电子化的步伐大大加快,这 种电子化、数字化的趋势已经波及社会生活的几乎所有的方面。人与人之间的许多交往活 动,包括商业贸易、金融财务和其他经济活动中,不少已以数字化信息的方式在网上流动着 。"数字化经济"(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难以找出它的两个巨大的质数因子。
对上面例子中的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),也无 法猜出或算出他的秘密密钥来冒充他的"签名"。
RSA的安全性
RSA公开密钥密码体制的安全性取决于从公开密钥(n,e)计算出秘密密钥(n,d)的困难 程度,而后者则等同于从n找出它的两个质因数p和q。因此,寻求有效的因数分解的算法就 是寻求一把锐利的"矛",来击穿RSA公开密钥密码系统这个"盾"。数学家和密码学家们一直 在刻苦努力寻求更锐利的"矛"和更坚固的"盾",而且不仅限于RSA一种方案。在此,我们只 考虑RSA的情况。
最简单的考虑是加厚我们的"盾",即n取更大的值,RSA实验室认为,512比特的n已不够 安全,在1997年或1998年后应停止使用。他们建议,现在的个人应用需要用768比特的n,公 司要用1024比特的n,极其重要的场合应该用2048比特的n。RSA实验室还认为,768比特的n 可望到2004年仍保持安全。
计算机硬件的迅速发展势头是不可阻挡的,这一因素对RSA的安全性是很有利的,因为 硬件的发展给"盾"带来的好处要多于"矛"。硬件计算能力的增强使我们可以给n加大几十 个比特,但不致放慢加密解密的计算,但同样水平的硬件计算能力的增强给予因数分解计算 的帮助却不那么大。
计算机软件和算法的发展对RSA的安全性的影响,情况比较复杂。至今,不管用怎样的 硬件和软件,大数的因数分解确实是极端困难的任务。
1977年,《科学的美国人》杂志悬赏征求分解一个129位十进数(426比特),直至1994年 3月,才由Atkins等人在因特网上动用了1600台计算机,前后花了八个月的时间,才找出了答 案。然而,这种"困难性"在理论上至今未能严格证明,但又无法否定。对于许多密码研究分 析人员和数学家而言,因数分解问题的"困难性"仍是一种信念,一种有一定根据的合理的信 念。
总之,随着硬件资源的迅速发展和因数分解算法的不断改进,为保证RSA公开密钥密码 体制的安全性,最实际的做法是不断增加模n的位数。
RSA的实用考虑
不对称密钥密码体制(即公开密钥密码体制)与对称密钥密码体制相比较,确实有其不 可取代的优点,但它的运算量远大于后者,超过几百倍、几千倍甚至上万倍,复杂得多。
在网络上全都用公开密钥密码体制来传送机密信息,是没有必要的,也是不现实的。在 计算机系统中使用对称密钥密码体制已有多年,既有比较简便可靠的,久经考验的方法,如 以DES(数据加密标准)为代表的分块加密算法(及其扩充DESX和Triple DES);也有一些新的 方法发表,如由RSA公司的Rivest研制的专有算法RC2、RC4、RC5等,其中RC2和RC5是分块加 密算法,RC4是数据流加密算法。
在传送机密信息的网络用户双方,如果使用某个对称密钥密码体制(例如DES),同时使 用RSA不对称密钥密码体制来传送DES的密钥,就可以综合发挥两种密码体制的优点,即DES 高速简便性和RSA密钥管理的方便和安全性。
关于RSA数字签名,前面的示意性介绍是不实用的,因为李先生的"签名"未与任何应签 署的报文(message)相联系,留下了篡改、冒充或抵赖的可能性。为了把那些千差万别报文 与数字签名不可分割地结合在一起,要设法从报文中提取一种确定格式的、符号性的摘要 ,称为"报文摘要"(message digest),更形象的说法是一种"数字指纹"(digital fingerpr int),然后对它"签名"并发送。
如果李先生要发送一个需签署的报文给张小姐,通讯安全软件会调用某种报文摘要算 法处理报文内容,得出一个数字指纹,然后用李先生自己的秘密密钥将它加密,这才是真正 的数字签名,将它同报文一并发送给张小姐。
张小姐收到报文和数字签名后,她用李先生的公开密钥将数字签名解密,恢复出数字指 纹。接着用李先生所用的一样的报文摘要算法处理报文内容,将算出的数字指文与收到的 经解密的数字指纹比较,如果两者完全相同,则李先生的数字签名被张小姐验证成功,她可 以相信报文是真实的,确实发自李先生。否则,报文可能来自别处,或者被篡改过,她有理由 拒绝该报文。
用上述方法,别人也不难读取报文并验证数字签名,这在实用中是不妥当的。为使报文 本身的内容不泄露给外人,李先生只要再添一个操作步骤:用张小姐的公开密钥先将待发的 报文加密,当然,张小姐在验证数字签名无误后,要用她自己的秘密密钥解密,才能得到原始 的机密信息。
即使这样做,别人还是可以插手验证数字签名,在实用中或许也要求改进,排除掉这种 可能性。其实,网上安全通讯实用中还有着多种不同的要求,研究人员已经提出了多种不同 的数字签名方案,以满足各种需求。其他不同的加密方案和数字签名方案,乃至不同的公开 密钥密码体制的研究,也正在紧锣密鼓地进行之中。
数字指纹
在数字签名中有重要作用的"报文摘要"算法,即生成报文"数字指纹"的方法,近年来倍 受关注,构成了现代密码学的一个重要侧面。
其实,报文摘要算法就是一类特殊的散列函数(hash函数,在计算机数据信息的检索过 程中有广泛应用),这些特殊要求是:
·接受的输入报文数据没有长度限制;
·对任何输入报文数据生成固定长度的摘要("数字指纹")输出;
·由报文能方便地算出摘要;
·难以对指定的摘要生成一个报文,由该报文可以得出指定的摘要;
·难以生成两个不同的报文具有相同的摘要。
显然,上面前三点是适用性的要求,保证对长短不一的报文易于生成同样大小的"数字 指纹";后三点则是安全性的要求,是建立在某种单向函数的基础之上的。
从八十年代末到九十年代,Rivest开发了好几种RSA公司专有的报文摘要算法,包括MD 、MD2、MD5等。以1991年发表的MD5为例,是克服了MD4算法的安全性缺陷的产物,"数字指 纹"的大小是128比特。1994年发表的一个研究报告称,可以花费一千万美元去制造一台专 门的机器,针对MD5搜索两个不同的报文具有相同的摘要,即"碰撞"现象,平均用24天才能找 到一个碰撞。至今,MD5被认为仍是一个安全的报文摘要算法。
专用数字签名方案
前面介绍的RSA数字签名方案的例子属于所谓"常规数字签名方案",这类方案具有如下 特点:
·签名者知道他签署的报文的内容;
·任何人只要知道签名者的公开密钥,就可以在任何时间验证签名的真实性,不需要签 名者的"同意"信号或来自其他方面的信号;
·具有基于某种单向函数运算的安全性。
但在电子货币、电子商业和其他的网络安全通讯的实用中,可能 要放宽或加强上列特 征中的一个或几个,或添上其他安全性特征,以适应各种不同的需求。
例如,在因特网上购买商品或服务,要向供应商(由银行)付款,顾客发出包含有他的银 行帐号或别的重要信息的付款报文,由收款者作出(电子)签名才能生效,但帐号之类的信息 又不宜泄露给签名者,以保证安全。这种情况,就要使用"专用数字签名方案"中的一种:"盲 签名方案"(Blind Signature Scheme)。
盲签名方案的工作原理是这样的:张小姐有报文m要求李先生签署,但不能让李先生知 道关于报文m的任何一点信息。设(n,e)是李先生的公开密钥,(n,d)是他的秘密密钥。张小 姐用她的安全通讯软件生成一个与n互质的随机数r,将
m′=r[RUe]m mod n发送给李先生,这样,李先生收到的是被r所"遮蔽"的m值,即m′,他不可 能从m′中获取有关m的信息。接着,李先生发回签名值
s′=(m′)d mod n=(r[RUe]m)d mod n=rmd mod n
张小姐对收到的s′计算
s′r-1 mod n=md mod n
就得到了真正的来自李先生的对m的签名
s=m[RUd] mod n
可见,运用盲签名方案,张小姐无法代替或冒充李先生的签名,而李先生则不知道他自 己所签署的报文的真实内容。
除了盲签名方案之外,我们简单介绍另外几种专用数字签名方案:
·"指定批准人签名方案"(Designated Confirmer Signature Scheme)
某个指定的人员可以自行验证签名的真实性,其他任何人除非得到该指定人员或签名 者的帮助,不能验证签名。
·"小组签名方案"(Group Signature Scheme)
一个小组的任一成员可以签署文件,验证者可以确认签名来自该小组,但不知道是小组 的哪一名成员签署了文件。
·"一次性签名方案"(One-time Signature Scheme)
仅能签署单个报文的签名方案。
·"不可抵赖签名方案"(Undeniable Signature Scheme)
在签名和验证的常规成分之外添上"抵赖协议"(Disavowal Protocol),则仅在得到签 名者的许可信息号后才能进行验证。
·带有"数字时间标记系统"(Digital Timestamping System)的签名方案
将不可篡改的时间信息纳入数字签名方案。
从列举的专用数字签名方案简介可以看到,为适应实用需求,数字签名方案是颇为丰富 多彩的。
Diffie-Hellman密钥一致协议
在本文的末尾,我们来回顾一下公开密钥密码体制的奠基人Diffie和Hellman所提出的 "指数密钥一致协议"(Exponential Key Agreement Protocol),该协议不要求别的安全性 先决条件,允许两名用户在公开媒体上交换信息以生成"一致"的,可以共享的密钥。
协议要求设定两个参数p和g,p是一个大质数,g是模p指数运算的生成元,p和g都是公开 的,系统中任何人都可用。
设想两名用户张小姐和李先生要得出一个共享的密钥,首先各自生成随机数,如果和张 小姐的随机数是a,她由a算出一个公开值。
k[RDa]=g[RUa] mod p发送给李先生。同样,如果李先生的随机数是b,他由b算出一个公开值
k[RDb=g[RUb] mod p发送给张小姐。然后他们收到公开值kb和ka分别用自己的随机数a和b作 模p指数运算,可得
k[RDab]=(k[RDb])[RUa] mod p=(g[RUb])[RUa] mod p=g[RUba] mod p
K[RDba]=(k[RDa])[RUb] mod p=(g[RUa])[RUb] mod p=g[RUab] mod p
两者是相等的,即
k=k[RDab]=k[RDba]
这样,张小姐和李先生经过在公开媒体上交换信息,生成了共享密钥k。
由于p、g、ka和kb都是公开的值,任何人只要能算出模p离散对数loggk[RDa]和loggk[RDb]就得 到了秘密值a或b。因此,Diffie-Hellman密钥一致协议的安全性取决于离散对数计算的困 难性,在p是巨大质数的场合,模p指数运算确实是一个单向函数。
研究表明,在p与n的比特数相同时,模p离散对数计算与n的因数分解计算的困难程度相 当;1991年有实验证明,计算要比因数分解计算略困难一些,即对100(十进)位的p值的离散 对数计算所付出的努力与对110位n值因数分解计算差不多。
模p离散对数方法在前文提及的一些专用数字签名方案中有着实际的应用;同时,为寻 求新的、更好的公开密钥密码体制,基于其他数学理论的离散对数方法是很吸引人的,所谓 "椭圆曲线公开密钥密码体制"就是其中的一种,是当前国际密码学界的一个热点。 (数据处理者注：A[RUx]----表示A的右上脚注为x, A[RDx]----表示A的右下脚注为x
--------------------------------------------------------------------------------
