3.2　公钥密码体制

前述算法面临着一个共同的挑战，即密钥的泄露问题。在系统设计中，需要考虑传输密钥的安全通道，这本身又是一个加密系统。为了避免陷入这种循环嵌套的难题，现代密码学走出了“公钥”密码体制的新方向。自1976年Whitfield Diffie与Martin Hellman提出理论方向后，公钥加密算法的研究已经持续了数十年。表3-4归纳了目前常见的公钥加密算法的主要技术方向。

对于一个隐秘的私钥ks，公钥加密算法的一般要求是：

• Bob很容易验证某个特定的km是否和ks“匹配”，若能匹配，则令km为公钥；
• Alice很容易用公钥km来加密明文；
• Bob很容易用私钥来ks解密密文；
• Carl无法用公钥km来解密密文，且无法从km中推算出ks。

公钥加密算法的核心是构建一个“数学难题”，使得人们很难从公开的km推算出ks，但是可以很容易地验证某个特定km是否和ks匹配。所谓“匹配”，即满足“公钥加密，私钥解密”的过程。为了方便理解，我们可以简称上述密钥的特征为“易验证，难推算”。由于“易验证”，Bob可以随机选择一个私钥并快速找到能匹配的公钥。由于“难推算”，在图3-2中，Carl即使得知了公钥，也无法计算私钥。

3.2.1　RSA算法

RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年共同提出的，并由此三人的名字命名。该算法是具有代表性的基于大整数分解的非对称加密算法。下面通过两部分了解RSA算法：公、私钥参数生成以及加、解密过程。

RSA的公、私钥参数生成过程如下。

• Step 1：选择大素数p和q。然后根据p和q直接计算n以及φ(n)，满足n=pq，且φ(n)= (p-1)(q-1)。
• Step 2：随机选择公钥t，使得t和φ(n)的最大公约数为1，且t<φ(n)。
• Step 3：计算t的乘法逆元h，满足t×h mod φ(n)=1。

上述结果中，{p,q,h}为私钥，{n,t}为公钥。生成参数之后，就可以进行相应的加、解密操作了。加、解密的过程如下。

• Step 1：Bob计算RSA密钥参数，并将公钥{n,t}公开发布，将私钥{p,q,h}本地保存。
• Step 2：Alice知道公钥{n,t}，利用函数s=mt mod n对原文m进行加密。
• Step 3：Bob得到密文s，并利用私钥{p,q,h}对密文进行解密，计算函数为m=sh mod n。

上述所有计算过程都是在集合Zn={0,1,…,n-1}中完成的。这些过程看上去复杂，不禁让人产生疑问：为什么这些参数和运算可以将明文加密再恢复成密文呢？我们不妨对该过程进行简单的推导。由于参数生成的过程中有t×h mod φ(n)=1，显然

(mt)h mod n=ma×φ(n)+1 mod n

这里a为整数。如果加密过程能恢复出明文m，需要有ma×φ(n) mod n=1。大家可以了解mφ(n) mod n=1这个结论是成立的。而且，当m和n的最大公约数为1时，这个结论是数论中非常著名的“欧拉定理”；当m和n的最大公约数不为1时，由于n是两个素数p和q的乘积，我们可以把m表示为p或q的倍数，那么mφ(n) mod n=1这个结论也比较容易验证，在此不展开具体证明。

以上是RSA算法的密钥生成和加、解密的基本过程。下面对RSA背后的数学原理做一些解释。

• 在参数生成的过程中，再一次用到了乘法逆的概念。我们已经知道，t的乘法逆h存在的充分必要条件是t和φ(n)的最大公约数为1。
• 如果Carl能很容易地把公钥n分解且得到n=p×q，并计算φ(n)，就可以像Bob一样计算出私钥{p,q,h}。但在实际中，这是不可能的。其原理在于大整数n的素数分解一直是世界级的数学难题。以目前的研究进展来看，长度为1024位的大整数是无法破解的。
• 当Bob试图生成公、私钥参数时，由于他也无法解决上述难题，不可能先随机找到一个大整数n再做素数分解。可行的方法是，Bob先找到两个比较大的素数p和q，然后用它们来计算n和φ(n)。这里就涉及数论中的另一个经典问题，即素性检测。目前的RSA算法实现常选取512位的p和q、1024位的n。幸运的是，对于这种数量级来说，随机生成一个整数且刚好为素数的概率约为几百分之一。Bob完全可以随机生成p和q，然后判断它们是否为素数。这种操作的复杂度是可以接受的。目前，比较常见的素性检测算法有费马检测、Miller-Rabin检测和Solovay-Strassen检测等，这些算法都是比较高效的。
• Bob在得到n和φ(n)后，还需要能快速计算出和φ(n)互素的整数t，以及t的乘法逆h，这可以用欧几里得算法高效实现。

RSA算法要求将明文m也表示成大整数，即m∈Zn。如果原文信息m太长，超出了RSA算法的要求，可以先对原文进行分块，再对每一块执行RSA加密。

3.2.2　ElGamal算法

ElGamal算法的过程分为三个步骤：第一步，Bob基于某个数学难题构造私钥和公钥参数，并将公钥公布，私钥自存；第二步，Alice根据公钥生成密文，并将密文发送给Bob；第三步，Bob利用私钥对密文解密。

大家会发现上述过程和RSA并无二致，因为这正是非对称加密的一般框架。但是，ElGamal算法和RSA算法到底有哪些区别呢？简要地说，区别主要有以下两个方面。第一，算法基于的数学难题不同，RSA的基础是大整数的素数分解，而ElGamal算法是基于离散对数问题构建的。第二，加密和解密的计算过程也不同，在ElGamal算法中Alice除了用公钥对明文进行加密之外，还利用自己秘密生成的一个随机数生成一个随机密码，并将该随机密码和密文一起发给Bob，Bob利用私钥、随机密码和密文恢复明文。下面对这两个方面进行详细的介绍。

Bob生成密钥参数的操作有以下几步：

• Step 1：找到一个大素数p。
• Step 2：基于p，满足一定条件的整数α，以及另一个整数t；其中t需要满足2≤t≤p-2。
• Step 3：计算β=αt mod p。

上述过程中，参数{α, β, p}为公钥，t为私钥。

Alice利用公钥参数加密的步骤如下：

• Step 1：选择秘密的随机数i，满足2≤i≤p-2。
• Step 2：计算随机密码ka=αi mod p。
• Step 3：用公钥对明文m进行加密得到密文s，即s=m×βi mod p。
• Step 4：将随机密码ka和密文s都发送给Bob。

Bob利用私钥参数进行解密的过程较简单，其计算方法如下：

m=s×[(ka)t]-1 mod p

从表面的数学形式来看，上述过程非常容易推导，其核心是β=αt mod p。但实际上，上述过程中参数{α,β,p}以及i的选择都有一定的限制条件，其背后有着比较丰富的数论原理。下面我们试图以比较简明的语言来解释ElGamal算法涉及的数论知识。

通常情况下，上述ElGamal算法的运算都发生在一个特殊的整数集合中。表示所有小于p且和p最小公约数为1的整数所构成的集合。

我们需要了解，集合有以下两个重要的性质。

• 该集合中任意一个元素都有乘法逆，即对任意都有。这确保了加密和解密算法中的求逆运算有效。
• 该集合中可以找到α，使得集合中任何一个元素都可以用α的幂来表示。这种情况下，称α为该集合的生成元。这个性质就使得以α为根来构造离散对数问题比较简单。

在数论中，有经典算法可以帮助我们根据p和快速找到适合的α。除此之外，算法中的乘法、求幂和求逆都是比较简单的操作。

至此，我们便可更加形象地理解ElGamal算法的原理了。简单地说，由于的特殊构造，集合中所有元素都可以表示为α的幂，当然β也可以表示成α的t次幂。由于β很大，以α底来求解其对数很难，因此只有Bob知道私钥t，其他人只知道公钥{α,β,p}。剩下的过程非常简单：Alice利用βi对明文进行加权，而Bob用[(ka)t]-1去除加权效果。因为：

在后续讨论中可以看到，ElGamal利用的离散对数问题也是数学难题，利用穷举或通用算法破解离散对数的计算复杂度非常高。并且，和RSA算法相比，ElGamal具有概率的特征，由于Alice选择随机密码i时有不确定性，对于相同的明文m1和m2，加密的密文是不同的。由于i也是在一个很大的集合中随机选择的，这显著增加了穷举型破解方式的计算复杂度。

3.2.3　椭圆曲线算法

ElGamal算法的思路可以从中推广到其他类型的群。椭圆曲线加密算法就是一个很好的例子。椭圆曲线算法于20世纪80年代被提出，稍晚于RSA和ElGamal算法。在相同密钥长度的情况下，攻击椭圆曲线算法的计算复杂度远高于RSA和ElGamal算法。而且，一般情况下椭圆曲线算法的计算复杂度也较低。但是，椭圆曲线的数学原理比之前提到的大整数分解、离散对数等都更复杂。在下面的篇幅中，我们试图以较为简明的语言阐述其基本原理。

在代数中常用方程式来定义曲线，例如直线、圆周和抛物线等。椭圆曲线也一样，它由一个二元方程来定义。

为了构建加密算法，我们先要在椭圆曲线上构建数学运算，这就是椭圆曲线上的“加法”。这里的加法运算和简单的加法或模和是完全不同的。从几何的角度来看，椭圆曲线上两个点{P, Q}的加法P+Q过程等效为定位一个点U，使得U是“P和Q点连线的延长线与曲线的交点的x轴对称点”。

依此类推，可继续利用P和2P在椭圆曲线上定位3P这个点。通过合理地构造椭圆曲线，我们可以保证在n足够大的时候，nP总是曲线上的某个点。这里又一次用到了“生成元”的概念。在一定条件下，椭圆曲线上所有的点都可以用P的多次“加法”来得到。

于是，引申出椭圆曲线加密中用到的数学难题，即：

给定两个点P和Q，若已知P=nQ，求n。

由于n足够大，通过P和Q求解n是很困难的。Bob确定椭圆曲线上的某个点G，然后根据一个秘密的随机数k来计算出F=kG，其中{G,F}为公钥，k为私钥。

然后是基于上述密钥的加密和解密过程。现简要介绍如下。

当Alice得到公钥后，分两个步骤构建密文。

• Step 1：找出一个随机数r，然后在椭圆曲线上找到rG；
• Step 2：用公钥加密明文m，即s=m+rF。Alice把两部分密文{rG, s}一并发给Bob。

Bob解密的过程比较简单。当Bob收到密文后，利用私钥和两部分密文进行运算，计算方式为：

m = s – krG

由于krG = rF，所以很容易验证上述加密、解密过程成立。

实际上，上述算法的几何意义非常容易理解。Bob生成私钥的过程，就是利用点G和随机选择的秘密参数k来找到点F。Alice利用rF加法操作将明文对应的点在椭圆曲线上搬运到密文对应的点，然后Bob利用krG加法操作把密文映射回明文。

研究表明，当椭圆曲线的参数p很大时，从G和F来推算k是非常困难的。例如，如果p是一个200位的数，那么椭圆曲线上可能的点的数量级是2160。在这样一个巨大的集合中，在椭圆曲线上回溯k基本是不可能做到的。但是反过来，如果已知n，则有快速算法可以直接由P求出Q。这和公钥加密算法中“易验证，难推算”的精神是一致的。

3.2.4　公钥密码的安全性分析

RSA算法的核心是大整数分解。在过去数十年中，许多学者对该难题进行了研究，提出了诸如二次筛选法、椭圆曲线算法、数域筛选法等一系列的算法，在这个方向上做出了一些成绩。但是，从20世纪90年代至今，算法或架构上并没有跨越性的新突破。这是RSA算法成立的重要基础。在花费大量财力和物力、组织大规模计算能力的前提下，目前已有学者提出可以分解512位甚至是768位长度的大整数。有研究表明，分解算法每十年约能多提升100位的分解长度。到目前为止，分解1024位乃至更大的整数在工程实现上基本是不可能的。因此，RSA一般选择1024或2048位的大整数长度。

ElGamal利用的离散对数问题也是数学难题。如果在集合Zp中遍历地寻找密钥d，其复杂度为2p。ElGamal算法一般选择p为1024位或2048位，这意味着暴力破解基本是不可能的。离散对数也有相应的通用算法，例如Shanks算法和Pohling-Hellman算法等。研究表明，这些算法的计算复杂度不低于2(p/2)。

在密钥长度相同的情况下，椭圆曲线的破解是最困难的。椭圆曲线的基本运算（求“和”是在曲线上做点的映射）比RSA和ElGamal复杂得多，因此一般认为密钥长度为160位的椭圆曲线算法和密钥长度为1024位的RSA/ElGamal算法安全性相当。实际中，常用的椭圆曲线算法密钥长度为256位。