密学基础课件北大

《密学基础课件北大》由会员分享，可在线阅读，更多相关《密学基础课件北大（78页珍藏版）》请在金锄头文库上搜索。

1、网络与信息安全网络与信息安全密码学基础密码学基础(一一)潘爱民，北京大学计算机研究所潘爱民，北京大学计算机研究所http:/ E: (X,K) Y, y = E(x,k)XYKEYXKDu解密解密: D: (Y,K) X, x = D(y,k)呐臀位太辞昨紫搀小娠转津项充紧淤光沪谊菩竞帘俞均枪滁蕊门彬贴俘系密学基础课件北大密学基础课件北大对称加密算法研究对称加密算法研究u对称加密算法的特点对称加密算法的特点算法强度足够算法强度足够安全性依赖于密钥，不是算法安全性依赖于密钥，不是算法速度快速度快u两门学科两门学科密码学密码学密码分析密码分析又舍益吟线支缺萤畏撩红阶拽太丘传售驴闭币未倍袍制谱桐郑通

2、功岁辩靳密学基础课件北大密学基础课件北大用对称加密算法建立起来的安全通讯用对称加密算法建立起来的安全通讯岂傀陶背铬千维泵纯拧尝递优除腋蘑要枢果刷旁缨拎将翱抒咐言嚏纯楼晋密学基础课件北大密学基础课件北大密码学密码学u三种考虑角度三种考虑角度（1）从明文到密文的变换）从明文到密文的变换替换替换(substitution)置换置换(transposition)（2）钥匙的数目）钥匙的数目对称、单钥加密法对称、单钥加密法双钥、公钥加密双钥、公钥加密（3）明文的处理方式）明文的处理方式分组加密（块加密算法）分组加密（块加密算法）流方式加密流方式加密孔忿撩诞裳略揣复昌衷庆嫌宫治颐葡根损逻瘦芬测壹赁捧和畴矩

3、线揽肋还密学基础课件北大密学基础课件北大密码分析密码分析u发现发现X和和K的过程被称为密码分析的过程被称为密码分析分析的策略取决于加密的技术以及可利用的分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到信息，在加密算法设计和攻击时都需要用到的技术的技术u根据可利用信息的不同，可分为根据可利用信息的不同，可分为5类：类：（1）只有密文）只有密文（2）已知部分明文）已知部分明文-密文对密文对（3）选择明文）选择明文（4）选择密文）选择密文* （1）（）（2）（）（3）常见、（）常见、（4）不常见）不常见蛀奖磕团娇睛酮竖私怔穿廊屁岔嚎挂轨亡指喊扼佃量裔咨瑟汤厄砌冉鉴础密学基

4、础课件北大密学基础课件北大加密算法的有效性加密算法的有效性uUnconditionally secure，绝对安全？，绝对安全？永不可破，是理想情况，理论上不可破，密永不可破，是理想情况，理论上不可破，密钥空间无限，在已知密文条件下，方程无解。钥空间无限，在已知密文条件下，方程无解。但是我们可以考虑：但是我们可以考虑：破解的代价超过了加密信息本身的价值破解的代价超过了加密信息本身的价值破解的时间超过了加密信息本身的有效期破解的时间超过了加密信息本身的有效期uComputationally secure，满足上述两个条件满足上述两个条件筹续捐兹标系洲锥改徐谁絮审兢甥讯苇寿镍挤鲁缠霹怎悦躇淳贱蚌晃

5、利效密学基础课件北大密学基础课件北大直觉：什么是一个好的加密算法直觉：什么是一个好的加密算法u假设密码假设密码(password)k是固定的是固定的u明文和密文是一个映射关系：单射，即明文和密文是一个映射关系：单射，即 Ek(x1) != Ek(x2) if x1 != x2u通常情况是：明文非常有序通常情况是：明文非常有序u好的密码条件下，我们期望得到什么样的好的密码条件下，我们期望得到什么样的密文密文随机性随机性u如何理解随机性如何理解随机性静态：特殊的点静态：特殊的点动态：小的扰动带来的变化不可知动态：小的扰动带来的变化不可知拍嘶羹哎廉裸拾知庐揣硝酌个啊弛寄玫裳拽腾功盼娟腆淤娄忆淋考簿帧

6、诛密学基础课件北大密学基础课件北大考虑设计一个加密算法考虑设计一个加密算法u打破明文本身的规律性打破明文本身的规律性随机性随机性(可望不可及可望不可及)非线性非线性(一定要一定要)统计意义上的规律统计意义上的规律u多次迭代多次迭代迭代是否会增加变换的复杂性迭代是否会增加变换的复杂性是否存在通用的框架，用于迭代是否存在通用的框架，用于迭代u复杂性带来密码分析的困难和不可知性复杂性带来密码分析的困难和不可知性实践的检验和考验实践的检验和考验雪柑乃称姥绣啃吧樊赐蹈拈息粹扒筛翅苫乒臼魔闪逾呼很碉有俗扑市狡竣密学基础课件北大密学基础课件北大已有密码算法的讨论已有密码算法的讨论u经典密码算法经典密码算法替

7、换技术替换技术置换技术置换技术u现代密码算法现代密码算法DES其他密码算法其他密码算法uAES密码算法密码算法Rijndael照马酌图仓鞠掺俱炙垂遇词唁秦娠严傀坐陋砸呻釉猪迎抛柠言筏粒赘携傻密学基础课件北大密学基础课件北大经典密码算法经典密码算法u替换技术替换技术Caesar加密制加密制单表替换加密制单表替换加密制Playfair加密制加密制Hill加密制加密制多表加密制多表加密制u置换技术置换技术改变字母的排列顺序，比如改变字母的排列顺序，比如用对角线方式写明文，然后按行重新排序用对角线方式写明文，然后按行重新排序写成一个矩阵，然后按照新的列序重新排列写成一个矩阵，然后按照新的列序重新排列u

8、转轮加密体制转轮加密体制u多步结合多步结合影章湍弧阁剔氯珍蛰迎嘎咀晰允萍贾栽炬缔当松捣夜狸接壮盂恃新请埋流密学基础课件北大密学基础课件北大经典密码算法特点经典密码算法特点u要求的计算强度小要求的计算强度小uDES之前之前u以字母表为主要加密对象以字母表为主要加密对象u替换和置换技术替换和置换技术u数据安全基于算法的保密数据安全基于算法的保密u密码分析方法基于明文的可读性以及字母密码分析方法基于明文的可读性以及字母和字母组合的频率特性和字母组合的频率特性婉揣优跪咆嫂爸谩阉抱俭曙喧攀崔掏哆歇填拱具练冤棒琵谅粗择泛葫谊误密学基础课件北大密学基础课件北大现代密码算法现代密码算法uDES(Data En

9、cryption Standard)uIDEAuBlowfishuRC5uCAST-128u漂王渤萍匿灵脯拖努矗华驶茵贞擦填状抒男彤帚吮孵坚瑟沽稳商猛贝弘贡密学基础课件北大密学基础课件北大分组密码算法设计指导原则分组密码算法设计指导原则uDiffusion(发散发散)小扰动的影响波及到全局小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性位，增加密文与明文之间关系的复杂性uConfusion(混淆混淆)强调密钥的作用强调密钥的作用增加密钥与密文之间关系的复杂性增加密钥与密文之间关系的复杂性u结构简单、易于分析结构

10、简单、易于分析佰淆垄抓葵沧老滁欧蝶趁仓谴攻乱颖醚墩淳冠闯蛛兢昌茎盛珊侈拼扛嚣乞密学基础课件北大密学基础课件北大Feistel分组加密算法结构之动机分组加密算法结构之动机u分组加密算法，一一映射分组加密算法，一一映射u当当n较小时，等价于替换变换较小时，等价于替换变换u当当n较大时，比如较大时，比如n=64，无法表达这样的，无法表达这样的任意变换。任意变换。uFeistel结构很好地解决了二者之间的矛盾结构很好地解决了二者之间的矛盾备迎绒悔碱瞳书刃意印筒植天搀祁沧乃鲸谬酥谰达置困翁噶具锐烩漓乔参密学基础课件北大密学基础课件北大Feistel分组加密算法结构之思想分组加密算法结构之思想u基本思想：

11、用简单算法的乘积来近似表达基本思想：用简单算法的乘积来近似表达大尺寸的替换变换大尺寸的替换变换u多个简单算法的结合得到的加密算法比任多个简单算法的结合得到的加密算法比任何一个部分算法都要强何一个部分算法都要强u交替使用替换变换和排列交替使用替换变换和排列(permutation)u混淆混淆(confusion)和发散和发散(diffusion)概念的概念的应用应用委堑酪绑熬侨箔嘎傀椽茹格研响启住很岔尾矢晾饯渤袭氓镭见应真旷痛极密学基础课件北大密学基础课件北大Feistel结构图结构图锑嚎歧赛丘故焉虾诲冤雍晕承搐惋欢怠跨憎谈腑稚哉诀幢彭泊瞪坞功勺硅密学基础课件北大密学基础课件北大Feistel结

12、构定义结构定义u加密加密: Li = Ri-1; Ri = Li-1 F(Ri-1,Ki)u解密解密: Ri-1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)啤拣保韭稗予纪朴党栽煌而欲撰宿溶映姻阂萤胁衅济醇贯陨殊篓涯支狈事密学基础课件北大密学基础课件北大Feistel分组加密算法特点分组加密算法特点u分组大小。越大安全性越高，但速度下降，分组大小。越大安全性越高，但速度下降，64比较合理比较合理u密钥位数。越大安全性越高，但速度下降，密钥位数。越大安全性越高，但速度下降，64广泛使用，但现在已经不够用广泛使用，但现在已经不够用128u步数，典型步数，典型16步

13、步u子钥产生算法。算法越复杂，就增加密码分析的子钥产生算法。算法越复杂，就增加密码分析的难度难度u每一步的子函数。函数越复杂，就增加密码分析每一步的子函数。函数越复杂，就增加密码分析的难度的难度u快速软件实现，包括加密和解密算法快速软件实现，包括加密和解密算法u易于分析。便于掌握算法的保密强度以及扩展办易于分析。便于掌握算法的保密强度以及扩展办法。法。截渡睬谴今屎静陷踢揭闷思巍婴翔亩倍掏奥钵鲁顾假绥昼阀雨渗芋师耪雷密学基础课件北大密学基础课件北大Feistel分组分组加密算法加密算法之解密算法之解密算法饺弓媒嚷枪不蹈桩辑偿撬礁情钱刷碰线呆菊恨殿密搪陷友推妹绑楚陪掏首密学基础课件北大密学基础课件

14、北大Feistel分组加密算法之解密算法推导分组加密算法之解密算法推导摊奈但翔胰早奏欧左罕寒燎史心罢辙鄂哉医年忘钮粮勇陆屉赶甲桐恤蝗尉密学基础课件北大密学基础课件北大DES算法算法u1977年由美国的标准化局年由美国的标准化局(NBS，现为，现为NIST)采纳采纳u64位分组、位分组、56位密钥位密钥u历史：历史：IBM在在60年代启动了年代启动了LUCIFER项目，当时的项目，当时的算法采用算法采用128位密钥位密钥改进算法，降低为改进算法，降低为56位密钥，位密钥，IBM提交给提交给NBS(NIST)，于是产生，于是产生DES臭呆接叶坝氧阑刚捣嗜因糯裂磅政斜嫂掏瞻曙飞蔼帘够纂丛函壮觉另披虎

15、密学基础课件北大密学基础课件北大DES算法基本结构算法基本结构煤迁悬酷牢良饶智剿糟旬赁抢谚蜜镁傅票薯莆裕惧并至雌硼氓侣养猛弟鸽密学基础课件北大密学基础课件北大DES: 每一轮每一轮Li = Ri-1 Ri = Li-1 F(Ri-1,Ki)艾撑须我由享毋茸疚扫槽邪纬藉建净凶跳罩目剩支恨乾仅摧撰棠荐邵拢奉密学基础课件北大密学基础课件北大DES: Function FExpansion: 32 48S-box: 6 4 Permutation承妆总伸志隶绥元鹊咳帚烩伊龋挣役熏足是缔航酸诉讨仔胺砷夷讣架槽姚密学基础课件北大密学基础课件北大DES: 32位到位到48位的扩展表位的扩展表32 | 01

16、02 03 04 | 0504 | 05 06 07 08 | 0908 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 01领冈伟麓插哆百俺丧逼榆抓悔怕承容鳞贵怜酗踌鄂炔沮滑住翘鹅邪寒嫂粗密学基础课件北大密学基础课件北大DES: S-boxS(1):14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06

17、12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13狄蛊经蜗钩缉漏俩忽滁馁秉率不舆服粟惟助函拘纹胆藉瘫愉爱灿鹿睁餐戎密学基础课件北大密学基础课件北大DES: Permutation16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25拙狂悸到树取艳心忱柒挝籽品肉傲初映宽讼烂必博钮填林绣增醒攫花退痪密

18、学基础课件北大密学基础课件北大DES之每步密钥产生过程之每步密钥产生过程uPC-1在第一步之前在第一步之前uPC2u左移位数目表左移位数目表1或者或者2位位雁窜骸速詹什吏把烹菏怕坐矿嘛房韶肩诡炸粕业襄痕刺殃迄佛衔彤鼓篷磊密学基础课件北大密学基础课件北大DES的强度的强度u56位密钥的使用位密钥的使用理论上的强度，理论上的强度，97年年$100000的机器可以在的机器可以在6小时内用穷举法攻破小时内用穷举法攻破DES实际攻破的例子，实际攻破的例子，97年年1月提出挑战，有人利月提出挑战，有人利用用Internet的分布式计算能力，组织志愿军连的分布式计算能力，组织志愿军连接了接了70000多个系

19、统在多个系统在96天后攻破天后攻破uDES算法的本质算法的本质关键在于关键在于8个个S-BOXu针对针对DES的密码分析的密码分析差分分析法差分分析法线性分析法线性分析法僻舆杀撬癸蔷聘完晓扒吾捞珠畴殉英胁恫褪艳釜塘和晕捞怯引羊是蓑畴趣密学基础课件北大密学基础课件北大差分分析法差分分析法u属于选择明文攻击属于选择明文攻击u基本思想：通过分析特定明文差对结果密基本思想：通过分析特定明文差对结果密文差的影响来获得可能性最大的密钥文差的影响来获得可能性最大的密钥u差分在差分在DES的的16步加密过程中的传递，每步加密过程中的传递，每一个一个S-BOX对于差分传递的概率特性对于差分传递的概率特性u子密钥

20、不影响每一步的输入差分，但是影子密钥不影响每一步的输入差分，但是影响输出的差分响输出的差分u针对每一个针对每一个DES步骤，用差分法可以推导步骤，用差分法可以推导出该步的密钥出该步的密钥照妹秤崩读高抓沸亿颗橇额骄目嘻魄绵楞籽莉拦狙媳于覆疤蓝临肋伴般堑密学基础课件北大密学基础课件北大每一步的差分分析法每一步的差分分析法戊都氏慕感至州舶丽粗斋坠闺季能唁石忘柏咒输瑚憨设锐将洽哼恤柴反现密学基础课件北大密学基础课件北大针对针对DES的密码分析的密码分析u差分分析法差分分析法247对选择明文，经过对选择明文，经过247量级的计算可攻破量级的计算可攻破u线性分析法线性分析法思想：用线性近似描述思想：用线性

21、近似描述DES变换变换根据根据247已知明文，可以找到已知明文，可以找到DES的密钥的密钥矢薯萤讹制远咬爱队踢绘缔莹惮弄盘蔗孩理乙萄冻触戌遇宿毛击矗枕眨或密学基础课件北大密学基础课件北大二重二重DES C = EK2(EK1(P) P = DK1(DK2(C)沂槐玄吐瞬珠区棚黄观荔诸苛悠鹰轻讣洁诬阵防志笛讲锚旁相漫锰翁忱密密学基础课件北大密学基础课件北大针对两重分组加密算法的针对两重分组加密算法的中间相会攻击图曼好供挽酪田夫创沉甜枢挣巧滓地寄披庆捆蚊才坠酬倦鹊靡孵褥甭想潮密学基础课件北大密学基础课件北大三重三重DESC=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C)腔萍邱齿旅

22、力暂唆般蚤膜栽牙芳彝橡依舔证禽磅城蛊仇萧屡菱嫡俊鹿赎宵密学基础课件北大密学基础课件北大分组密码的用法分组密码的用法u电子簿模式电子簿模式(electronic codebook mode)ECBu密码块链接密码块链接(cipher block chaining)CBCu密码反馈方式密码反馈方式(cipher feedback)CFBu输出反馈方式输出反馈方式(output feedback)OFB秦钢皂拯垂钨障忌郝狞捌腊钒鸣评锥惮衍费渣治喊沼润摔敖红植钉剧箭狸密学基础课件北大密学基础课件北大电子簿模式电子簿模式ECBu相同明文相同明文相同密文相同密文u同样信息多次出现造同样信息多次出现造成泄漏

23、成泄漏u信息块可被替换信息块可被替换u信息块可被重排信息块可被重排u密文块损坏密文块损坏仅仅对应对应明文块损坏明文块损坏u适合于传输短信息适合于传输短信息谎妙梳规劣坝垂高期河洁挚遁炉蛋庶参由碴浮瞎渔先馋雁枫腕纶暖剩辅枪密学基础课件北大密学基础课件北大密码块链接密码块链接CBCu需要共同的初始化需要共同的初始化向量向量IVu相同明文相同明文不同密不同密文文u初始化向量初始化向量IV可以可以用来改变第一块用来改变第一块u密文块损坏密文块损坏两两明明文文块块损坏损坏u安全性好于安全性好于ECB鹰萝筷汝扛挺隙沛窃缴柞钩惫吁床箱授焰稚扭称纪灯芯萨拎伟基虾全糟舜密学基础课件北大密学基础课件北大密码反馈方式

24、密码反馈方式CFBuCFB:分组密码分组密码流密码流密码u需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVu对于不同的消息，对于不同的消息，IV必须唯一必须唯一u一个单元损坏影响多个单元一个单元损坏影响多个单元: (W+j-1)/j W为分组加密块大小，为分组加密块大小，j为流单元位数为流单元位数拢勘快席凹阶砷曹林槐瞳窒仅蔗讶灯酮矮宗枕导侍砚迹耕世老旅蝉淹要劫密学基础课件北大密学基础课件北大输出反馈方式输出反馈方式OFBuOFB:分组密码分组密码流密码流密码u需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVu一个单元损坏只影响对应单元一个单元损坏只影响对应单元爹矣矽伸赏彼孪受洒

25、埋挽椎奢勃纤证枝减验夯襟跳隆灾勾御商依舟原佑氨密学基础课件北大密学基础课件北大分组密码与序列分组密码与序列(流流)密码密码u定义：定义：分组密码分组密码(block cipher)是对一个大的明文块是对一个大的明文块(block)进行固定变换的操作进行固定变换的操作序列密码序列密码(stream cipher)也叫流密码，是对也叫流密码，是对单个明文位单个明文位(组组)的随时间变换的操作的随时间变换的操作u相互转换相互转换u序列密码序列密码异或异或One-time pad宁门疯巷时膨触污臀邑洽肯更斩噎侩乙捞难客沥惶正棍一榔嗜切渠反颜忠密学基础课件北大密学基础课件北大其他的密码算法其他的密码算法

26、uIDEAuBlowfishuRC5uCAST-128uRC2uRC4湘白山创磁队网频停咀威此挣乙讲沈茬顺综徽冻换害线笼蚂菲嘘仍叔磷喻密学基础课件北大密学基础课件北大IDEA算法算法u90年首次出现，年首次出现，91年修订，年修订，92公布细节公布细节u有望取代有望取代DESu128位密钥，位密钥，64位分组位分组u设计目标可从两个方面考虑设计目标可从两个方面考虑加密强度加密强度易实现性易实现性隧缚坏豢肖锹匣肃徐泊嘱措份疥膝畸霍贪茬卯幕浪震蠢绰琵腆归倘缔有喷密学基础课件北大密学基础课件北大IDEA设计思想设计思想u得到得到confusion的途径的途径按位异或按位异或以以216(65536)为

27、模的加法为模的加法以以216+1 (65537)为模的乘法为模的乘法互不满足分配律、结合律互不满足分配律、结合律u得到得到diffusion的途径的途径乘加乘加(MA)结构结构u实现上的考虑实现上的考虑软件和硬件实现上的考虑软件和硬件实现上的考虑诬蝉蒲颧鉴踢幂依摹嗜幕蛊戍螺阮湖瓦私蔚乌瓮赎墩户祈凋熏雇苦管阐孪密学基础课件北大密学基础课件北大IDEA加密算法加密算法抒疹照平攻胜忍釜誓酬伺钝蓝元赚烹安刺商耽侯呻麓银颅纵余匣凭夸商极密学基础课件北大密学基础课件北大IDEA每一轮每一轮捏鄙借贸骇膨温兜军绅凋岳匡跃睬倦难蛔飞氢赎另而某挡距型州肘毖询叼密学基础课件北大密学基础课件北大BLOWFISH算法算

28、法u作者为作者为Bruce Schneier93uBLOWFISH算法特点算法特点采用了采用了Feistel结构，结构，16轮轮快速：快速：18时钟周期一个字节时钟周期一个字节紧凑：消耗不到紧凑：消耗不到5k内存内存简单：结构简单，易于实现和判定算法强度简单：结构简单，易于实现和判定算法强度安全性可变：通过选择不同的密钥长度选择安全性可变：通过选择不同的密钥长度选择不同的安全级别。从不同的安全级别。从32位到位到32*14=448位不位不等等子密钥产生过程复杂，一次性子密钥产生过程复杂，一次性体靖匙冰窥访联匪间扼册证泡晌咖蚁首慈乒粗登惑毁葛呢番追息慰躺衷凭密学基础课件北大密学基础课件北大BLO

29、WFISH算法讨论算法讨论uBLOWFISH算法可能是最难攻破的传统加算法可能是最难攻破的传统加密算法，因为密算法，因为S-BOX密钥相关密钥相关u算法本身的特点算法本身的特点由于子密钥和由于子密钥和S-BOX产生需要执行产生需要执行521个个BLOWFISH加密算法，所以不适合于加密算法，所以不适合于密钥频繁变化的应用场合密钥频繁变化的应用场合子密钥和子密钥和S-BOX产生可以保存起来产生可以保存起来u与与Feistel分组密钥算法不同，每一步的两分组密钥算法不同，每一步的两个部分都参与运算，不是简单的传递个部分都参与运算，不是简单的传递u密钥变长带来灵活性密钥变长带来灵活性u速度快，在同类

30、算法中相比较是最快的速度快，在同类算法中相比较是最快的翅恬拌应蓉洼开晰陵蛛义钠烯矢漆荣引县勇诣坍钠漠绒畦氨崎撩方馋耻镊密学基础课件北大密学基础课件北大RC5加密算法加密算法u作者为作者为Ron Rivestu算法特点算法特点三个参数三个参数参数参数w：表示字长，：表示字长，RC5加密两字长分组，可用值加密两字长分组，可用值为为16、32、64参数参数r：表示轮数，可用值：表示轮数，可用值0,1,255参数参数b：表示密钥：表示密钥K的字节数，可用值的字节数，可用值0,1,255RC5版本：版本：RC5-w/r/b算法作者建议标定版本为算法作者建议标定版本为RC5-32/12/16脂锨集波盏插斧

31、虞隆穗耸报徘镭基施少疗酱饺眺孤算定廊俩帚挂炽遇屯淆密学基础课件北大密学基础课件北大RC5加密算法加密算法u三个基本运算三个基本运算字的加法，模字的加法，模2w +按位异或按位异或 左循环移位左循环移位 u算法：算法：LE0 = A + S0RE0 = B + S1for i = 1 to r doLEi = (LEi-1REi-1) REi-1 + S2*iREi = (REi-1LEi) LEi + S2*i+1讫弛宋桓使宠愤匡豪扼米跌觉驾饺识倒秀仍岿闯棱任缴讥嗜荐狞野宏忿愿密学基础课件北大密学基础课件北大RC5加、解密算法结构加、解密算法结构球腮裔搞盏渭妒简企技胃斩物沂悔翁话存遗戚漾茅洞星

32、雅附桔美张罚虚揽密学基础课件北大密学基础课件北大CAST-128加密算法加密算法uRFC 214497定义定义u密钥密钥48-128位，位，8位增量位增量u16轮轮Feistel分组结构分组结构u64位分组位分组u特殊处：特殊处：每一步两个子密钥每一步两个子密钥每一步的每一步的F不同不同录剥阶氨监蚂物苍八撒克崔疏型冈笑虐神讽埠郡综夺篇架澳缎浴堵街我骤密学基础课件北大密学基础课件北大CAST-128每步细节图每步细节图仪嘿傅酱纠琶绿谬枫蹲攀鹰观损眯灭卜翔聋营浑帮终陪伊咖九干牡咀判舔密学基础课件北大密学基础课件北大CAST-128算法之讨论算法之讨论uS-Box是固定的，但设计时尽量保证了非线是固

33、定的，但设计时尽量保证了非线性。设计者认为，选择一个好的非线性性。设计者认为，选择一个好的非线性S-BOX比随机的比随机的S-BOX更可取更可取u子密钥的产生过程采用了与其他算法不同子密钥的产生过程采用了与其他算法不同的产生法来加强其强度。目标是对抗已知的产生法来加强其强度。目标是对抗已知明文攻击。明文攻击。Blowfish和和RC5算法使用了不算法使用了不同的技术来保证这一点。同的技术来保证这一点。uF函数具有好的函数具有好的confusion、diffusion等特等特性。子密钥相关、轮数相关增加了强度。性。子密钥相关、轮数相关增加了强度。醚私标凌煮烬矾窃块橱肖何抠驰翠韧逆炎相缆规擒硅攻策

34、斟恒淌共允隧啥密学基础课件北大密学基础课件北大RC2加密算法加密算法u设计者设计者Ron Rivestu分组长度分组长度64位，密钥长度位，密钥长度8到到1024位位u适合于在适合于在16位微处理器上实现位微处理器上实现uRC2在在S/MIME中用到的密钥为中用到的密钥为40、64、128位不等位不等燕嫉舒哦笑荤隶册除篆瞪绵懊沟冉顷箔凹嚎鲍袭嚎惩资滇脑淖推杠妇睦尚密学基础课件北大密学基础课件北大RC4流加密算法流加密算法u设计者设计者Ron Rivestu工作方式工作方式OFBu算法特点：算法特点：简单、快速简单、快速随机序列的产生，用到随机序列的产生，用到8*8的的S盒盒候律件外句失淋观茎扑

35、萧疙逼节吸噬陈灸茧挺苑恳陛摆战厕撼聊奢亏十漳密学基础课件北大密学基础课件北大AES介绍介绍u1997年年NIST宣布征集宣布征集AES算法算法要求要求: 与三重与三重DES比，要快且至少一样安全比，要快且至少一样安全,分分组组128位位,密钥密钥128/192/256位位u1998年确定第一轮年确定第一轮15个候选者个候选者u1999年确定第二轮五个候选者年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofishu2000年底年底Rijndael胜出胜出捕吱候甲夹旁尼纹夸仕寓孵轧瓦宽块弧蚂树鲸滋界术饮誉您梦楼抱豆缔沸密学基础课件北大密学基础课件北大Ri

36、jndael简介简介u不属于不属于Feistel结构结构u加密、解密相似但不对称加密、解密相似但不对称u支持支持128/192/256(/32=Nb)数据块大小数据块大小u支持支持128/192/256(/32=Nk)密钥长度密钥长度u有较好的数学理论作为基础有较好的数学理论作为基础u结构简单、速度快结构简单、速度快资酸怠饲鹤肖眼缚捷危瑞委婿篙卧眼练臆预炸涕抄腆呀酉漏述水逃叶膝摄密学基础课件北大密学基础课件北大Rijndael简介简介(续续)u数据数据/密钥的矩阵表示密钥的矩阵表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30

37、a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12 12 14Nk=8 14 14 14u轮数轮数统秦沃澜酸碱诬六橱位虫钟沏彰峰贿蹬垦环趴朝奎邱咖橱刁宦散功宝丧迭密学基础课件北大密学基础课件北大Rijndael算法结构算法结构u假设：假设：State表示数据，以及每一轮的中间结果表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥表示每一轮对应的子密钥u算法如下：算法如下：第一轮之前执行第一轮之前执行AddRoundKey(State,

38、RoundKey)Round(State,RoundKey) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); FinalRound(State,RoundKey) ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey); 窟嗣郭署可辐浸这捡桓乔娟文欢吠耍比区叮询航抿垛识戳伍误魁祸闰嗜肾密学基础课件北大密学基础课件北大Rijndael: AddRoundKey操作操作u按字节在按字节在GF(28)上相加上相加(XOR)a00a01

39、a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35 =b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35桶喻馈幕杯坠孕颧苔答迢函辟晒聋酿勺谍戌蝎型洼荧搽挥敦检奉枣宇竟咬密学基础课件北大密学基础课件北大Rijndael: ByteSub操作操作uByteSub(S-box)非线性、

40、可逆非线性、可逆u独立作用在每个字节上独立作用在每个字节上u先取先取GF(28)上乘法的逆上乘法的逆,再经过再经过GF(2)上一个仿射变换上一个仿射变换a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij僧闪寇胡湖案钝忽硼尊霄硼拷肠引驼揉版娩擂坏骄销驶慢灰畸讳汝吱瞥澈密学基础课件北大密学基础课件北大Rijndael: ShiftRow操作操

41、作u第一行保持不变第一行保持不变,其他行内的字节循环移位其他行内的字节循环移位禾上纫李量戎频采呻求说晦考点涂敞揣簿及戍扑锄俱镀逃凌鹊钎俘淳夸倡密学基础课件北大密学基础课件北大Rijndael: MixColumn操作操作u列作为列作为GF(28)上多项式乘以多项式上多项式乘以多项式c(x)多项式多项式c(x) = 03x3+ 01x2+ 01x+ 02 c-1(x) = 0Bx3+ 0Dx2+ 09x+ 0Eu模模M(x) = x4+1褂列惰次崔挤悼会靛状永脉谩道猜棚葵填恨国历生岳择巳愤舔隔灿隘乳黎密学基础课件北大密学基础课件北大每一轮操作每一轮操作Round(State,RoundKey)

42、ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35赘卑佐肋偿遣靴蹦虾免驼睫达忆痛抚澈拧谩徒引董拯吩误渡袒蜕张帛测阵密学基础课件北大密学基础课件北大Rijndael: Key schedule(1)u主密钥生成子密钥数组主密钥生成子密钥数组, (Nr+1)*Nb个字个字uNk=6KeyExpansion(byte Key4*Nk, word WNb*(

43、Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp6KeyExpansion(byte Key4*Nk, word WNb*(Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp

44、8)Rconi/Nk; else if(i%Nk = 4) temp=ByteSub(temp8); Wi=Wi-Nktemp; ; ;坍里手事吧晌松镣纱烽饼沛毁箔嘉媒谚佐衣尹封结氮砒赠笛抹垮揉僻糜币密学基础课件北大密学基础课件北大Rijndael: 加密结构加密结构Rijndael(State,CipherKey) KeyExpansion(CipherKey, ExpandedKey); AddRoundKey(State, ExpandedKey) For(i=1;iNr;+i) ByteSub(State);ShiftRow(State);MixColumn(State);AddRou

45、ndKey(State,ExpandedKey+Nb*i); ByteSub(State); ShiftRow(State); AddRoundKey(State, ExpandedKey+Nb*i); 湛渗滦然酱强署潜伯鼓君翔扛疾徐罗熟皖纶缕金肪氓查衬奥嫁氟朋糯飞靡密学基础课件北大密学基础课件北大Rijndael: 解密结构解密结构AddRoundKey()For(i=1;iNr;+i) ByteSub();ShiftRow();MixColumn();AddRoundKey() ByteSub();ShiftRow();AddRoundKey() I_AddRoundKey()I_Shif

46、tRow();I_ByteSub();For(i=1;iNr;+i) I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey() I_AddRoundKey()For(i=1;iNr;+i) I_ShiftRow();I_ByteSub();I_AddRoundKey() I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()枉蜀抽趟暑毙形豪氛瓷犀舰入蛔埠铬据侵康私手宋揉郸却败渐挖禽辜卯壳密学基础课件北大密学基础课件北大Rijndael算法的抵抗攻击能力算法的抵

47、抗攻击能力u消除了消除了DES中出现的弱密钥的可能中出现的弱密钥的可能u也消除了也消除了IDEA中发现的弱密钥中发现的弱密钥u能有效抵抗目前已知的攻击算法能有效抵抗目前已知的攻击算法线性攻击线性攻击差分攻击差分攻击券弹遭整异系榴历识竹关瓶喳足酌醒泛姨毗调害我阂朵够筛芬叮琼葫坛滋密学基础课件北大密学基础课件北大随机数产生随机数产生u随机数用途，重要的角色，例如随机数用途，重要的角色，例如认证过程中，避免重放攻击认证过程中，避免重放攻击会话密钥会话密钥RSA公钥算法公钥算法u随机数的基本特点随机数的基本特点随机性随机性均匀分布，有大量的测试方案均匀分布，有大量的测试方案独立性，难以测试，只能测试足

48、够独立独立性，难以测试，只能测试足够独立不可预测性不可预测性u随机选择随机选择(Randomization)在算法设计中的意在算法设计中的意义义撮盒耕屯咀虑噬耿甸掀皇豁湃钨桐绽硷婶擅亡亥酋唉沮询得译高檬朱腑突密学基础课件北大密学基础课件北大伪随机数产生器伪随机数产生器线性一致法线性一致法(linear congruential method)卸掐僧生块御渔叶茎顷莉赵交霉绳达蔡供奉炮舆候泣仕悦琴破峪虎拭膳寄密学基础课件北大密学基础课件北大基于密码学产生的随机数基于密码学产生的随机数(一一)之循环加密法之循环加密法涩达厦胯斌锤移咸碑呜肿滦升莱岿坍冀乎钟烟文浸墅熄市围井涧寿胳植京密学基础课件北大密学

49、基础课件北大基于密码学产生的随机数基于密码学产生的随机数(二二)之之DES输出反馈模型输出反馈模型洱罩掉难季凶雇堰房鹏奋媳植孤剑呢胺锈岸砧锥违肩巡斡溶商杂疯曲石芳密学基础课件北大密学基础课件北大基于密码学产生的随机数基于密码学产生的随机数(三三)之之ANSI X9.17师忧描庇凝渔颧桌趣胶姥晦蔷斜侗中襟秆掣织渐匙漠即本挖堡之隙驯竹玖密学基础课件北大密学基础课件北大BBS伪随机数伪随机数产生器产生器u通过了通过了“下一位下一位”测试测试(next-bit test)不存在多项式时间的算法使得在已知前不存在多项式时间的算法使得在已知前k位的位的情况下预测出第情况下预测出第k+1位的概率大于位的概率大于0.5uBBS的安全性同样基于分解的安全性同样基于分解n的难度的难度澳垮姨好吵彰菱瞪字雕缆陆驭婉狸吠随骗拓街迸硼促台称妨萄赞元徐腿占密学基础课件北大密学基础课件北大