现代密码学第六章汇编资料

1、第六章 公钥密码和离散(lsn)对数汇报(hubo)人：孙宗臣共四十七页内容提要(ni rn t yo)6.1离散对数问题及其困难性6.2 两个基本公钥密码体制(tzh)6.3离散对数问题的算法6.4 椭圆曲线6.5 椭圆曲线上的密码体制2/第六章 公钥密码和离散对数共四十七页6.1离散(lsn)对数问题及其困难性有限域GF(p)上的离散(lsn)对数问题若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=logg y mod p。（例如 Diffie-hellman问题）求解离散对数问题的“最笨的方法”当然就是穷举，运算次数约为( p1)/2。许多求解离散对数问题的算法

2、比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。数域筛法最快求解法的运算次数约为数量级这个计算量称为亚指数计算量，当log2p1024时，亚指数计算量不小于2100数量级，因此是安全的。如果p-1不含大素因子，很多情况下也是容易计算的，这时x=x mod p-1,如果都是小因子，则可分别求出模小因子，再用CRT定理。3/第六章 公钥密码和离散对数（RSA）共四十七页6.2 两个(lin )基本公钥密码体制6.2.1 ElGamal密码体制1. 密钥产生选择一个大的素数p；选择g，1g p；选择x，1x p-1；计算(j sun)y=gxmod p，公钥是(p, g, y

3、)，私钥是x2. 加密设欲加密明文消息M，0 M p随机选一整数k ,满足 gcd(k,p1)=1计算对C1gk mod p,C2ykM mod p，密文为C = C1|C2 (级联)3. 解密M=C2/C1x mod p (演示)这是因为C2/C1x mod pykM/gkx mod pykM/yk mod pM mod p 4/第六章 公钥密码和离散对数 ElGamal密码体制与DH密钥交换共四十七页6.2.1 ElGamal密码(m m)体制特点：密文由明文和所选随机数k来定，因而是一种概率加密体制，代价是使数据扩展一倍。 显然(xinrn)，如果Oscar可以计算x=logg y mo

4、d p，那么ElGamal密码体制就是不安全的。因此， ElGamal密码体制安全的必要条件，就是GF(p)上的离散对数是难处理的。对于这种形式的的离散对数问题，不存在已知多项式时间算法。为了防止已知的攻击，p应该至少取300个十进制位，p-1应该具有至少一个“较大”的素因子。第六章 公钥密码和离散对数共四十七页6.2.2 Diffie-Hellman 密钥交换(jiohun)ElGamal加密体制的本质是使用了DH密钥交换技术DH密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公钥密码算法，已在很多商业产品中得以应用算法的唯一目的是使得两个用户能够安全地交换密钥，得到一

5、个共享地会话密钥，算法本身不能用于加、解密算法的安全性基于求离散对数的困难性假设p是大素数，g是p的本原根，p和g作为公开元素，协议如下： 用户Alice选择随机数x，计算a=gx mod p，保密(bo m)x，发送a给Bob 用户Bob选择随机数y，计算b=gy mod p，保密y，发送b给Alice Bob和Alice各自计算 k=bx mod p和k=ay mod p, 从而得到共享密钥k这是因为k=bx mod p=(gy)xmod p=(gx)ymod p=ay mod p6/第六章 公钥密码和离散对数 共四十七页6.3离散对数(du sh)问题的算法7/第六章 公钥密码(m m)

6、和离散对数共四十七页6.3离散对数(du sh)问题的算法8/第六章 公钥密码和离散(lsn)对数6.3.1 Shanks 算法共四十七页6.3离散(lsn)对数问题的算法9/第六章 公钥密码和离散(lsn)对数6.3.2 Pollard 算法共四十七页6.3离散(lsn)对数问题的算法10/第六章 公钥密码(m m)和离散对数6.3.3 Pohling Hellman 算法共四十七页6.3离散对数问题(wnt)的算法11/第六章 公钥密码和离散(lsn)对数6.3.4 指数演算法共四十七页6.3离散对数问题(wnt)的算法12/第六章 公钥密码和离散(lsn)对数6.3.4 指数演算法共四十

7、七页6.6.4 椭圆(tuyun)曲线为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景，软硬件实现都有优势ECC已被IEEE公钥密码标准P1363采用1985年，N. Koblitz和V. Miller独立(dl)将其引入密码学中，成为构造双钥密码体制的一个有力工具其安全性主要基于ECDLP椭圆曲线离散对数问题有限域上的方案都可以用椭圆曲线实现13/第六章 公钥密码和离散对数共四十七页6.4.1 有限(yuxin)域14/

8、第六章 公钥密码(m m)和离散对数 有限域在应用密码学和编码理论中有着极其广泛的应用。 一个只含有限个元素的域叫做有限域。共四十七页6.4.2 椭圆(tuyun)曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式(xngsh)的三次方程： y2+axy+by=x3+cx2+dx+e (4-1)其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。从图可见，椭圆曲线关于x轴对称。15/第六章 公钥密码和离散对数共四十七页6.4.2 椭圆(tuyun)曲线椭圆曲线上

9、的加法(jif)运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： O为加法单位元，即对椭圆曲线上任一点P，有 P+O=P (这是因为P与-P在曲线的第三个交点是O) 设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=P1=(x, -y)这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O= -O16/第六章 公钥密码和离散对数共四十七页6.4.2 椭圆(tuyun)曲线 设Q和

10、R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q或P1=R 由Q+R+P1=O 得 Q+R=-P1 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似(li s)地可定义3Q=Q+Q+Q+，以上定义的加法具有加法运算的一般性质，如交换律、结合律等17/第六章 公钥密码和离散对数共四十七页6.4.3 有限(yuxin)域上的椭圆曲线密码中普遍采用(ciyng)的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4-1)中

11、，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）其中最为常用的是由方程(4-2)定义的曲线 y2x3+ax+b(mod p) (4-2) (a,bGF(p),4a3+27b2(mod p)0)因为(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b0的判别式，当4a3+27b2 0时方程有重根，设为x0，则点Q0(x0,0)是方程(4-2)的重根即x3+ax+b(x-x0)3或者(x-x0)2(x-x1)，重根将使得一阶导数3x2a在该Q0点为0令F(x,y)=y2x3axb，则F/x|Q0=F/y|Q0=0所以dy/dx=(F/x)/(F/y)(3x2a

12、)/2y在Q0点无定义，即曲线y2x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义18/第六章 公钥密码和离散对数共四十七页6.4.3 有限域上的椭圆(tuyun)曲线有限域上的椭圆曲线群定义如下：设Ep(a,b)表示方程(4-2)所定义的椭圆曲线上的点集(x,y)|0 xp,0yp，且x,y均为整数并上无穷远点OEp(a,b)是一个Abel群对一般的Ep(a,b)，可证其上的加法运算(yn sun)是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，有单位元O，所以Ep(a,b)是一个Abel群19/第六章 公钥密码和离散对数共四十七页6.4.3 有限域上的椭圆(t

13、uyun)曲线一般来说，Ep(a,b)由以下方式产生： 对每一x(0 xp且x为整数），计算x3+ax+b(mod p)。 决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个(lin )平方根 (y=0 时只有一个平方根)。即判断是否是模p的平方剩余例：椭圆曲线E23(1, 1)，4a3+27b2(mod 23)80，方程为y2x3+x+1(mod 23)，那么曲线在GF(23)中的整数点，注意点和其逆元，表中未给出O20/第六章 公钥密码和离散对数(0，1)(0，22)(1，7)(1，16)(3，10)(3，13)(4，0)(5，4)(5，19)

14、(6，4)(6，19)(7，11)(7，12)(9，7)(9，16)(11，3)(11，20)(12，4)(12，19)(13，7)(13，16)(17，3)(17，20)(18，3)(18，20)(19，5)(19，18)共四十七页6.4.3 有限(yuxin)域上的椭圆曲线Ep(a,b)上的加法定义如下： 设P，QEp(a,b)，则 P+O=P； 若P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，记为-P。显然任一点P和其逆元-P都是Ep(a,b)中的点，如上例，P=(13,7)和-P=(13, -7)=(13, 16)E23(1,1) 设P=(x1

15、,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则(guz)确定： x32x1x2(mod p) y3(x1x3)y1(mod p)其中 切线21/第六章 公钥密码和离散对数提示：计算中凡是除法b/a在约减后一定要先求a的逆元，再乘法ba-1另外，计算点加后可带入原方程验证共四十七页6.4.3 有限(yuxin)域上的椭圆曲线公式推导(tudo)示例22/第六章 公钥密码和离散对数共四十七页6.4.4 椭圆(tuyun)曲线上的点数一条椭圆曲线Ep(a,b)（含无穷远点O)的总点数关系到运算(yn sun)群的规模，即建立的密码系统的安全性，有以下定理：定理4-13 GF

16、(p)上的椭圆曲线y2x3+ax+b(a,bGF(p), 4a3+27b2(mod p)0)在第一象限中的整数点加无穷远点O共有1+p+ = 1+p+个，其中 是Legendre符号定理中的由以下定理给出定理4-14(Hasse定理) | |23/第六章 公钥密码和离散对数共四十七页6.4.5 明文消息到椭圆曲线(qxin)上的嵌入使用椭圆曲线构造密码体制前，需要将明文消息镶嵌到椭圆曲线上去，作为椭圆曲线上的点。设明文消息是m(0mM)，k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误的概率是2-k实际情况中，k可在3050之间取值。不妨设k30，对明文消息m，如下计算一系列x：x

17、mk+j,j=0,1,2,=30m,30m+1,30m+2,直到x3+ax+b(mod p)是平方剩余，即得到椭圆曲线上的点(x, )。因为(yn wi)在0到p的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(mod p)是平方根的概率不小于12-k。反之，为从椭圆曲线上的点(x,y)得到明文消息m，只须求mx/3024/第六章 公钥密码和离散对数共四十七页6.4.6 点压缩(y su)和ECIES25/第六章 公钥密码和离散(lsn)对数点压缩 点压缩可以表示为函数共四十七页6.4.6点压缩(y su)和ECIES26/第六章 公钥密码和离散(l

18、sn)对数ECIES共四十七页6.4.7 计算椭圆(tuyun)曲线上的乘积倍点运算(yn sun)仍定义为重复加法，如4P=P+P+P+P快速倍点运算 kP可采用类似于快速指数运算的相同算法即令k=bt2t+bt-12t-1+b12+b0，则可写出2倍点和加法运算的迭代形式。下面将“倍数-和”扩展来展示，这个扩展称为“倍数-和差”算法。27/第六章 公钥密码和离散对数共四十七页6.4.7 计算(j sun)椭圆曲线上的乘积28/第六章 公钥密码和离散(lsn)对数共四十七页6.5 椭圆曲线(qxin)上的密码29/第六章 公钥密码(m m)和离散对数为使用椭圆曲线构造密码体制，需要找出椭圆曲

19、线上的数学困难问题在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，kp，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制共四十七页6.5.1 椭圆曲线(qxin)上的密码体制1. Diffie-Hellman密钥交换(GF(p)上的方案见5.2.3节)第1步：取一素数p2180和两个参数a、b，则得椭圆曲线上面的点及无穷远点构成Abel群Ep(a,b)，a，b应使群的阶

20、n具有大素因子第2步: 取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数第3步: 两用户A和B之间的密钥交换如下进行： A随机选整数nA0,q)公钥：(g1,g2,c,d,h,H)；私钥(x1，x2，y1，y2，z )43/第六章 公钥密码和离散对数共四十七页6.3.4 标准模型下可证明(zhngmng)安全的体制加密对于明文消息m，发送者Bob选择一个随机数r U0,q)，并计算u1=g1r， u2=g2r ，e=hrm，=H(u1, u2,e),v=erdr密文是(u1, u2,e,v)解密1. 计算=H(u1, u2,e)；2. 验证u1x1+y1 + u2x2+y2 =v，若不成立则拒绝该密文，否则计算明文m=e/u1z 该方案中的典型(dinxng)特征是明文m参与了验证在该方案中，hash函数只假设其为单向的，而不是输出随机的标准模型仅假设hash函数的单向性和无碰撞性，因而更为合理，但所设计出来的方案一般