2.3 公钥密码算法

对称密码算法在密钥分配方面面临着管理和分发的困难，而且对称加密算法无法实现抗抵赖的要求，公钥密码算法的出现解决了这一难题。1976年，Diffie和Hellman首次提出了公开密钥加密算法，在密码学的发展史上具有里程碑式的意义。之后，Rivest、Shamire和Adleman提出了第一个比较完善的公钥密码算法，即著名的RSA算法。

公钥密码算法提出了“公私密钥对”的概念，这一对“互补”的密钥能够提供身份认证和抗否认等安全保障，并且使得安全的密钥交换成为可能。目前，已经出现的多数非对称密码算法所依赖的数学难题大致有：大整数因式分解、离散对数、多项式求根、背包问题、二次剩余问题和模n的平方根问题等。这里所说的数学难题指的是不存在一个计算该问题的有效方法，或者说在目前和以后足够长的时间里，计算该问题都是不可行的，要花很长的时间，这就大大增加了密码破译的成本。

常见的公钥密码算法有：RSA、ElGamal公钥密码算法、椭圆曲线公钥密钥算法（ECC）、NTRU公钥加密算法和Rabin公钥加密算法等。一些算法如著名的背包算法等都已经被破译，比较安全的公开密钥算法主要有：RSA及其变种Rabin算法，以及基于离散对数难题的ElGamal算法和椭圆曲线算法。

2.3.1 公钥密码基本概念

在对称密码算法中，解密密钥与加密密钥相同或者由加密密钥可以推导出解密密钥，但在公钥密码算法中，解密密钥和加密密钥是不同的。这不仅仅体现在形式上，还体现在从其中的一个难以推导出另外一个，这就从根本上决定了公钥密码算法的加密密钥与解密密钥是可以分离的。公钥密码算法解决了密钥的管理和分发问题，每个用户都可以公开自己的公钥，并由用户自己保存私钥，不被他人获取。

公开密钥算法与对称加密算法显著的不同是用一个密钥进行加密，而用另一个不同但是相关的密钥进行解密。

A加密：X-＞Y，Y=E（PuB（X））　A用B的公钥PuB对明文X进行加密得到Y

B解密：Y-＞X，X=D（PrB（Y））　B用自己的私钥PrB对密文Y进行解密获得X

上式中，X表示明文，Y表示加密后的密文，E表示加密，D表示解密。PuB是B的公钥，该密钥是公开的，A使用此密钥加密数据传给B；P rB是B的私钥，由B保存且不能被外人所知，B使用此密钥解密A用P uB加密过的数据。P uB和P rB是相互关联的，而且是成对出现的。

公钥密码算法的另一个特性是，仅仅知道密码算法和加密密钥而想确定解密密钥，在计算上是不可能的。显然，PuB和PrB虽然相关，但是由PuB不能推导出PrB，否则将无安全性可言。

公钥密码算法大多数都是基于困难问题的。正如把盘子打碎成数千个碎片很容易，但是把所有这些碎片再拼成一个完整的盘子就很难了。类似地，将许多大素数相乘比将其乘积的结果进行因式分解要容易得多。

2.3.2 RSA密码算法

在实际中，求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，从而把使用公钥将密文恢复成明文的难度等价于分解两个大素数之积。

还有基于RSA算法建立的签名算法，由于计算能力的不断提高，RSA的密钥长度也在不断提升，从512增加到1024、2048、4096。

RSA算法的密钥产生和加解密过程如下所述。其中，m表示明文，c和s表示密文。

1.密钥的产生过程

1）独立选取两个大素数p和q（各为100～200位十进制数字，根据需要的密钥长度进行选择）。

2）计算n=p∗q，其欧拉函数值ϕ（n）=（p-1）（q-1）。

3）随机选取一个整数e，满足1≤e＜ϕ（n），并使最大公约数gcd（ϕ（n），e）=1。

4）在模ϕ（n）下，计算e的逆：d=e^-1 mod（p-1）（q-1）。

5）以n，e为公钥，d为私钥（p，q不再需要，可以销毁）。

2. RSA算法用于加密和解密

1）加密过程：c=m^emodn。

2）解密过程：m=c^dmodn。

3. RSA算法用于数字签名和验证

1）签名过程：s=m^dmodn。

2）验证过程：m=s^emodn。

RSA算法的安全性是基于大整数分解的困难性假定。如果能分解n=p∗q，就可以立即获得ϕ（n）=（p-1）（q-1），从而计算得到d。

2.3.3 椭圆曲线密码算法

椭圆曲线密码算法是另外一类重要的公钥密码算法，它是基于椭圆曲线上的离散对数问题。我们首先对椭圆曲线的概念及椭圆曲线中的运算做简要介绍。

1.椭圆曲线概念

所谓椭圆曲线是指由韦尔斯特拉（Weierstrass）方程

E：y²+axy+by=x³+cx²+dx+e

所确定的曲线，其中的参数a，b，c，d，e以及变量x和y都属于F，F是一个域，可以是有理数域、复数域或是有限域GF（p），椭圆曲线是其上所有点（x，y）的集合，再加上一个无限远点。这个无限远点是椭圆曲线的一个特殊点，记为O，也称为无穷远点，它并不在椭圆曲线E上，如图2-19所示。

对椭圆曲线上的加法运算定义：设P和Q两点是椭圆曲线上的两点，通过这两点的直线与曲线交于第三点R，该点的x轴对称点R′即为P和Q之和，图2-20a可以清楚地说明该过程；当P=Q时，则通过这点作曲线的一条切线，这条切线与曲线的交叉点R的x轴对称点R′则为P和Q之和，如图2-20b所示。

椭圆曲线的加法运算特性归纳如下。

1）封闭性：两点相加的结果是曲线上的另一点。

2）结合性：（P+Q）+R=P+（Q+R）。

3）交换性：P+Q=Q+P。

4）单位元素：存在加法单位元素O，使得P=P+O=O+P。

5）存在逆元素：曲线上每一点都有逆元素，其逆元素对称于x轴，单位元素为其本身的逆元素。

在密码学中，普遍使用有限域上的椭圆曲线，即在前面的椭圆曲线方程中，所有的系数都属于某个有限域GF（p）中的元素，最常用的方程为

E：y²=x³+ax+b（modp）

其中，p是一个大于3的素数，参数a，b以及变量x和y都属于有限域GF（p），即从{0，1，…，p-1} 中取值，且4a³+27b²（modp）≠0。该椭圆曲线包括有限个点数N（称为椭圆曲线的阶，包括无穷远点Ω），N越大，安全性越高。

定理2.3.1 椭圆曲线上的点集对于如下定义的加法规则构成一个阿贝尔（Abel）群。此加法运算的定义如下。

设P（x₁，y₁），Q（x₂，y₂）∈E，若x₂=x₁，y₂=-y₁，则P+Q=O；否则，P+Q=（x₃，y₃），其中

x₃=aλ²-x₁-x₂ ，y₃=λ（x₁-x₃ ）-y₁

且

此外，对于所有的P∈E有

P+O=O+P=P

在这样一个阿贝尔群中，P的逆元为（x₁，-y₁），写作-P。这个阿贝尔群记作E_p（a，b）。

椭圆曲线密码算法的重点在于一个点P及其在这个阿贝尔群上的k倍（即kP）之间的关系。为了直观地表现出这种关系，借用实数域上的图形来对此加以解释。

图2-20b所示，2P所在的点为R，即经过P作一条切线，该切线与椭圆曲线相交的点沿x轴对称的那一点即为2P所在的位置。那么3P则为R+P，即连接P和R与曲线的交点关于x轴的对称点，依此类推可以得出kP。

椭圆曲线密码算法的安全性基于如下的问题。

对于给定的两个点P和Q，它们存在如下关系。

P=kQ

一个外人在拥有点P和Q的坐标的情况下，计算k值是困难的，这一问题被称为椭圆曲线离散对数问题（ECDLP）。ECDLP可以用穷尽查找法来求解，即已知条件点P和Q，将P不断自加，直至到达Q点。如果k值很大，解决这一问题就十分困难了。

在ECDLP的基础上，如何对明文、密文及密钥进行处理以使它们构成一个在模P上的加密系统的方法有多种，不同的方法可以构成不同的加密算法。下面给出其中的一种算法。

2.椭圆曲线密码算法

基于前面所定义的阿贝尔群，现在只给出一种椭圆曲线密码算法的描述，这里不对其有效性进行详细证明。

假设发送方为A，接收方为B，A需要将消息加密后传送给B。那么，首先需要考虑如何用椭圆曲线来生成B的公私密钥对，可以分为以下3步。

（1）构造椭圆群

设E：y²=x³+ax+b（modp）是GF（p）上的一个椭圆曲线（p＞3），首先构造一个群E_p（a，b）。

（2）挑选生成元点

挑选E_p（a，b）中的一个生成元点G=（x₀，y₀），G应满足使nG=O成立的最小的n是一个大素数。

（3）选择公私密钥

选择整数k_B（k＜n）作为私钥，然后产生其公钥P_B=k_BG，则B的公钥为（E，n，G，P_B），私钥为k_B。

下面介绍如何利用公私密钥对进行加解密的运算（以下的运算都是在modp下进行的）。

（1）加密过程

1）发送方A将明文消息编码成一个数m＜p，并在椭圆群E_p（a，b）中选择一点P_t=（x_t，y_t）。

2）发送方A计算密文：C=mx_t+y_t。

3）发送方A选取一个保密的随机数r（0＜r＜n），并计算rG。

4）依据接收方B的公钥P_B，计算P_t+rP_B。

5）发送方A对m进行加密，得到数据C_m={rG，P_t+rP_B，C}。

（2）解密过程

接收方B在收到A发来的加密数C_m={rG，P_t+rP_B，C}之后，进行如下操作。

1）使用自己的私钥k_B计算

P_t+rP_B-k_B（rG）=P_t+r（k_BG）-k_B（rG）=P_t

2）接收方B计算：m=（C-y_t）/x_t，得到明文m。

从上面的描述可以看出，如果攻击者想从密文C得到明文m，就必须知道r或k_B，但是，已知rG或P_B求得r或k_B，都必须去解决椭圆曲线上的离散对数问题。因此，在现有的计算条件下，椭圆曲线密码算法是安全的。与其他算法相比较，椭圆曲线密码具有两个优点：一是算法的密钥长度短，对于带宽和存储的要求比较低，运算效率高，适合在智能卡等计算与存储资源都有限的硬件设备上使用；二是所有用户可以选择使用同一基域F上的不同曲线E，从而可以让所有用户使用相同的硬件来完成域算术。

3.椭圆曲线密码算法的安全性

相对于基于有限域乘法群上的离散对数问题的密码算法，椭圆曲线密码算法的安全性是基于椭圆曲线上的离散对数问题，目前这一方法还没有发现明显的弱点，但也有一些这方面的研究思路，如利用一般曲线离散对数的攻击方法以及针对特殊曲线的攻击方法等。

为了保证椭圆曲线密码算法的安全性，就需要选取安全的椭圆曲线。用于建立密码算法的椭圆曲线的主要参数有p、a、b、G、n和h，其中p是域的大小，取值为素数或2的幂；a、b是方程的系数，取值于GF（p）；G为生成元点；n为点G的阶；还定义了参数h为椭圆曲线上所有点的个数N除以n所得的结果。为了较好地建立一个椭圆曲线算法，需要大致满足如下几个条件。

1）p的取值应尽可能大，但数值越大，计算时所消耗的时间也越多，为满足目前的安全要求，p的位数可为160位。

2）n为大素数，并且应尽可能大。

3）4a³+27b²≠0（modp）。

4）为保证n的取值足够大，需满足h≤4。

5）不能选取超奇异椭圆曲线和异常椭圆曲线这两类特殊的椭圆曲线。

由于椭圆曲线的离散对数问题被公认为比整数的因式分解以及有限域的离散对数问题还要困难得多。因此，对于它的密钥长度的要求可以大大降低，这也是该算法能够高效运行的一个原因。通常而言，160位的椭圆曲线密钥的安全强度就能达到1024位RSA算法的安全强度，这也使其成为目前已知的公钥密码算法中安全强度最高的算法之一。

2.3.4 NTRU公钥密码

传统公钥算法在无线通信安全领域的使用还不是很广泛，主要原因是移动终端上的计算和存储资源的限制，使得这些算法在移动终端上的运行速度难以满足某些应用的要求。因此，对快速公钥系统的研究是当前公钥系统研究的一个热点。

1. NTRU概述

NTRU（Number Theory Research Unit）是一种基于多项式环的加密系统，其加解密过程是基于环上多项式代数运算和对数p及q的模约化运算，只使用了简单的模乘法和模求逆运算，因此它的加解密速度快，密钥生成速度也快，而且NTRU是迄今为止唯一的增加格的维数而不损害其实用性的格密码算法。它很好地解决了公钥密码算法的最大瓶颈——速度问题，使其适用于安全性要求、体积、成本、内存及计算能力等受限的电子设备。近年来，NTRU算法引起了许多密码学家的讨论，它是目前为止已知的速度最快的公钥密码算法之一。

NTRU是1995年由J. Hoffstein、J. Pipher和J. Silverman发明的一种密码算法。在数学上，NTRU比RSA和ElGamal密码还要复杂。由于它的复杂性和出现的时间相对较短，国内外密码学界针对NTRU的安全性研究仍在继续。NTRU也存在一些缺点，比如它虽然能够实现概率加密却存在解密失败的问题，虽然人们对它进行了改进，然而这也大大损伤了该算法的简洁性。另外，与RSA和ECC算法相比，NTRU算法需要更大的带宽和更大的密钥空间。例如，对应于公钥长度为1024位的RSA算法，NTRU的公钥长度是RSA的两倍。但是，这种差异会随着安全级别的增大而降低。

虽然密码学界对NTRU进行了各种各样的攻击，但是这些都没有对它造成致命的威胁。据密码学家表示，只有当量子计算机得到应用时，NTRU密码算法才有可能被破解，而那时RSA和普通的ElGamal密码已经被破解了。

2. NTRU的理论基础

Diffie和Hellman提出应利用计算的复杂性来设计加密算法，并指出可利用格理论以及NP C问题构造密码系统。此后的各种公钥系统设计均遵循这一原则，而NTRU算法正是基于格理论在密码学上的重要应用。

格在不同的领域有不同的定义。在代数系统中，格通常定义为：设＜L，≤＞是一个偏序集，如果对任意a，b∈L，{a，b}都有最大下界和最小上界存在，则称＜L，≤＞是格，这时＜L，≤＞可简写成L。

而NTRU系统中所涉及的格的概念不同于上述的代数格，而是一个定义在n维欧式空间上的离散子群。设R^m是一个m维的欧式空间，则R^m（m≥n）是由n个线性无关的向量a₁，a₂，…，a_m的所有整数线性组合的集合。

L（a₁，a₂，…，a_m）={∑x_ia_i：x_i∈Z}构成了R^m的一个格。B=（a₁，a₂，…，a_m）称为格L的一组基，维数为m，秩为n。若m=n则称格L（a₁，a₂，…，a_m）是满维的。

简单来说，NTRU是基于高维格中寻找一个短向量的困难问题（SVP），即给定一个多项式h（x）=F_q∗g（x）（modq），其中F_q是多项式f（x）在模q时的逆元，f（x）和g（x）的系数相对于q来说是小的，在适当参数设置下，如果仅知道h（x），恢复出多项式f（x）或g（x）是困难的。

3. NTRU算法描述

NTRU密码算法的工作过程如下。

（1）密钥生成

在NTRU公钥密码算法中，接收方需要生成一组公/私密钥对。具体步骤如下：

1）选择公开参数。选择正整数参数N、p、q，其中p、q不必为素数，但是它们必须互素，且满足gcd（N，pq）=1。

2）选择多项式f（x）和g（x）。由接收方选择两个小系数多项式f（x）和g（x），其中模q的随机多项式的系数一般随机地分布在区间[0，q]上，而所谓的小系数多项式的系数相对于模q的随机多项式要小得多。接收方需要对多项式f（x）和g（x）保密，因为任何一个多项式信息泄露都可能导致密文被破解。

3）计算逆元F_p（x）和F_q（x）。接收方计算多项式f（x）在模p和模q时的逆元F_p（x）和F_q（x），即F_p（x）∗f（x）=1（modp，modx^N-1）和F_q（x）∗f（x）=1（modq，modx^N-1）。如果f（x）的逆元不存在，接收方需要重新选取f（x）。

4）计算公钥。计算h（x）=F_q（x）∗g（x）（modq，modx^N-1），多项式f（x）和F_p（x）为私钥，h（x）为公钥。

（2）加密过程

假设发送者发送一条明文消息m（x）给接收者，m（x）是次数为N-1的多项式，具有模p约简的系数（可以理解为系数的范围在（-p/2，p/2）内）。发送方随机选择一个次数为N-1的多项式r（x）进行计算得到

c（x）=pr（x）∗h（x）+m（x）（modq，modx^N-1）

然后将其发送给接收方。

（3）解密过程

假设接收者收到加密消息c，首先计算多项式a（x）

a（x）=f（x）∗c（x）（modq，modx^N-1）

接着计算

d（c）=F_p（x）∗a（x）（modp，modx^N-1）

d（c）就是解密后的明文。

（4）说明

这里的加法+，是通常的多项式加法。这里的乘法∗，是比较特殊的乘法。设R为关于x的多项式的集合，具有整数系数和严格比N小的次数，乘法∗表示

xⁱ∗x^j=x^{i+j（modN）}

也就是

该乘法依然满足交换律、结合律和分配律。此外，算法还会涉及模p约简和模q约简运算，这是指分别对多项式的系数做模p或q的约简。可以写作

f（x）（modp）=系数经过模p约简的多项式f（x）

f（x）（modq）=系数经过模q约简的多项式f（x）

（5）解密原理

因为a（x）=f（x）∗c（x）（modq，modx^N-1）

=f（x）∗（pr（x）∗h（x）+m（x））（modq，modx^N-1）

=f（x）∗（pr（x）∗F_q（x）∗g（x）+m（x））（modq，modx^N-1）

=f（x）∗pr（x）∗F_q（x）∗g（x）+f（x）∗m（x））（modq，modx^N-1）

=f（x）∗F_q（x）∗pr（x）∗g（x）+f（x）∗m（x））（modq，modx^N-1）

=1∗pr（x）∗g（x）+f（x）∗m（x））（modq，modx^N-1）

=pr（x）∗g（x）+f（x）∗m（x））（modq，modx^N-1）

考虑到多项式pr（x）∗g（x）+f（x）∗m（x），只要参数选取适当，几乎可以确保多项式pr（x）∗g（x）+f（x）∗m（x）每一项的系数都在（-q/2，q/2）区间上，即

a（x）=pr（x）∗g（x）+f（x）∗m（x）（modx^N-1）

将a（x）再modp得到

a（x）=f（x）∗m（x）（modp，modx^N-1）

则解密操作后可以得到

d（c）=F_p（x）∗a（x）（modp，modx^N-1）

=F_p（x）∗f（x）∗m（x）（modp，modx^N-1）

=1∗m（x）（modp，modx^N-1）

=m（x）