第6章非对称密码体制.ppt

《第6章非对称密码体制.ppt》由会员分享，可在线阅读，更多相关《第6章非对称密码体制.ppt（53页珍藏版）》请在优知文库上搜索。

1、第6章 非对称密码体制6.1 概述o 1976年W.Diffie和M.E.Hellman发表了杰出的论文-密码学的新方向，该文奠定了公开密钥密码体制的基础。o 区别于传统的单密钥密码体制(或称对称密钥密码体制)，公开密钥密码体制是所谓的双密钥密码体制，加密密钥可以公开，即任何人都可以用这个公开的密钥进行加密,而相应的脱密密钥是秘密的，任何第三者想利用已知的公开密钥求脱密密钥是计算上困难的。o 只有掌握相应的秘密的脱密密钥的人才可以脱密。第6章 非对称密码体制o 公钥密码体制由于用户私钥的私有性，公钥密码在实现数字签名数字签名和防抵赖性防抵赖性方面有着巨大的优势。注：注：教材的6.1.1节所述内

2、容基本上都是片面的或错误的。o 记E和D分别为加、脱密变换，m为明文，M为明文空间，c是密文，C是密文空间。o 一个公开密钥密码体制必须满足以下基本要求:（1）脱密的唯一性mM，有D(E(m)=m；（2）实现E和D的有效性存在(低次)多项式时间算法实现加、脱密；（3）安全性从已知的加密变换，求得脱密变换D或与等效的D，使得mMM,有D(E(m)=m在计算上是不可行的。其中M是M的一个足够大的子集；（4）可行性 任何用户要构造一对加、脱密密钥是容易的，比如说能使用某种概率多项式时间算法来实现；（5）可交换性C=M，mM，有E(D(m)=m。o 其中的可交换性并不是每一个公钥体制所必备的。如果一个

3、公钥体制满足这一条，那么它就可以用作数字签名。6.2 DH密钥交换协议o 系统包括一个大素数p(512比特长度)以及GF(p)中的本原元g。用户U、V双方要建立共享秘密，步骤如下：1.U从ZP-1中产生一个随机数x，计算X=gxmodp，并将它传送给V；2.V从ZP-1中产生一个随机数y，计算Y=gymodp，并将它传送给U；3.U计算：Yxmodp=gyxmodp V计算：XYmodp=gxymodp于是U、V双方拥有了共享的秘密K=gxymodp。6.2 DH密钥交换协议o D-H密钥建立协议的安全性基础是计算有限域上的离散对数是“困难的”问题。o 中间人攻击UVExy xxgX ygY

4、xgX xgX 6.2 DH密钥交换协议1UV：X=gx modp；2E(U)V：X=gx modp；3VE(U)：Y=gy modp；4E(V)U：X=gx modp；5U计算Xx modp=gxx modp，V计算Xy modp=gyx modp，E计算Xx modp=gxxmodp，Xy modp=gyx modp。于是，U和E共享gxx modp=ku，V和E共享gyx modp=kv，其中E表示攻击者，E(U)和E(V)分别表示E冒充U和V。6.3 RSA公钥密码体制及其实现o 公钥RSA密码体制是1978年由美国麻省理工学院的M.Rivest，A.Shamir和L.Adlman三人

5、提出的，它是建立在大合数分解是计算上不可行基础上的公钥密码体制。1.RSA公钥密码体制及其工作过程o 记ZN*=a:aZN,(a,N)=1，容易证明ZN*对模乘法构成一个交换群，称为模N乘群。o 引理引理 设p和q是两个不同的素数，N=pq，则mZN以及任意的非负整数k，有mk(N)+1=m modN证明证明 若p不整除m，由欧拉定理mp-1=1 modp，从而有6.3 RSA公钥密码体制及其实现mk(N)+1=m modp若p整除m，则m=0 modp，从而仍然有mk(N)+1=m modp因此对于任意的m，恒有mk(N)+1=m modp同理可证对于任意的m，恒有mk(N)+1=m mod

6、q由于p和q是两个不同的素数，从而有 mk(N)+1=m modNo 下面我们介绍RSA的原理及工作过程（1）首先随机选取两个大素数p和q，pq，并计算出N=pq及(N)=(p-1)(q-1)；（2）选取加密指数e:(e,(N)=1，并利用欧几里德算法求出的逆元d(de)，使得ed=1 mod(N)其中d脱密指数；（3）公开密钥：N和e；（4）秘密密钥：d和（p、q）。6.3 RSA公钥密码体制及其实现（5）加密过程）加密过程 如果A要向某用户B传送消息，则A利用B用户公开的加密密钥，计算c=me modN将c传送给用户B；（6）脱密过程）脱密过程 用户B接收到密文c之后，利用自己秘密的脱密密

7、钥d，计算cd modN从而得到m=cd modN。例：B选择素数p=7，q=17，则N=pq=119，(N)=(7-1)(17-1)=96B选择加密指数e=5，这里5与96互素，由欧几里德算法得到(N)=19e+1，即1(N)+(-19e)=1因此d=-19=77 mod(N)，于是e=5和N=119是B的公钥，d=77是B的私钥。o 现假设A想发送明文m=19给B，A计算：c=me modN=195 mod119=66 并将c发送给B，B收到后，计算：cd modN=6677 mod119=19从而得到明文m。6.3 RSA公钥密码体制及其实现2.RSA公钥密码体制的实现o 从目前的密码分

8、析水平来看,要想实现一个安全的RSA公钥密码体制,大合数的规模至少要在1024比特以上，因此是否存在有效的随机产生大素数的算法以及RSA在这种规模下的加、脱密运算的速度等问题自然提了出来。（1）产生大素数的算法o 判定一个非负整数是否为素数的工作称为素性检测，我们介绍Rabin提出的有效的产生素数的概率算法-素素性检测算法性检测算法，这个算法的原理基于欧拉定理，即：6.3 RSA公钥密码体制及其实现aZn*，有a(n)=1 modn。而当n是素数时，有an1=1 modn 设n2，则n是奇数，令n-1=2eu，其中2不能整除u，这样上式变为:则下式至少有一个成立：au=1 modn或存在一个i

9、(0ie-1)，使得naaeiuuimod0)1()1(102nauimod12o 由此Rabin引入了素性集：o 判定n是素数的算法如下：step1：任取一个大奇数n；Step2：取a2,3,n-1；Step3：如果(a,n)=1，且a不属于Pn，则n是素数，否则n是合数。o Rabin证明了由上述算法所产生的素数的误判概率为 o 根据这个结论,我们将算法中的第(2)和(3)步骤重复k次，这样判定n为素数的误判概率小于或等于4-k。关于这一点的证明请参看相关文献。mod1,mod1:2*naeinaZaPuunni且41)(*nnnZPZnnP是合数数判定为素6.3 RSA公钥密码体制及其实

10、现（2）有关RSA算法实现的几个问题o 关于加法、减法和乘法 按照系统指令所能支持的最大的字展开进行运算。o 利用窗口法进行指数运算 以512比特加密指数为例：其中加密过程为：me modN=5115112210222eeeee511,2,1,0,2iZeiNmmmmeeeemod)(015105112226.3 RSA公钥密码体制及其实现o 在上述计算过程中，对e是按比特进行处理的，为加快实现速度，我们可以对e按两位或三位进行处理(这取决于模数的规模和运算的软、硬件环境)，以两位为例得到:其中o 当要对明文进行加密时，可先进行预处理，计算出和,这种方法我们称之为窗口法。通过实验证明，这种方法

11、对提高RSA的加、脱密速度是十分有效的。2552552210444eeeee255,2,1,0,4iZeio 模数处理方法 第一种方法：先预计算模数N的倍数；第二种方法：直接进行除法运算；第三种方法：蒙哥马利方法。o 提高脱密运算速度的一种方法普通的脱密运算为m=cd modN，现在记 c1=c modp，c2=c modqd1=d mod(p-1)，d2=d mod(q-1)m1=m modp，m2=m modq则由c1、c2、d1、d2求得利用孙子定理，由同余式组即可求出明文m。,mod111pcmdqcmdmod222qmmpmmmodmod216.3 RSA公钥密码体制及其实现o RS

12、A设计的基本要求以及安全性分析 1.RSA设计的基本要求（1）p和q不能太接近o 由于(p+q)2=4N+(p-q)2如果p和q太接近，则|p-q|就相对地较小，这样我们就可以通过穷尽p-q，求出p+q，从而得到p和q。o 注意开平方运算存在多项式时间算法。6.3 RSA公钥密码体制及其实现（2）p+1、p-1和q+1、q-1不能有太多的小因子，必须存在大的素因子o 如果p+1、p-1和q+1、q-1由小的素因子乘积而得，我们就可以通过穷尽小素数的方法，根据已知的N，有可能求出p和q。o 由此，在许多的场合都要求p和q是安全素数安全素数 定义定义：设p是素数，p2，p=2p1+1，若p1仍然是

13、素数，则称p是安全素数。（3）脱密指数d应满足o 否则，可由连分数的方法进行攻击。o 另外，还可能要求加密指数e为错乱指数。Nd22log41log6.3 RSA公钥密码体制及其实现（4）模数规模o 从目前的攻击水平看,模数的位数应至少设计在1024比特以上,取2048比特更为安全。o 这种增加的安全性是以牺牲运算速度和增加软硬件资源为代价的。2.RSA公钥密码体制的安全性分析结论1:求(N)的难度与分解N的难度等价。证明：如果能分解N，则就可以求出(N)。反之，如果能求出(N)，则由(p+q)=N-(N)+1，以及pq=N或，便可求出p和q。Nqpqp4)(26.3 RSA公钥密码体制及其实

14、现结论2:求脱密指数d的难度与分解N等价。该定理的证明比较复杂，这里略去。结论3:求(N)的难度与分解N等价。结论4:能够猜出1比特明文信息的难度与猜出整个明文的难度等价。结论5:由非平凡不动点可能分解N。o 所谓不动点,即使得me=m modN明文m。o 显然对于任意的RSA体制，m=0,1,-1均为其不动点，这些不动点，被称为平凡不动点。o 该结论的证明与结论2的证明过程类似。3.共模RSA公钥密码体制 的安全性分析o 如果若干个用户同时共用相同的合数N(即共模)，那么这时的RSA体制安全性又有其新的特点。结论1:已知一对加、脱密指数时，即可分解公用的模数N。这一结论的证明与结论2的证明过

15、程类似。结论2:已知一对加、脱密指数时，不分解也可以求出其它用户等价的脱密密钥。如果已知加、脱密密钥eA和dA，则可求出eAdA-1，而eAdA-1是(N)的倍数，从而可由公开的其它用户的加密密钥eB，求出等价的脱密密钥dB。3.共模RSA公钥密码体制 的安全性分析结论3:通播信息是不安全的。如果某一用户向n个其它用户发送相同的消息m，于是攻击者就可以得到：c1=me1，c2=me2，cn=men modN 如果n比较大。我们就有很大的可能性找到两个互素的加密指数，设为ei和ej满足(ei,ej)=1，于是存在s和t，使得eis+ejt=1，这样就可以由截获的密文ci和cj通过下式：ciscj

16、t=meismejt=m modN从而得到明文。6.4 非对称密码体制 -椭圆曲线密码体制(ECC)o 椭圆曲线的概念与分类 椭圆曲线是一个具有两个变元的三次方程，它是满足y2+axy+by=x3+cx2+dx+e 的所有点(x,y)的集合，外加一个零点或无穷远点。6.4 非对称密码体制-ECC1有限域GF(p)上的椭圆曲线y2=x3+ax+bmodp其中a,bGF(p),x,y均在GF(p)中取值。定理：(Hasse定理)如果E是定义在GF(p)上的椭圆曲线，N是E上的点的个数，则|N-(P+1)|2p1/2 6.4 非对称密码体制-ECC例：GF(23)上的一个椭圆曲线为y2=x3+x mod23，则该方程在GF(23)上的解（即该椭圆曲线上的点）为(0,0),(1,5),(1,18),(9,5),(9,18),(11,10),(11,13),(13,5),(13,18),(15,3),(15,20),(16,8),(16,15),(17,10),(17,13),(18,10),(18,13),(19,1),(19,22),(20,4),(20,19),(21,6),(21,17)