公钥密码技术理论及应用介绍

,1,1.1,1.1.1,1.1.1,1.1.1.1,-,37,-,第三章 公钥密码技术,第三章 公钥密码技术,1,公钥密码的概念,公钥密码学的理论基础,公钥密码算法,密钥交换,公钥密码算法的应用,提出公钥密码的动因,密钥分配问题。使用对称加密算法的通信双方要进行加密通信时，需要通过秘密的安全信道协商加密密钥，而这种安全信道如何实现呢？机械阶段,数字签名问题。信息的电子化对密码学提出了新的要求：电子报文和电子文件需要一种与书面材料中使用的签名等效的认证手段。,公钥密码的初始化阶段,加密通信阶段,公钥密码的概念,公钥密码学的理论基础,公钥密码算法,密钥交换,公钥密码算法的应用,第三章 公钥密码技术,2,计算复杂度与,公钥密码,计算复杂度,P,问题和,NP,完全问题,密码与计算复杂度的关系,单向陷门函数,单向陷门函数的数学问题,分解整数问题。,离散对数问题。,RSA,问题。,公钥密码的概念,公钥密码学的理论基础,公钥密码算法,密钥交换,公钥密码算法的应用,第三章 公钥密码技术,3,公开密钥算法,公钥算法的种类很多，具有代表性的三种密码：,基于离散对数难题（,DLP）,的算法体制，例如,Diffie-Hellman,密钥交换算法,；,基于整数分解难题（,IFP）,的算法体制，例如,RSA,算法；,基于椭圆曲线离散对数难题（,ECDLP）,的算法体制；,RSA,算法,麻省理工学院的,Ron,Rivest,Adi,Shamir,和,Len,Adleman,于,1977,年研制，并于,1978,年首次发表；,RSA,是一种分组密码，其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；既可用于加密，又可用于数字签名，已得到广泛采用；,RSA,已被许多标准化组织,(,如,ISO,、,ITU,、,IETF,和,SWIFT,等,),接纳；,RSA-155(512 bit), RSA-140,于,1999,年分别被分解；,Euler,函数,欧拉函数 (,Eulers,totient,function)，,记为,(n)，,表示小于,n,而且与,n,互素的正整数个数；,对于任一素数,p，(p)=p-1;,对于两个不同的素数,p,和,q，,若,n=pq，,则,(n)= (pq) (p)(q)(p-1)(q-1)；,Euler,函数举例,设,p=3, q=5,那么,n=pq=15；,1）小于,15,而且与,15,互素的正整数是：,1，2，4，7，8，11，13，14,因此，,（15）8；,2）（15）=（3-1）*（5-1）=8,欧拉定理,对于任何互素的整数,a,和,n， (,mod n)，,或者写作,a(mod n),给定两个素数,p,和,q，,以及整数,n=pq，,和,m，,其中0,mn，,则,mod n,mod n,RSA,算法的描述,对于明文分组,M,和密文分组,C，,加密解密形式分别为：,C = M,e,mod n,M =,C,d,mod n = (M,e,),d,mod n = M,ed,mod n,因此，公钥,K,U,=e,n,私钥,K,R,=d,n,公钥算法必须满足:,1）有可能找到,e、d、n,的值，使得对所有,Mn,有,M,ed,=M mod n；,2）,对于所有,Mn，,要计算,M,e,和,C,d,相对简单；,3）给定,e,和,n,时，判断出,d,是不可行的；,RSA,算法的描述,如何找到：,？,参考欧拉定理,可以得到：,ed= k(n)+1,也就是说：,RSA,算法的实现,实现的步骤如下：,Bob,为实现者,(1),Bob,寻找出两个大素数,p,和,q,(2) Bob,计算出,n=pq,和,(n)=(p-1)(q-1),(3) Bob,选择一个随机数,e (0e (n)，,满足(,e,(n)=1,(4) Bob,使用辗转相除法计算,d=e,-1,mod(n),(5) Bob,在目录中公开,n,和,e,作为公钥,密码分析者攻击,RSA,体制的关键点在于如何分解,n。,若分解成功使,n=pq，,则可以算出,(n)（p-1)(q-1)，,然后由公开的,e，,解出秘密的,d,RSA,算法举例,设,p=7, q=17, n=7*17=119;,参数,T=n=119;,(n)=(7-1)(17-1)=96;,选择,e=5, gcd(5,96)=1;,计算,d, d*e =1 mod 96; d=77;,因为7753854961,设:明文,m=19,加密：（19）,5,mod 119 = 66,解密：（66）,77,mod 119 = 19,RSA,算法的安全性分析,密码分析者攻击,RSA,体制的关键在于分解,n,若分解成功使,n=pq,，,则可以算出,(n)（p-1)(q-1),，,然后由公开的,e，,解出秘密的,d;,若使,RSA,安全，,p,与,q,必为足够大的素数，使分析者没有办法在多项式时间内将,n,分解出来,建议选择,p,和,q,大约是100位的十进制素数,模,n,的长度要求至少是512比特;,RSA,算法的安全性分析,EDI,攻击标准使用的,RSA,算法中规定,n,的长度为512至1024比特位之间，但必须是128的倍数;,国际数字签名标准,ISO/IEC 9796,中规定,n,的长度位512比特位;,为了提高加密速度，通常取,e,为特定的小整数,如,EDI,国际标准中规定,e2161;ISO/IEC9796,中甚至允许取,e3;,这时加密速度一般比解密速度快10倍以上;,RSA,算法的安全性分析,为了抵抗现有的整数分解算法，对,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；,椭圆曲线密码编码学,ECC,1985年,Miller,Koblitz,独立提出,y,2,+axy+by=x,3,+cx,2,+dx+e,表示曲线上的点连同无穷远点,O,的集合,加法:若曲线三点在一条直线上,则其和为,O；,倍数:一个点的两倍是它的切线与曲线的另一个交点；,椭圆曲线上的加法规则,加法公式:,O,作为加法的单元，,O=-O，P+O=P,如果,P=(x,y)，,则,P+(x,-y)=O，(x,-y),点是,P,的负点，记为-,P,而且(,x,-y),也在,E,P,(a,b),中,如果,P=(x,1,y,1,)，Q=(x,2,y,2,)，,则,P+Q=(x,3,y,3,),为,x,3,=,2,-x,1,-x,2,(mod p)y,3,=,(x,1,-x,3,)-y,1,(mod p),其中，,如果,PQ，,则 = (,y,2,-y,1,)/(x,2,-x,1,),如果,P=Q，,则 = (3,x,1,2,+a)/(2y,1,),椭圆曲线示例,椭圆曲线上的加法:,P + Q = -R,椭圆曲线上一点的2倍:,Q+Q=-S,有限域上的椭圆曲线,有限域上的椭圆曲线定义如下：,y,2,x,3,+ax+b (mod p),p,是素数,a,b,为非负整数，且满足4,a,3,+27b,2,(mod p),0,针对所有的0=,x p，,可以求出有效的,y，,得到曲线上的点 (,x,y)，,其中,x,y p。,曲线记为,E,P,(a,b),E,P,(a,b),中也包括,O,点,例如，令,P=23，a=b=1，,椭圆曲线为,y,2,x,3,+x+1，,4132712(mod 23)=8,0,满足模23椭圆群的条件,椭圆曲线上的密钥交换,1）双方选择,E,P,(a,b),以及,E,P,(a,b),的一个元素,G,使得,nG=0,的最小,n,值是一个非常大的素数；,2）,A,选择私钥,Xn,计算公钥,P,A,=X,G,；,3）,B,选择私钥,Yn,计算公钥,P,B,=Y,G；,4）A,计算秘密密钥:,K=X,(P,B,)=X,YG,5）B,计算秘密密钥:,K=Y,(P,A,)=Y,XG=,X,YG,因此，双方获得了一个共享会话密钥(,X,Y,G,),椭圆曲线上的密钥交换攻击,双方选择,E,P,(a,b),以及,E,P,(a,b),的一个元素,G,使得,G,的阶,n,是一个大素数,A,选择私钥,Xn,计算公钥,P,A,=X,G,A,B: P,A,E,截获,P,A,选私钥,Z,计算,P,E,=Z,G,冒充,A,B:,P,E,B,选择私钥,Yn,计算公钥,P,B,=Y,G, B,A,: P,B,E,截获,P,B,冒充,B,A,:,P,E,A,计算:,X,P,E,=,X,ZG,B,计算:,Y,P,E,= YZG,E,计算:,Z,P,A,=ZXG, Z,P,B,=ZYG,E,无法计算出,XYG,E,永远必须实时截获并冒充转发,否则会被发现,.,椭圆曲线加密/解密,1）双方选择椭圆群,E,P,(a,b),以及,E,P,(a,b),的一个元素,G,使得,nG=0,的最小,n,值是一个非常大的素数；,2）,A,选择私钥,Xn,计算公钥,P,A,=X,G,；,3）,B,选择私钥,Yn,计算公钥,P,B,=Y,G；,4）A,若想加密和发送报文,P,m,给,B，,选择随机数,k，,并产生一对点组成的密文,Cm=k,G,P,m,+kP,B,；,5）B,解密密文，,P,m,+kP,B,-Y,k,G P,m,+k,Y,G- Y,k,G= P,m,除了,A，,无人知道,k，,因此无法破译,两类加密算法比较,公钥密码的概念,公钥密码学的理论基础,公钥密码算法,密钥交换,公钥密码算法的应用,第三章 公钥密码技术,4,Diffie-Hellman,密钥交换算法,若用户,A,和用户,B,希望交换一个密钥，如何进行？,1）全局公开参数：一个素数,q,和其一个原根,a；,2）用户,A,选择一个随机数,X,A,q，,计算,Y,A,=,a,XA,mod q，Y,A,公开；,3）,用户,B,选择一个随机数,X,B,q，,计算,Y,B,=,a,XB,mod q ，Y,B,公开,；,4）,用户,A,计算密钥,K=(Y,B,),XA,mod q;,5）用户,B,计算密钥,K=(Y,A,),XB,mod q;,Diffie-Hellman,密钥交换算法,证明：,K = (Y,B,),XA,mod q = (a,XB,mod q),XA,mod q =(a,XB,),XA,mod q,=a,XBXA,mod q =(a,XA,),XB,mod q =(a,XA,mod q),XB,mod q,=(Y,A,),XB,mod q,攻击分析：公开数据,q，a，Y,A,和,Y,B，,若想攻击用户,B,的秘密密钥，攻击者必须计算,X,B,= ind,a,q,(Y,B,)；,安全性分析：计算模一个素数的指数相对容易，计算离散对数却很难；,Diffie-Hellman,密钥交换算法举例,1）密钥交换基于素数,q=97,和,q,的一个原根,a=5；,2）A,和,B,分别选择密钥,X,A,=36,和,X,B,=58，,并分别计算其公开密钥,Y,A,= 5,36,= 50 mod 97,Y,B,= 5,58,= 44 mod 97,3）,交换了公开密钥后，每人计算共享的秘密密钥如下,K= (Y,B,),XA,mod 97 = 44,36,= 75 mod 97,K= (Y,A,),XB,mod 97 = 50,58,= 75 mod 97,ECC,密钥交换算法,类似,Diffie,Hellman,密钥交换，思考如何用,ECC,来实现密钥交换。,公钥密码的概念,公钥密码学的理论基础,公钥密码算法,密钥交换,公钥密码算法的应用,第三章 公钥密码技术,5,公钥,密码,的典型,应用,使用,RSA,和,DES,对信息加密,使用散列函数和,RSA,进行数字签名,