公钥密码体制基本原理介绍及研究方向探索

◆郭东栋 杜文博 周浩

（北京奔驰汽车有限公司 北京 100176）

随着通信、电子和计算机技术的进步，密码学得到前所未有的系统发展，1976 年Whitfield Diffie 和Martin E.Hellman 发表了奠定密码学理论体系的论文《New Directions in Cryptography》，这为解决密码学面临的两大难题（可靠密钥的传输通道问题和如何提供与手写签名等效的认证体系）提供了开拓性的理论基础。此篇论文提出的公钥密码算法、公钥分配算法、单项认证算法等，为解决有效认证问题提供了全新的思路；同时，此篇论文介绍的公钥加密和数字签名新构想为今天公共密码交换系统打下了坚实的基础，被广泛应用于当前网络通信和计算机安全。该论文的引用目前已经超过16，000 次。两位作者Whitfield Diffie 和Martin E.Hellman 因密码学研究，获得2015 年度的图灵奖。下面简要地介绍一下这篇论文的主要内容。

1 常规密码体系

密码学是研究解决保密和认证这两类安全问题的“数学”方法的学科，本质上与数学学科存在千丝万缕的关系。常规密码体系主要包含密钥、加密、解密等基本概念，现代密码学主要基于数学理论和计算机科学实践。密码算法是围绕计算难度假设进行设计的，因此这种算法在实践中很难被任何对手破坏。理论上有可能破坏这样的系统，但是用任何已知的实际手段来破坏是不可行的。这些方案因此被称为计算安全。理论上的进步，例如整数因数分解算法的改进，以及更快的计算技术，要求这些解决方案必须不断调整。存在信息理论上安全的方案，即使使用无限制的计算能力也无法证明是可靠的，但是这些方案比最佳的理论上可破解但计算安全的机制在实践中更难使用。同时，根据Shannon 理论，无条件安全的算法是存在的，但因为其密钥过长而不符合实际应用，这也是在计算上开发安全算法的原因。

2 公钥密码学

公钥密码的两个主要组成部分是公钥密码和公钥分发算法。《New Directions in Cryptography》一文首次提出的设计方案充分体现了公钥密码的设计思想和实践，即密钥是由公钥和私钥组成，不再是机密内容。解决复杂问题的步骤通常称为算法，由明文生成密文的步骤是加密的步骤，称为“加密算法”，解密的步骤称为“解密算法”，解密算法统称为密码算法。密钥交换的功能是允许双方协商同一密钥，而无须事先共享信息。此密钥用于数据加密。公钥密码或非对称密码是一种使用密钥对的密码系统：可以广泛传播的公钥和私钥。这种密钥的产生取决于基于数学问题的密码算法以产生单向函数。有效的安全性只需要使私钥保持机密即可。公钥可以公开分发而不会损害安全性。在这样的系统中，任何人都可以使用接收者的公钥对消息进行加密，但是只能使用接收者的私钥对加密的消息进行解密。

公钥算法是现代密码系统，应用程序和协议中的基本安全成分，可确保电子通信和数据存储的机密性，真实性和不可否认性。它们支持各种Ⅰnternet 标准，例如传输层安全性（TLS），S/MⅠME，PGP 和GPG。一些公共密钥算法提供了密钥分发和保密性（例如，Diffie-Hellman 密钥交换），一些提供了数字签名（例如，数字签名算法），而另一些提供了两者（例如RSA）。

Diffie-Hellman 密钥交换在两方之间建立了一个共享的秘密，该秘密可用于秘密通信以通过公共网络交换数据。一个类比通过使用颜色而不是非常大的数字来说明公共密钥交换的概念：

该过程开始于让两方Alice 和Bob 商定一个不需要保密的任意起始颜色，但每次都应有所不同。在此示例中，颜色为黄色。每个人还选择自己保留的秘密颜色-在这种情况下，是红色和蓝绿色。该过程的关键部分是，Alice 和Bob 分别将自己的秘密颜色和彼此共享的颜色混合在一起，分别形成橙色棕褐色和浅蓝色的混合物，然后公开交换两种混合色。最后，这两种颜色都将他们从伙伴那里收到的颜色与自己的私有颜色混合在一起。结果是最终配色（在这种情况下为黄棕色），与伙伴的最终配色相同。

公钥加密是指在有限信息空间{M}上并基于算法{Ek}和{Dk}定义的可逆算法：

Ek：{M}->{M

Dk：{M}->{M

满足下列条件：

（1）对任给K∈{K}，Ek 是Dk 的互逆变

（2）对任意的K∈{K}和M∈{M}，用Ek 和Dk 进行加密和解密是容易计算

（3）对几乎所有的K∈{K}，从Ek 推出Dk 在计算上是不可行

（4）对任意的K∈{K}，从K 计算Ek 和Dk 是可行

在此，K 是用于生成Ek 和Dk 的随机数。第三个条件确保在不损害Dk 的安全性的情况下可以公开Ek，从而确保了公钥密码算法的安全性。矩阵求逆仅需n3 时间，密码分析时间与正常解密时间之比为n。尽管此事例不切实际，但对于解释公共密钥密码算法很有用。一种更实用的方法是使用机器语言的可理解性将加密算法编译为机器语言并发布，而解密算法是机密的。分析人员很难理解机器语言的整个操作过程，因此很难破解。当然，此算法必须足够复杂，以避免被输入和输出对破解。

公钥分配算法基于计算对数然后取模数的难度。令q 为质数，取有限域GF（q）中的任何q，计算Y=axmod q，其中a 是GF（q）上的固定基元，然后X=log aYmod q。不难发现，从X 计算Y 更容易，这需要大约2×log2q 乘法。但是，由于需要q1/2 运算，因此很难从Y 导出X。这样，对于每个用户，从[1，2，...，q-1]中随机选择一个q，计算出Yi=aXi mod q，并发布Yi，并对Xi 保密。然后，当用户i 和j 进行通信时，请使用Kij=aXiXjmod q 作为其公共密钥。该关键用户i 是通过j 发布的Yj 获得的，即Kij=Yj Ximod q=（aXj）Ximod q=aXiXjmod q。为了让第三方获得密钥，必须对其进行计算，而这在计算上是不可行的，以便实现在公共信道上分发私钥的效果。

3 单向认证

身份验证涉及验证个人身份文件，使用数字证书验证网站的真实性，通过碳日期确定工件的年龄或确保产品或文件不伪造。现有的认证体系只能保证不被第三方冒名顶替，但不能解决发送者和接收者之间的冲突，为此引入单向函数的概念，即对定义域中的任意x，f（x）是容易计算的，但对几乎所有的值域中的y，求满足y=f（x）的x在计算上是不可行的。例如已知多项式p（x）和x，求y=p（x）是容易的，但若已知y 求出x 是困难的。值得注意的是，这里的计算上不可逆与数学中的不可逆是完全不同的（数学上的不可逆可能是有多个原像）。

公钥密码算法可用来产生一个真正的单向认证体系。当用户Alice 要发信息M 给用户Bob 时，他用其保密的解密密钥解密M 并传给Bpb，Bob 收到时用Alice 公布的加密密钥“加密”此消息从而得到信息M。因为解密密钥是保密的，只有Alice 发送的消息才具有这样的性质，从而确认此信息来源于Alice，也就建立了一个单向认证体系。

Leslie Lamport 还提出了另一种单向信息认证方法，该方法通过在k 维二进制空间中将单向函数f 映射到其自身来实现。如果发送方发送了N 位信息m，则他必须生成2N 个随机的k 维二进制矢量x1，X1，x2，X2，...xn，Xn，并将其保密，然后将这些矢量置于y1 之类的f 下，Y1，Y2，Y2，...yn，Yn 发送给接收者。当发送信息m=（m1，m2，...，mN）时，当m1=0 发送x1，m1=1 发送X1，以此类推。接收器用f 映射接收到的信息，如果它是y1，则m1=0，而Y1，则m1=1，然后获得m。由于函数f 的单向性，接收者无法从y得出x，因此不能更改收到的任何收据。当然，当N 相对较大时，该方法的开销非常大。因此，有必要引入单向映射g 来将N 位信息映射到n 位（n 大约为50），但是这里要求g 具有比一般单向函数更强的特性。

以Web 普遍使用的SSL 认证为例，只有客户端才能验证服务器以确保其从目标服务器接收数据。为了实现单向SSL，服务器与客户端共享其公共证书。

以下是在单向SSL 情况下在客户端和服务器之间建立连接和数据传输所涉及的步骤的描述：

（1）客户端通过HTTPS 协议从服务器请求一些受保护的数据。这将启动SSL/TLS 握手过程。

（2）服务器将其公共证书以及服务器问候消息返回给客户端。

（3）客户端验证/验证接收到的证书。客户端通过证书颁发机构（CA）验证CA 签名证书的证书。

（4）SSL/TLS 客户端发送一个随机字节字符串，以便客户机和服务器都可以计算用于加密后续消息数据的密钥。随机字节字符串本身使用服务器的公钥加密。

（5）商定此秘密密钥后，客户端和服务器通过使用此密钥对数据进行加密/解密，进一步交流实际数据传输。

4 问题的相关性和陷门

在1970 年代中期，Diffie，Hellman 和Merkle 提出了非对称（或公共密钥）加密技术后，陷门功能在加密技术中占据了重要地位。实际上，Diffie＆Hellman（1976）创造了这个词。已经提出了几个函数类，并且很明显，陷门函数比最初想象的要难找到。例如，早期的建议是使用基于子集和问题的方案，很快事实证明不适合。

安全地抵抗已知的明文攻击的加密算法可以产生单向功能。假设：{P}->{K}就是这样的算法，取P=P0，考虑映射f：{K}->{C}定义为f（x）=Sx（P0），则f 是单对函数而言，因为f（x）是要获得x且已知的明文攻击是等效的（即已知的P=P0 和SK（P0）找不到K）。埃文斯还提出了另一种方法。他使用的映射为f（x）=Sx（X），这增加了破解的难度，但是这种单向功能违反了已知明文攻击的安全要求，公钥密码算法可用于生成单向身份验证系统。

陷门加密算法是一种函数，它易于在一个方向上计算，但又在没有特殊信息的情况下却很难在相反方向上计算（找到其反函数）。陷门加密算法函数广泛用于加密中，可用于生成公钥分发算法。所谓的陷门密码算法是指仅在已知陷门信息的情况下才能正确还原明文，并且在不掌握陷门信息的情况下破解明文在计算上是不可行的。

5 计算复杂性问题

在计算机科学中，算法的计算复杂性或简单性就是运行它所需的资源量，特别关注时间和内存需求。最坏情况下的复杂性（大小为n的所有输入上所需资源的最大值）或平均情况下的复杂性（大小为n的所有输入上所需资源的平均值）。时间复杂度通常表示为大小为n的输入上所需的基本运算的次数，其中假定基本运算在给定计算机上花费固定的时间量，并且在不同的计算机上运行时仅改变恒定的因子。空间复杂度通常表示为算法在大小为n 的输入上所需的内存量。

现代密码算法的安全性基于计算的不可行性，因此有必要研究计算的复杂性。在确定性图灵机上用多项式时间可以解决的问题定义为P 型复杂度，在不确定性图灵机上用多项式时间可以解决的问题定义为NP 型复杂度。大多数加密算法现在都使用NP 完整集中的问题。密码分析的难度如下：如果可以在P 时间内完成加解密算法，则密码分析的难度将不会大于NP 时间。

6 研究方向探索

在论文发表后，一系列公钥密码学的构造破土而出，包括且不仅限于：公钥加密（RSA、ElGamal、椭圆曲线、Rabin 等）、密钥交换（Diffie-Hellman、椭圆曲线DH、RSA 等）、数字签名（DSA、椭圆曲线DSA、RSA 等），更复杂的构造包括：身份加密、属性加密、功能加密、全同态加密等等。以上构造充分应用在系统的各个环节上，保护了信息和数据的安全，著名的RSA 算法就是第一个公钥加密算法。

本文从各个角度介绍了密码学的过去、现在和将来，详细分析了公钥密码学的概念和常用算法，让我们系统了解到关于密码学的理论基础。如何在现有密码学的理论基础上，发展密码理论和创新密码算法成为亟待研究的课题和方向。由于科技的发展和计算机网络的进步，不仅给密码学的发展提供了前所未有的契机和条件，但是也为算法的复杂度进行了更高的考验。计算机运算能力的加强，使得原来复杂的算法已经可以在有限的时间内解决，这就需要我们进行计算复杂度研究，创建更加复杂的算法，用以保证密码的安全性。同时如何确保在公开的计算机网络中安全地传送和保管密钥，确保密码的安全性和隐私性，也是当前面临的严峻问题。

总结一下，这篇1976 年的论文对密码学和信息安全产生了不可估量的影响，这使得一系列的算法、协议和应用破土而出。正是这些数学家、密码学家的贡献才使得现在的一切变得可能。这些算法和协议在幕后默默精巧而准确的运行，保障了信息的保密、完整和可用。同时，计算机网络通信技术的发展和信息时代的到来，使得密码学仍然面临着严峻的挑战和难得的机遇。因此，在密码学领域开展开拓性工作，努力开创密码学发展的新时代，保护网络信息的隐私和安全。