第十一章公钥密码学基础

2020/1/18计算机算法设计与分析1第十一章公钥密码学基础2020/1/18计算机算法设计与分析2密码、加密与解密密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照法则变明文为密文，称为加密变换；依照法则变密文为明文，称为解密变换。早期密码学仅对文字或数码进行加、解密变换。现代密码学还可以对语音、图像、数据等都可实施加、解密变换。2020/1/18计算机算法设计与分析3密码体制进行明密变换的法则，称为密码体制。密码体制可以分为四种基本类型：错乱：按照规定方式改变明文符号的位置；代替：用一个或多个代替表来代替明文符号；密本：用预先编定的字母或数字密码组来代替明文中一定的词组单词等；加乱：用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。这四种体制，既可单独使用，也可混合使用。2020/1/18计算机算法设计与分析4密钥和公钥密码的思想1976年美国斯坦福大学的Diffle和Hellman提出了公钥密码的思想：W.DiffieandM.E.Hellman:“NewDirectrionsinCryptography”,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654为密码系统分别设计一个加密密钥kc和一个解密密钥kd。把kc公开，而把kd保密，同时kc的公开不会影响kd的安全。这样：加密的过程为：c=Ekc(m)，解密的过程为：m=Dkd(c)。2020/1/18计算机算法设计与分析5秘钥与公钥密码学分为秘钥密码学和公钥密码学。秘钥密码学在加密和解密所使用的密钥是相同的，又称为对称密码学。公钥密码学加密和解密所使用的密钥是不相同的，且前者(签字密钥)公开而后者(验证密钥)保密，又称为非对称密码学。2020/1/18计算机算法设计与分析6公钥密码学的各种技术及功能1、保密通信2、数字签名3、秘密共享4、认证功能2020/1/18计算机算法设计与分析7单向函数加密的过程和解密的过程分别为：c=E(m)和m=D(c)显然D是E的逆函数，即D=E–1。设f(x)是En上的一个变换，En={0,1,…,n–1}，f(x)是单向的，若由x计算y=f(x)是容易的，即P问题，而由y计算出x是困难的，即NPC问题。因此，公钥密码学的思想就是让加密函数是一个单向函数。加密容易解密难！2020/1/18计算机算法设计与分析8单向陷门函数加密容易解密难。要难住别人，却不要难住自己。怎么办？f(x)说是单向陷门函数，如果有陷门信息K，当K未知时，f(x)是单向的，当K已知时，由y计算出x是容易的。公约密码学的思想就是将加密函数设计为一个单向陷门函数，而把陷门信息K作为解密密码。解密密码K是保密的。有了解密密码，就很容易解密，而不知道解密密码，就很难解密。2020/1/18计算机算法设计与分析9单向陷门函数例如：取两个不相等的质数p和q，令n=pq，取函数f(x)=xkmodn，且(k,ф(n))=1，其中ф(n)是n的欧拉函数(即ф(n)=(p–1)*(q–1))，则f(x)是一个单向函数。如果有d使得kd≡1(modф(n))，已知d，由y计算出x是容易的，因为yd≡x(modn)。d就是它的陷门信息。如果我们不知道ф(n)，而仅知道k，要想求出d是很困难的，这是一个NPC问题。所以f(x)还是一个单向陷门函数。2020/1/18计算机算法设计与分析10代表算法RSA(Rivest,Shamir,Adleman)椭圆曲线(ECC)(EillipticCurveCroptography)背包算法2020/1/18计算机算法设计与分析11RSA公钥密码体制2020/1/18计算机算法设计与分析12RSA公钥算法RSA公钥算法是由R.Rivest,A.Shamir和L.Adleman在1977年提出来的。该算法的数学基础是初等数论中的欧拉(Euler)定理并建立在大整数因子分解的困难性之上的2020/1/18计算机算法设计与分析13欧拉定理若整数a和m互素，则a(n)≡1(modn)其中(n)为比n小但与n互素的正整数个数,称为n的欧拉函数。比如：(10)=|{9，7，3，1}|=4，(15)=|{14,13,11,8,7,4,2,1}|=8。计算(n)很困难。但可以证明，若n=p*q(p、q均为素数)，(n)=(p–1)*(q–1)。2020/1/18计算机算法设计与分析14用欧拉函数构造单向陷门函数选取大整数n和一个与(n)互质的整数e，将n和e公开。若要对明文m加密，则令c=me(modn)。显然，这是一个单向函数。若已知一个整数d满足e*d(mod(n))=1，则cd=(me)d(modn)=(med)(modn)=(m(n)+1)(modn)=(m*m(n))(modn)=m。这里，整数d就是陷门。2020/1/18计算机算法设计与分析15RSA密码体制描述A.密钥的生成：1、选择两个素数p、q，计算n=p*q和(n)=(p–1)*(q–1)。2、选取整数b，使其满足gcd(b,(n))=1，1b(n)，3、计算a，满足a*b≡1mod(n)。4、将n和b作为加密秘钥公开，将p、q和a作为解密秘钥保密。2020/1/18计算机算法设计与分析16RSA密码体制描述B.加密的过程：1、将明文数字化，并选取长度小于logn位的数字作为明文信息块。2、加密明文m，令c=E(m)=mbmodn。C.解密的过程：对密文c计算，m=D(c)=camodn，得到明文m。2020/1/18计算机算法设计与分析17RSA算法的举例A.密钥的生成1、取素数43和59，则n=43*59=2537，(n)=42*58=2436。2、选取b为13，显然满足gcd(b,(n))=1，1b(n)。3、解方程ab≡1mod2436，a=937。4、将2537和13作为加密公钥，937和2436保密。2020/1/18计算机算法设计与分析18RSA算法的举例B.加密过程：现有明文“publickeyencryptions”要加密。首先将其以两个字符为一组进行分组为：publickeyencryptions令00表示a，01表示b，…，将其数字化编码为：15200111080210042404130217421519081414182020/1/18计算机算法设计与分析19RSA算法的举例先讨论对第一个明文数字m1=1520的加密：E(m1)=m1bmodn=152013mod2537=(15202)6*1520mod2537∵152021730mod2537=(1730)6*1520mod2537=(17302)3*1520mod2537∵173021777mod2537=(1777)3*1520mod2537=(1777)2*(1777*1520)mod2537∵177721701mod25371777*15201672mod2537=1701*1672mod2537=00952020/1/18计算机算法设计与分析20RSA算法的举例类似地，对其它数字加密后得到密文序列为：0095164814101299136513792333213217511289C.解密过程：解密运算的过程与加密过程类似，只不过将b换成a。例如：m1=D(0095)=0095937mod2537=(952)468*95mod2537=……=15202020/1/18计算机算法设计与分析21RSA算法的讨论若使RSA安全，p与q必为足够大的素数。建议选择p和q为100位以上的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位。2020/1/18计算机算法设计与分析22RSA算法的讨论为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：1、|p–q|很大，通常p和q的长度相同；2、p–1和q–1分别含有大素因子p1和q1；3、P1–1和q1–1分别含有大素因子p2和q2；4、p+1和q+1分别含有大素因子p3和q3。2020/1/18计算机算法设计与分析23RSA算法的讨论为了提高加密速度通常取b为特定的小整数。如EDI国际标准中规定b=216+1,ISO/IEC9796中甚至允许取b=3。这时加密速度一般比解密速度快10倍以上。加密和解密算术运算主要是模n的求幂运算。著名的“平方-和-乘法”方法将计算xcmodn的模乘法的数目缩小到至多为2l。这里的l是指数a的二进制表示的比特数。若设n以二进制形式表示有k比特即k=[log2n]+1由lk这样xcmodn能在o(k3)时间内完成。2020/1/18计算机算法设计与分析24椭圆曲线密码体制2020/1/18计算机算法设计与分析25椭圆曲线实数域上的一个椭圆曲线是指满足方程：y2=x3+ax+b(x,y,a,bR)的所有点(x,y)所形成的平面曲线。有限域上模p，p为素数，的一个椭圆曲线是指满足方程：y2=x3+ax+bmodp(x,y,a,bZ)的所有点(x,y)所形成的平面曲线。2020/1/18计算机算法设计与分析26椭圆曲线群若椭圆曲线y2=x3+ax+b满足4a3+27b20modp则由该椭圆曲线上的点再加上一个无穷远点，可以形成一个Abel群。这里无穷远点是一个抽象的点，可以想象为平行线的交点。有限域上模p的椭圆曲线群记为Ep(a,b)。2020/1/18计算机算法设计与分析27一个有限域上的椭圆曲线群设p=23，令y2=x3+x+1，即a=1,b=1。∵4a3+27b20modp∴该曲线在F23上的点：(0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(4,0)(5,4)(5,19)(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)，再加上无穷远点构成椭圆曲线群E23(1,1)。群E23(1,1)包括无穷远点在内有28个点。2020/1/18计算机算法设计与分析28椭圆曲线群的加法定义Ep(a,b)上点的加法为：⑴为单位元素；⑵(x,y)(x,–y)=，即点(x,y)的逆为(x,–y)。⑶令P=(x1,y1),Q=(x2,y2)且非互逆，则PQ=(x1,y1)(x2,y2)=(x3,y3),其中，x3=k2–x1–x2modp，y3=k(x1–x3)–y1modp，k=(y2–y1)/(x2–x1)。易证Ep(a,b)对加法构成Abel群。2020/1/18计算机算法设计与分析29椭圆曲线群的点加运算PQ在几何上的定义是P、Q两点的连线与椭圆曲线E的交点的对称点。而当P=Q，PQ在几何上的定义就成了椭圆曲线E在P点的切线与E的交点的对称点。因此，倍点运算，即2P=PP的计算，有别于PQ。2020/1/18计算机算法设计与分析30椭圆曲线群的倍点运算令P=(x1,y1)，y10，则2P=2(x1,y1)=(x3,y3),其中，x3=k2–2x1modp，y3=k(x1–x3)–y1modp，k=(3x12+a)/2y1。注意，虽然x3和y3的计算公式与点加公式中的形式仍然完全是一样的，但是k的计算却完全不一样了。2020/1/18计算机算法设计与分析31椭圆曲线点群的离散对数问题1985年N.Koblitz和V.Miller分别独