神奇的公钥密码

杨亚涛 黄洁润

密码学与数学难题有着非常密切的关系，非对称密码就是基于有名的数学难题（如利用普通的离散对数、大整数分解和椭圆曲线离散对数等问题）来设计的公钥密码系统。从破译公钥密码系统的角度来看，可以将破译过程视为对一种数学难题的求解，难题越难，破译起来就会越困难，而公钥密码体制也就越安全。

什么是公钥密码

公钥密码算法为加密和解密使用不同密钥的密码算法，其中一个密钥是公开的，称为公开密钥（Public Key），简称公钥，用于加密或验证签名；另一个密钥为用户专用，是保密的，称为私钥（Private Key），用于解密或签名。由于公钥密码体制的公钥是公开的，通信双方不需要利用传统的秘密信道就可以进行加密通信，同时也可以很方便地为数据加密协商出共享的会话密钥，因此在现代密码通信领域中有着广泛应用。

公钥密码体制的出现是迄今为止密码学发展史上一次最伟大的革命。1976年，威特菲尔德·迪菲（Whitefield Diffie）和马丁·海尔曼（Martin Hellman）提出了公钥密码的思想。基于此思想建立的密码体制，被称为公钥密码体制或非对称密码体制。对于公钥密码体制，算法具有以下重要特性：已知密码算法和公钥来求解私钥，这在计算上是不可行的。

密码算法

在公钥密码体制问世之前，所有的密码算法，包括古典密码、手工计算密码、机械密码、对称密码等，都是基于代换或置换这两个基本方法。

国外的公钥密码主要有RSA公钥密码体制和ElGamal公钥密码体制等。1978年，麻省理工学院的三位密码学家瑞斯特

（Ron Rivest）、夏米尔（Adi Shamir）

和阿德尔曼（Leonard Adleman）提出了RSA密码算法，它是一种用数论构造的、也是迄今为止理论上较为成熟完善的公钥密码体制。

1985年，厄格玛尔

（T. ElGamal）提出了ElGamal公钥密码体制，它是基于离散对数问题且主要是为实现数字签名的目的而设计的，是继RSA算法之后也比较有名的密码方案。目前，科学家对于离散对数问题的研究已经取得了一些重要的研究成果，也设计出了一些计算离散对数的算法，但在现有计算机的计算能力下，利用已有的算法来计算离散对数依然是很困难的。

公钥密码体制原理

公钥密码体制的加密和解密过程包括如下几个步骤：

（1）产生一对密钥（pk，sk），其中pk是公钥，sk是私钥。

（2）将密钥pk予以公开，另一密钥sk则保密存放。

（3）发送方使用接收方的公钥加密明文m，得到并发送密文c。

（4）接收方收到密文c后，用自己的私钥sk解密。由于只有接收方知道其自身的私钥sk，所以其他人都无法对密文c解密。

这里以RSA密码算法为例，来说明一下公钥密码体制的加密与解密过程。

为了进行RSA密码系统的初始化，即生成RSA算法的公私密钥对，需要进行以下几个步骤：

（1）选取两个不同的大素数p和q；

（2）计算n=pq，φ（n）=（p-1）（q-1），其中φ（n）是n的歐拉函数；

（3）随机选取整数e∈Z，同时满足，1

（4） 计算得出与e互逆的d。e和n是公钥，d是私钥。

下面通过一个小例子简单说明RSA算法公钥和私钥的具体产生过程。

设p=13，q=17，e=11，n=p×q=13×17=221，则φ（n）=（p-1）（q-1）=（13-1）×（17-1）

=192，显然，公钥e=11（一般为素数），满足1

得到公私钥后，发送方用接收方的公钥加密信息，接收方接收到信息后用私钥解密，即实现了加解密过程。

公钥密码的不可抵赖性

对于信息安全来说，除机密性之外，不可抵赖性也是不可忽视的方面。特别是今天，信息网络渗透到金融、商业以及社会生活的各个领域，信息的不可抵赖性已经变得越来越重要。比如电子商务活动中，主要的支付方式有通过IC卡终端转账、通过信用卡金融网络划拨、电子支票、扫码支付等，无论哪种方式，任何环节的纰漏都会引发安全问题。而公钥密码可以有效地解决机密性、不可抵赖性和身份认证这些信息安全问题。

不可抵赖性是指在信息交互活动中的参加者不能否认所发生的事件和行为。一般情况下，不可抵赖性包含两个方面：一个方面是发送方的不可抵赖，也就是说，张三发了一个消息给李四，张三就不能否认这个事实；另一个方面是接收方的不可抵赖性，例如小明要购买某个玩具公司的产品，通过网络给公司成功支付了订金，公司收到了订金，但是却耍赖说没有收到。在很多互联网活动比如电子商务、个人办公等系统中，都要解决好不可抵赖性的问题。

不可抵赖可以用公钥密码算法和数字签名技术来实现。数字签名，类似现实生活中人的手写签名，它的本质是该签名只有通过签名者本人的私有信息才能产生，即一个签名者的签名只能唯一地由他自己产生，别人不能伪造。当收发双方产生争议时，第三方权威机构就能够根据消息上的数字签名来裁定这条信息来自何方，从而实现对信息发送或接收行为的不可抵赖。公钥密码算法是实现数字签名技术的基础。

通信或交易时，应该保证信息的接收方和发送方能够被唯一地标识出来，让通信双方都能够知道信息从哪里来或者到哪里去，我们也将这种安全保障简称为身份认证。按照被验证对象可以将身份认证问题分成三种：一是对设备的身份认证，二是对人的身份认证，三是对信息的身份认证。通过主机地址、主机名称、拥有者的口令等都在一定程度上保证了对设备的验证，但通过公钥密码算法和数字签名技术，可以比较完美地实现对人员、设备或信息的身份认证。

上述主要介绍了公钥密码与数学的紧密关系以及公钥密码体制在生活中的广泛应用。在密码学的发展历程中，密码与数学相伴而生，数学已经成为密码学发展的重要基石和理论基础。基于数学难题构造的公钥密码体制是现代密码学中不可或缺的重要组成部分。