第3章 公钥密码

教学提示：如果加密/解密过程各有不相干的密钥，构成加密/解密的密钥对，则称这种加密算法为“非对称加密算法”或称为“公钥加密算法”，相应的加密/解密密钥分别称为“公钥”和“私钥”。在公钥加密算法中，公钥是公开的，任何人可以用公钥加密信息，再将密文发送给私钥拥有者。私钥是保密的，用于解密其接收的公钥加密过的信息。典型的公钥加密算法RSA是目前使用比较广泛的加密算法。

教学目标：掌握密码学必需的数学基础知识, 为接下来密码学的学习打下一个坚实的基础。而这些内容本身也是数学学科的若干重要的知识点。发现人们是如何巧妙地将纯数学的理论应用于实际中的密码编码技术，清楚公钥密码所基于的安全因素与数学计算难题的关系，明确这些密码体制所必须遵守的预定或要求，理解它们与对称密码的互补或不可替代关系。

3.1 公钥密码概述

在1976年以前的密码系统都是对称密码系统（也叫单钥密码系统），对称密码系统是一种比较传统的加密方式，其加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码）。因此，通信双方都必须获得这把钥匙，并保持钥匙的秘密。对称密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，没有必要确保算法的秘密性（事实上，现实中使用的很多单钥密码系统的算法都是公开的），但是一定要保证密钥的秘密性。从对称密码的这些特点容易看出它的主要问题有两点：第一，密钥量问题。在单钥密码系统中，每一对通信者就需要一对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的产生、存放和分配将是一个难以解决的问题。第二，密钥分发问题。对称密码系统中，加密的安全性完全依赖于对密钥的保护，但是由于通信双方使用的是相同的密钥，人们又不得不相互交流密钥，所以为了保证安全，人们必须使用一些另外的安全信道来分发密钥，例如用专门的信使来传送密钥，这种做法的代价是相当大的，甚至可以说是非常不现实的，尤其在计算机网络环境下，人们使用网络传送加密的文件，却需要另外的安全信道来分发密钥。

针对对称密码系统中密钥的分发和管理非常复杂这一难题，Diffie和Hellman在《密码学的新方向》一文中提出了“公钥密码”的概念。公钥密码体制突破性地解决了困扰着无数科学家的密钥分发问题，事实上，在这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为是密码史上两千年来自单码替代密码发明以后最伟大的成就。在公钥密码系统中，加密和解密使用的是不同的密钥（相对于对称密钥，人们把它叫做非对称密钥），这两个密钥之间存在着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。这使得通信双方无须事先交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的，人人都可以通过这个密钥加密文件然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文件后，它可以使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并不需要分发，因此又称为私钥，这就解决了密钥分发的问题（图3-1）。公开密钥密码体制下，加密密钥不等于解密密钥。加密密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发送，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时间而成为不可行的。所以将加密密钥公开也不会危害密钥的安全。1978年，密码学家Rivest、Shamir和Adleman设计出了第一个实用的公钥密码方案一RSA。三十多年以来，RSA仍然是应用最广泛的密码体制。此后，人们基于不同的计算问题，提出了大量的公钥密码算法。其中具有代表意义的有基于整数分解问题的Rabin算法，基于有限域上离散相关难题的EIGamal算法和目前被视为可以代替RSA算法的椭圆曲线算法（ECC）。

一般情况下，网络中的用户约定一个共同的公开密钥密码系统，每个用户都有自己的公钥和私钥，并且所有的公钥都保存在某个公开的数据库中，任何用户都可以访问这个数据库。

3.2 RSA密码体制

3.2.1 简介

当前最著名、应用最广泛的公钥系统 RSA是在1978年，由美国麻省理工学院（MIT）的Rivest、Shamir和Adleman 在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称（公开密钥）密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。它的安全性是基于大整数素因子分解的困难性，而大整数素因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。

RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密文件。为提高保密强度，RSA密钥至少为512位长，一般推荐使用1024位。RSA 公钥密码算法是目前网络上进行保密通信和数字签名的最有效的安全算法之一。RSA算法的安全性基于数论中大素数分解的困难性，所以，RSA须采用足够大的整数。因子分解越困难，密码就越难以破译，加密强度就越高。

同大多数公钥密码体制一样，RSA的安全性主要取决于构造其加密算法的数学函数的求逆的困难性，称这样的函数为单向函数。单向函数在密码学中起一个中心作用，它对公钥密码体制的构造是非常重要的。单向函数的研究是公钥密码体制理论中的一个重要课题。但是，虽然很多函数（包括RSA算法的加密函数）被认为或被相信是单向的，但目前还没有一个函数能被证明是单向的。

下面看看如何生成私钥和公钥，如何用其进行加密与解密，整个过程如下。

1.密钥的产生

① 选大素数p和q（100～200位十进制数字）；

② 计算n= p×q，ϕ(n)=(p-1)(q-1)，其中ϕ(n)是n的欧拉函数值；

③ 随即选一整数e，满足1≤e≤ϕ(n)，且gcd=(ϕ(n),e)=1；

④ 计算d，满足d⋅e≡1modϕ(n)，即d是e在模ϕ(n)下的乘法逆元，因e与ϕ(n)互素，由模运算可知，它的逆元一定存在；

⑤ 以{e, }n 为公钥，{d, }n 为密钥。

2.加密

加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2 n。然后对每个明文分组m作加密运算：

c≡me mod n

3.解密

对密文分组的解密运算为：

m≡cd mod n

选p=7，q=17。求n= p × q=7×17=119。可以看到，ϕ(n)=(p-1)(q-1)=6×16=96，96的因子为2和3，因此公钥e不能有2或者3的因子。取e=5，满足1<e<ϕ(n)，且gcd=(ϕ(n),e)=1。确定d⋅e=1 mod 96且小于96的d，因为77×5=385=4×96+1，所以d为77，因此公钥为{5，119}，私钥为{77，119}。

设明文m=19，则由加密过程得密文为

c≡195 mod 119≡2476099 mod 119≡66

解密为

6677mod 119≡19

3.2.2 RSA密钥的产生

产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。

因为n= pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（10200≈2664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。

寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。

可见寻找大素数是一个比较烦琐的工作。然而在RSA体制中，只有在产生新密钥时才需要执行这一工作。

p和q决定出后，下一个需要解决的问题是如何选取满足1≤e≤ϕ(n)和gcd=(ϕ(n),e)=1的e，并计算满足d⋅e≡1modϕ(n)的d。这一问题可由推广的Euclid算法完成。

3.2.3 RSA的安全性分析

RSA的安全性基于分解大整数的困难性假定，之所以假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p × q，则立即获得ϕ(n)=(p-1)(q-1)，从而能够确定e模ϕ(n)的乘法逆元d，即d≡e-1 modϕ(n)，因此攻击成功。

随着人类计算能力的不断提高，原来被认为是不可能分解的大整数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解。RSA-140 已于1999年2月被成功分解， RSA-155（512比特） 已于1999年8月被成功分解，得到了两个78位（十进制）的素数。

对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。

是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定ϕ(n)等价于对n的分解。

设n= pq中，p>q，由ϕ(n)=(p-1)(q-1)，则有

p+q=n-ϕ (n)+1

以及

由此可见

所以，由p、q确定ϕ(n)和由ϕ(n)确定p、q是等价的。

为保证算法的安全性，还对p和q提出以下要求。

（1）|p-q|要大

由，如果|p-q|小，则也小，因此稍大于n，稍大于。可得n的如下分解步骤：

① 顺序检查大于的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。

② 由x2-n=y2，得n=(x+y)(x-y)。

（2）p-1和q-1都应有大素因子

因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：若≡c(mod n)，即≡c(mod n)，则有 ≡m(mod n)，即 ≡m(mod n)，所以在上述重复加密的倒数第2步就已恢复出明文m，这种攻击法只有在t较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使t很大。

设m在模n下阶为k，由 ≡m(mod n)得≡1(mod n)，所以k|(et -1)，即et ≡1(mod k)， t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|ϕ(k)。为使t大，k就应大且ϕ(k)应有大的素因子。又由k|ϕ(n)，所以为使k大，p-1和q-1都应有大的素因子。

此外，研究结果表明，如果e<n且，则d能被容易地确定。

3.2 椭圆曲线密码体制

自RSA提出以后，人们对大整数分解问题的研究产生了空前的兴趣，而对大整数分解问题的求解和对有限域上离散对数问题的求解在本质上具有某种一致性。借助于计算机技术的不断提高，经过人们的不懈努力，目前人们对两类问题的求解能力较过去有了很大的提高。这迫使RSA体制中使用的模数和基于有限域离散对数问题的公钥密码体制中的有限域越来越大。对这两类体制，过去512bit 大小的密钥已足够安全，但现在就不能保证它的安全性了，不得不使用1024bit 或2048bit大小的密钥。密钥位数的增加导致了其加密和解密的速度大为降低，存储空间增大，硬件实现变得越来越困难。相反地，近10年来人们对椭圆曲线离散对数问题求解方法的研究几乎毫无进展，对椭圆曲线密码体制，160bit长的密钥所具有的安全性和前两类体制中1024bit长的密钥所具有的安全性相当，210bit长的密钥所具有的安全性和前两类体制中2048bit长的密钥所具有的安全性相当。

1985年Koblitz、Miller等人分别独立提出椭圆曲线密码体制ECC，即基于椭圆曲线离散对数问题的各种公钥密码体制，它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制。ECC与其他两类体制比较，有如下优点。

第一，ECC具有最强的单位比特安全性。就安全性而言，每一比特椭圆曲线密码体制的密钥至少相当于5比特长的RSA密钥的安全性，并且这种比例关系随密钥长度的增加呈上升趋势。ECC的这一特点使得它在未来计算能力逐渐提高的情况下与其他两类体制相比具有更强的竞争力。它所具有的相对小的密钥长度尤其适合像IC卡技术那样一种存储条件受到严格限制的情况。

第二，在同样的基域下，ECC具有更多的可选择性。也就是说，对给定的素数p或q，都唯一地对应一个RSA算法或ElGamal类算法。但是对于ECC情况不是这样。因为在同一基域上，通过改变椭圆曲线方程的系数就能够得到更多具体的算法。

第三，可以主动选取基域GF(q)中的素数q，这样就可选取更便于计算机处理的素数。

ECC的这些优点，使得人们普遍认为，ECC会取代RSA而成为21世纪最主要的公钥密码体制。从1998年起一些国际标准化组织开始了对椭圆曲线密码的标准化工作。

3.2.1 椭圆曲线

椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：

其中 a，b，c，d，e 是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为 O。图3-2是椭圆曲线的两个例子。

从图3-2可见，椭圆曲线关于x轴对称。

椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：

① O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。

② 设P1=(x,y)是椭圆曲线上的一点（图3-2），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2、O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O。

③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是唯一的，除非所做的直线是Q点或R点的切线，此时分别取1P1=Q和P1=R）。由Q+R+P=0得Q+R=-P1。

④ 点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…。

以上定义的加法具有加法运算的一般性质，如交换律、结合律等。

3.2.2 椭圆曲线上的密码

为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P,Q∈Ep(a,b)，k<p，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。

ElGamal 密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。

1.ElGamal密码体制

（1）ElGamal密码体制的原理

密钥产生过程：首先选择一素数p以及两个小于p的随机数g和x，计算y≡gx mod p。以(y, g, p)作为公开密钥，x作为秘密密钥。

加密过程：设欲加密明文消息M，随机选一与p-1互素的整数k，计算C1≡gk mod p， C2≡yk M mod p，密文为C=(C1，C2)。

解密过程：

这是因为

（2）利用椭圆曲线实现ElGamal密码体制

首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入曲线上得点Pm，再对点Pm做加密变换。

取Ep(a,b))的一个生成元G，Ep(a,b)和G作为公开参数。

用户A选nA作为秘密钥，并以PA=nAG作为公开钥。任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文：

Cm = {kG,Pm+kPA}

A解密时，以密文点对中的第二个点减去用自己的私钥与第一个点的倍乘，即

Pm+kPA-nAkG=Pm+k (nAG)-nAkG=Pm

攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。

取p=751 Ep， (-1，188)，即椭圆曲线为y2≡x3-x+188，Ep(-1，188)的一个生成元是G=(0， 376)，A的公开钥为P A=(201，5)。假定B已将欲发往A的消息嵌入椭圆曲线上的点Pm=(562，201)， B选取随机数k=386，由k G=386(0，376)=(676，558)，Pm+k PA=(562，201)+386(201，5)=(385， 328)，得密文为{(676，558)，(385，328)}。

2.椭圆曲线密码体制的优点

椭圆曲线密码体制有如下优点。

（1）安全性高

攻击有限域上的离散对数问题可以用指数积分法，其运算复杂度为，其中p是模数（为素数）。而它对椭圆曲线上的离散对数问题并不有效。目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为，其中pmax是椭圆曲线所形成的 Abel 群的阶的最大素因子。因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全。

（2）密钥量小

由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。

（3）灵活性好

有限域GF(q)一定的情况下，其上的循环群（即GF(q)-{0}）就定了。而GF(q)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性。

正是由于椭圆曲线具有丰富的群结构和多选择性，并可在保持和 RSA/DSA 体制同样安全性能的前提下大大缩短密钥长度（目前160比特足以保证安全性），因而在密码领域有着广阔的应用前景。