《【安全课件】第12讲--分组密码小节课件.pptx》由会员分享，可在线阅读，更多相关《【安全课件】第12讲--分组密码小节课件.pptx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分组密码小结 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=rb,并记并记amodb=r.引理引理3 设a、b、r为不全为零的整数，且a=bq+r，则gcd(a,b)=gcd(b,r).证明：设d=gcd(a,b)，由于d|a=bq+r,且
2、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 Aa;BbStep2 计算带余除法，求出满足A=qB+r和0=r0时,执行AB;Br后返回执行 Step2.5例例1 计算gcd(63,100)解解 63=0100+63,100=163+37,63=137+26 37=126+11,26=211+4,11=24+3,4=13+1,3=31+0 故gcd(63,100)=1.6系数的计算倒推进行(将余数代入):1=
3、4-13=4-1(11-24)=-111+(1+2)4=-111+34=-111+3(26 211)=-711+326=-7(37 26)+326 =-737+(7+3)26=-737+1026 =-737+10(63-37)=1063-1737 =1063-17(100-63)=-17100+27637输出使得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 Aa;Bb;s=1;t=0;x=0;y=
4、1;Step2 计算带余除法，求出满足 A=qB+r和0=r0时,执行 AB;Br wx;xs-qx;sw;wy;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(
5、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-
6、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
7、(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(
8、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+x2+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即(10110110)-=(01111000)1315个候选算法RijndaelRC6MarsSerpen
9、tTwofish(前前前前5 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分组密码的一般设计原理针对安全性的一般原则:混乱扩散重要的设计原理:必须能抵抗现
10、有的攻击方法针对实现的原则软件硬件16分组密码的整体结构Feistel 网络:DESSP网络:AES其它密码结构：Frog17S盒的设计准则S-盒首次出现在Lucifer算法中,因DES的使用而流行.S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度.提供了密码算法所必须的混乱作用.如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题.非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门18本章需要掌握的主要内容本章需要掌握的主要内容分组密码的基本概念及原理分组密码的基本概念及原理DES分组密码算法及安全性分析分组密码算法及安全性分析分
11、组密码的加密模式（分组密码的加密模式（4种）及短块处理方法种）及短块处理方法IDEA算法及共处理变换的加解密相似性算法及共处理变换的加解密相似性辗转相除法及求模的逆元辗转相除法及求模的逆元序列密码191、有时候读书是一种巧妙地避开思考的方法。3月-233月-23Monday,March 6,20232、阅读一切好书如同和过去最杰出的人谈话。13:39:3413:39:3413:393/6/2023 1:39:34 PM3、越是没有本领的就越加自命不凡。3月-2313:39:3413:39Mar-2306-Mar-234、越是无能的人，越喜欢挑剔别人的错儿。13:39:3513:39:3513:
12、39Monday,March 6,20235、知人者智，自知者明。胜人者有力，自胜者强。3月-233月-2313:39:3513:39:35March 6,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。06三月20231:39:35下午13:39:353月-237、最具挑战性的挑战莫过于提升自我。三月231:39下午3月-2313:39March 6,20238、业余生活要有意义，不要越轨。2023/3/613:39:3513:39:3506 March 20239、一个人即使已登上顶峰，也仍要自强不息。1:39:35下午1:39下午13:39:353月-2310、你要做多大的事情，就该承受多大的压力。3/6/2023 1:39:35 PM13:39:3506-3月-2311、自己要先看得起自己，别人才会看得起你。3/6/2023 1:39 PM3/6/2023 1:39 PM3月-233月-2312、这一秒不放弃，下一秒就会有希望。06-Mar-2306 March 20233月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Monday,March 6,202306-Mar-233月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。3月-2313:39:3506 March 202313:39谢谢大家谢谢大家