【安全课件】第12讲--分组密码小节

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分组密码,小,小结,王滨,2005.03.25,1,主要内容,欧几里德,算,算法,求最大公,约,约数,求模,n,的逆元,2,欧几里得,算,算法（辗,转,转相除法,）,）,引理,1,记,gcd(a,b),是非负整,数,数,a,和,b,的最大公,因,因子,则,gcd(a,b)=1,等价于存,在,在整数,x,y,使得,ax+by=1,其中的,x,和,y,可由辗转,相,相除法求,出,出。,3,辗转相除,法,法,引理,2(,带余除法,),设,a,是整数,b,是自然数,则存在整,数,数,q,和非负整,数,数,r,使得,a=bq+r,，且,0=rb,并记,amodb=r.,引理,3,设,a,、,b,、,r,为不全为,零,零的整数,，,，且,a=bq+r,，则,gcd(a,b)=gcd(b,r).,证明：设,d=gcd(a,b),，由于,d|a=bq+r,且,d|b,，则一定,有,有,d|r,，则,d|gcd(b,r).,下证,d=gcd(b,r).,由于,gcd(a/d,b/d)=1,一定有,gcd(r/d,b/d)=1,，故,d=gcd(b,r),。证毕。,4,辗转相除,法,法：,-,计算,gcd(a,b),Step1 A,a;B,b,Step2,计算带余,除,除法，求,出,出满足,A=qB+r,和,0=r0,时,执,行,行,A,B;B,r,后,返,返,回,回,执,执,行,行,Step2.,5,例,1,计,算,算,gcd(63,100),解,63=0,100,+,63,100=1,63,+,37,63=1,37,+,26,37=1,26,+,11,26=2,11,+,4,11=2,4,+,3,4=1,3,+,1,3=3,1,+0,故,gcd(63,100)=1.,6,系,数,数,的,的,计,计,算,算,倒,推,推,进,进,行,行,(,将,余,余,数,数,代,代,入,入,):,1=,4,-1,3,=,4,-1,(11-2,4),=-1,11+(1+2),4=-1,11,+3,4,=-1,11,+3,(26,2,11,)=-7,11,+3,26,=-7,(37,26,)+3,26,=-7,37+(7+3),26,=-7,37+10,26,=-7,37+10,(63-37),=10,63-17,37,=10,63-17,(100-63),=-17,100+27,63,7,输,出,出,使,使,得,得,ax+by=gcd(a,b),的,gcd(a,b),和,x,y,的,推,推,理,理,过,过,程,程,.,记,a,0,=a,a,1,=b,则,求,求,ax+by=gcd(a,b),的,过,过,程,程,可,可,写,写,为,为,：,：,即,8,欧,几,几,里,里,得,得,算,算,法,法,：,：,-,计,算,算,gcd(a,b),和,使,使,ax+by=gcd(a,b),成,立,立,的,的,x,y.,Step1,A,a;B,b;s=1;t=0;x=0;y=1,;,Step2,计,算,算,带,带,余,余,除,除,法,法,，,，,求,求,出,出,满,满,足,足,A=qB+r,和,0,=r0,时,执,行,行,A,B;B,r,w,x;x,s-qx;s,w;,w,y;y,t-qy;t,w;,后返回执行,Step2.,9,欧几里得算,法,法：,-,计算,gcd(a(x),b(x),和使,z(x)a(x)+y(x)b(x)=gcd(a(x),b(x),成立的,z(x),y(x).,Step1,A(x),a(x);B(x),b(x);s(x)=1;t(x)=0;z(x)=0;y(x)=1;,Step2,计算带余除,法,法，求出满,足,足,A(x)=q(x)B(x)+r(x),和,deg(r)deg(B),的,q(x),和,r(x).,Step3,当,r(x)=0,时,输出,B(x)=gcd(a(x),b(x),和,z(x),m(x),;,当,r(x)!=0,时,执行,A(x),B(x);B(x)r(x),w(x),z(x);z(x)s(x)-q(x)z(x);s(x)w(x);,w(x),y(x);y(x)t(x)-q(x)v(x);t(x)w(x);,后返回执行,Step2.,10,辗转相除法,的,的,C,语言算法,int inverse(a),int a;,registerintn1,n2,q,r,b1,b2,t;,if(!a)b2=0;,else n1=n;n2=a;b2=1;b1=0;,do,r=(n1%n2);q=(n1-r)/n2;,if(!r)if(b20)b2=n+b2;,else n1=n2;n2=r;t=b2;b2=b1-q*b2;b1=t;,while(r);,return(b2);,11,例子：,求,10110110,在,modb(x),中的逆,10110110,a(x)=x,7,+x,5,+x,4,+x,2,+x,b(x)=x,8,+x,4,+x,3,+x+1100011011,求,z(x),满足,z(x)a(x)+y(x)b(x)=1.,解：,step1:A(x)=a(x),B(x)=b(x),s(x)=1,z(x)=0,t(x)=0,y(x)=1;,step2:A(x)=0*B(x)+r(x),r(x)=a(x);,由于,r(x)!=0,，则,A(x)=B(x),B(x)=r(x);,w(x)=z(x)=0;z(x)=s(x)-q(x)z(x)=s(x)=1;s(x)=w(x)=0,执行,step2(100011011)=x*(10110110)+r,故,q(x)=x;r(x)=(01110111),A(x)=,(10110110);B(x)=r(x);,w(x)=1,z(x)=x;s(x)=1;,执行,step2(10110110)=x*(01110111)+r,q(x)=x;r(x)=(01011000),w(x)=x,z(x)=x,2,+1;s(x)=x;,12,w(x)=z(x);z(x)=s(x)-q(x)z(x);s(x)=w(x),执行,step2(01110111)=1*(01011000)+r,q(x)=1;r(x)=(00101111),w(x)=x,2,+1,z(x)=x,2,+x+1;s(x)=x,2,+1;,执行,step2(01011000)=x*(00101111)+r,q(x)=x;r(x)=(00000110),w(x)=x,2,+x+1,z(x)=x,3,+x+1;s(x)=x,2,+x+1,执行,step2(00101111)=(,x,3,+x,2,+1,)*(110)+r,q(x)=,x,3,+x,2,+1,;r(x)=1,w(x)=x,3,+1,z(x)=x,6,+x,5,+x,4,+x,3,;s(x)=x,3,+1,执行,step2(110)=(,x,2,+x,)*1+r,r(x)=0,故,z(x)=x,6,+x,5,+x,4,+x,3,即,(,10110110),-,=(01111000),13,15个候选,算,算法,Rijndael,RC6,Mars,Serpent,Twofish,(,前,5,个算法是第,二,二轮筛选出的,5,个决赛算法,),CASt-256,CRYPTON,DEAL,DFC,E2,FROG,HPC,MAGENTA,Safer+,LOKI97,14,先进对称分,组,组加密算法,的,的特点,可变的密钥,长,长度,:RC5,混合的运算,IDEA,数据相关的,圈,圈数,RC5,密钥相关的,圈,圈数,CAST-128,密钥相关的,S,盒,:Blowfish,冗长密钥调,度,度算法：,Blowfish,可变的,F,：,CAST-128,可变长明文,/,密文块长度,可变圈数,每圈操作作,用,用于全部数,据,据,15,分组密码的,一,一般设计原,理,理,针对安全性,的,的一般原则,:,混乱,扩散,重要的设计,原,原理,:,必须能抵抗,现,现有的攻击,方,方法,针对实现的,原,原则,软件,硬件,16,分组密码的,整,整体结构,Feistel 网络:DES,SP网络:AES,其它密码结,构,构：Frog,17,S盒的设计,准,准则,S-,盒首次出现,在,在,Lucifer,算法中,因,DES,的使用而流,行,行,.,S-,盒是许多密,码,码算法的唯,一,一非线性部,件,件,因此,它的密码强,度,度决定了整,个,个算法的安,全,全强度,.,提供了密码,算,算法所必须,的,的混乱作用,.,如何全面准,确,确地度量,S-,盒的密码强,度,度和设计有,效,效的,S-,盒是分组密,码,码设计和分,析,析中的难题,.,非线性度、,差,差分均匀性,、,、严格雪崩,准,准则、可逆,性,性、没有陷,门,门,18,本章需要掌,握,握的主要内,容,容,分组密码的,基,基本概念及,原,原理,DES,分组密码算,法,法及安全性,分,分析,分组密码的,加,加密模式（,4,种）及短块,处,处理方法,IDEA,算法及共处,理,理变换的加,解,解密相似性,辗转相除法,及,及求模的逆,元,元,序列密码,19,9,、静夜,四,四无邻,，,，荒居,旧,旧业贫,。,。11月-2211月-22,Friday,November 4,2022,10,、雨中,黄,黄叶树,，,，灯下,白,白头人,。,。21:31:0221:31:0221:31,11/4/20229:31:02PM,11,、以我独,沈,沈久，愧,君,君相见频,。,。11月-2221:31:0221:31,Nov-2204-Nov-22,12,、故人江,海,海别，几,度,度隔山川,。,。21:31:0221:31:0221:31,Friday,November4,2022,13,、,乍,乍,见,见,翻,翻,疑,疑,梦,梦,，,，,相,相,悲,悲,各,各,问,问,年,年,。,。,。,。11,月,月-2211,月,月-2221:31:0221:31:02,November 4,2022,14,、他乡生白,发,发，旧国见,青,青山。04 十一,月,月 20229:31:02 下午21:31:0211月-22,15,、比,不,不了,得,得就,不,不比,，,，得,不,不到,的,的就,不,不要,。,。十一,月,月229:31,下,下,午,午11,月,月-2221:31,November4,2022,16,、行,动,动出,成,成果,，,，工,作,作出,财,财富,。,。2022/11/421:31:0221:31:02,04November2022,17,、做前，,能,能够环视,四,四周；做,时,时，你只,能,能或者最,好,好沿着以,脚,脚为起点,的,的射线向,前,前。9:31:02,下,下午9:31,下,下午21:31:0211月-22,9,、没有失败,，,，只有暂时,停,停止成功！,。,。11月-2211月-22,Friday,November 4,2022,10,、很多事,情,情努力了,未,未必有结,果,果，但是,不,不努力却,什,什么改变,也,也没有。,。,。21:31:0221:31:0221:31,11/4/20229:31:02PM,11,、成,功,功就,是,是日,复,复一,日,日那,一,一点,点,点小,小,小努,力,力的,积,积累,。,。11,月,月-2221:31:0221:31,Nov-2204-Nov-22,12,、世间,成,成事，,不,不求其,绝,绝对圆,满,满，留,一,一份不,足,足，可,得,得无限,完,完美。,。,。21:31:0221:31:0221:31,Friday,November 4,2022,13,、不知香,积,积寺，数,里,里入云峰,。,。11月-2211月-2221:31:0221:31:02,November4,2022,14,、,意,意,志,志,坚,坚,强,强,的,的,人,人,能,能,把,把,世,世,界,界,放,放,在,在,手,手,中,中,像,像,