单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分组密码小结,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;Bb,Step2,计算带余除法，求出满足,A=qB+r,和,0=r0,时,执行,A,B;Br,后返回执行,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),=-111+(1+2)4=-1,11,+3,4,=-1,11,+3(26 2,11,)=-7,11,+3,26,=-7(37,26,)+3,26,=-737+(7+3),26,=-737+10,26,=-737+10(63-37),=1063-17,37,=1063-17(100-63),=-17100+2763,7,输出使得,ax+by=gcd(a,b),的,gcd(a,b),和,x,y,的推理过程,.,记a0=a,a1=b,那么求ax+by=gcd(a,b)的过程可写为：,即,8,欧几里得算法：,-,计算,gcd(a,b),和使,ax+by=gcd(a,b),成立的,x,y.,Step1,A,a;Bb;s=1;t=0;x=0;y=1,;,Step2,计算带余除法，求出满足,A=qB+r,和,0,=r0,时,执行,A,B;Br,w,x;xs-qx;sw;,w,y;yt-qy;tw;,后返回执行,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;,register int n1,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),中的逆,10110110a(x)=x7+x5+x4+x2+x,b(x)=x8+x4+x3+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)=x2+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,