应用密码学第8讲

12010-2011年度济南大学网络工程专业本科班课程应用密码学第八讲公钥密码体制贾忠田济南大学信息科学与工程学院电子信箱：[e-mail]2本次课的安排：公钥密码体制的概念RSA密码算法椭圆曲线密码算法3一、公钥密码体制的基本概念先考虑两个问题：1、密钥分配问题。2、数字签字问题。——数字签字是考虑如何为数字化的信息提供一种类似于书面文件签字或盖章的方法。这两个问题，导致了公钥密码体制的产生。公钥密码体制的产生是密码史上一次真正的革命。公钥密码算法的基本工具不再是代换和置换，而是数学函数。公钥密码算法的理论基础是数论。41、公钥密码体制的原理加密密钥和解密密钥：公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开。其中一个密钥是公开的，称为公开密钥（或称为公钥）。用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥（或称为私钥），用于解密。PK：公开密钥SK:秘密密钥在下面的讲解中：5图4.1公钥体制加密的框图EPKB[m]m=DSKB[c]加密原理：6认证原理：图4.2公钥密码体制认证框图c=ESKA[m]m=DPKA[c]注意：实际应用时先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质：如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。7认证保密——实际应用模型图4.3公钥密码体制的认证、保密框图c=EPKB[ESKA[m]]加密过程：解密过程：m=DPKA[DSKB[c]]82、公钥密码算法应满足的要求①接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。②发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKB[m]在计算上是容易的。③收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的。9④敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。⑤敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。⑥加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)]其中最后一条虽然非常有用，但不是对所有的算法都作要求。103、对公钥密码体制的攻击穷搜索攻击：攻击对象是短密钥。——然而，密钥长度太大又会使得加解密运算太慢而不实用，因此公钥密码体制目前主要用于密钥管理和数字签字。利用公钥计算私钥：常用的公钥算法还都未能够证明这种攻击是不可行的。可能字攻击：例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。11二、RSA算法RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。121.密钥的产生①选两个保密的大素数p和q。②计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1。④计算d，满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。⑤以{e,n}为公开密钥,{p,q,φ(n),d}为秘密密钥。132.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：c≡memodn3.解密对密文分组的解密运算为：m≡cdmodn14例题：4-8选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1eφ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77,7,96,17}。设明文m=19，则由加密过程得密文为c≡195mod119≡2476099mod119≡66解密为6677mod119≡1915三、椭圆曲线密码体制为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（ellipticcurvecryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用。161、椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e(4.1)其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下面举两个椭圆曲线的例子。17图4.4椭圆曲线的两个例子18椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：①O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。②设P1=(x,y)是椭圆曲线上的一点（如图4.4），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O19③设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1，由Q+R+P1=O得Q+R=-P1。20④点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。s-s以上定义的加法具有加法运算的一般性质，如交换律、结合律等。212、有限域上的椭圆曲线密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4.1)中，y2+axy+by=x3+cx2+dx+e所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程y2≡x3+ax+b(modp)(4.2)(a,b∈GF(p),4a3+27b2(modp)≠0)定义的曲线。22设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集{(x,y)|0≤xp,0≤yp,且x,y均为整数,x,y满足4.2式}并上无穷远点O。3、椭圆曲线上的密码为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。考虑方程Q=kP，其中P，Q∈Ep(a,b)，kp，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。23用椭圆曲线实现Diffie-Hellman密钥交换第1步：取一素数p≈2180和两个参数a、b，则得方程(4.2)表达的椭圆曲线及其上面的点构成的Abel群Ep(a,b)。第2步，取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数。下面看一下两用户A和B之间的密钥交换过程：24①A选一小于n的整数nA，作为秘密钥，并由PA=nAG产生Ep(a,b)上的一点作为公开密钥。②B类似地选取自己的秘密钥nB和公开钥PB③A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密密钥。这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的。25用椭圆曲线实现ElGamal密码体制假设用户B要把信息加密传送给用户A：用户A选择一条椭圆曲线Ep(a,b)，取椭圆曲线上的一个生成元G；用户A选择一个正整数nA作为秘密密钥，并生成公开密钥PA=nAG；用户A把Ep(a,b)、PA和G传给用户B；用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M,并生成一个随机数k，并计算C1=M+kPA，C2=kG；用户B把C1,C2传给用户A；用户A计算C1–nAC2，结果就是M。因为：C1–nAC2=M+kPA–nAkG=M+kPA–k(nAG)=M+kPA–kPA=M26例4.15取p=751，Ep(-1,188)，即椭圆曲线为y2≡x3-x+188,Ep(-1,188)的一个生成元是G=(0,376)A的公开钥为PA=(201,5)假定B已将欲发往A的消息编码到椭圆曲线上的点Pm=(562,201)B选取随机数k=386，由kG=386(0,376)=(676,558)Pm+kPA=(562，201)+386(201,5)=(385,328)，得密文为{(676,558),(385,328)}27椭圆曲线密码体制的优点（1）安全性高目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为，其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子。因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全。max(exp(log))Op28(2)密钥量小由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。(3)灵活性好有限域GF(q)一定的情况下，其上的循环群（即GF(q)-{0}）就定了。而GF(q)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性。29小结：1、公钥密码算法的加密、认证及认证加密原理2、公钥密码算法应满足那些要求3、RSA加密算法的过程4、椭圆曲线密码算法的过程及方法