现代密码学第六章

1、汇报人：孙宗臣汇报人：孙宗臣6.1离散对数问题及其困难性离散对数问题及其困难性6.2 两个基本公钥密码体制两个基本公钥密码体制6.3离散对数问题的算法离散对数问题的算法6.4 椭圆曲线椭圆曲线6.5 椭圆曲线上的密码体制椭圆曲线上的密码体制2/有限域GF(p)上的离散对数问题l若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=logg y mod p。（例如 Diffie-hellman问题）求解离散对数问题的“最笨的方法”当然就是穷举，运算次数约为( p1)/2。l许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。数域筛

2、法l最快求解法的运算次数约为数量级l这个计算量称为亚指数计算量，当log2p1024时，亚指数计算量不小于2100数量级，因此是安全的。如果p-1不含大素因子，很多情况下也是容易计算的，这时x=x mod p-1,如果都是小因子，则可分别求出模小因子，再用CRT定理。3/)ln)(ln(ln(exp(ppO（RSA）l选择一个大的素数p；选择g，1g p；选择x，1x p-1；l计算y=gxmod p，公钥是(p, g, y)，私钥是xl设欲加密明文消息M，0 M pl随机选一整数k ,满足 gcd(k,p1)=1l计算对C1gk mod p,C2ykM mod p，密文为C = C1|C2

3、(级联)lM=C2/C1x mod p (演示)l这是因为C2/C1x mod pykM/gkx mod pykM/yk mod pM mod p 4/特点：密文由明文和所选随机数k来定，因而是一种概率加密体制，代价是使数据扩展一倍。 显然，如果Oscar可以计算x=logg y mod p，那么ElGamal密码体制就是不安全的。因此， ElGamal密码体制安全的必要条件，就是GF(p)上的离散对数是难处理的。对于这种形式的的离散对数问题，不存在已知多项式时间算法。为了防止已知的攻击，p应该至少取300个十进制位，p-1应该具有至少一个“较大”的素因子。ElGamal加密体制的本质是使用了

4、DH密钥交换技术DH密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公钥密码算法，已在很多商业产品中得以应用l算法的唯一目的是使得两个用户能够安全地交换密钥，得到一个共享地会话密钥，算法本身不能用于加、解密l算法的安全性基于求离散对数的困难性l假设p是大素数，g是p的本原根，p和g作为公开元素，协议如下：l 用户Alice选择随机数x，计算a=gx mod p，保密x，发送a给Bobl 用户Bob选择随机数y，计算b=gy mod p，保密y，发送b给Alice l Bob和Alice各自计算 k=bx mod p和k=ay mod p, 从而得到共享密钥kl这是因为k=

5、bx mod p=(gy)xmod p=(gx)ymod p=ay mod p6/7/8/6.3.1 Shanks 算法算法9/6.3.2 Pollard 算法算法10/6.3.3 Pohling Hellman 算法算法11/6.3.4 指数演指数演算法算法12/6.3.4 指数演指数演算法算法为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景，软硬件实现都有优势ECC已被IEEE公钥密码标准P1363采用1985年，N.

6、 Koblitz和V. Miller独立将其引入密码学中，成为构造双钥密码体制的一个有力工具其安全性主要基于ECDLP椭圆曲线离散对数问题有限域上的方案都可以用椭圆曲线实现13/14/ 有限域在应用密码学和编码理论中有着极其广泛的应用。 一个只含有限个元素的域叫做有限域。椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：l y2+axy+by=x3+cx2+dx+e (4-1)l其中其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。l从图可见，椭圆曲线

7、关于x轴对称。15/l如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： l O为加法单位元，即对椭圆曲线上任一点P，有 P+O=P (这是因为P与-P在曲线的第三个交点是O)l 设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=P1=(x, -y)l这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。l由O+O=O，还可得O= -O16/l 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R

8、的直线与椭圆曲线交于P1l这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q或P1=R 由Q+R+P1=O 得 Q+R=-P1l 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，l以上定义的加法具有加法运算的一般性质，如交换律、结合律等17/l其中最为常用的是由方程(4-2)定义的曲线 y2x3+ax+b(mod p) (4-2) (a,bGF(p),4a3+27b2(mod p)0)l因为(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b0的判别式，当4a3+27

9、b2 0时方程有重根，设为x0，则点Q0(x0,0)是方程(4-2)的重根l即x3+ax+b(x-x0)3或者(x-x0)2(x-x1)，重根将使得一阶导数3x2a在该Q0点为0l令F(x,y)=y2x3axb，则F/x|Q0=F/y|Q0=0l所以dy/dx=(F/x)/(F/y)(3x2a)/2y在Q0点无定义，即曲线y2x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义18/l对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，有单位元O，所以Ep(a,b)是一个Abel群19/l 对每一x(0 xp且x为整数），计算x3

10、+ax+b(mod p)。 l 决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根 (y=0 时只有一个平方根)。即判断是否是模p的平方剩余20/l设P，QEp(a,b)，则 l P+O=P；l 若P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，记为-P。l显然任一点P和其逆元-P都是Ep(a,b)中的点，l如上例，P=(13,7)和-P=(13, -7)=(13, 16)E23(1,1)l 设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定：l x32x1x2(m

11、od p)l y3(x1x3)y1(mod p)l其中 l 切线21/ QPyaxQPxxyy,23,121121222/l1+p+ = 1+p+个，其中 是Legendre符号l定理中的由以下定理给出l| |23/ pbaxx3 )(3pGFxpbaxxp2l设明文消息是m(0mM)，k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误的概率是2-kl实际情况中，k可在3050之间取值。不妨设k30，对明文消息m，如下计算一系列x：lxmk+j,j=0,1,2,=30m,30m+1,30m+2,直到x3+ax+b(mod p)是平方剩余，即得到椭圆曲线上的点l(x, )。因为在0到p

12、的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(mod p)是平方根的概率不小于12-k。l反之，为从椭圆曲线上的点(x,y)得到明文消息m，只须求mx/3024/baxx 325/点压缩点压缩 点压缩可以表示为函数点压缩可以表示为函数26/ECIESl可采用类似于快速指数运算的相同算法即令k=bt2t+bt-12t-1+b12+b0，则可写出2倍点和加法运算的迭代形式。下面将“倍数-和”扩展来展示，这个扩展称为“倍数-和差”算法。27/28/29/l在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，kp，则由k

13、和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。lDiffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制l第1步：取一素数p2180和两个参数a、b，则得椭圆曲线上面的点及无穷远点构成Abel群Ep(a,b)，a，b应使群的阶n具有大素因子l第2步: 取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数l第3步: 两用户A和B之间的密钥交换如下进行： l A随机选整数nA0,q

14、)l公钥：(g1,g2,c,d,h,H)；私钥(x1，x2，y1，y2，z )43/l对于明文消息m，发送者Bob选择一个随机数r U0,q)，并计算lu1=g1r， u2=g2r ，e=hrm，=H(u1, u2,e),v=erdrl密文是(u1, u2,e,v)l1. 计算=H(u1, u2,e)；l2. 验证u1x1+y1 + u2x2+y2 =v，若不成立则拒绝该密文，否则计算明文m=e/u1z该方案中的典型特征是明文m参与了验证在该方案中，hash函数只假设其为单向的，而不是输出随机的l标准模型仅假设hash函数的单向性和无碰撞性，因而更为合理，但所设计出来的方案一般比较复杂44/实际上就是一种数字信封技术对于长消息加密非常重要l混合体制输出的密文包括两个部分：密钥封装机制(KEM)和数据封装机制(DEM)l即KEM|DEM=