第4章 公钥密码体制

四川大学电子信息学院第1章密码学概述 第2章古典密码技术 第3章分组密码第4章公钥密码体制第5章散列函数与消息鉴别第6章数字签名技术第7章密钥管理技术第8章身份鉴别技术第9章序列密码基础第10章密码技术应用课程主要内容10周讲到……四川大学电子信息学院第4章 公钥密码体制1.对称密码体制的主要问题：一、概述Catch22问题:

保密的关键在于密钥的秘密传送，但你怎样证明你所使用的密钥是安全的？难有充分的证据证明密钥在传输过程中未被窃取、篡改和调换。加密变换E解密变换D明文m密钥源密码分析者明文mKK’X’密文cShannon保密通信模型安全信道普通信道信源信宿四川大学电子信息学院（1）系统开放性差，需要可靠的密钥传递渠道。（2）密钥管理量的困难

传统密钥管理两两分别用一对密钥时则n个用户需要

C(n,2)=n(n-1)/2个密钥当用户量增大时密钥空间急剧增大如:

n=100时，C(100,2)=4,995；

n=5000时，C(5000,2)=12,497,500（3）数字签名的问题对称加密算法难以实现抗抵赖的安全需求。对称密码体制不能满足信息安全需求的发展。四川大学电子信息学院2.公钥密码的基本思想

加密变换E解密变换D明文m密钥源密码分析者明文m公开密钥KeK’X’密文c普通信道秘密密钥Kd公开密钥密码模型信源信宿

公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的.

使用两个密钥：公开密钥和私有密钥；加解密的非对称性四川大学电子信息学院2.1对公钥密码的要求(1)生成密钥对的计算很简单；

(2)发送方A用接收方B的公钥PKB生成密文C，在计算上是容易的。

C=EPKB(M)(3)接收方B用自己的私钥SKB对C解密，在计算上是容易的。

M=DSKB(C)=DSKB(EPKB(M))(4)攻击者通过B的公钥PKB计算出私钥SKB在计算上是不可行的。

(5)攻击者通过B的公钥PKB和密文c还原出明文m在计算上是不可行的。四川大学电子信息学院(1)每个用户都生成一对加密和解密时使用的密钥；

(2)每个用户都在公共位置放置一个密钥，这就是公钥。另一个密钥就是私钥。私钥由用户自己保存，不能公开。

(3)如果A想要向B发送私有信息，A可以用B的公钥加密信息。

(4)当B收到信息时，它可以用自己的私钥进行解密。其他方不能解密信息。即用这种方法，所有的参与者都可以访问公钥，而私钥却有参与者个人拥有，不需传送。2.2公钥密码加密的基本步骤四川大学电子信息学院严格单向函数是满足下列条件的函数f:(1)给定x计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是困难的

(所谓计算x=f-1(y)困难是指计算上相当复杂，已无实际意义)陷门单向函数，存在附加信息k,(1)如果知道k,X,计算Y=fk(X)是容易的。(2)如果知道k,Y,计算X=fk-1(Y)是容易的。(3)如果知道Y,而不知道k,计算X=fk-1(Y)是困难的。因此，研究公钥密码算法就是要找出合适的陷门单向函数。2.3严格单向函数与陷门单向函数的概念：（以上要求的本质是在于要求一个陷门单向函数）四川大学电子信息学院严格单向函数与陷门单向函数的概念(续)1）k称为陷门信息；

2）当用陷门函数f

作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk。f函数的设计者将其保密用作解密密钥，此时称为秘密钥匙记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)。然后送给函数的设计者。当然可以通过不安全信道传送。由于设计者拥有Sk，自然可以解出x=f-1(y)。

3）单向陷门函数的第(3)条性质表明，窃听者由截获的密文y=f(x)推测x是不可行的。说明：四川大学电子信息学院3公钥密码体制的应用

(1)数字签名

(2)密钥分发和协商 (3)加密/解密四川大学电子信息学院4.

两种密码体制的比较对称密码:对明文/密文变换时，加解密密钥相同，或可相互导出；双方在通信前需要安全地协商共享密钥；加解密算法效率较公开密码算法高；系统开放性差，密钥管理复杂；不能提供抗抵赖服务。

公开密码:对明文/密文变换时，加解密密钥不相同，且不可能相互导出；公钥应公开，私钥保密；系统开放性好，密钥管理较容易；可提供抗抵赖服务（数字签名）加解密运算复杂，效率低，不宜作数据加密；存在特有的，“可能报文攻击”的威胁。RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（实现数字签名和公钥密码系统的一种方法，CommunicationsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126)。

该算法的数学基础是初等数论中的Euler(欧拉)定理，并建立在大整数的因子分解困难性之上。是目前应用最广泛的公钥密码算法。只在美国申请专利，且已于2000年9月到期。二、RSA公钥密码体制RivestShamirAdelmanRSA公钥密码体制（续）大素数相乘和因子分解可以被看成一个单向函数：p，qn＝pq困难容易如何根据这个事实构造一个公钥密码体制？考虑：能否用求幂运算来进行加解密？（1）加解密的形式：

C=MemodnM=Cdmodn=(Me)

dmodn=Medmodn{n，e}为公开密钥KU；{d}为私有密钥KR；（2）对此公开密钥算法的要求①存在e,d,n的值,使得对所有的M<n，有Medmodn=Mmodn

②对于所有M<n

的值，要计算Me

和Cd

相对来说是简单的③在给定e

和n

时，计算出d

是不可行的。为什么要用方幂运算？

已有研究表明：以方幂运算构造的加密函数E(m)=me(modn)

是一个单向函数，求逆计算不可行。四川大学电子信息学院Euler定理：设n,m∈Z，且(m，n)=1，则Euler定理的推论

:

给定两个素数p,q，以及整数n=pq和m，其中0<m<n，则，对于任意整数k，有下列关系成立：

m

k(n)+1=

m

k(p-1)(q-1)+1

≡mmodn……(2)(Euler定理要求(m，n)=1，而其推论将m的条件放宽，只要求0<m<n)比较式(1)(2)，考虑：ed=k(n)+1

即ed≡1mod(n)d≡e－1mod(n)根据模运算规则，e在模n下存在乘法逆元的必要条件是e与(n)互素。显然同时有，d与(n)互素。问题：构造e、d、n的值，使得对所有的M<n，有Medmodn=Mmodn……(1)四川大学电子信息学院

1.

RSA算法描述首先明文空间P=密文空间C=Zn①密钥的生成

1.选择两个大素数p，q，（p，q为互异素数，需要保密），

2.计算n=p×q，(n)=(p－1)×(q－1)3.选择整数e使((n)，e)=1,1<e<(n)4.计算d，使d=e－1mod(n),

得到：公钥KU={e,n}；私钥KR={d}对于明文：m<n②加密(用e，n)：密文c=me(modn).③解密(用d，n)：对密文c，明文m=cd(modn)有人将RSA看成是一种分组加密算法：明文和密文在0~n-1之间，n是一个正整数四川大学电子信息学院RSA算法举例

选p=47，q=71，则n=47×71=3337，

(n)=(p－1)×(q－1)=46×70=3220。若选e=79(与(n)互素)，可计算：d=e－1(mod3220)=1019。公开n=3337和e=79。秘密密钥：d=1019。销毁p,q。设M=6882326879666683，如何进行加密？分组得m1=688，m2=232，m3=687，m4=966，m5=668，m6=3

m1的加密为：(688)79(mod3337)=1570=c1，

类似地可计算出其他各组密文，得到

C=c1

c2

c3

c4

c5

c6=15702756209122762423158。验证：第1组密文的解密为(1570)1019mod3337=688=m1。类似地可解出其他各组密文。思考：如果在密码参数生成阶段，p，q不为素数会有什么问题？四川大学电子信息学院RSA的实质

RSA加密实质上是一种ZnZn上的单表代换！给定n=pq和合法明文xZn，其相应密文y=xe

modnZn。对于xx’，必有yy’。

Zn中的任一元素(0,p及q的倍数除外)是一个明文，但它也是与某个明文相对应的一个密文。

因此，RSA是ZnZn的一种单表代换密码，关键在于n极大时在不知陷门信息下极难确定这种对应关系，而用模指数算法又易于实现一种给定的代换。正由于这种一一对应性，使RSA不仅可以用于加密也可以用于数字签字。RSA的安全性是基于加密函数E(m)=me(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。四川大学电子信息学院2.RSA的实现问题（1）加解密运算问题

RSA的加解密运算归结为求一个整数的方幂，再取模。但是，如果直接计算6677mod119，中间结果就已远远超出计算机允许的整数取值范围。思路，①运用模运算的性质

(a×b)modn=[(amodn)×(bmodn)]modn

②提高指数运算的有效性如计算x16若直接计算，需作15次乘法，若按平方运算，即求，x

，x2，x4，x8，x16，

只需要4次乘法！四川大学电子信息学院2.RSA的实现问题（续）（1）加解密运算问题（续）

按此思路，可将计算am(modn)的模乘法的数目缩小到至多为2k，这里的k是指数m的二进制表示比特数。

若设m以二进制形式表示有k比特，即k=[log2m]+1。指数m以二进制形式表示为：四川大学电子信息学院计算am

(modn)，（1）Z=1（2）fori=k－1downto0do{Z←Z2

modn；

ifbi=1thenZ←Z×amodn

}

（乘法次数=k+t，其中t为m中非0位的个数，显然乘法次数至多为2k）平方－乘法算法：四川大学电子信息学院【例】用平方－乘法算法计算152013mod2539解：13=1101(B)，Z=1，a=1520，n=2539b3=1，Z←Z2×a=12×1520≡1520

mod

2539；b2=1，Z←Z2×a=15202×1520≡306mod

2539；b1=0，Z←Z2=3062≡2232mod

2539；b0=1，Z←Z2×a=22322×1520≡95mod

2539；∴152013mod2539=95平方－乘法算法（续）四川大学电子信息学院用中国剩余定理实现RSA的快速计算费马小定理

：若p是素数，且a不被p整除，则：a

p1≡1modp或

a

p

≡amodp等价为：md≡

b1modpmd≡

b2modq……(1)注意同余方程组：计算mdmodn，其中n=pq，p，q为互异素数，d为加解密密钥。因为p，q为素数，所以可用费马定理来简化

md≡

b1modp

md≡

b2modq的运算。四川大学电子信息学院用中国剩余定理实现RSA的快速计算（续）如计算31143mod292143mod2925×(29－1)+3mod2923mod298

mod29这里将式(1)看成是同余方程组，而其中的md为未知量x，由CRT有解：

md≡b1qM1’＋b2pM2’modpq……(2)而其中：b1=mdmodp，b2=mdmodq

qM1’≡1modp，

pM2’≡1mod

q

(可利用扩展Euclid算法计算M1’，M2’)这样，在求出M1’，M2’，b1

，b2后，

即可由式(2)求出md

modn四川大学电子信息学院【例】在RSA公开密钥加密系统中,设密文为c=66，模数n=119，公开密钥指数e=5，求对应的私有密钥指数d和明文m。解：p=7,q=17,(n)=(7－1)×(17－1)=96

私有密钥指数d=e-1mod(n)=5-1mod96=77

明文m

=

cdmod

n=6677mod119=6677mod(7×17)而由费马小定理有：6677≡312×(7-1)+5≡35≡5(mod7)6677≡154×(17-1)+13≡1513≡157+6≡2(mod17)由中国剩余定理有：6677=5×17×M1’+2×7×M2’(mod7×17)并有17×M1’≡1(mod7)，7×M2’≡1(mod17)

利用扩展的Euclid算法：M1’=-2≡5(mod7)，M2’=5故6677=5×17×(－2)+2×7×5≡-100

=19(mod119)或6677=5×17×5+2×7×5(mod119)=19四川大学电子信息学院定理：若p是一个奇素数,则方程x2

≡1modp的解只有

x

≡1或x

≡－1证明：由x2

≡1modp，有x2

－1≡0modp

即：(x－1)(x＋1)≡0modp因此由模运算规则，一定有：p|(x+1)或p|(x－1)，或p|(x+1)且p|(x－1)

若p|(x+1)且p|(x－1)，则存在两个整数k1和k2，使得

(x+1)=k1

p，(x－1)=k2

p，

两式相减得2=(k1－k2)p而

p为奇素数，此式不可能成立，故只有p|(x+1)或p|(x－1)。设p|(x－1)，则由对模p同余的充要条件有，x

≡1modp

类似地可得x

≡－1modp得证考虑定理的逆否命题：如果方程x2

≡1modp存在一解x0∈{1,－1}，则

p不为素数。(2)素数检测（Miller-Rabin的素数概率检测法）四川大学电子信息学院Miller-Rabin的核心算法（WITNESS算法）：WITNESS(a,n)(n是待检验数，a是小于n的整数)将n－1表示成为二进制形式bk-1bk-2…b0；

然后，用平方－乘法算法计算an－1modn

d←1fori=k－1downto0do{

x←d；

d←(d×d)modn；

ifd=1and(x≠1)and(x≠n－1)

thenreturnFALSE；

ifbi=1thend←(d×a)

modn}ifd≠1thenreturnFALSE

；

returnTRUE

For循环结束后，d=an－1modn，由费马小定理，若n为素数，则d为1，因此，若d≠1，

则n肯定不是素数，返回FALSE。

因为n－1≡－1modn，所以(x≠1)and(x≠n－1)

意指x2

≡1modn有非{1,－1}中的根。因此n

肯定不是素数，返回FALSE。四川大学电子信息学院

WITNESS算法特点：

对s个不同的a，重复调用该算法，只要有一次返回为FALSE，就可以肯定n不是素数。

如果算法s次都返回为TRUE，则n是素数的概率至少为1－2－s，因此，对于足够大的s，就可以非常肯定地相信n为一个素数。定理（Wilson定理）：《计算机密码应用基础》

p是一个奇素数的充要条件是：

(p－1)!≡－1modp或(p－1)!+1≡0modp

（也即p|(p－1)!+1）例如，p=5，(p－1)!=2424mod5=4≡－1mod5此定理在理论上具有比较重要的意义。四川大学电子信息学院

使用公开密钥密码系统要求对每个用户产生一对密钥：公钥KU和私钥KR。具体任务包括：

确定两个素数p和q；

选择d或e，并计算另外一个。

注意：n=pq，且是公开的。为抗穷举式攻击，要求p、q应是在一个足够大的整数集合中选取的大数。

选取一个大素数的一般过程：①随机选一个奇数p

（例如使用伪随机数产生器，并使最低位为1）；②确保p不能被任何小素数（<256）整除，如3，5，7，11等等；③随机选一“整数”a<p④完成随机素数性检验，诸如Miller-Rabin。如果p没有通过检验，舍弃值p并转到步骤①。⑤如果p通过了足够多次的检验，就接受p；否则转到步骤③。（3）RSA密钥的产生问题四川大学电子信息学院在SUN工作站SparcII上实现上面描述的方法，其结果如下表。平均时间素数长度2.8秒256位24.0秒512位2分钟768位5.1分钟1024位（3）RSA密钥的产生问题（续）四川大学电子信息学院

确定了p和q以后，就需要选取满足1<e<(n)和((n)，e)=1，并计算d=e－1mod(n)。这一问题可由扩展的Euclid算法完成。密钥产生的一般过程：①产生一个随机数e（例如使用伪随机数产生器）；②判断((n)，e)=1？若不满足则转①；（已证明两个数互素的概率为0.6）③由扩展的Euclid算法计算：d=e－1mod(n)

如果e选择适当，RSA的加密速度将快得多。最常用的三个e值是：3、17、和65537（即216+1）。X.509建议采用65537，PEM中建议采用3，而PKCS#1中建议采用3或65537。

寻找大素数是一项比较繁琐的工作，然而，在RSA体制中，只有在产生新密钥对时才需进行此项工作。(需要产生新的n)

以实现DES每秒1Gbit的硬件实现技术，RSA的硬件加密速度大约为600Kbit（使用一个512bit的模n）,可见RSA比DES大约慢1500倍。软件实现时，DES大约比RSA快100倍，当然，这些数字会随技术的发展而相应发生变化，但RSA永远达不到对称算法的速度。下表给出RSA软件实现的实例。具有8位公开密钥的RSA对于不同长度模数n的加密速度（在SPARCII中）四川大学电子信息学院功能512位768位1024位加密0.03秒0.05秒0.08秒解密0.16秒0.48秒0.93秒签名0.16秒0.52秒0.97秒验证0.02秒0.07秒0.08秒（4）RSA的速度4.RSA的安全性问题

三种对RSA的数学攻击方式：

(1)将n分解为两个素数因子p，q。进而可计算(n)=(p－1)(q

－1)，d=e－1mod(n)

因此，不难得出结论：破译RSA不会比大整数分解更加困难!

思考：用中国剩余定理实现RSA的快速计算有无限制条件？(2)不分解n的因子而计算(n)

如果破译者能够直接求出(n)

，就可以通过

de≡1mod(n)

求出d，从而破译RSA。而一旦知道了(n)，由：

(n)=(p－1)(q

－1)=pq－p－q+1=n－(p+q)+1，可求出:(p+q)=n－(n)+1（1）再由：(p+q)2

－4n=(p+q)2－4pq=(p－q)2

(注意n是公开的)

可求出：(2)RSA的安全性问题(续)在联立求解关于(p+q)和(p－q)的方程(1)(2)，得：

因此，如果能够以一种可行的方法直接得到(n)，那么我们就可以很容易地分解n，所以直接由n确定(n)等价于分解n。

也就是说，由n＝p

q确定(n)和由(n)确定p、q是等价的。

四川大学电子信息学院

假设我们通过一种可行的办法在不分解n的因子或求解(n)的情况下就可以确定d，这样，我们就可以计算(ed－1)，而且(ed－1)是(n)的倍数。利用(n)的倍数，在数学上也可以较容易地分解出n的因子p与q。因此，不难理解，直接计算解密密钥出d并不比对n进行分解更容易。到目前为止，除了进行大数分解以外，人们还没有找到更有效的破译办法来破译RSA。但值得注意的是：虽然人们猜测破译RSA等价于分解n，但目前尚未能证明破译RSA的任何方法都等价于大整数分解问题。(3)不分解n的因子或者求解(n)就确定d目前密码分析者攻击RSA体制的关键点在于如何分解n！四川大学电子信息学院

为保证RSA算法的实际安全性，p与q必为足够大的素数，使分析者没有办法在有限时间内将模n进行分解。对模n的长度要求至少是512bit，EDI标准使用的RSA算法中规定n的长度为512至1024bit之间，但必须是128的倍数，国际数字签名标准ISO/IEC9796中规定n的长度为512bit。随人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。RSA的安全性问题（续）四川大学电子信息学院RSA-129：(n为129位十进制数，大约428bit)

Rivest等人最初悬赏$100的RSA-129，由包括五大洲43个国家600多人参加，用1600台机子同时产生820条指令数据，通过Internet网，耗时8个月，于1994年4月2日利用二次筛法分解出为64位和65位的两个因子，原来估计要用4亿亿年。所给密文的译文为“这些魔文是容易受惊的鱼鹰”。这是有史以来最大规模的数学运算。RSA-130于1996年4月10日利用数域筛法分解出来。RSA-140于1999年2月分解出来。RSA-154(512bit)

于1999年8月被成功分解，历时7个月注。RSA的安全性问题（续）四川大学电子信息学院

虽然512bit模(约154位)在短期内仍具一定安全性，但大素数分解工作在WWW上大协作已构成对512bit模RSA的严重威胁。下表给出以数域筛NFS算法破译RSA体制与用穷搜索密钥法破译对称密码体制的等价密钥长度。对称密码体制RSA体制56-bit384-bit64-bit512-bit80-bit768-bit112-bit1792-bit128-bit2304-bit目前RSA模n的建议长度:1024～2048bitRSA的安全性（续）大整数分解算法研究是当前数论和密码理论研究的一个重要课题四川大学电子信息学院（1）对RSA的选择密文攻击

有些攻击专门针对RSA的实现。他们并不攻击基本的算法，而是攻击协议，攻击有关的安全机制。仅会使用RSA而不重视它的实现是不够的，其实现的细节也很重要。实例：Eve在Alice的通信线路上进行窃听，获取了用Alice公开密钥e

加密的密文C。

前提：Alice用RSA密钥进行加密和签名。对RSA的其它攻击方式：四川大学电子信息学院（1）对RSA的选择密文攻击（续）攻击目标：在不能获得Alice的私有密钥的前提下解密出明文：

M=Cdmodn攻击步骤：

(1)选取一个随机数r(r与n互素)，r<n，然后计算：

x=remodn(显然有：r=xdmodn)y=xCmodn(2)

Eve设法让Alice用她的私有密钥对她以前从未见过的y进行签名。（必须是对消息签名，而不是其散列值签名）：u=ydmodn

(3)然后Eve在模n下计算：

r–1

u≡r–1

yd

≡r–1(xC)d

≡r–1

xdCd

≡r–1r

Cd

≡Cd≡

Mmodn现在Eve就获得了M。对RSA的其它攻击方式（续）四川大学电子信息学院（2）小加密指数e攻击对RSA的其它攻击方式（续）

采用小的e可以加快加密和验证签字的速度，且所需的存储密钥空间小，但若加密钥e选择得太小，则容易受到攻击（多用户环境）。令网中三用户的加密钥e均选3，而有不同的模n1,n2,n3，若有一用户将消息m传给三个用户的密文分别为

y1=m3modn1

；m<n1y2=m3modn2

；m<n2y3=m3modn3

；m<n3

一般选n1,n2,n3互素(否则，可求出公因子，而破坏安全性)，利用中国剩余定理，可从y1,y2,y3求出y=m3mod(n1

n2

n3)。由m<n1,m<n2,m<n3，可得m3<n1

n2,n3，故有因此，如果有相同的消息要传送给多个实体，就不能使用小的加密指数。四川大学电子信息学院5.RSA体制实用中的一些问题(1)不同的用户不可共享模值n(存在公共模数攻击)

主要原因有两个：首先，研究结果表明，由任何一对(ei,di)都能使分解模数n成为可能。另外，假定用户U1与U2共享模数为n，他们的加密密钥分别是e1和e2，且这两个指数又互素即(e1，e2)=1，则攻击者不需要解密密钥d就可恢复出明文。设用户用U1与U2的公钥e1和e2加密明文消息为m，则密文为：

c1=m

e1

modnc2=m

e2

modn而c1或c2又与n互素（概率很大），四川大学电子信息学院5.RSA体制实用中的一些问题(1)不同的用户不可共享模值n(存在公共模数攻击)下面看攻击者如何从n，e1和e2，c1和c2恢复出m。由于e1和e2互素，攻击者由扩展的Euclid算法能找到两个整数s和t，满足：

se1+te2=1s和t中必有一个是负数，假定s为负数，再用扩展Euclid算法可计算c1–1modn然后计算：

(c1–1)–s

×c2t

=(m

–

e1

)–s

×(m

e2

)t=

m

(se1+te2)modn=m四川大学电子信息学院RSA体制实用中的一些问题（续）(2)不同的用户选用的素数不能相同若用户U1与U2选用了同一个素数p，设n1=pq1；n2=pq2分别是他们的模数那么任何人都可以用欧几里得算法求得(n1，n2)=p，从而得到n1与n2的分解式。

所以，不同用户的n必须互素。（3）RSA的不动点问题对明文x，0mn－1，采用RSA体制加密，可能出现

me=mmodn，致使消息暴露。这是明文在RSA加密下的不动点。如m=0，1和n－1。一般有[1+gcd(e－1,p－1)][1+gcd(e－1,q－1)]个不动点。由于e－1，p－1和q－1都是偶数，所以不动点至少为9个。

(证明可参考柯召、孙琦“数论讲义”上P140)

（4）不宜直接用于数据加密四川大学电子信息学院(1)|p－q|很大，通常p

和q

的长度相同（或相差很小）(2)（p－1，q－1）应该较小；(3)p－1和q－1分别含有大素因子，分别记为p1和q1(4)p1－1和q1－1都应有大素因子；(5)p+1和q+1都应有大素因子；满足以上条件的素数称为强素数，据目前的研究对由强素数构成的整数的分解更困难。

（对p，q是否必要是强素数数学界尚存在争论。）为了提高加密速度，通常取e为特定的小整数。如EDI国际标准中规定e=216+1，ISO/IEC9796中甚至允许取e=3，这时加密速度一般比解密速度快10倍以上。（但应避免遭小指数攻击）

此外，研究结果表明：如果e<n且d<n1/4，则d容易被确定。关于素因子p、q的选择问题（增加n被分解的困难性)四川大学电子信息学院三、ElGamal算法ElGamal公钥密码体制是由T．ElGamal于1985年提出的。它至今仍然是一个安全性能良好的公钥密码体制。在论文中，T．ElGamal同时提出了两个算法分别用于数字签名与数据加密。

这里讨论的ElGamal公钥密码体制是论文中提出的用于数据加密的算法，另外的一个算法用于数字签名的体制将在以后描述。四川大学电子信息学院三、ElGamal算法（续）(一)算法描述：系统参数选取大素数p，∈Zp*是一个本原元（生成元）。

p、作为系统参数所有用户共享。系统中每个用户U都随机挑选一个整数xu，2≤xu≤p－2，并计算：

yu=xu(modp)，(若mu取为p－1，则公开密钥cu为1)

yu作为用户U的公开密钥，而xu作为用户U的秘密密钥加解密过程

假设用户A想传送明文M给用户B，用户A将采用如下算法加密消息M。四川大学电子信息学院三、ElGamal算法（续）(一)算法描述：（续）加密过程：(1)用户A先把明文M编码为一个在0到(p－1)之间的整数

m

作为传输的明文；(2)用户A挑选一个秘密随机数k

(

2≤k≤p－2)，并计算：c1＝k

(modp)；c2＝

m·

yBk

(modp)

其中yB是用户B的公开密钥；(4)用户A把二元组(c1,c2)作为其密文传送给用户B。四川大学电子信息学院2．解密算法用户B接收到密文二元组(c1,c2)后，做解密计算：其中xB是用户B的秘密密钥；解密验证：四川大学电子信息学院(1)“非确定性的”。由于密文依赖于执行加密过程的用户A所选择的随机数k

，所以，加密相同的明文可能会产生不同的密文。(2)密文空间大于明文空间。明文空间为Zp*

，而密文空间为Zp*

×Zp*

对于每个明文，其密文由2个Zp*上的元素组成。ElGamal算法特点：过程特点：ElGamal加密体制通过明文m

乘以yBk

掩盖明文，产生c2；同时值c1=k也作为密文的一部分进行传送。

四川大学电子信息学院【举例】

设p=2357及Z2357*的生成元=2，Alice选取私钥xA=1751并计算：xmodp=21751mod2357=1185Alice的公钥：yA=1185加密过程：假设用户Bob想秘密发送消息m=2035给Alice,Bob秘密选取一个随机整数k=1520,并计算：c1=k(modp)=21520mod2357=1430，c2=m·

yAk(modp)=2035×11851520mod2357=697Bob发送(c1,c2)=(1430,697)给Alice。解密过程：Alice收到(1430,697)

后，计算:c2×(c1xA

)－1

(modp)≡

697×(14301751)－1

mod2357

≡697×1430－1751mod2357

≡697×14302357－1－1751mod2357

≡697×1430605mod2357

≡

697×872mod2357

＝2035完成解密。四川大学电子信息学院

1.ElGamal公开密钥密码算法的安全性建立在计算ZP上离散对数的困难性上。2.要使用不同的随机数k来加密不同的信息。

假设用同一个k来加密两个消息m1,m2，所得到的密文分别为(c1,c2)、(c1’,c2’)，则

c2/c2’=m1/m2,故当m1已知，m2可以很容易地计算出来。(二)ElGamal算法安全性

3.随机数k不可预测：若k已知，可从c2直接计算出明文m。四川大学电子信息学院四.椭圆曲线密码体制多数公钥密码(RSA,ElGamal)使用非常大的数或多项式;给密钥和信息的存储和处理带来很大的运算量;椭圆曲线是一个代替，可以用更小的尺寸得到同样的安全性;1985年，NealKoblitz和VictorMiller分别独立地提出了椭圆曲线密码体制;ANSI、IEEE、ISO和NIST都制定了ECC标准草案ECC(EllipticCurveCryptography)四川大学电子信息学院等价安全强度的密钥尺寸大小比较

ECC密钥长度（bit）RSA密钥长度（bit）破解时间(MIPS年)RSA/ECC密钥尺寸比率1065121045：1160102410117：12102048102010：160021000107835：1IEEE，ANSI，ISO，IETF组织的标准化情况：ISO/IEC数字签名标准：ISO14888-3，1998ANSI数字签名标准(ECDSA)：X9.62-1998椭圆算法D-H体制：ANSIX9.63；IEEE1363-2000;FIPS186-2四川大学电子信息学院1.实数上的椭圆曲线所描述的曲线。

其中a1,a2,a3,a4,a5是满足一定条件的实数。

集合包括曲线上的点连同无穷远点O的集合

不同数域上的椭圆曲线的表示和运算是不相同的。“椭圆曲线”并非一定是椭圆，是指由二元三次方程：yxyx四川大学电子信息学院2.椭圆曲线上的加法运算椭圆曲线上的加法运算定义：若P、Q、R三点位于一条直线上，则定义其和为零点（zeropoint）或无穷点(pointatinfinity)：

P+Q+R=OPQR－R=P+Qyx四川大学电子信息学院PQR－R=P+Qyx（2）加法逆元：若P、S位于一条垂线上（x坐标相同），则和曲线交于无穷点，即：P＋S＋O

＝O

P+S=O,即

P＝－S故，ECC上点的加法逆元是：具有相同x坐标和负y

坐标的点。S（1）O称为加法单位元，对ECC上任意点有：P＋O

＝P椭圆曲线上的加法运算(续)四川大学电子信息学院

对ECC上x坐标不同的两点P、Q，由P+Q+R=O有：

P＋Q＝－R－R=2PPRyx(3)

ECC上的点加定义：在ECC上点P做一条切线，设切线与对ECC交于点R，定义：2P=P+P=－R

类似有，3P=P+P+P,kP=P+P+P+…+P(4)

ECC上的倍点运算定义：P+P=2P=?四川大学电子信息学院3.有限域上的椭圆曲线椭圆曲线密码使用系数和变量定义在有限域的椭圆曲线。通常使用的有两类:–定义在素域GF(p)上的Ep(a,b)•useintegersmoduloaprime•bestinsoftware–定义在GF(2n)上的二元曲线E2m(a,b)•usepolynomialswithbinarycoefficients•bestinhardwar四川大学电子信息学院有限域GF(p)上的椭圆曲线曲线方程所有系数都是定义在某一有限域中GF(p)的元素(p为大素数)。典型有限域上的椭圆曲线定义：设p一个足够大的奇素数，有限域Zp

上的椭圆曲线是由一个称为无穷远点的特殊点O和满足同余方程：

y2=x3+ax+b(modp)

的点(x,y)∈Zp×Zp组成的集合E。其中a,b∈Zp,4a3+27b2≠0(modp)一般可用Ep(a,b)表示所定义的椭圆曲线上的点集为：

{(x，y)|0≤x＜

p,0≤y＜

p,且x，y均为整数}∪O四川大学电子信息学院有限域上椭圆曲线上的加法另外，对任意点定义1：设P＝(x1，y1)，Q＝(x2，y2)，且P，Q∈Ep(a,b)，则：（返回）四川大学电子信息学院注意：

1.无穷远点O是零元，有O+O=O，O+P=P2.点P(x,y)的逆元是(x,－y)，有P+(－P)=O3.椭圆曲线关于运算＋构成一个交换群。交换群：又称Abel群，满足交换律、闭合性、存在逆元可用|E|表示有限域上ECC中点的个数，下面定理给出|E|的上下界。Hasse定理:

设E是有限域Zp

上的椭圆曲线，则四川大学电子信息学院方法：对于每个x∈Z11,首先计算z=x3+x+6(mod11)

然后再求同余方程y2=z(mod11)的解来实现。判断z是否是一个模p的平方剩余，可由Euler准则来实现。若p是一个奇素数，则z是模p的平方剩余的充要条件是：根据上面的方法可以确定该椭圆曲线ECC中的所有的点，结果如表所示。例：设p

＝11，ECC是由y2=x3+x+6(mod11)，a=1，b=6，p=11,所确定的有限域Z11

上的椭圆曲线，要求确定ECC中的点。当p≡3

(mod4)，若z是模p的平方剩余，则z的两个模p下的平方根为y：四川大学电子信息学院xy2=x3+x+6(mod11)是否模11的平方剩余y06不是——18不是——25是4，733是5，648不是——54是2，968不是——74是2，989是3，897不是——104是2，9Z11

上椭圆曲线y2=x3+x+6(mod11)中的点椭圆曲线上的点集为：(2,7)，(3,6)，(5,9)，(7,9)，(8,8)，(10,9)，O,共7个元素。四川大学电子信息学院所以，因此，2P＝（5，2）然后根据公式计算3P＝2P+P=(5,2)+(2,7)=(8,3),依次可以计算出kP:P=(2,7)，2P=(5,2),3P=(8,3),4P=(10,2)，5P=(3,6),6P=(7,9),7P=(7,2)，8P=(3,5),9P=(10,9),10P=(8,8)，11P=(5,9),12P=(2,4),13P＝12P＋P＝(2,4)＋(2,7)＝(2,4)＋(2,－4)＝O因此，P=(2,7)是ECC的生成元，ECC是一个循环群。考察ECC上一点P(2,7)的倍点运算：

（公式）