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

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

2、误的。 记E和D分别为加、脱密变换，m为明文，M为明文空间，c是密文，C是密文空间。 一个公开密钥密码体制必须满足以下基本要求:,（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。 其中的可交换性并不是每一个公钥体制所必备的。 如果一个公钥体制

3、满足这一条，那么它就可以用作数字签名。,6.2 DH密钥交换协议,系统包括一个大素数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密钥交换协议,D-H密钥建立协议的安全性基础是计算有限域上的离散对数是“困难的”问题。 中间人攻击,6.2 DH密钥交换协议

4、,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公钥密码体制及其实现,公钥RSA密码体制是1978年由美国麻省理工学院的M.Rivest，A.Shamir和L.Adlman三人提出的，它是建立在

5、大合数分解是计算上不可行基础上的公钥密码体制。 1. RSA公钥密码体制及其工作过程 记ZN*=a:aZN,(a,N)=1，容易证明ZN*对模乘法构成一个交换群，称为模N乘群。 引理 设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 modq 由

6、于p和q是两个不同的素数，从而有 mk(N)+1=m modN,下面我们介绍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)=96 B选择加密指数e=5，这里5与96互素，由欧几里德算法得到 (N)=19e+1，即1(N)+(-19e)=1 因此d=-19=77 mod(N)，于是 e=5和N=119是B的公钥，d=77是B的私钥。 现假设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公钥密码体

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

9、 modn 或存在一个i(0ie-1)，使得,由此Rabin引入了素性集： 判定n是素数的算法如下： step1：任取一个大奇数n； Step2：取a2,3,n-1； Step3：如果(a,n)=1，且a不属于Pn，则n是素数，否则n是合数。 Rabin证明了由上述算法所产生的素数的误判概率为 根据这个结论,我们将算法中的第(2)和(3)步骤重复k次，这样判定n为素数的误判概率小于或等于4-k。关于这一点的证明请参看相关文献。,6.3 RSA公钥密码体制及其实现,（2）有关RSA算法实现的几个问题 关于加法、减法和乘法 按照系统指令所能支持的最大的字展开进行运算。 利用窗口法进行指数运算 以5

10、12比特加密指数为例： 其中 加密过程为： me modN=,6.3 RSA公钥密码体制及其实现,在上述计算过程中，对e是按比特进行处理的，为加快实现速度，我们可以对e按两位或三位进行处理(这取决于模数的规模和运算的软、硬件环境)，以两位为例得到: 其中 当要对明文进行加密时，可先进行预处理，计算出和,这种方法我们称之为窗口法。通过实验证明，这种方法对提高RSA的加、脱密速度是十分有效的。,模数处理方法 第一种方法：先预计算模数N的倍数； 第二种方法：直接进行除法运算； 第三种方法：蒙哥马利方法。 提高脱密运算速度的一种方法 普通的脱密运算为m=cd modN，现在记 c1=c modp，c2

11、=c modq d1=d mod(p-1)，d2=d mod(q-1) m1=m modp，m2=m modq 则由c1、c2、d1、d2求得 利用孙子定理，由同余式组 即可求出明文m。,6.3 RSA公钥密码体制及其实现,RSA设计的基本要求以及安全性分析 1. RSA设计的基本要求 （1）p和q不能太接近 由于 (p+q)2=4N+(p-q)2 如果p和q太接近，则|p-q|就相对地较小，这样我们就可以通过穷尽p-q，求出p+q，从而得到p和q。 注意开平方运算存在多项式时间算法。,6.3 RSA公钥密码体制及其实现,（2）p+1、p-1和q+1、q-1不能有太多的小因子，必须存在大的素因

12、子 如果p+1、p-1和q+1、q-1由小的素因子乘积而得，我们就可以通过穷尽小素数的方法，根据已知的N，有可能求出p和q。 由此，在许多的场合都要求p和q是安全素数 定义：设p是素数，p2，p=2p1+1，若p1仍然是素数，则称p是安全素数。 （3）脱密指数d应满足 否则，可由连分数的方法进行攻击。 另外，还可能要求加密指数e为错乱指数。,6.3 RSA公钥密码体制及其实现,（4）模数规模 从目前的攻击水平看,模数的位数应至少设计在1024比特以上,取2048比特更为安全。 这种增加的安全性是以牺牲运算速度和增加软硬件资源为代价的。 2. RSA公钥密码体制的安全性分析 结论1: 求(N)的

13、难度与分解N的难度等价。 证明：如果能分解N，则就可以求出(N)。反之，如果能求出(N)，则由(p+q)=N-(N)+1，以及pq=N或，便可求出p和q。,6.3 RSA公钥密码体制及其实现,结论2: 求脱密指数d的难度与分解N等价。 该定理的证明比较复杂，这里略去。 结论3: 求(N)的难度与分解N等价。 结论4: 能够猜出1比特明文信息的难度与猜出整个明文的难度等价。 结论5: 由非平凡不动点可能分解N。 所谓不动点,即使得me=m modN明文m。 显然对于任意的RSA体制，m=0,1,-1均为其不动点，这些不动点，被称为平凡不动点。 该结论的证明与结论2的证明过程类似。,3. 共模RS

14、A公钥密码体制 的安全性分析,如果若干个用户同时共用相同的合数N(即共模)，那么这时的RSA体制安全性又有其新的特点。 结论1: 已知一对加、脱密指数时，即可分解公用的模数N。 这一结论的证明与结论2的证明过程类似。 结论2: 已知一对加、脱密指数时，不分解也可以求出其它用户等价的脱密密钥。 如果已知加、脱密密钥eA和dA，则可求出eAdA-1，而eAdA-1是(N)的倍数，从而可由公开的其它用户的加密密钥eB，求出等价的脱密密钥dB。,3. 共模RSA公钥密码体制 的安全性分析,结论3: 通播信息是不安全的。 如果某一用户向n个其它用户发送相同的消息m，于是攻击者就可以得到： c1=me1

15、，c2=me2 ，cn=men modN 如果n比较大。我们就有很大的可能性找到两个互素的加密指数，设为ei和ej满足(ei,ej)=1，于是存在s和t，使得eis+ejt=1，这样就可以由截获的密文ci和cj通过下式： ciscjt=meismejt=m modN 从而得到明文。,6.4 非对称密码体制 -椭圆曲线密码体制(ECC),椭圆曲线的概念与分类 椭圆曲线是一个具有两个变元的三次方程，它是满足 y2+axy+by=x3+cx2+dx+e 的所有点(x,y)的集合，外加一个零点或无穷远点。,6.4 非对称密码体制- ECC,1有限域GF(p)上的椭圆曲线 y2=x3+ax+bmodp

16、其中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),

17、(19,1), (19,22), (20,4), (20,19), (21,6), (21,17)，以及无穷远点. 以(11,10)为例: y2=100=8 mod23 x3+x=113+11=1342=8 mod23,6.4 非对称密码体制- ECC,2有限域GF(2m)上的椭圆曲线 y2+xy=x3+ax2+b 其中a,bGF(2m),x,y均在GF(2m)中取值。 例：考虑由多项式f(x)=x4+x+1定义的域GF(24)，基为g=(0010)，实际上该元素对应多项式x。g的各次幂如下：,6.4 非对称密码体制- ECC,g0=(0001),g1=(0010),g2=(0100),g3=

18、(1000) g4=(0011),g5=(0110),g6=(1100),g7=(1011) g8=(0101),g9=(1010),g10=(0111),g11=(1110) g12=(1111),g13=(1101),g14=(1001),g15=(0001) 以上数值的计算过程如下： g2=g*gx2(0100) g3=g*g*gx3(1000) g4x4=x+1(0011) g5x5=x2+x(0110) 实际上，x5+x2+x=x(x4+x+1)=0 modf(x)，所以 x5=x2+x modf(x),6.4 非对称密码体制- ECC,我们定义GF(24)上的椭圆曲线为 y2+xy

19、=x3+g4x2+1 共有16个点： (1,g13),(g3,g13),(g5,g11), (g6,g14), (g9,g13), (g10,g8), (g12,g12), (1,g6), (g3,g8), (g5,g3), (g6,g8), (g9,g10), (g10,g), (g12,0), (0,1), . 以(g5,g3)为例： y2+xy=g6+g5g3=g6+g8=(1100)+(0101) =(1001)=g14 x3+g4x2+1=g15+g4g10+g0=g14,6.4 非对称密码体制- ECC,椭圆曲线的加法规则 用Ep(a,b)表示GF(p)上的椭圆曲线 y2=x3+a

20、x+b modp 上所有点构成的集合(包括无穷远点)，称 =4a3+27b2 为该椭圆曲线的判别式，要求0。 在Ep(a,b)上定义一个加法群运算+，该群运算的几何意义如图所示。,6.4 非对称密码体制- ECC,6.4 非对称密码体制- ECC,设P和Q是椭圆曲线上的两点,L是连接P和Q的直线。如果P=Q，则L就是P点的切线。设直线L与椭圆曲线Ep(a,b)相交于另一点R,过R做y轴的平行线L,记L与椭圆曲线Ep(a,b)相交于另一点，这一点就是P+Q。 当L与y轴平行时,L与椭圆曲线Ep(a,b)没有交点,此时就将P+Q定义为无穷远点。也就是说，两个x坐标相同的点的和是无穷远点，即P(x1

21、,y1)+Q(x1,y2)=，其中y1y2。,6.4 非对称密码体制- ECC,用数学语言描述椭圆曲线Ep(a,b)这个集合上的群运算，有以下规则： 加法规则1：+=。 加法规则2：对于曲线上所有点P，满足P+=P。 加法规则3：对于任意点P，都存在点Q使得P+Q=，称Q为-P(即P与Q互逆)，从而有 R-S=R+(-S)。 加法规则4：满足交换律即P+Q=Q+P。 加法规则5：满足结合律，即 P+(Q+R)=(P+Q)+R。,6.4 非对称密码体制- ECC,加法规则6：对于两个不同而且不互逆的点P(x1,y1)和Q(x2,y2)，这里x1x2，有 P(x1,y1)+Q(x2,y2)=S(x

22、3,y3) 其中 =(y2-y1)/(x2-x1) x3=2-x1-x2 y3=(x1-x3)-y1,6.4 非对称密码体制- ECC,加法规则7：(倍点规则) 2P(x1,y1)P(x1,y1)+P(x1,y1)Q(x3,y3) 其中 y10 =(3x12+a)/2y1 x3=2-2x1 y3=(x1-x3)-y1,6.4 非对称密码体制- ECC,以上定义了GF(p)上的椭圆曲线加法规则，而对于GF(2m)上的椭圆曲线加法规则，需对上述的第6和7条规则修改如下： 加法规则6：对于两个不同且不互逆的点P(x1,y1)和Q(x2,y2)，有 P(x1,y1)+Q(x2,y2)=S(x3,y3)

23、 其中 =(y2+y1)/(x2+x1) x3=2+x1+x2+a y3=(x1+x3)+x3+y1,6.4 非对称密码体制- ECC,加法规则7：(倍点规则) 2P(x1,y1)P(x1,y1)+P(x1,y1)Q(x3,y3) 其中 =(x12+y1)/x1 x3=2+a y3=x12+(+1)x3 定义1：mP=P+P+P 定义2：P是椭圆曲线上的一个点，若存在最小的正整数n，使得nP=，则称n是P点的阶。,例：考虑GF(23)上的椭圆曲线 y2=x3+x+1 mod23 曲线上的两个点P=(3,10)，Q=(9,7)，计算P+Q和2P。 解：这里a=1，b=1。首先求P+Q，这时 =(

24、y2-y1)/(x2-x1)=(7-10)/(9-3) =(-3)/6=20/6=10/3=10*8=80 =11 mod23 x3=2-x1-x2=121-3-9=17 mod23 y3=(x1-x3)-y1 =11(3-17)-10=11*9-10=20 mod23 即P+Q=(17,20)。可以验证(17,20)仍为该椭圆曲线上的点。,6.4 非对称密码体制- ECC,求2P，这时 =(3x12+a)/2y1=(3*32)+1/2*10 =5/20=1/4=1*6=6 mod23 x3=2-2x1=62-2*3=30=7 mod23 y3=(x1-x3)-y1=6(3-7)-10=12

25、mod23 即2P=(7,12)。 可以验证(7,12)仍为该椭圆曲线上的点。,例：我们考虑前面定义在GF(24)上的椭圆曲线 y2+xy=x3+g4x2+1 曲线上的两个点P=(g3,g13)，Q=(g6,g8)，计算P+Q和2P。 解：这里a=g4，b=g0=1。 首先求P+Q，这时 =(y2+y1)/(x2+x1)=(g8+g13)/(g6+g3) =(g3)/(g2)=g3g-2=g x3=2+x1+x2+a =g2+g+g3+g6+g4=g0 y3=(x1+x3)+x3+y1=g(g3+g0)+g0+g13=g13 即P+Q=(x3,y3)=(g0,g13)。 仍为该椭圆曲线上的点。

26、,6.4 非对称密码体制- ECC,求2P，这时 =(x12+y1)/x1=(g6+g13)=g x3=2+a=g2+g+g0=g10 y3=x12+(+1)x3 =g6+(g+g0)g10=g6+g14=g8 2P=(x3,y3)=(g10,g8),仍为该椭圆曲线上的点。,6.4 非对称密码体制- ECC,椭圆曲线密码体制 GF(p)上的椭圆曲线适合软件实现；GF(2m)上的椭圆曲线适合硬件实现。 椭圆曲线离散对数问题：已知椭圆曲线E和点P，随机生成一个整数d，计算Q=dP是容易的，但由给定的Q和P，计算d是困难的。 椭圆曲线密码体制的安全性基础就是建立在曲线点群上的离散对数的难解性之上的。

27、,6.4 非对称密码体制- ECC,1系统的建立和密钥生成 选取一个基域GF(P)和定义在该素域上的椭圆曲线Ep(a,b)，以及该曲线上的一个具有素数阶n的点P(xp,yp)。其中曲线和P(xp,yp)都是公开信息，P(xp,yp)被称为基点。 密钥生成：在区间1,n-1中随机选取一个整数d，计算Q=dP，则点Q和整数d分别为实体的公钥和私钥。 2椭圆曲线加密体制 以下介绍三种椭圆曲线加密体制 ECES、ECELG和ECMO,2.1 ECES-椭圆曲线密码体制 (1) 加密过程 用户A发送消息m给用户B时，A执行以下步骤： step1：查找B的公开密钥Q； step2：在区间1,n-1中随机选

28、取一个整数k； step3：计算(x1,y1)=kP和(x2,y2)=kQ，如果x2=0，返回step2； step4：计算c=mx2，并将(x1,y1,c)传送给B。 (2) 脱密过程 用户B收到密文消息(x1,y1,c)后，使用私钥d计算 d(x1,y1)=dkP=kdP=kQ=(x2,y2) 然后计算cx2-1=mx2x2-1=m。,6.4 非对称密码体制- ECC,2.2 ECELG-椭圆曲线ELGamal密码体制 设mPm是明文空间到椭圆曲线的嵌入(即将明文转化为椭圆曲线上的点)，GE为椭圆曲线的基点。用户A、B分别拥有各自的私钥和公钥： dA、PA=dAG以及dB、PB=dBG (

29、1) B为了向A发送消息m，则B向A发送 (PB,Pm+dBPA) (2) A的脱密过程： (Pm+dBPA)-dAPB=Pm+dBdAG-dAdBG=Pm,例：考虑椭圆曲线E23(13,22) y2=x3+13x+22，G=(10,5) 设用户A的私钥dA=7，则公钥PA=dAG=7G=(17,21); 设用户B的私钥dB=13，则公钥PB=dBG=13G=(16,5). 用户B向A发送编码后的消息为Pm=(11,1)。 step1：B计算 Pm+dBPA=(11,1)+13(17,21)=(18,19) 并将(16,5),(18,19)发送给A。 step2：A计算 (Pm+dBPA)-dAPB=(18,19)-7(16,5)=(11,1) 从而得到编码后的明文消息。,2.2 ELGamal密码体制 为了与ECELG密码体制相比较，继而加深对该体制的理解，下面介绍基于有限域上的ELGamal密码体制。 ElGamal公钥密码体制是由T.ElGamal于1984年提出的，它至今仍然是一个安全性能良好的公钥密码体制。 ElGamal公钥密码体制描述如下： （1）选取大素数p，g是ZP的本原元，p和g公开。 （2）随机选取整数d，1dp-2，计算 D=gd modp， D是用户A公开的加密密钥，d是A保密的脱密密钥。 （3）明文空间为ZP*，密文空间为ZP*ZP