公钥密码学进展

公钥密码学进展伍前红张焕国武汉大学关键词：密码交换公钥加密密钥交换许多密码系统都要求用户之间有一个秘密信道，密钥交换的目的就是要建立一个这样的信道。密钥交换协议是公钥密码系统中最基本、最核心的协议，也是公钥密码学的基础之一。经典的密钥交换协议密钥交换协议的目的是使两方或多方在一个公开网络中协商出一个公共密钥。经典的密钥协商协议有迪菲-赫尔曼（Diffie-Hellman（DH））协议[1]、布尔梅斯特-德梅特（Burmester-Desmedt（BD））协议[2]、尤克斯（Joux）协议和博内-席维伯格（Boneh-Silverberg（BS））协议。这些巧妙的协议都是为静态群设计的，它们在被动攻击下是安全的。但这种安全性只是直觉上的，除了2003年在假设迪菲-赫尔曼协议安全的条件下，布尔梅斯特-德梅特协议完成过安全性证明[3]外，其余协议的安全性都没有证明，而是直接作为密码学中的标准假设。基本的迪菲-赫尔曼协议是一个单轮两方协议。如果在每次会话中固定一方而让另一方动态改变，从迪菲-赫尔曼协议就可以得到一种公钥加密方案，即著名的盖莫尔（ElGamal）密码体制[4]。布尔梅斯特-德梅特协议是一个两轮n方协议，作为目前效率最高的群密钥交换（GroupKeyExchange，GKE）协议，其轮效率不受n的限制。尤克斯协议是一个类似于DH协议的单轮三方协议，如果固定三方中的两方，从尤克斯协议就可以得到一个微型的广播加密方案，除了发送者，只有被固定下来的两方可以解密消息。尤克斯协议只适用于三方密钥交换，到目前为止，是否能将其扩展到三方以上而不增加额外的轮数仍然是一个公开问题。博内-席维伯格协议是一个单轮n+1方协议，它基于多线性对，但多线性对的构造本身也是一个公开问题。如果将n个用户公开的消息作为他们的公钥，则该协议蕴含着一个n个用户的广播加密方案。遗憾的是，多线性继迪菲（Diffie）和赫尔曼（Hellman）的开创性工作之后，密码学的研究从密室里走向了公开。经过数十年的发展，公钥密码学已经成为现代密码学的最主要内容之一，其本身也得到极大的丰富，并在实践中保护着成千上万用户的敏感数据和隐私。本文综述了公钥密码学的主要分支，包括密钥协商、公钥加密、数字签名以及可证明安全理论的基本模型，并回顾了这些领域的历史发展和现状，指出这些领域中的一些公开的重要问题，从而帮助有兴趣的读者进行深入研究。此外，还讨论了一些密码学界在可证明安全理论方面的很有启发意义的争议。wk_ad_begin({pid:21});wk_ad_after(21,function(){$('.ad-hidden').hide();},function(){$('.ad-hidden').show();});21对构造不出来，而且与尤克斯协议类似，即使假设存在多线性对，博内-席维伯格协议最多也只适用于ｎ+1方，将其扩展到超过ｎ+1方而不增加额外的轮数似乎很难。因此，构造单轮的ｎ方密钥交换协议仍然是一个长期的公开问题。认证密钥交换协议除了在被动攻击（窃听）下安全的基本密钥交换协议外，许多工作致力于研究如何对抗主动攻击者。这个目标基本上可以使用认证方法来实现，另外还有一些工作致力于研究如何提高密钥交换协议在实际应用中的效率。最早提出密钥协商安全性概念的是贝拉尔（Bellare）和罗加威（Rogaway）[5]。文献[5]的主要贡献是使用了不可区分性来定义协商出来的密钥的安全性。粗略地说，在该定义中，如果在允许的攻击行为下，攻击者仍然不能区分一个密钥是由真实协议生成的，还是来自密钥空间的一个独立随机值，那么就称该密钥交换协议是安全的。后来对这个模型也有一些扩展，最著名的是布莱克-威尔逊（Blake-Wilson）等所作的研究。对两方密钥交换协议的研究已经比较成熟且被广泛接受，如文献[1]、[5]和[6]等。对如何在n方中安全建立一个秘密信道的群密钥交换协议的研究还不多，还有一些工作致力于研究如何将两方的迪菲-赫尔曼协议推广到多方的环境[2]中去。这些协议都只考虑了被动攻击下的安全性。在抗主动攻击的认证群密钥交换协议方面具有开创性意义的工作包括文献[7~9]所列的内容，它们最早给出了群密钥交换协议安全性在标准模型下的形式化证明。随后，文献[10~11]分别提出了在随机预言机模型下可证明安全的常数轮的认证群密钥交换协议。文献[7]中的安全性模型和可证明安全性协议是用于静态认证群密钥交换的，其安全模型源于贝拉尔等的两方密钥交换的安全模型[5~6]。他们的方案需要O(n)轮。在文献[10~11]中分别提出了具有常数轮的静态认证群密钥交换协议。博伊德（Boyd）和涅托（Nieto）在随机预言机模型下证明了协议[10]的安全性。卡茨（Katz）和扬（Yung）提出了基于两轮协议[2]的认证静态群密钥交换协议[3]。最近，基于标准秘密共享技术，布列松（Bresson）和卡塔拉诺（Catalano）又提出了在标准模型下只需要两轮的可证明安全的认证静态群密钥交换协议。对于动态群，布列松等改进了文献[9]中的协议，提出了动态群密钥交换协议[8]。但布列松等的协议不是常数轮，原因是每一个成员在中间密钥协商材料中嵌入他们的秘密，并将用这个秘密生成的最后结果提交给下一个群成员，这就使得在启动/加入算法中的轮数和群成员数目成线性关系。布列松等提出了一个两轮的可证明安全的认证群密钥分发协议，主要解决群成员的移动设备计算效率瓶颈，可用于功率受限的设备和无线环境。金（Kim）等人提出了一个不使用任何信任树的两轮动态认证协议，这是目前适用于动态群的最有效的群密钥交换方案。基于口令的密钥交换协议与熵很高的随机密钥不同，口令的熵通常很低，容易记忆，不必使用可信硬件产生或存储随机密钥。当然，从另一方面讲，低熵的口令容易遭到穷举搜索。如何在两方或多方中使用提前共享的由低熵口令组成的秘密信息来认证生成高质量的密钥，这是基于口令的密钥交换要解决的主要问题。在这种环境中，攻击者可以穷举整个口令空间，借助在线字典进行攻击，通过选择正确的口令，冒充一方使用每一个可能的共享秘密。因为这样的攻击是不可避免的，所以这个领域的工作就集中在如何防止离线字典攻击，保证在线穷举攻击是最有效的攻击，也就是说，为了验证每一个猜测的口专题报道28机预言机模型下实现了一种具体的方案，其签名长度是一个常数。在PKC2007会议上，藤崎和铃木（Suzuki）提出可追踪环签名概念，实现文献[22]同样的安全目标，但他们的实现是线性复杂度的。盲签名盲签名允许签名请求者获得一个秘密消息的签名，签名者不能知道所签署的消息以及最终的签名，其主要用于电子现金和匿名认证。在物理世界，盲签名可以用下面简单的方法实现。请求者在待签署的秘密文件上附上一张复写纸装在一个信封里，将信封密封后让签名者在信封上指定的位置签名，请求者将信封打开，拿掉复写纸就得到了想要的秘密文件签名。密码学意义上的盲签名是这种物理方式签名的一个模拟。当然，这种简单的物理签名方式在密码学意义上是不安全的，恶意的请求者可能在信封里装了不止一份秘密文件，从而获得多个秘密文件的签名。在密码学意义上的盲签名需要防止这种攻击，这种安全性要求称为(k+1)-不可伪造性，即请求者与签名者k次交互后，至多只能获得k个签名。盲签名的概念是常最先引入的，他最初实现的是基于RSA的盲签名，但没有安全证明。直到2003年，常最初的方案才在随机预言机模型下得到证明，还使用了一个非标准的计算假设。而盲签名的安全性定义直到2000年才由波伊切沃和斯特恩[16]正式给出。最初的盲签名概念有一个显著的缺点。由于签名者完全不知道签署的内容，恶意的签名请求者可以欺骗签名者。例如，当签名请求者向银行申请1美元的电子硬币时，他可能让银行签署的消息却声称该银行欠他100万美元。为了防止这类攻击，对每一种面值的电子货币，银行必须使用不同的公钥，并有其它机构证实该公钥只用于签署该面值的货币，而不管被签署的消息的实际语意。这无疑增加了系统的负担，因为可能有很多种面值的货币，而且嵌入的公开信息可能还有很多，比如货币的发行时间、有效期和适用范围等，这些信息的组合可以产生指数级的复杂度，上述简单的抗攻击方法显得很无力。为此阿贝（Abe）等提出了部分盲签名的概念，允许签名者在盲签名中嵌入一些公开信息。显然，盲签名是部分盲签名的一种特殊情况，即嵌入的公开信息是一个空串的情形。在文献中，给出了部分盲签名的形式化定义，并提出了一种在随机预言机模型下可证明安全的实现。吴等在文献[29]提出的盲签名和部分盲签名效率更高，实现同样的安全级别可以节省大约25%的带宽。绝大多数的（部分）盲签名都是在随机预言机模型下考虑的安全性。波伊切沃和斯特恩[16]第一个证明了安全的盲签名，不过该证明中的盲签名最多只能签发O(logλ)次，其中λ是系统的安全参数。比如对于盲施努尔签名，最多只能签发几次。显然这样的限制使得盲签名在电子现金中的应用很不理想。目前，这个限制放松到了O(λ)次，阿贝等在文献提高了轮效率，并允许同时请求签名。贝拉尔等和博驰路（Boldyreva）提出了两轮的盲签名方案，在同时请求盲签名的情况下也是安全的。在标准模型下可证明安全的盲签名很少。早期曾有文献指出，盲签名可以用通用两方安全计算技术构造，然而从实用的角度来看这样的构造是很不现实的。由于朱叶斯（Juels）、卢比（Luby）和奥斯特罗夫斯基（Ostrovsky）发现，简单地按这种方法构造盲签名并不安全，因此研究出了改进方法，以便得到安全的盲签名。尽管这些文章中都声称在同时申请盲签名的情形下方案仍然是安全的，但都没有提供安全证明的技术细节。卡梅尼西（Camenisch）等提出了第一个在标准模型下安全的高效盲签名方案，但其只允许顺序请求签名。林德尔已经证明在基于仿真的安全定义中不可能获得在同时请求签名下仍然安全的盲29签名。为了绕开这个限制，近期的研究工作集中在假定一个公共参考串的情况下证明同时请求签名的盲签名安全性。注意到林德尔限制并不适用于基于博弈的安全性定义，哈赞（Hazay）等提出了第一个在并行签名下安全的盲签名，该签名不需要随机预言机的帮助。奥（Au）和吴等提出了一种可以签署基群中的元素而不使用哈希函数的高效签名方案[25]，该签名可以方便地转化为在标准模型下的两轮盲签名。可证明安全性在贝拉尔精彩的综述文章中，他认为现代密码学的发展可以分为2个阶段：一是设计和研究基本的单向函数阶段；二是设计和研究实现特定安全目标的安全方法阶段。前者的主要工作是构造基本的密码学原子原型，是一门艺术，因为直觉和经验在其中扮演着最重要的角色。后者的主要工作是对密码协议的设计与分析，可以视之为一门科学，因为安全性的数学方法证明在其中扮演了最重要的角色。由此可见，可证明安全在现代密码学中的重要地位。然而，密码学中的可证明安全理论发展充满了曲折、误解和争议，科布利茨（Koblitz）和梅内塞斯（Menezes）在文献[26]和其他文献中对此进行了很有启发意义的评论。下面将简述可证明安全中的基本数学模型及对它们的争议。随机预言机模型与标准模型许多密码协议的设计都需要用到哈希函数，因此在进行安全证明时，如何对待哈希函数成为密码学中的一个重要课题。在随机预言机模型里，哈希函数被视为一个随机函数，它的输出被认为是随机的，攻击者必须询问它才能知道输出，但对相同的询问，它的输出是一致的。绝大多数的密码学方案是在随机预言机模型下证明它们的安全性，其中最经典的结果包括文献[16]等等对基于RSA的签名、加密以及基于离散对数的签名的安全性证明。而在标准模型里，哈希函数被视为一个满足单向性和抗碰撞性的确定性函数。当然，在标准模型下的密码学方案还可能根本就不需要哈希函数。已有少量的实用密码学方案在标准模型下证明了安全性，其中最经典包括文献[17]等等基于标准的DDH假设对克拉梅-舒普加密方案和基于标准的CDH假设对沃特斯签名[17]的安全性证明。然而，多年来有不少密码学家对随机预言机模型表示了怀疑。例如，卡内蒂、戈德瑞克和哈列维（Halev