《【安全课件】第12讲--分组密码小节精编版》由会员分享，可在线阅读，更多相关《【安全课件】第12讲--分组密码小节精编版（20页珍藏版）》请在金锄头文库上搜索。
1、分组密码小结,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，
2、则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;Bb Step2 计算带余除法，求出满足 A=qB+r和00时,执行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,10
3、0)=1.,6,系数的计算,倒推进行(将余数代入): 1 = 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 + 2763,7,输出使得ax+by=gcd(a,b)的gcd(a,b)和x,y的推理过程.,记a0=a,a1=b, 则求ax+by=gcd(a,b)的过程可写
4、为： 即,8,欧几里得算法：-计算gcd(a,b)和使ax+by=gcd(a,b)成立的x,y.,Step1 Aa;Bb;s=1;t=0;x=0;y=1; Step2 计算带余除法，求出满足 A=qB+r和00时,执行 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 计算带余除法，求出
5、满足 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;
6、 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)
7、=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
8、)=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)=x2+1,z(x)= x2+x+1;s(x)=x2+1; 执行step2 (01011000) =x *(00101111) +r q(x)=x;r(x)=(00000110), w(x)=x2+x+1,z(x)=x3+x+1;s(x)=x2+x+1 执行step2 (00101111) =
9、(x3+x2+1) *(110) +r q(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 +r r(x) =0故z(x)=x6+x5+x4+x3 即(10110110)-=(01111000),13,15个候选算法,Rijndael RC6 Mars Serpent Twofish (前5个算法是第二轮筛选出的5个决赛算法) CASt-256,CRYPTON,DEAL,DFC,E2, FROG,HPC,MAGENTA,Safer+,LOKI97,14,先进对称分组加密算法的特点
10、,可变的密钥长度: RC5 混合的运算 IDEA 数据相关的圈数 RC5 密钥相关的圈数 CAST-128 密钥相关的S盒: Blowfish 冗长密钥调度算法： Blowfish 可变的F：CAST-128 可变长明文/密文块长度 可变圈数 每圈操作作用于全部数据,15,分组密码的一般设计原理,针对安全性的一般原则: 混乱 扩散 重要的设计原理:必须能抵抗现有的攻击方法 针对实现的原则 软件 硬件,16,分组密码的整体结构,Feistel 网络:DES SP网络:AES 其它密码结构：Frog,17,S盒的设计准则,S-盒首次出现在Lucifer算法中,因DES的使用而流行. S-盒是许多密
11、码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度. 提供了密码算法所必须的混乱作用. 如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题. 非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门,18,本章需要掌握的主要内容,分组密码的基本概念及原理 DES分组密码算法及安全性分析 分组密码的加密模式（4种）及短块处理方法 IDEA算法及共处理变换的加解密相似性 辗转相除法及求模的逆元,序列密码,19,1、有时候读书是一种巧妙地避开思考的方法。20.9.1620.9.16Wednesday, September 16, 2020 2、阅读一切好书如
12、同和过去最杰出的人谈话。10:39:2510:39:2510:399/16/2020 10:39:25 AM 3、越是没有本领的就越加自命不凡。20.9.1610:39:2510:39Sep-2016-Sep-20 4、越是无能的人，越喜欢挑剔别人的错儿。10:39:2510:39:2510:39Wednesday, September 16, 2020 5、知人者智，自知者明。胜人者有力，自胜者强。20.9.1620.9.1610:39:2510:39:25September 16, 2020 6、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2020年9月16日星期三上午10时39分25
13、秒10:39:2520.9.16 7、最具挑战性的挑战莫过于提升自我。2020年9月上午10时39分20.9.1610:39September 16, 2020 8、业余生活要有意义，不要越轨。2020年9月16日星期三10时39分25秒10:39:2516 September 2020 9、一个人即使已登上顶峰，也仍要自强不息。上午10时39分25秒上午10时39分10:39:2520.9.16 10、你要做多大的事情，就该承受多大的压力。9/16/2020 10:39:25 AM10:39:252020/9/16 11、自己要先看得起自己，别人才会看得起你。9/16/2020 10:39 AM9/16/2020 10:39 AM20.9.1620.9.16 12、这一秒不放弃，下一秒就会有希望。16-Sep-2016 September 202020.9.16 13、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Wednesday, September 16, 202016-Sep-2020.9.16 14、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。20.9.1610:39:2516 September 202010:39,谢谢大家,
