长袖善舞多面手——公钥密码

撰文 | 康老师

通过上两期聊过对称密码之后，本期进入公钥密码领域，由于这个领域实在太过丰富与辽阔，本期尽量从使用者的角度、从共性特征的角度阐述公钥密码而不陷入到具体的技术细节中去。公钥密码体制的产生是密码学发展中意义最重大的革命。有了公钥密码，密码科技服务的行业领域和用户范围才得以大幅扩张，密码应用才迎来了大发展，密码基础设施才为大众所认识和接受。可以说，公钥密码是现代密码家族中发明最晚、内涵最丰富、应用最为广泛的密码。

公钥密码总体特点

公钥密码发展的驱动力

公钥密码的起源和标志就是1976年Diffie和Hellman共同发表的“密码学的新方向”一文，在密码领域，公钥密码为什么能以如此快的速度获得发展是个有趣又复杂的问题。公钥密码从技术原理上绝不是对称密码发展的自然结果，结合当时的技术发展状况，只能说是新的需求促进了公钥密码的产生。公钥密码发明的初衷是为解决对称密码体制中难于解决的两个问题：如何安全高效的进行密钥分配，以及如何实现保证数据来源真实性的数字签名。而自从基于公钥密码的从D-H密钥协商协议为开端的一系列研究成果被发表以后，人们发现它们非常适用于公共网络中的保密通信需求，人人都可以很方便的使用公钥密码进行加密，这是公钥密码最大的发展驱动力。再加上上世纪七十年代计算理论的发展和计算机技术的发展为它提供了理论基础和工程技术实现基础。这才迎来了密码发展史上影响最大的一次大发展。

密钥特点

公钥密码的每个使用者都具有一对不同的、总是配合使用的密钥：一个密钥是公开的，称为公开密钥（Public Key），简称公钥，用于加密和验证；另一个密钥是保密的，称为秘密密钥（Secret Key）或私有密钥（Private Key），简称私钥，用于解密和签名。公钥可以公开传播而不危及密码体制的安全性，这样做的最大好处就是不需要通过安全信道传送公钥。

算法特点

公钥密码依其“不对称的”密钥特点而决定了其加密算法和解密算法（也包括签名/验签算法）也是各自独立、“不对称”的，而不像对称密码那样是互为逆过程。从算法应用者角度会发现各算法函数的输入输出参数完全不像对称密码那样“规范齐整”。
                                   

算法使用特点

所有公钥密码的运算速度都较慢，比对称密码的速度差距一到两个数量级，因此它只适合于少量数据的加密而不像对称密码可以用于大数据量的加密，比如用公钥密码加密传送分组密码的密钥等。

阐释公钥密码安全的理论前提——单向函数与计算复杂度

公钥密码体制安全性的理论基础都是基于特定的称为陷门单向函数（Trapdoor One-way Function）的数学难解问题。设f是一个函数，t是与f有关的一个参数。对任意给定的x，计算y使得y = f(x) 是容易的。如果当不知道参数t时，计算f的逆函数是难解的，但当知道参数t时，计算f的逆函数是容易的，则称f是一个陷门单向函数。公钥密码的加密变换就是一个陷门单向函数。知道陷门的人可以容易地进行解密变换，而不知道陷门的人则无法有效地进行解密变换。也就是它确保了从公钥即加密密钥计算解密密钥即私钥是难解的。设计公钥密码的任务就是要找出合适的陷门单向函数。大多数研究者认为陷门单向函数是存在的，这是公钥密码安全性得以被普遍认可的一个基本假设。但迄今为止，没有任何函数在数学上被严格证明是单向函数，也就是没有从理论证明从公钥能计算对应私钥在计算上是不可行的。这也就是有些“保守”的研究者还是对公钥密码不太放心的原因。寻找到了合适的陷门单向函数后，如果我们没法证明它的理论完备，那就换个思路去评估它是难解的——这就涉及到如何定量的描述一个计算问题是“容易的”还是“困难的”，称为计算复杂度理论。迄今为止所有公钥加密方案都是通过计算复杂度评估的，计算复杂度理论使用解决这个问题的算法的计算时间（时间复杂度，是最重要的评估指标）和存储空间（空间复杂度）来定量评估描述。人们把“最难解”的那类问题归类为完全NP问题，量子计算机之所以对破译公钥密码有价值，也就在于它能够降低这类最难解问题的难度，由于公钥密码的计算复杂度问题依具体算法的不同而各不相同，在此不具体展开。

应用公钥密码的实体前提——公钥密码基础设施

公钥密码的应用需要可信第三方的介入和支撑，这个可信第三方通常形态就是公钥密码基础设施。它是一个集中了密码管理和信任管理、证书管理等功能的中心型的基础设施——有时也称为证书认证中心或PKI/CA。它是对实体身份信息进行管理、并可信的颁发身份证书的独立可信第三方，它的价值在于使原本不信任的实体之间可以基于它来互相验证对方身份的正确性、真实性和有效性。公钥密码基础设施建立的信任关系的数字形式介质是数字证书，通过数字证书把用户公钥与用户身份信息相绑定，这样，只要网络用户都信任该基础设施，在网络中素不相识的人，相互之间就可以通过验证证书来确定身份了。公钥密码基础设施主要由如下图所示CA、RA和证书查询服务子系统组成。那公钥密码基础设施又是如何可信分发证书并确保证书信息的正确性、真实性和有效性呢？公钥密码基础设施首先是由权威部门或经过密码和安全认证的商业部门建立和运营的，有管理上的权威性；其次，从技术角度，公钥密码基础设施遵循公钥密码的游戏规则，它本身有标识其身份的CA证书，自身也是通过使用公钥密码来达到安全可信分发证书的目的。具体的实现流程就不在此赘述了。

使用公钥密码实现加密的基本过程

以如下图所示的各用户A、C…N都要给用户B各自发送只有B能够解密的信息为例，在公钥密码基础设施的支持下，各用户都拥有B的公钥，并使用它进行消息加密，然后发送给B端，此时B端再用自己的私有密钥进行消息解密（若B向A反向发送消息，则B用A的公钥加密，不赘述）。这样，就实现了多个用户加密的消息只能由一个用户解读，设在系统用户数为n的通信网络中，公钥管理系统只需要安全分发2n个密钥（其中需保密分发的的密钥是n个）就实现了双向的自由安全通信目的。

这个典型场景也最能彰显公钥密码服务大量用户所具有的独特优势。如果使用对称密码达到同样目的，每个用户要想和其他n-1个用户进行安全通信，必须使用n−1个密钥（否则就必然有其他用户和他共享密钥，意味着其他用户就同样能查看密文，无法确保点到点信息的保密），对称密钥管理系统为此所需分发的总密钥量将达到n(n-1)/2，而且必须全部是保密分发的。随着用户数n的增大，分发密钥的代价将越来越大。

但对于上图场景读者会产生一个疑问，由于各用户在加密操作都是使用的同一密钥、同一算法，假若用户C仿冒用户A发送信息，用户B该如何区分该信息到底是来自A还是C呢？这就要用到公钥密码送给我们的另一套利器——签名验签。

使用公钥密码实现签名的基本过程

数字签名（Digital Signature）是对当事者实际签名的一个绝妙的数字化比拟。日常生活中当事者的手签、印章、手印等形式的签名，都能证明当事者的身份和数据真实性，起到确认、核准、生效和负责任等多种作用。数字签名作为一段数据形式的电子对应物，同样能对数据信息的真实性进行确认，它在身份认证、数据完整性、不可否认性、匿名性等方面有着广泛的应用。数字签名由两部分算法组成，即签名算法和验证算法。签名算法作用是产生数字签名，验证算法是验证一个数字签名是否由声称的当事者生成，验证算法的输出是验证正确——签名是来自声称者，或者是验证错误——签名不是来自声称者或者输入的签名值有误。如下图所示，用户A使用自己的私钥对待签名数据进行签名操作得到签名值后，就可以在公开信道发送给其它用户。只要预先分发给各用户的A所属公钥是正确无误的（这点由公钥密码基础设施来保证），则各用户B、C…N只要使用用户A的公钥和收到的信息（信息是密文或明文均可）以及签名值，就可以各自使用验签算法对签名进行认证，知道信息是否是由所声称的A发送而来的。

既然公钥密码作为网络空间可信链基石的作用如此重要，设计又非常困难，当前密码领域的最新发展也很大程度体现在公钥密码的各种新发展上。从2016年开始美国国家标准技术研究院（NIST）面向全球征集具备抗量子计算机攻击能力的新一代公钥加密算法。经过历时五年、三轮次征集，全球有七个算法入选（其中没有我国参与的算法入选），密码界对此的高度关注和审慎可见一斑，世界已经进入了量子计算攻击与现代公钥密码防护间展开的新博弈阶段。

康老师 简介

深耕信息安全领域二十余年，从事安全增强系统、密码应用系统及通用软件系统开发、信息安全理论研究、标准规范编研及开发团队管理。参与多项国家863、973、核高基专项等重大科研项目，作为主要完成人编研完成国家/军用标准多项，发表学术论文二十余篇。