第6章 非对称密码体制6.1 概述o1976年W.Diffie和M.E.Hellman发表了杰出的论文-密码学的新方向，该文奠定了公开密钥密码体制的基础。o区别于传统的单密钥密码体制(或称对称密钥密码体制)，公开密钥密码体制是所谓的双密钥密码体制，加密密钥可以公开，即任何人都可以用这个公开的密钥进行加密,而相应的脱密密钥是秘密的，任何第三者想利用已知的公开密钥求脱密密钥是计算上困难的。o只有掌握相应的秘密的脱密密钥的人才可以脱密。非对称密码体制第6章 非对称密码体制o公钥密码体制由于用户私钥的私有性，公钥密码在实现数数字字签签名名和防防抵抵赖赖性性方面有着巨大的优势。注注：教材的6.1.1节所述内容基本上都是片面的或错误的。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其中的可交换性并不是每一个公钥体制所必备的。 如果一个公钥体制满足这一条，那么它就可以用作数字签名。非对称密码体制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密钥交换协议oD-H密钥建立协议的安全性基础是计算有限域上的离散对数是“困难的”问题。o中间人攻击非对称密码体制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三人提出的，它是建立在大合数分解是计算上不可行基础上的公钥密码体制。 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 modq由于p和q是两个不同的素数，从而有 mk(N)+1=m modN非对称密码体制o下面我们介绍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之后，利用自己秘密的脱密密钥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从目前的密码分析水平来看,要想实现一个安全的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(0ie-1)，使得非对称密码体制o由此Rabin引入了素性集：o判定n是素数的算法如下：step1：任取一个大奇数n；Step2：取a2,3,n-1；Step3：如果(a,n)=1，且a不属于Pn，则n是素数，否则n是合数。oRabin证明了由上述算法所产生的素数的误判概率为 o根据这个结论,我们将算法中的第(2)和(3)步骤重复k次，这样判定n为素数的误判概率小于或等于4-k。关于这一点的证明请参看相关文献。非对称密码体制6.3 RSA公钥密码体制及其实现（2）有关RSA算法实现的几个问题o关于加法、减法和乘法 按照系统指令所能支持的最大的字展开进行运算。o利用窗口法进行指数运算 以512比特加密指数为例：其中加密过程为： me modN=非对称密码体制6.3 RSA公钥密码体制及其实现o在上述计算过程中，对e是按比特进行处理的，为加快实现速度，我们可以对e按两位或三位进行处理(这取决于模数的规模和运算的软、硬件环境)，以两位为例得到:其中o当要对明文进行加密时，可先进行预处理，计算出和,这种方法我们称之为窗口法。通过实验证明，这种方法对提高RSA的加、脱密速度是十分有效的。 非对称密码体制o模数处理方法 第一种方法：先预计算模数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。非对称密码体制6.3 RSA公钥密码体制及其实现oRSA设计的基本要求以及安全性分析 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仍然是素数，则称p是安全素数。（3）脱密指数d应满足o否则，可由连分数的方法进行攻击。o另外，还可能要求加密指数e为错乱指数。 非对称密码体制6.3 RSA公钥密码体制及其实现（4）模数规模o从目前的攻击水平看,模数的位数应至少设计在1024比特以上,取2048比特更为安全。o这种增加的安全性是以牺牲运算速度和增加软硬件资源为代价的。2. RSA公钥密码体制的安全性分析结论1: 求(N)的难度与分解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。o所谓不动点,即使得me=m modN明文m。o显然对于任意的RSA体制，m=0,1,-1均为其不动点，这些不动点，被称为平凡不动点。o该结论的证明与结论2的证明过程类似。 非对称密码体制3. 共模RSA公钥密码体制 的安全性分析o如果若干个用户同时共用相同的合数N(即共模)，那么这时的RSA体制安全性又有其新的特点。结论1: 已知一对加、脱密指数时，即可分解公用的模数N。这一结论的证明与结论2的证明过程类似。结论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通过下式：ciscjt=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)，以及无穷远点.以(11,10)为例:y2=100=8 mod23x3+x=113+11=1342=8 mod23 非对称密码体制6.4 非对称密码体制- ECC2有限域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 非对称密码体制- ECCg0=(0001),g1=(0010),g2=(0100),g3=(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=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 非对称密码体制- ECCo椭圆曲线的加法规则椭圆曲线的加法规则用Ep(a,b)表示GF(p)上的椭圆曲线y2=x3+ax+b modp上所有点构成的集合(包括无穷远点)，称=4a3+27b2为该椭圆曲线的判别式，要求0。在Ep(a,b)上定义一个加法群运算+，该群运算的几何意义如图所示。非对称密码体制6.4 非对称密码体制- ECC非对称密码体制6.4 非对称密码体制- ECCo设P和Q是椭圆曲线上的两点,L是连接P和Q的直线。如果P=Q，则L就是P点的切线。设直线L与椭圆曲线Ep(a,b)相交于另一点R,过R做y轴的平行线L,记L与椭圆曲线Ep(a,b)相交于另一点，这一点就是P+Q。o当L与y轴平行时,L与椭圆曲线Ep(a,b)没有交点,此时就将P+Q定义为无穷远点。也就是说，两个x坐标相同的点的和是无穷远点，即P(x1,y1)+Q(x1,y2)=，其中y1y2。 非对称密码体制6.4 非对称密码体制- ECCo用数学语言描述椭圆曲线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(x3,y3)其中=(y2-y1)/(x2-x1)x3=2-x1-x2y3=(x1-x3)-y1 非对称密码体制6.4 非对称密码体制- ECC加法规则7：(倍点规则)2P(x1,y1)P(x1,y1)+P(x1,y1)Q(x3,y3)其中y10=(3x12+a)/2y1x3=2-2x1y3=(x1-x3)-y1 非对称密码体制6.4 非对称密码体制- ECCo以上定义了GF(p)上的椭圆曲线加法规则，而对于GF(2m)上的椭圆曲线加法规则，需对上述的第6和7条规则修改如下：加法规则6：对于两个不同且不互逆的点P(x1,y1)和Q(x2,y2)，有P(x1,y1)+Q(x2,y2)=S(x3,y3)其中=(y2+y1)/(x2+x1)x3=2+x1+x2+ay3=(x1+x3)+x3+y1 非对称密码体制6.4 非对称密码体制- ECC加法规则7：(倍点规则)2P(x1,y1)P(x1,y1)+P(x1,y1)Q(x3,y3)其中=(x12+y1)/x1x3=2+ay3=x12+(+1)x3 定义1：mP=P+P+P定义2：P是椭圆曲线上的一个点，若存在最小的正整数n，使得nP=，则称n是P点的阶。 非对称密码体制o例：考虑GF(23)上的椭圆曲线y2=x3+x+1 mod23曲线上的两个点P=(3,10)，Q=(9,7)，计算P+Q和2P。解：这里a=1，b=1。首先求P+Q，这时=(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 mod23y3=(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 mod23x3=2-2x1=62-2*3=30=7 mod23y3=(x1-x3)-y1=6(3-7)-10=12 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=gx3=2+x1+x2+a=g2+g+g3+g6+g4=g0y3=(x1+x3)+x3+y1=g(g3+g0)+g0+g13=g13即P+Q=(x3,y3)=(g0,g13)。仍为该椭圆曲线上的点。 非对称密码体制6.4 非对称密码体制- ECC求2P，这时=(x12+y1)/x1=(g6+g13)=gx3=2+a=g2+g+g0=g10y3=x12+(+1)x3=g6+(g+g0)g10=g6+g14=g82P=(x3,y3)=(g10,g8),仍为该椭圆曲线上的点。非对称密码体制6.4 非对称密码体制- ECCo椭圆曲线密码体制GF(p)上的椭圆曲线适合软件实现；GF(2m)上的椭圆曲线适合硬件实现。椭圆曲线离散对数问题：已知椭圆曲线E和点P，随机生成一个整数d，计算Q=dP是容易的，但由给定的Q和P，计算d是困难的。椭圆曲线密码体制的安全性基础就是建立在曲线点群上的离散对数的难解性之上的。 非对称密码体制6.4 非对称密码体制- ECC1系统的建立和密钥生成o选取一个基域GF(P)和定义在该素域上的椭圆曲线Ep(a,b)，以及该曲线上的一个具有素数阶n的点P(xp,yp)。 其 中 曲 线 和 P(xp,yp)都 是 公 开 信 息 ，P(xp,yp)被称为基点基点。o密钥生成：在区间1,n-1中随机选取一个整数d，计算Q=dP，则点Q和整数d分别为实体的公钥公钥和私钥私钥。2椭圆曲线加密体制o以下介绍三种椭圆曲线加密体制ECES、ECELG和ECMO非对称密码体制2.1 ECES-椭圆曲线密码体制(1) 加密过程用户A发送消息m给用户B时，A执行以下步骤：step1：查找B的公开密钥Q；step2：在区间1,n-1中随机选取一个整数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 非对称密码体制- ECC2.2 ECELG-椭圆曲线ELGamal密码体制设mPm是明文空间到椭圆曲线的嵌入(即将明文转化为椭圆曲线上的点)，GE为椭圆曲线的基点。用户A、B分别拥有各自的私钥和公钥：dA、PA=dAG以及dB、PB=dBG(1) B为了向A发送消息m，则B向A发送(PB,Pm+dBPA)(2) A的脱密过程：(Pm+dBPA)-dAPB=Pm+dBdAG-dAdBG=Pm 非对称密码体制o例：考虑椭圆曲线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密码体制o为了与ECELG密码体制相比较，继而加深对该体制的理解，下面介绍基于有限域上的ELGamal密码体制。oElGamal公钥密码体制是由T.ElGamal于1984年提出的，它至今仍然是一个安全性能良好的公钥密码体制。oElGamal公钥密码体制描述如下：（1）选取大素数p，g是ZP的本原元，p和g公开。（2）随机选取整数d，1dp-2，计算D=gd modp，D是用户A公开的加密密钥，d是A保密的脱密密钥。（3）明文空间为ZP*，密文空间为ZP*ZP*。非对称密码体制6.4 非对称密码体制- ECC（4）加密变换 对任意明文mZP*,用户B秘密选取一个随机数k,1kp-2,设密文为c=(c1, c2)，其中c1=gk modp，c2=mDk modp。（5）脱密变换 对任意密文c=(c1, c2) ZP*ZP*，明文为m=c2(c1d)-1 modp非对称密码体制6.4 非对称密码体制- ECC2.3 ECMO-椭圆曲线Massey-Omura密码体制 设E是GF(p)上的椭圆曲线，N为椭圆曲线的阶(点的个数)，明文消息m编码后的消息为Pm。记用户A的公私钥分别为eA和dA，满足eAdA=1 modN 其中1eAN，1dAN。(1) 用户B计算Cm=eAPm，发送给用户A；(2) 用户A计算dACm=Pm，从而得到明文消息。 非对称密码体制6.4 非对称密码体制- ECCo例：考虑椭圆曲线E23(13,22)：y2=x3+13x+22，N=22 用户A选取公钥为eA=13，从而得到dA=17，即13*17=1 mod22 设Pm=(11,1),(1) B计算Cm=eAPm=13(11,1)=(14,21)，并发送给A；(2) A计算dACm=17(14,21)=(11,1)=Pm，从而得到明文消息。 非对称密码体制6.4 非对称密码体制- ECC3椭圆曲线加密体制的主要优点 同基于有限域上离散对数问题的公钥密码体制相比，椭圆曲线密码体制主要具有以下三个优点：（1）安全性高）安全性高o目前攻击有限域上离散对数问题的计算复杂度为其中，素数p是模数。o攻击椭圆曲线上离散对数问题的计算复杂度为其中pmax是椭圆曲线所构成的加法群的阶的最大素因子。非对称密码体制6.4 非对称密码体制- ECC（2）密钥长度短）密钥长度短o由攻击两类密钥体制的计算复杂度可知，在相同的安全要求下，椭圆曲线密码体制所需要的密钥长度远小于基于有限域上离散对数问题的公钥密码体制的密钥长度。（3）算法灵活性）算法灵活性o在GF(p)确定的情况下，其上的循环群也就确定了。但GF(p)上的椭圆曲线却可以通过改变曲线的参数得到不同的曲线，从而形成不同的循环群。非对称密码体制作业题1. 题6-5。2. RSA公钥密码体制基于什么数学难题？3. 设某用户的公钥为(e,N)=(5,91)，求该用户的私钥d，及求其它用户利用该用户的公钥对消息m=12加密的的密文。4. 题6-14。5. 题6-15。6. 题6-17。非对称密码体制