2.5　典型公开密钥密码系统

本节介绍几种典型的公开密钥密码系统：RSA密码体制、ElGamal公钥密码体制、椭圆曲线密码体制、基于身份的密码体制，以及Diffie-Hellman密钥交换协议。

2.5.1　RSA公开密钥密码系统

1977年美国麻省理工学院的3位教授Rivest、Shamir和Adleman研制出了一种公开密钥密码系统，该密码系统以三位教授姓氏的首字母命名，被称为RSA公开密钥密码系统，简称为RSA公钥密码系统。1978年介绍RSA公钥密码系统的论文《获得数字签名和公开钥密码系统的方法》发表问世。RSA公钥密码系统是目前应用最广泛的公开密钥密码系统。

RSA公钥密码系统基于“大数分解”这一著名数论难题。将两个大素数相乘十分容易，但要将乘积结果分解为两个大素数因子却极端困难。举例来看，将两个素数11 927和20 903相乘，可以很容易地得出其结果249 310 081。但是要想将249 310 081分解因子得到相应的两个素数却极为困难。

Rivest、Shamir和Adleman提出，两个素数的乘积如果长度达到了130位，则将该乘积分解为两个素数需要花费近百万年的时间。为了证明这一点，他们找到1个129位数，向世界挑战找出它的两个因子，这个129位的数被称为RSA129。RSA129的值为114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541。世界各地六百多名研究人员通过Internet协调各自的工作向这个129位数发起进攻。花费了9个月左右的时间，终于分解出了RSA129的两个素数因子。两个素数因子一个长为64位，另一个长为65位。64位的素数是3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577，65位的素数是32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533。RSA129虽然没有如Rivest等三位专家预计的那样花费极长的时间破解，但它的破解足以说明两方面的问题。首先，大整数的因子分解问题有高昂的计算开销，此外，通过Internet让大量的普通计算机协同工作可以获得强大的计算能力。

1.RSA的密钥产生过程

RSA算法涉及到欧拉函数的知识，这里进行简要介绍。

在数论中，对正整数n，欧拉函数Φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者的姓名命名。举例来看，Φ(1)=1，因为唯一和1互质的数就是1本身。Φ(8)=4，因为1、3、5、7均和8互质。如果p是素数，则Φ(p)=p− 1。如果p、q均是素数，则Φ(pq)=Φ(p)× Φ(q)＝ (p−1)× (q−1)。

RSA密钥的产生过程如下：

（1）选择两个大素数p和q。

（2）计算两个素数的乘积n=p× q。

（3）计算欧拉函数Φ(n)，Φ(n)=(p−1)× (q−1)。

（4）随机选择整数e，要求e满足条件：1<e< Φ(n)，且e和Φ(n)互质。

（5）依据等式e×dmod Φ(n)=1，计算数字d。

被作为公钥的是{e,n}，与之对应的私钥是{d}。此外，数字p、q以及Φ(n)在RSA的加解密过程中不直接使用，但都必须严格保密，防止攻击者通过获取这些信息破解私钥。

举一个简单的例子看，选取素数p=47，q=71，两者的乘积为n=p× q=3337，欧拉函数Φ(3337)=(p−1)× (q−1)=3220。选取e=79，可以求得d=1019。则公钥为{79,3337}，私钥为{1019}。

2.RSA的加密算法和解密算法

RSA公钥密码系统的加密和解密将依据公钥和私钥进行。以mi表示明文，ci为使用公钥{e,n}得到的密文，RSA公钥密码系统的加密过程可以表示为：

ci=miemod n；

RSA的加密过程以指数计算为核心。需要加密的明文消息，一般首先划分为多个消息块，每个消息块由二进制数形式转化为十进制数。在划分的过程中需要保证每个消息块转化得到的十进制数都小于公钥中的数字n，同时，划分得到的每个十进制数的位数通常相同，位数不足的可以采用添加0的形式补足。在加密时每个消息块独立加密。

举例来看，如果要发送的明文消息是“Hello”，该明文消息以ASCII码的形式表示，所对应的二进制字符串为“01001000 01100101 01101100 01101100 01101111”，消息中每8位转化为一个十进制数，可以得到“072 101 108 108 111”，其中数字72由于不满3位，特别在头部增加0补足为3位。

采用公钥{79,3337}对“072 101 108 108 111”加密，明文划分为m1=072，m2=101，m3=108，m4=108，m5=111等5个明文块。m1的加密过程为c1=m1emod n=7279mod 3337=285，m2的加密过程为c2=m2emod n=10179mod 3337=1113。类似地，可以计算得到其他密文块。为了保证各密文块位数相同，通常也会采用在密文块头部增加0的方式补足密文块的位数。

密文块的解密依据私钥进行。在RSA公钥密码系统中，对于密文块ci，使用私钥{d}将其解密恢复明文mi的过程可以表示为：

mi=cidmod n；

例如，在之前的例子中，通过公钥{79,3337}对“072 101 108 108 111”加密，m1的密文c1为285，m2的密文c2为1 113。采用私钥{1019}解密，m1=2851019mod 3337=72，m2=11131019mod 3337=101。解密能够将明文恢复。

为了确保RSA密码的安全，必须认真选择密码参数，基本原则如下：

① p和q要足够大。对于一般应用而言，p和q应为512 b，而对于重要应用，p和q应为1 024 b及以上。

② p和q应为强素数。已有文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。

③ p和q的差要大。

④ (p-1)和(q-1)的最大公因子要小。如果(p-1)和(q-1)的最大公因子太大，则易受迭代加密攻击。

⑤ e的选择。随机且含1多就安全，但加密速度慢。于是有学者建议取e=216+1=65537。

⑥ d的选择。d要足够大，不能太小。

⑦ 不要许多用户共用一个模n，否则易受共模攻击。

3.RSA的安全性与不足

破解RSA的关键是对公钥{e,n}中的n进行因子分解。一旦找到n的两个因子p和q，则可以计算欧拉函数Φ(n)，进而依据条件e×dmod Φ(n)=1，求解出私钥d。

虽然n作为公钥的一部分，完全公开，但是要对其进行因子分解并不容易。RSA在设计时就考虑到“大数分解”是一个数学难题，将整个RSA系统的安全性建立在对n进行分解的困难性上。目前速度最快的因子分解方法，其时间复杂度为exp(sqrt(ln(n)lnln(n)))。n的值足够大时分解因子非常困难。

对n进行因子分解是最直接有效的一种攻击RSA系统的方法。如果随着数学研究的发展，发现“大数分解”问题能够轻松解决，则RSA系统将不再安全。此外，RSA的破解是否与“大数分解”问题等价一直没有能够在理论上得到证明，因此并不能肯定破解RSA需要进行大数分解。如果能够绕过“大数分解”这一难题对RSA系统进行攻击，则RSA系统也非常危险。

Rivest等三位科学家在提出RSA算法时，建议取p和q为100位的十进制数，相应生成200位的十进制数n。按照他们的估算，分解200位的十进制数，如果采用每秒107次运算的超高速电子计算机，大概需要花费108年。随着计算机处理能力的不断提升，特别是通过Internet使大量计算机协同工作，解决一个具体的“大数分解”问题需要的时间越来越短。1999年，美国、荷兰、英国等国的一些数学家和计算机学家通过Internet共同努力，仅仅花费1个月左右的时间就成功分解了长达140位的RSA-140。在这种情况下，为了保证RSA系统的安全，对n值的大小提出了越来越高的要求。目前普遍认为，为了确保安全，n的值应该取到1 024位，最好能够达到2 048位。

RSA公钥密码系统存在的主要缺陷是：加密操作和解密操作都涉及到复杂的指数运算，处理速度很慢。与典型的对称密钥密码系统DES相比，即使在最理想的情况下，RSA也要比DES慢上100倍。因此，一般来说RSA只适用于少量数据的加密和解密。在很多实际应用系统中，RSA被用来交换DES等对称密钥密码系统的密钥，而用对称密钥密码系统加密和解密主体信息。这些应用系统通过混合使用RSA系统和DES系统，将两类密码系统的优点结合在一起。

2.5.2　Diffie-Hellman密钥交换协议

Diffie-Hellman密钥交换算法（简称为“DH算法”或“DH交换”）由Whitfield Diffie和 Martin Hellman于1976提出，是最早的密钥交换算法之一，它使得通信的双方能在非安全的信道中安全地交换密钥，用于加密后续的通信消息。该算法被广泛应用于安全领域，比如HTTPS协议（参见第9章）使用的TLS（Transport Layer Security）和IPsec协议（参见第6章）的IKE（Internet Key Exchange）均以DH算法作为密钥交换算法。

Diffie-Hellman算法的有效性依赖于计算离散对数的难度。下面对离散对数做一个简要介绍。

首先定义一个素数p的原根（也称为“素根”或“本原根”），其各次幂能够产生从1到p-1的所有整数，也就是说，如果a是素数p的一个原根，那么数值amodp,a2mod p,...,ap-1modp是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数，它是整数1到p-1的一个置换。对于任意整数b和素数p的一个原根a，可以找到唯一的指数i，使得b=ai(mod p)，其中0≤i≤(p-1)，指数i称为b的以a为基数的模p的离散对数或者指数，记为dloga,p(b)。当已知大素数p和它的一个原根a后，对给定的b，要计算i，被认为是很困难的，而给定i计算b却相对容易。

假设用户A希望与用户B建立一个连接，并用一个共享的秘密密钥加密在该连接上传输的报文，用户A产生一个一次性的私有密钥XA，并计算出公开密钥YA并将其发送给用户B；用户B产生一个私有密钥XB，计算出公开密钥YB并将它发送给用户A作为响应。必要的公开数值q和a都需要提前知道，或者用户A选择q和a的值，并将这些数值包含在第一个报文中。A和B各自收到对方的公钥后计算出共享密钥K，整个交换过程如图2-34所示。

下面给出一个具体的密钥交换例子。假定素数q=97，取97的一个原根a=5。A和B分别选择私有密钥XA=36和XB=58。

每人计算其公开密钥YA=536mod 97=50，YB=558mod 97=44。在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：

Alice的计算过程：K=(YB)XAmod 97=4436mod 97=75。

Bob的计算过程：K=(YA)XBmod 97=5058mod 97=75。

如果只知道公开密钥50和44，攻击者要计算出75是一个难解问题。

Diffie-Hellman算法具有两个吸引力的特征：①仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会；②除对全局参数的约定外，密钥交换不需要事先存在的基础设施。

算法的不足之处主要有两点：

（1）没有提供双方身份的任何信息，因此易受中间人攻击。

假定第三方C在和A通信时扮演B，和B通信时扮演A。A和B都与C协商了一个密钥，然后C就可以监听和传递通信流量。具体攻击过程如下：B在给A的报文中发送他的公开密钥，C截获并解析该报文。C将B的公开密钥保存下来并给A发送报文，该报文具有B的用户ID但使用C的公开密钥YC，仍按照好像是来自B的样子被发送出去。A收到C的报文后，将YC和B的用户ID存储在一块。类似地，C使用YC向B发送好像来自A的报文。B基于私有密钥XB和YC计算秘密密钥K1。A基于私有密钥XA和YC计算秘密密钥K2。C使用私有密钥XC和YB计算K1，并使用XC和YA计算K2。从现在开始，C就可以转发A发给B的报文或转发B发给A的报文，在途中根据需要修改它们的密文，使得A和B都不知道他们在和C共享通信。

这一缺陷可以通过数字签名和公钥证书来解决。

（2）容易遭受阻塞性攻击。由于算法是计算密集性的，如果攻击者请求大量的密钥，被攻击者将花费大量计算资源来求解无用的幂系数而不是在做真正的工作。

2.5.3　ElGamal公钥密码体制

ElGamal公钥密码体制是由T.ElGamal于1984年提出的，算法既能用于数据加密也能用于数字签名。与Diffie-Hellman算法一样，其安全性也依赖于计算有限域上离散对数这一难题。

1.密钥产生方法

选择一个素数q，获取素数q的一个原根a。其中，q和a是公开的，并且可由一组用户共享。

用户A生成的密钥对如下：

生成一个随机数x作为其秘密的解密密钥，使得1 ≤x≤q– 1，计算y=axmod q，则公钥为(y,a,q)，私钥是x。

2.加解密

如果用户B要向A发送信息，则其利用A的公钥(y,a,q)对信息进行加密，过程如下：

将B要发送的信息表示为一个整数m，其中1 ≤m≤q– 1，以分组密码序列的方式来发送信息，其中每个分块的长度不小于整数q。

（1）秘密随机选择一个随机整数k，1≤k≤p– 1。

（2）计算一次密钥U=ykmod q。

（3）生成密文对(m1,m2)，其中：m1=akmod q；m2=(U×m)mod q。

由于密文由明文和所选随机数k来定，因而是非确定性加密，一般称为随机化加密。对同一明文，由于不同时刻的随机数k不同而得到不同的密文，这样做的代价是使数据长度扩展了一倍，即密文长度是明文的两倍。

解密时通过计算U=m1xmod q恢复密钥，然后恢复明文：m=m2×(U)-1mod q。下面举例说明加解密过程：

假设q=2579，a=2，x=765，计算出公开密钥y=2765mod 2579=949。

取明文m=1299，随机数k=853，则：

U=949853mod 2579=2424

m1=2853mod 2579=435

m2=(2424 ×1299 )mod 2579 ＝ 2396

得密文(435,2396)。

解密时计算m=2396 × (435765mod 2579)-1mod 2579=1299，从而得到明文。

3.安全性分析

关于有限域上的离散对数问题已有很深入的研究，但到目前为止还没有找到一个非常有效的多项式时间算法来计算有限域上的离散对数。通常只要把素数q选得足够大，有限域上的离散对数问题是难解的。在ElGamal密码体制中，从公开的y和a求保密的解密密钥x，就是计算一个离散对数。因此，ElGamal算法的安全性是建立在有限域上求离散对数问题的难解性上。

为了安全，一般要求在ElGamal密码算法的应用中，素数q按十进制数表示，那么至少应该有150位数字，并且q– 1至少应该有一个大的素数因子。同时，加密和签名所使用的k必须是一次性的。如果k不是一次性的，时间长了就可能被攻击者获得。又因y是公开密钥，于是攻击者就可以根据U＝ykmod q计算出U，进而利用Euclid算法求出U-1；又因为攻击者可以获得密文c，于是可根据式c＝Ummod q通过计算U-1c得到明文m。

2.5.4　椭圆曲线密码体制

椭圆曲线密码（Elliptic Curve Cryptography,ECC）是一种公开密钥密码体制，于20世纪80年代由华盛顿大学的Neal Koblitz和IBM的Victor Miller分别独立提出。ECC以椭圆曲线理论为基础，利用有限域上椭圆曲线的点构成的Abel群离散对数难解性，实现加密、解密和数字签名，将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，就可以建立基于椭圆曲线的对应密码体制。ECC的主要优势是密钥小，算法实施方便，计算速度快，非常适于无线应用环境，而且安全性也能与RSA相当。

1.算法描述

ECC是在离散对数问题难解的群上定义的密码算法。设K为一个有限域，而E是域K上的椭圆曲线，则E是一个点的集合：

E[K]={(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6，a1，a3，a2，a4，a6∈K}∪{O}

其中O是无穷远点。在E上定义加法运算：P+Q=R，R是过P、Q的直线与曲线的另一交点关于X轴的对称点，如图2-35所示。当P=Q时，R是P点的切线与曲线的另一交点关于X轴的对称点，如图2-36所示。这样，（E，+）构成交换群（Abel加法群）。

而椭圆群上的离散对数问题（ECDLP）指的是：从椭圆曲线E[K]上的解点所构成的交换群中可以找到一个n阶循环子群，当n是足够大的素数时，这个循环子群中的离散对数问题是困难的。具体而言，设A和B是椭圆曲线上的两个解点，以点A为生成元来生成n阶循环子群，x为一正整数，且，若给定A和x，可以很容易地计算出B=xA，但要是已知A，B点，要想找出x则很困难。

事实上，目前也只有特殊的几类椭圆曲线的ECDLP被解决，大多数一般的ECDLP还不能有效求解。根据这个原理，可以找到一条椭圆曲线Y，将明文编码后嵌入Y的解点中，再对Y进行加密，加密方式可以是我们以前熟知的算法。因此根据加密方式的不同，椭圆曲线密码又可分为ElGamal型，Diffie-Hellman型和RSA型等等。下面以最常用的ElGamal型为例简介其加解密过程：

设椭圆曲线的生成元为A，阶为n。

接收方先随机生成自己的私钥kR，满足1≤kR≤n-1。然后计算并公开公钥。

加密：设S方需向R方传递的明文数据为m，则S先随机选择一个满足条件1≤kS≤n-1的正整数kS，相当于S的私钥，而后计算出自己的公钥BS=kS·A，同时发送方S计算出点P=kS·BR=(Px,Py)，只要Px不为0，则密文c=mPxmod n。S将c与自己的公钥BS一起发送给R方。

解密：R收到c后，先用自己的私钥kR和S的公钥BS求出点P，即P=kR·BS=kR·(kS·A)=kS·(kR·A)=kS·BR，再恢复出明文m=cPx-1modn。

2.安全性分析

首先，ECC依赖的椭圆曲线离散对数难题的计算复杂度是指数级的，而RSA所采用的整数因式分解难题的计算复杂度是亚指数级的，所以椭圆曲线密码从理论上来说更难以攻破，更安全。其次，ECC可以采用比RSA更短的密钥，如表2-3所示，160位长的ECC可以达到与1 024位RSA相同的安全强度，而且所用的系统参数也更短，因此可以加快计算速度。最后，由于ECC将明文嵌入解点集中进行编码，节约了不少存储空间，也节省了传输带宽，在传递短消息时更加有利。正是由于ECC的这些优势，特别适用于航空、航天、移动通信等存储、信道和计算资源都受限的环境。

2.5.5　基于身份标识的密码体制

基于身份标识的密码体制（Identity-Based Cryptograph,IBC），简称为“标识密码系统”或“标识密码技术”，是一种非对称的公钥密码体制，其概念在1984年由Shamir提出。与传统公钥密码一样，每个用户有一对相关联的公钥和私钥。不同的是，标识密码系统使用用户的标识，如姓名、IP地址、电子邮箱地址、手机号码等作为公钥，不需要额外生成和存储，只需通过某种方式公开发布。用户的私钥则由密钥生成中心（Key Generate Center,KGC）根据系统主密钥和用户标识计算得出，由用户秘密保存。由于用户的公钥由用户标识唯一确定，因而不需要第三方来保证公钥的真实性。

2000年，D.Boneh和M.Franklin，以及R.Sakai、K.Ohgishi 和 M.Kasahara两个团队独立提出用椭圆曲线配对构造标识公钥密码，将标识密码从概念推向现实。利用椭圆曲线对的双线性性质，在椭圆曲线的循环子群与扩域的乘法循环子群之间建立联系，构成了双线性DH、双线性逆DH、判决双线性逆DH、q-双线性逆DH和q-Gap-双线性逆DH等难题。当椭圆曲线离散对数问题和扩域离散对数问题的求解难度相当时，可用椭圆曲线对构造出安全性和实现效率最优化的标识密码。

Boneh等人利用椭圆曲线的双线性对得到Shamir意义上的基于身份标识的加密体制。在此之前，一个基于身份的更加传统的加密方案曾被Cocks提出，但效率极低。目前，基于身份的方案包括基于身份的加密体制、可鉴别身份的加密体制、签名体制、密钥协商体制、鉴别体制、门限密码体制、层次密码体制等。

基于身份的标识密码是传统的公钥证书体系的最新发展，国家密码局于2006年组织了国家标识密码体制标准规范的编写工作，并于2007年12月16日正式评审通过了国家IBC标准，给予SM9商密算法型号。IBC密码体系标准主要表现为IBE加解密算法组、IBS签名算法组、IBKA身份认证协议。

标识密码的加解密方案由四部分组成：系统参数生成（Setup）算法、密钥生成（Extract）算法、加密（Encrypt）算法和解密（Decrypt）算法。

Setup算法：给出一个安全参数k，输出系统参数params和主密钥MasterKey。其中，系统参数params是公开的，而主密钥MasterKey只有密钥生成中心知道。

Extract算法：利用params、MasterKey和任意的ID∈{0,1}*,返回私钥PrivateKeyID。ID是任意长度的字符串，并作为加密公钥，PrivateKeyID是解密用的私钥。

Encrypt算法：利用params和公钥ID对明文M进行加密，计算C=Encrypt(params,M,ID)，得出密文C。

Decrypt算法：利用params和私钥PrivateKeyID对密文C进行解密，得出明文M=Decrpyt(params,C,PrivateKeyID)。

标识密码虽然在技术原理上与传统的公钥密码体制属于不同的体系，但在应用上却能对传统的公钥密码构成补充，甚至替代。近年来，标识密码技术得到了蓬勃发展，已在某些政府行政领域和商用领域成功运用。标识密码体系没有证书管理（将在第4章介绍）的负担，简化了实施应用过程，能够快速实现安全通信，尤其适用于安全电子邮件系统、移动通信的客户以及需要向未注册人群发送信息的用户。