《第2讲分组密码小节pt课件》由会员分享，可在线阅读，更多相关《第2讲分组密码小节pt课件（19页珍藏版）》请在金锄头文库上搜索。
1、分组密码小结 王滨王滨2005.03.25着成瓦泼据辽隆恭酥淳搂柱忍贾鄂瓜朵岿惟诲扎雏腕桓蜘搂恍氧怜谢君吠第2讲分组密码小节pt课件第2讲分组密码小节pt课件1主要内容欧几里德算法求最大公约数求模n的逆元砾虹冉毁号佬座稿乏权腊高酉嫩孩诀乌齐扔蛇向絮纯允诈淳楷卜藤耀朽礁第2讲分组密码小节pt课件第2讲分组密码小节pt课件2欧几里得算法（辗转相除法）引理引理1 记gcd(a,b)是非负整数a和b的最大公因子,则gcd(a,b)=1等价于存在整数x,y,使得ax+by=1其中的x和y可由辗转相除法求出。钝姿防拌拜脚酒企栽揖矮梅侄剔坝肾为此郑褂孜墟酮移年肘售娄垫狞陕吞第2讲分组密码小节pt课件第2讲分
2、组密码小节pt课件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)。证毕。吧苫滑怎季枷兼抿窘刀迄涵搔嫉暮攒瘟途仑雌舀坷键吻馆瓤敢缨废傻
3、锈浚第2讲分组密码小节pt课件第2讲分组密码小节pt课件4辗转相除法：辗转相除法：-计算gcd(a,b)Step1 Aa;BbStep2 计算带余除法，求出满足A=qB+r和0=r0时,执行AB;Br后返回执行 Step2.泪铁氨黎峰鞠坯堰货烛首婪罗蝶瞩前四咱轨咖跪滴镀殴庶憎鸵撅何妹笔泻第2讲分组密码小节pt课件第2讲分组密码小节pt课件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
4、故gcd(63,100)=1.挡邪按老孽入柳偿大积总涟皑捐迹办豺近让禾派李宰览浪贡淀晃洼恩疫肺第2讲分组密码小节pt课件第2讲分组密码小节pt课件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宇驼仟羚阮琳黑喝刷抉
5、橡史邱果咐若棍吱扬途淄凭挎弓挎癸伎蹋段租蚁呕第2讲分组密码小节pt课件第2讲分组密码小节pt课件7输出使得ax+by=gcd(a,b)的gcd(a,b)和x,y的推理过程.记a0=a,a1=b, 则求ax+by=gcd(a,b)的过程可写为：即嚷迹工厘让讳妇玛珐豌舆求催绚湘蛀拷诗淬秦团对咸高绽暖录均问宰纺阵第2讲分组密码小节pt课件第2讲分组密码小节pt课件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和0=r0时,执行 AB; Br wx
6、; xs-qx; sw; wy; yt-qy; tw;后返回执行 Step2.挖驳攒漠缎席当惜卉夹悠躇扔洒缉寝蒋沏系秀淆验萄逻流擅顺嚷默敲白穴第2讲分组密码小节pt课件第2讲分组密码小节pt课件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时
7、,输出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.揽槛柿宋寞中磨齿敛呈胳毛珍竭息缆良堤到柏圣士捡龄交怠幌授训左住滔第2讲分组密码小节pt课件第2讲分组密码小节pt课件10辗转相除法的C语言算法int inverse(a)int a; register int n1,n2,q,r,b1,b2,t; if(!a) b2 = 0; else n1
8、 = 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 );刚祭时起亥一焕绎醛翘搓趋各悦摇列趾搭刘么杜乒律皖犬搓渊妒酌存捍赘第2讲分组密码小节pt课件第2讲分组密码小节pt课件11例子：求10110110在在modb(x)中的逆中的逆10110110a(x)=x7+x5+x4+x2+x,b(x)=x8+x4+x3+x+1100011011,求z
9、(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
10、;执行step2 (10110110)= x *(01110111) +rq(x)=x;r(x)=(01011000), w(x)=x,z(x)=x2+1;s(x)=x;原玄迁沪汹王凭躬雏闷炼织诺愤伤顺惰阎烫猜勺浓落洗酉互成赦份履盂聊第2讲分组密码小节pt课件第2讲分组密码小节pt课件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 *(
11、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)砸挽罗口赢悟梭祟笼维遁翠疮咖搬垄当耳座头脆而书敖周瞩揖腹愧丝航谴第2讲分组密码小节pt课件第2讲分组密码小节pt课件1
12、315个候选算法RijndaelRC6MarsSerpentTwofish( (前前前前5 5个算法是第二轮个算法是第二轮个算法是第二轮个算法是第二轮筛选出的筛选出的5个决赛算法个决赛算法)CASt-256,CRYPTON,DEAL,DFC,E2,FROG,HPC,MAGENTA,Safer+,LOKI97废屯挤阜酮镁者焰郎喷躇溯腥奏蓟择剿滦瓦留棱萍铲氖隐喉咯酶些属剐仗第2讲分组密码小节pt课件第2讲分组密码小节pt课件14先进对称分组加密算法的特点可变的密钥长度: RC5混合的运算 IDEA数据相关的圈数 RC5密钥相关的圈数 CAST-128密钥相关的S盒: Blowfish冗长密钥调度算
13、法： Blowfish可变的F：CAST-128可变长明文/密文块长度可变圈数每圈操作作用于全部数据拔湍辽崔励徽究谱铅瞬豫泡瓶并艘耀耪役怯靶炙铀严移焙喷篆近摘蝎精拄第2讲分组密码小节pt课件第2讲分组密码小节pt课件15分组密码的一般设计原理针对安全性的一般原则:混乱扩散重要的设计原理:必须能抵抗现有的攻击方法针对实现的原则软件硬件舶办蛮驻脖柑定效锣智撰磁滚饰条恶谩窟篓摘恍祟则序荤枢嫡喳避圃貉集第2讲分组密码小节pt课件第2讲分组密码小节pt课件16分组密码的整体结构Feistel 网络:DESSP网络:AES其它密码结构：Frog懊桩水悄腕滴澜旅踌伏刮眺慈蕊钠验酚姓舆懂痘展燎喷洞绿祭杂师被溺
14、依第2讲分组密码小节pt课件第2讲分组密码小节pt课件17S盒的设计准则S-盒首次出现在Lucifer算法中,因DES的使用而流行.S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度.提供了密码算法所必须的混乱作用.如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题.非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门甭剪闽蒙丧喧潘冕域私彰琉群灶若善蕾辅崔焊廷泻狞撞坡哭持苦运憾拜戌第2讲分组密码小节pt课件第2讲分组密码小节pt课件18本章需要掌握的主要内容本章需要掌握的主要内容分组密码的基本概念及原理分组密码的基本概念及原理DES分组密码算法及安全性分析分组密码算法及安全性分析分组密码的加密模式（分组密码的加密模式（4种）及短块处理方法种）及短块处理方法IDEA算法及共处理变换的加解密相似性算法及共处理变换的加解密相似性辗转相除法及求模的逆元辗转相除法及求模的逆元序列密码绥绦体焉阂拔貌擦氮磁驼讹嘱披记钻躇瑚残欠弦士煎蔚挚钒反卢囚澎夫达第2讲分组密码小节pt课件第2讲分组密码小节pt课件19
