【文档说明】【安全课件】第12讲--分组密码小节.pptx，共(19)页，140.633 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-288096.html

以下为本文档部分文字说明：

分组密码小结王滨2005.03.251主要内容▪欧几里德算法▪求最大公约数▪求模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<=r<b,并记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)▪Step1Aa;Bb▪Step2计算带余除法，求出满足A=qB+r和0<=r<B的q和r.▪Step3当r=0时,输出B=gcd(a,b);当r>0时,执行AB;Br后返回执行Step

2.5▪例1计算gcd(63,100)▪解63=0×100+63,100=1×63+37,63=1×37+2637=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×637输出使得ax+by=gcd(a,b)的gcd(a,b)和x,y的推理过程.▪记a0=a,a1=b,则求ax+by=gcd(a,b)的过

程可写为：▪即0,22111132112100=+=+=+=+=++++−−kkkkkkkkkaaaqaaaqaaaqaaaqa且0,22111121131002=+=−=−=−=+++−−+kk

kkkkkkkaaaqaaqaaaqaaaqaa且8欧几里得算法：----计算gcd(a,b)和使ax+by=gcd(a,b)成立的x,y.Step1Aa;Bb;s=1;t=0;x=0;y=1;S

tep2计算带余除法，求出满足A=qB+r和0<=r<B的q和r.Step3当r=0时,输出B=gcd(a,b)和x,y;当r>0时,执行AB;Brw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).Step1A(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语言算法intinverse(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(b2<0)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)=x7+x5+x4+x2+x,b(x)=x8+x4+x3+x+1→1000110

11,求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)+rq(x)=x;r(x)=(01011000),w(x)=x,z(x)

=x2+1;s(x)=x;12w(x)=z(x);z(x)=s(x)-q(x)z(x);s(x)=w(x)执行step2(01110111)=1*(01011000)+rq(x)=1;r(x)=(00101111),w(x)=x2+1,z(x)=x2+x+1;s(x

)=x2+1;执行step2(01011000)=x*(00101111)+rq(x)=x;r(x)=(00000110),w(x)=x2+x+1,z(x)=x3+x+1;s(x)=x2+x+1执行step2(00101111)=(x3+x

2+1)*(110)+rq(x)=x3+x2+1;r(x)=1,w(x)=x3+1,z(x)=x6+x5+x4+x3;s(x)=x3+1执行step2(110)=(x2+x)*1+rr(x)=0故z(x)=x6+x5+x4+x3即(101101

10)-=(01111000)1315个候选算法▪Rijndael▪RC6▪Mars▪Serpent▪Twofish(前5个算法是第二轮筛选出的5个决赛算法)CASt-256,CRYPTON,DEAL,DFC,E2,FROG,HPC,MAGENTA,Safer+,LOKI9714先进对称分

组加密算法的特点▪可变的密钥长度:RC5▪混合的运算IDEA▪数据相关的圈数RC5▪密钥相关的圈数CAST-128▪密钥相关的S盒:Blowfish▪冗长密钥调度算法：Blowfish▪可变的F：CAST-128▪可变长明文/密文块长度▪可变圈数▪每圈操作作用于全部数据15分组密

码的一般设计原理▪针对安全性的一般原则:➢混乱➢扩散▪重要的设计原理:必须能抵抗现有的攻击方法▪针对实现的原则➢软件➢硬件16分组密码的整体结构▪Feistel网络:DES▪SP网络:AES▪其它密码结构：Frog17S盒的设计准则▪S-盒首次出现在Lucif

er算法中,因DES的使用而流行.▪S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度.▪提供了密码算法所必须的混乱作用.▪如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题.▪非线性度、差分均

匀性、严格雪崩准则、可逆性、没有陷门18本章需要掌握的主要内容▪分组密码的基本概念及原理▪DES分组密码算法及安全性分析▪分组密码的加密模式（4种）及短块处理方法▪IDEA算法及共处理变换的加解密相似性▪辗转相除法及求模的逆元序列密码19