无线网络安全技术____-第二讲.ppt

无线网络安全技术第二讲对称密码学 宋宇波songyubo 密码学历史 演化的历史 1949 一门古老的技巧 Art 1949 1975 一门新兴的科学 Sience 1975 公钥密码学 一 引言 玛丽女王的故事 沃尔辛厄姆 巴宾顿 密码学内容 密码编码学 Cryptography 密码编码专家 cryptographer 明文 plaintext 原始的消息密文 ciphertext 被伪装的消息加密 encrypt encipher 明文转换为密文的过程解密 decrypt decipher 密文还原为明文的过程算法 algorithm cipher 用于加密和解密的数学函数密码分析学 Cryptanalysis 密码分析专家 cryptanalyst 穷举攻击 Brute forceattack 密码编码学 加密 Encryption 将明文 Plaintext 变换为密文的过程 把可懂的语言变换成不可懂的语言 密文 Ciphertext 这里的语言指人类能懂的语言和机器能懂的语言 解密 Decryption 加密的逆过程 即由密文恢复出原明文的过程 把不可懂的语言变换成可懂的语言 密钥 Key 一种用于加密过程和解密过程的参数 只有加密者或解密者拥有 加密和解密算法的操作通常都是在一组密钥的控制下进行的 分别称为加密密钥 EncryptionKey 和解密密钥 DecryptionKey 密钥数量加密密钥 解密密钥 对称密钥 单密钥 私钥加密密钥 解密密钥 非对称密钥 双钥 公钥 Kerchoffs原则 1883 即使密码系统的任何细节已为人悉知 只要密钥未泄漏 它也应是安全的 算法的安全性只与密钥的安全性相关 密码分析 密码分析是研究密钥未知的情况下恢复明文的科学 成功的密码分析恢复明文或密钥 基本假设 算法已知 Kerchoff原则 分析目的 恢复明文恢复密钥分析方法 穷举分析 BruteForce 将密码进行逐个推算直到找出真正的密码为止 算法分析 对密码算法结构进行分析 尝试推导出明文或密钥 常见的攻击类型 依据分析者掌握的资源划分 唯密文攻击 cybertextonlyattack 分析者知道一些消息的密文 尝试恢复明文或推导密钥 已知明文攻击 knownplaintextattack 分析者不仅知道一些消息的密文 也知道与之对应的明文 尝试推导出密钥 选择明文攻击 chosenplaintextattack 分析者可以控制加密机 选择明文进行输入 通过观察对应的输出 密文 尝试推导出密钥 选择密文攻击 chosenciphertextattack 分析者可以控制解密机 选择密文进行输入 通过观察对应的输出 明文 尝试推导出密钥 选择文本攻击 Chosentext 分析者同时拥有加密机和解密机 因此可以选择明文输入观察输出密文 也可选择密文输入观察输出明文 尝试推导出密钥 密码算法的安全性 无条件安全和计算上安全 无条件安全 一次一密 计算上安全 破译的代价超出信息本身的代价 破译的时间超出信息自身的生命周期 通信安全模型 巴宾顿 玛丽女王 沃尔辛厄姆 通信安全模型 安全攻击 阻断 窃听 篡改 伪造 密码学提供的服务 机密性 Confidentiality 保证信息为授权者享用而不泄漏给未经授权者 完整性 Integrity 数据完整性 未被未授权篡改或者损坏 系统完整性 系统未被非授权操纵 按既定的功能运行 可鉴别性 Authentication 使一定能确认数据的来源就是他 实体鉴别数据源鉴别抗抵赖性 Nonrepudiation 收发双方在事后都不能抵赖进行了本次通信活动 可用性 Availability 保证信息和信息系统随时为授权者提供服务 而不要出现非授权者滥用却对授权者拒绝服务的情况 二 古典密码学 2 1古典密码术 Cryptography 代换明文的字母由其他字母或数字或符号代替置换改变明文字母排列顺序 2 1 1置换 Skytle加密法 栅栏技术 按照对角线的顺序写入明文 而按行的顺序读出作为密文 明文 meetmeaftertheparty写为 mematrhpryetefeteat密文 mematrhpryetefeteat 更复杂的例子 密钥 4312567明文 attackpostponeduntiltwoamxyz密文 ttnaaptmtsuoaodwcoixknlypetz Caesar密码 破译以下密文 密文 PHHWPHDIWHOWKHSDUWB明文 meetmeaftertheparty 字母表 密码本 密文 DEFGHIJKLMNOPQRSTUVWXYZABC明文 abcdefghijklmnopqrstuvwxyzi 0123456789 加密算法 C P 3 mod 26 解密算法 P C 3 mod 26 2 1 2代换 安全性分析 设密钥为K 加密算法 C E K P P k mod 26 解密算法 P D K C C K mod 26 25个可能的密钥k k 1 25 单表代换密码 凯撒密码只有25个密钥k 非常不安全 若有意改变字母的排列顺序 可增大密钥空间 任意置换 26 密码破解者使用的方法暴力破解 穷举攻击 密钥的空间问题移位密码 26种可能的密钥替换密码 4 1027种可能的密钥 密钥的复杂度问题过于复杂的密码难以记忆过于简单的密码容易猜出 替换密码的改进 例如 利用关键词KeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyzabcdfghijlmnopgrstuvwxspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaculrvwxyzbdfghijkmnoq优点 便于记忆 无需记在纸上虽然密钥数量变少 但仍然很庞大 频率分析 字母频率统计分析起源 阿拉伯文明 神学家需建立古兰经中描述的天使造访的年表 关于破译加密信息的手稿 如果我们知道一条加密信息所使用的语言 那么破译这条加密信息的方法就是找出用同样的语言写的一篇其他文章 大约一页纸长 然后我们计算其中每个字母的出现频率 我们将频率最高的字母标为1号 频率排第2的标为2号 第三标为3号 依次类推 直至数完样品文章中所有字母 然后我们观察需要破译的密文 同样分类出所有的字母 找出频率最高的字毋 并全部用样本文章中最高频率的字毋替换 第二高频的字母用样文中2号代替 第三则用3号替换 直到密文中所有字母均巳被样文中的字母替换 英文中字母的使用频率 基于语言统计规律的破译 1密文 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ2统计字母的相对频率 3猜测PZ可能是e和t 4统计字母的相对频率 双字母5猜测ZW可能是th 因此ZWP可能是the6经过反复猜测 分析和处理 明文 itwasdisclosedyesterdaythatserveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow E E E NEVER N V R 福尔摩斯密码 密码本 改进的方法 代码将每个单词用另外一个单词或符号替代 问题 灵活性差 对明文中可能出现的单词定义代码是项艰巨工程 更换非常麻烦 玛丽女王用的密码本 Playfair密码 例 秘钥 monarchy 安全性分析 可能的密钥个数26 26 676双子母组合 字母出现的几率被一定程度均化了依然保留了相当多的结构信息 仍可以利用频率统计进行分析 多表代换密码 使用两个或两个以上的密码表交替使用 维基尼亚密码 Vigenere 以移位代换为基础的周期代换密码 m个移位代表由m个字母组成密钥字 字母abcd xyz分别由数字0123 2425表示 加密时 明文字母Pi在密钥Ki的作用下向后移位d Ki 得到密文字母Ci 解密时 密文字母Ci在密钥Ki的作用下向前移位d Ki 得到明文字母Pi 维基尼亚表 26x26矩阵表示26种排列组合 举例 StandardVigenereTable Keyword FORTUNEFORT ROW Plaintext MEETMEATSIX COLUMN PolyalphabeticSubstitutionCiphers StandardVigenereTable Ciphertext RSVMGREYGZQ 维基尼亚密码安全性分析 维基尼亚密码是多表替换体制 分析起来更加困难 密钥空间大 可能的密钥字达26m如果秘钥字的长度是m 明文中的一个字母能够映射成这m个可能的字母中的一个 例如 当m 5 密钥空间所含密钥的数量是 1 1x107明文和密文的字母频率分布相同 仍然能使用统计分析破译 Vigenere密码分析 Kasiski测试寻找密钥长度频率分析Vigenere的弱点周期性 一次一密 Vigenere密码的改进思路Vigenere密码的弱点 周期性加长密钥长度 用一个和明文长度一样长的密钥如何破解 利用密钥的语言特性 举例 有ypt结构的单词apocalyptic crypt egypt 改进办法 使用没有任何解构特征的密钥 如果每次加密都用与明文一样长的真随机密钥 将是最安全的 一次一密 无法破解 缺点 维吉尼亚密码的机械实现 密码盘 Enigma 属Vigenere的实现每个轮子是一个单代替表多个轮子组合为多表密码可视作Vigenere的一个实现 Three RotorMachineWithWiringRepresentedbyNumberedContacts ENIGMA 2 2乘积密码 productcipher 由于语言的统计特性使得使用替换或置换进行加密并不安全可以交替的使用多种加密方式 两种替换得到更复杂的替换结果两种置换得到更复杂的置换结果替换后再进行置换得到的结果相对更复杂 这种思想是从经典密码到现代密码体制的桥梁 第1轮第2轮第3轮第4轮第5轮 第6轮第7轮第8轮第9轮第16轮 第24轮第48轮第72轮 以某种方式连续执行两个或多个密码构造简单迭代密码 多次重复执行一个简单的密码函数 轮函数 Feistel密码结构 多轮迭代先代换 异或 后置换 左右两部分交换 每轮迭代输入分为两部分Li 1和Ri 1 第i轮 Li Ri 1Ri Li 1 F Ki Ri 1 Feistel解密 使用相同的结构颠倒密钥的使用顺序F可以是不可逆函数 混淆和扩散 混淆 使密文与明文之间的关系复杂 通过使用一个复杂的 非线性的代换操作 S box 扩散 扩散增加明文的冗余度 增加明文与密文之间的相关性 一个好算法设计是 改变输入的1位 输出的一半为数会发生改变 雪崩效应 S P网络 两个基本操作 代换 置换substitution S box permutation P box 轮流使用 2 3对称密码算法分类 分组密码 blockcipher 序列密码 streamcipher 分组密码 blockcipher 明文被分为固定长度的块 即分组 对每个分组用相同的算法和密钥加解密 分组长度 64 128 256bits密文长度 同明文分组长度相同问题 若待加密的明文不是64 128 256的整数倍 该如何处理 解密 加密 流密码 每次加密数据流的一位或一字节 连续加密 Ci Ki Pi 2 3 1DES算法 DES DataEncryptionStandard 算法是一种用56位密钥来加密64位数据的方法 发明人 IBM公司W Tuchman和C Meyer 基础 1967年美国HorstFeistel提出的理论 产生 美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准 于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告 1977年最终选定DES DES的加密 采用分组密码体制 用56bit密钥来加密64bit数据的方法 16轮Feistel结构迭代每轮使用48bit的子密钥 DES算法流程 第一步 初始置换 IP 对给定的64位比特的明文x 首先通过一个置换IP表来重新排列x 从而构造出64位比特的x0 x0 IP x L0R0 其中L0表示x0的前32比特 R0表示x0的后32位 第二步 16轮Fiestel结构迭代按照规则迭代 规则为Li Ri 1Ri Li F Ri 1 Ki i 1 2 3 16 第三步 末尾置换 IP 1 对L16R16利用IP 1作逆置换 就得到了密文y 可以看出 DES加密需要三个关键点 IP置换表和IP 1逆置换表 函数f 子密钥Ki 初始置换 IP 初始置换 InitialPermutation IP M m1m2 m62m63 m64 M m58m50 m23m15 m7 IP M 单轮DES 密钥Ki 密钥Ki 1 P 盒置换 S 盒代替 压缩置换 E 盒置换 移位 移位 Ki 48bits 48 32 Li Ri 1 Ri Li 1f Ri 1 Ki f Li 1 Ri 1 28 28 48 32 32 扩展置换 E 盒置换 将Ri从32位扩展到48位目的 输入的一位影响下一步的两个替换 使得输出对输入的依赖性传播得更快 密文的每一位都依赖于明文的每一位 1234 5678 1234 5678 32 48 321234545678989 31321 1234567891011121314 464748 输出 输入 efghijklmnop defghihijklmlmnopq 扩充置换E S 盒置换 将48比特压缩成32比特 E S1 S2 S3 S4 S5 S6 Ri 1 32bits Ki 48bits 48bits S7 S8 32bits 6bits 4bits S 盒置换 输入6比特 b1b2b3b4b5b6输出4比特 S b1b6 b2b3b4b5 S1 b1b2b3b4b5b6 举例 S1 100110 1000 P 盒置换 P 盒 32比特输入 32比特输出 B b1b2 b30b31 b32 B b16b7 b11b4 b25 P B 子密钥生成 拆分 56bits的密钥分成两部分 Ci Di 各28bits 循环左移 根据迭代的轮数 分别左移一位或两位 轮数 左移 子密钥生成 PC 2置换 压缩置换 从56bits中选择48bits 末置换 IP 1 初始置换的逆置换 M m1m2 m62 m63 m64 M m40m8 m17 m57 m25 IP 1 M DES解密过程 DES解密过程与加密过程完全相似 只不过将16次迭代的子密钥顺序倒过来 即m DES 1 c IP 1 T1 T2 T15 T16 IP c 可以证明 DES 1 DES m m 雪崩效应 AvalancheEffect 雪崩效应 指明文或密钥的少量变化会引起密文的很大变化 DES的强度 密钥长度 56比特强力攻击 尝试次差分密码分析 尝试次线性密码分析 尝试次 但是后两种攻击是不实用的 1976年 耗资2000万美元的计算机 可以在一天中找到密钥 1993年 设计100万美元的计算机 3 5小时用穷举法找到密钥 1998年 EFF宣布破译了DES算法 耗时不到三天时间 使用的是25万美元的 DES破译机 DES弱密钥 弱密钥 每轮密钥都是一样 EK EK I DES存在4个弱密钥 半弱密钥 一个密钥能够解另一密钥加密的密文 EK1 EK2 至少有12个半弱密钥 2 3 2三重DES 3DES 三重DES加密 密钥长度为168比特 k k1k2k3 双密钥三重DES加密 密钥长度为112比特 k k1k2 2 3 3AES算法 有着30年历史的DES算法显然应该退休了理论上存在破解它的攻击方法已经表明可以用密钥穷举方法破解1997年 NIST开始征求新的加密标准算法 AES1998年 第一轮通过15个候选算法1999年 第二轮通过5个候选算法2000年 选择Rijndael算法作为AES2001年 AES标准正式发布 最后的5个候选算法 算法递交者MARSIBMRC6TMRSALaboratoriesRijndaelJoanDaemen VincentRijmenSerpentRossAnderson EliBiham LarsKnudsenTwofishBruceSchneier JohnKelsey DougWhiting DavidWagner ChrisHall NielsFerguson AES算法 Rijndael 比利时的Rijmen Daemen设计密钥长度 128 192 256bit明文长度 128bit采用了置换组合结构将处理的数据堪称一个4 4的字节矩阵每轮所有的数据都参与运算主要特性 可以抵御已知的攻击在各种CPU上执行速度快且代码紧凑设计简单 AES要求 对称密钥分组加密算法分组长度为128位 密钥长度为128 192 256位安全性不低于3DES 运算速度要比3DES快在未来的20 30年内不会被淘汰要公开所有的设计细节提供C和JAVA的实现代码公开和免费许可 公开定义 公开评估 公正公开的选择 AES算法加密 2 4工作模式 分组加密只处理固定长度的明文DES处理的明文长度为64位在现实中我们需要处理任意长度的明文5种推荐模式用于分组加密用于流加密 ECB模式 ElectronicCodebookBook ECB模式 ElectronicCodebookBook 报文被顺序分割分成b位长度分组每个明文都有密文唯一对应 像密码本一样 名字的来由 各个分组独立加密 与其他分组无关 Cj E K Pj j 1 NPj D K Cj j 1 N若明文长度不为b的整数倍 最后一个分组需进行填充 优点并行加密 随机存取缺点相同的明文分组对应着相同的密文分组暴露了统计规律替换 窜改 乱序重排 ECB加密有可能保存数据的结构特征 原始图片 使用ECB加密后 利用其他模式加密 CBC模式 CipherBlockChaining CBC模式 CipherBlockChaining 前一个分组的加密结果被反馈到当前分组的加密明文加密前要与前面的密文进行异或 象链条一样链在一起 名字来由 Cj E K Pj Cj 1 j 2 NPj D K Cj Cj 1j 2 N初始状态 明文和初始向量IV initializationvector 异或C1 E K P1 IV P1 D K C1 IV用途 大数据量的明文加密 认证 优点 当前的密文跟前面所有的明文都相关当前明文的改变将影响后面所有的密文输出 CFB模式 CipherFeedBack 消息看作比特流 每次加密长度s位可以比分组长度b位小 明文与加密算法的输出相加结果被反馈到下一步中 名字的来由 用途 流加密 认证 Cj Pj Ss E K Cj 1 Pj Cj Ss E K Cj 1 OFB模式 OutputFeedBack 消息看作比特流 每次加密长度s位可以比分组长度b位小 加密的输出和明文进行相加上一步的加密输出被反馈到下一个加密输入中 名字的来由反馈过程与明文独立 因此可以先计算 在有噪声干扰的信道上进行流加密 Cj Pj Ss E K Cj 1 Pj 1 Pj Cj Ss E K Cj 1 Pj 1 CTR模式 Counter 优点 效率高 可以并行加解密 可以进行预处理 可随机访问特定密文 randomaccesstoencrypteddatablocks可证明与其他模式的安全性一样缺点 需确保每次不能使用相同的密钥 计数器值 2 5流加密 StreamCipher 一位一位处理 好像流一样 算法结构 密钥流 伪随机序列伪随机数是使用一个确定性的算法计算出来的 似乎是随机的数序 因此伪随机数实际上并不随机 明文与密钥流逐位XOR 流密码特性 设计上的考虑 密钥流周期要长 统计上随机密钥流的随机性与密钥长度有关如果设计得当 则流密