密码学课件：八、公钥密码体制

1、公钥密码体制主要内容概述公钥密码的应用RSA公钥密码体制ElGamal公钥密码体制椭圆曲线密码体制概述公钥密码体制提出的背景（1）在对称密码体制中，密钥分发过程复杂，代价高。安全信道的建立是突出问题。（2）密钥量增大造成密钥管理困难。当用户增多，密钥量增加，密钥管理复杂化。如n个用户两两保密通信，则每个用户需要获取并保管(n-1)个密钥，总密钥量为n(n-1)/2，当n=100时，密钥量是4995个；当n=5000时，密钥量是增加到超过1200万个。概述公钥密码体制提出的背景（3）保密通信系统的开放性差。如果收发双方素不相识，或没有可靠的密钥传递渠道，则无法通信。（4）存在数字签名的困难性。当

2、用对称密码算法实现数字签名时，由于通信双方拥有相同的密钥，使得接收方可以伪造数字签名，发送方可以抵赖发送过的消息。概述公钥密码体制的发展是密码学历史上的一次革命，有着极其重要的历史里程碑意义。公钥密码体制出现之前的几乎所有的密码系统都建立在基本的代替和换位基础上（如DES、AES等）公钥密码体制与以前的方法不同，基于一种特殊的数学函数而不是代替和换位操作公开密钥体制不对称，有两个密钥，一个公钥，一个私钥。概述基本思想所有用户的公开密钥可以被其他所有用户访问，每一个用户的解密密钥将由用户保存并严格保密。一般公钥密码体制的示意图：KUB为公钥，KRB为私钥。概述基本思想公钥密码体制的要求：（1）D

3、KRB(c)是EKUB(m)的逆变换DKRB(c)= DKRB(EKUB(m)=m（2）在已知加密密钥或解密密钥时，相应的加密或解密计算是容易的（3）如果不知道私钥KRB，那么即使知道公钥KUB 、具体的加密与解密算法以及密文，确定明文是计算上不可行的。单向函数定义：设定义域为X，值域为Y，函数y=f(x)称为单向函数：如果对于所有xX计算f(x)都是“容易的”，而对于“基本上所有yY”发现任意一个xX满足f(x)=y都是“计算不可能的”。xf(x)HardEasy单向陷门函数定义：单向陷门函数是单向函y=f(x)再附加如下特性：如果给定一些附加信息，这些附加信息称为陷门信息K，那么，就对任意

4、yY求解xX满足fK(x)=y都变得“容易了”。xf(x)HardEasyEasyK概述因此设计公钥密码体制就变成了寻找单向陷门函数，目前基于的单向函数设计的公钥密码体制：（1）大整数分解问题（公钥密码体制RSA）（2）有限域上的离散对数问题（公钥密码体制ElGamal）（3）椭圆曲线上的离散对数问题（公钥密码体制ECC）公钥密码的应用1. 用于数据加密实现机密性要求对数据进行加密：发送方用接收方的公钥加密消息，接收方用自己的私钥解密。2. 用于数字签名发送方用自己的私钥签名消息，接收方通过发送方对应的公钥来鉴别消息，并且发送方不能对自己的签名进行否认。公钥密码的应用3. 用于密钥分发和协商在

5、公开信道上进行大规模的密钥分发和协商。公钥密码算法运算量大，相对而言，对称加密算法运算量小。如AES在256个元素的范围内运算，基本的运算如乘法、求逆可通过“查表”来完成，效率非常高。故一般不直接用公钥密码系统来加密量大的数据。一般采用混合体制：用公钥密码体制加密对称密码体制短期所需的一个密钥来进行分发，用对称体制加密数据。RSA公钥密码体制对称密码体制# 加密密钥与解密密钥同：K1=K2在通信前，由发送方生成密钥，通过安全信道送到接收方。非对称密码体制# 加密密钥与解密密钥不同：K1K2在通信前，每个用户都有一对用于加密和解密的密钥对，公钥可以发布，私钥自己保管。RSA由MIT的Ron Ri

6、vest、Adi Shamirh和LenAdleman在1978年提出。RSA取名来自开发他们三者的名字。已成为公钥密码的国际标准数学基础是欧拉定理，安全性建立在大整数因子分解的困难性之上。基于数论事实：将两个大素数相乘很容易，反过来对乘积进行因式分解非常困难。RSA算法描述初等数论中的三个定理和两个定义：欧拉函数的定义：设nZ且n1，将小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。定理1：设m1,m2N，gcd(m1,m2)=1，则(m1m2)=(m1)(m2)。定理2：如果p为素数，则(p)=p-1欧拉定理：设m是正整数，且gcd(a,m)=1，则a(m)1 mod m乘法逆

7、元的定义：设a，nZ且n1，如果存在bZ使得ab1 mod n，则a,b称为互为模n的乘法逆元，记为ba-1 mod n。1.密钥生成（1）选择两个随机的大素数p和q，并计算n=pq和(n)=(p-1)(q-1)（2）选择一个随机数e,1e(n)，满足gcd(e,(n)=1，并计算d=e-1 mod (n)（3）公钥为(e, n)，私钥为d。RSA算法描述RSA算法描述2.加密对明文mn，其对应的密文为c=me mod n3.解密对密文c，其对应的明文为m=cd mod nRSA算法描述对算法的说明：RSA密码体制中用到两个群：群(Z(n), )和群(Zn, )（1）群(Z(n), )密钥对(

8、e,d)的产生的乘法运算是在群(Z(n), )中，此时， ed=1 mod (n)即，在群(Z(n), )中，元素d是元素e的逆元。（2）群(Zn, )加密运算c=me mod n与解密运算m=cd mod n中的乘法运算是在群(Zn, )中，n=pq。RSA算法描述进一步说明：因在群中运算，必须满足群运算的条件如下。（1）1e(n)：若e1e2 mod (n)，则对所有的明文x，有xe1xe2 mod n，因此公钥e的只需在范围(1e(n)中选择。（2）e与(n)互素：保证e模(n)的乘法逆d存在，e、d互为乘法逆，所以d也与(n)互素。（3）规定明文mn，则(m-tn)e mod n=me

9、 mod n，tZ即m-tn与m的加密结果相同，这样使得解密结果唯一。RSA算法描述下面证明加密和解密是逆运算。m必与p和q中至少一个互素。否则，若与p和q都不互素，因p和q都是素数，则m必是p和q的倍数，故也是n的倍数，这与mn矛盾。另： de=1 mod (n)故存在整数k满足： de=k(n)+1分两种情况讨论：RSA算法描述（1）m仅与p和q两者之一互素，不凡设仅与p互素，则m是q的倍数，那么存在整数a使得m=aq，由欧拉定理：mk(n)mk(p)(q)(m(p)k(q)1 mod p于是存在整数t使得：mk(n)=tp+1两边同乘 m=aq得： mk(n)+1=tapq+m=tan+

10、m由此得： cd=med=mk(n)+1=tan+mm mod nRSA算法描述（2）如果m与p和q都互素，那么m也和n互素，有cd=med=mk(n)+1=m(m(n)km mod n证毕。RSA算法描述第二种方法证明加密和解密是逆运算。先介绍模运算的两个性质：（1）p和q互素，若x mod p=0，且x mod q=0，则x mod pq=0（2）p和q互素，若y mod p=x，且y mod q=x，则y mod pq=x。RSA算法描述第二种方法证明加密和解密是逆运算。由于： de=1 mod (n)故存在整数k满足： de=k(n)+11.当gcd(m,p)=1，由费尔马小定理有mp

11、-1=1 mod p故有med=mk(n)+1=mk(p-1)(q-1)+1=m(m(p-1)k(q-1)m mod p2.当gcd(m,p)=p时，medm mod p显然成立。RSA算法描述同样可推出：med=mk(n)+1 m mod q故有：cdmed=mk(n)+1 m mod nRSA算法描述例，用户B取p=47，q=71，n=pq=4771=3337，(n)=4670=3220。设e=79,用扩展欧几里得算法：d=e-1 mod (p-1)(q-1)=79-1 mod 3220=1019因此B的公钥为(3337,79)，私钥为1019.假定用户A将消息688加密后发给B，A首先获

12、得B的公钥(3337,79) ，然后计算出密文c=68879 mod 3337=1570并把密文发给B。B收到密文后，用私钥进行解密m=15701019 mod 3337=688思考题：公钥为(e, n)，私钥为d，设m=(n)=(p-1)(q-1),有ed1 mod m针对给定的n，满足条件的密钥对(e,d)有多少？说明：e与(n)互素，且1e(n)，所以e的数量最多有(n)= (p-1)(q-1)个。对每个选定的e，其乘法逆d即是同余方程ex1 mod m的解。方程的解的数量是满足条件的同余类的数量，模m的同余类最多有m个。因此在1e,de(e+1)/2时，运用低指数攻击法便可求出m。选型

13、e为16位的素数，是一种可加速加密运算并同时可以避免低指数攻击法的选择。为避免第3种攻击，e应选择在其模(n)时的阶最大，即ei=1 mod (n)中最小的i为i=(p-1)(q-1)/2。RSA在应用中的问题6.私钥d长度应大于n长度的1/4在许多应用场合，人们常常使用位数较短的私钥d，以降低解密或签名的时间，尤其是在智能卡的应用中，因其CPU的处理能力低。若d的长度很小，则猜测d的空间变小。1990年Wiener提出一种针对d长度较小的攻击方法，证明了若d的长度小于n长度的1/4，利用连分数算法，可以求出正确的d。考虑实际使用和安全性，一般尽量降低e的长度而不应降低d的长度。RSA在应用中

14、的问题7.不可使用公共的模nRSA使用公共模n有很多优点：密钥管理简单，节省公钥的存储空间，但存在风险。相同的明文分别发送给两个不同的人i，j，公钥为ei，ej，且互素，ci=mei mod n，cj=mej mod n。由扩展欧几里得算法可求得两个整数r及s使得rei+sej=1，显然r和s一定有一个负数。假设r为负，若ci与n互素，则ci乘法逆元存在，并轻易求得ci-1，因此易得明文m：(ci-1)|r|(cj)s=(mei)-|r|(mej)s=mrei+sej=m mod n。若ci与n不互素，则可以利用最大公因子方法求出ci与n的最大公因子，即为p或q，进而分解n。RSA在应用中的问

15、题8.不仅要注意私钥d和大素数p、q的保密，还要保密(n)（1）若(n)已知，则能确定e模(n)的乘法逆元，即d=e-1 mod (n)（2）(n)=(p-1)(q-1)=pq-p-q+1=n-(p+q)+1(p+q)=n+1-(n)(p-q)2=(p+q)2-4pq=(p+q)2-4n从而求出p+q和p-q，进而可以求出p、q。RSA在应用中的问题9.避免不动点问题每个RSA系统都存在不动点，即存在特定的明文m1）成立的最小正整数n为a模p的阶。如果a模p的阶n=(p)，则称a为p的本原根。概述设p为素数，a是p的本原根，则在模p下a mod p, a2 mod p, a3 mod p, a

16、p-1 mod p产生1到p-1之间的所有值，且每个值仅出现一次。因此：对任意bZp*=1,p-1，都存在唯一正整数kZp*，使bak mod p。这样，模指数函数yax mod p是Zp*到Zp*的一一映射。概述对映射yax mod p， xZp*进行变换，使得y作为自变量，x作为因变量，表示成：xlogay mod p。上式称x为模p下以a为底y的对数。由于运算定义在Zp*上，所以称为离散对数运算。概述在实数域上，设a,b,cR，如果a=bc，则称c是以b为底a的对数，记作c=logba，a0。如果a,b为实数，计算c容易，如果a,b为有限域中的元素，求正整数n，使a=bn，则是一个很困难

17、的问题。概述针对函数yax mod p和xlogay mod p：如果已知a、x、p，使用快速指数算法容易计算得到y，反过来，如果仅知a、p和y，当p较大时（如p的长度在150位以上）计算xlogay mod p非常困难。ElGamal密码体制基本以上计算的困难性之上。密钥的生成选取一个大素数p，aZp*是p的一个本原根。随机生成一个整数x，2xp-2，并计算：y=ax mod p。以（p,a,y）作为公钥，x作为私钥。加密设用户想加密的明文为m3的素数)上的一条椭圆曲线产生的循环群，对于Ep(a,b)上任意两点P和Q，寻找一个整数k3的素数)上的一条椭圆曲线产生的循环群，任取gEp(a,b)

18、，再取正整数xp，计算y=xg。公钥为g、y、p，私钥为x。（因Ep(a,b)为循环群，故任意元素g是其生成元，即Ep(a,b)=gk|kZ。）椭圆曲线密码算法加密变换对于明文m，随机选取正整数kp，计算c1=kg和c2=mky。密文为c=(c1,c2)解密变换m=c2(-xc1)加解密互逆验证：c2(-xc1)=(mky)(-xkg)=(mkxg)(-xkg)=m密文依赖于明文和随机数k，因此一个明文对于多个密文，即密文具有“非确定性”。椭圆曲线密码算法总结对任意素数p构造一个有限域GF(p)即（Zp,+p,p），Zp=0,1,2,p-1。任取a,bZp，定义a+pb=(a+b) mod p

19、, apb=(ab)mod p。构造循环群(E,)，集合E中的元素除无穷远点O之外，都由序偶(x,y)构成，且x和y都来自于有限域GF(p)，两者之间的关系由椭圆曲线方程： y2x3+ax+b (mod p)（ 4a3+27b20 mod p，a,bZp）进行约束。根据椭圆曲线的特性，可得(x1,y2)(x1,y2)运算的具体实现方法。在循环群(E,)上数乘的逆运算即是离散对数难题。例：取g=(2,7)为E11(1,6)的生成元，假设某用户的私钥是x=7，那么y=7g=(7,2)，公钥(g,y,p)=(2,7), (7,2),11)。假设有一明文消息m=(10,9)，取k=3，密文计算如下：c

20、=(c1,c2)=(kg,mky)=(3g,(10,9)3(7,2)=(8,3),(10,9)(3,5)=(8,3),(10,2)解密：m=c2(-xc1)=(10,2)(-7(8,3)=(10,2)(-(3,5)=(10,2)(3,6)=(10,9)算法中的运算都是群Ep(a,b)上元素的加法运算，因此要用某种编码方式将原始的明文消息m嵌入到Ep(a,b)的点上，然后才能使用群Ep(a,b)的运算规则进行运算。明文信息嵌入椭圆曲线明文信息嵌入椭圆曲线一个算法设椭圆曲线E：y2x3+ax+b (mod p)，p为素数。数字明文m将被植入一个点G(x,y)的x坐标。设x=mK+j，0jK，其中K

21、表示一个大整数。明文信息嵌入椭圆曲线(1)计算G(x,y)的x坐标step 1：取整数K，使m满足(m+1)K2160）曲线阶的大素数因子不能整除pk-1(1k20)对于二进制域F(2m)，m不能为合数。公钥密码体制总结单向函数定义：设定义域为X，值域为Y，函数y=f(x)称为单向函数：如果对于所有xX计算f(x)都是“容易的”，而对于“基本上所有yY”发现任意一个xX满足f(x)=y都是“计算不可能的”。xf(x)HardEasy单向陷门函数定义：单向陷门函数是单向函y=f(x)再附加如下特性：如果给定一些附加信息，这些附加信息称为陷门信息K，那么，就对任意yY求解xX满足fK(x)=y都变得“容易了”。xf(x)HardEasyEasyKRSA算法基于大整数分解问题的难解已知公钥(e,n)和明文m，加密计算c=me mod n很容易；但是已知c、n、e，解密计算m很难