第06讲 现代密码学.ppt

密码学与计算机安全 第六讲现代密码学 上海交通大学计算机科学与工程系郑东Zheng dong 1 现代分组密码 moden blockciphers 目前最广泛使用的加密算法提供保密与认证服务 2 私钥加密算法private keyencryption 也叫单钥或对称算法 通信实体双方使用相同的密钥加密和解密古典密码是私钥加密算法现代密码 由乘积密码构成 包括DES Blowfish IDEA LOKI RC5 Rijndael AES 及其它一些算法 3 分组密码 在分组密码中 消息被分成许多块每块都要被加密类似与许多字符被替换 64 bitsormore 许多现代密码具有下列形式 3 分组密码 cont 4 理论基础 理想的方法是使用尽可能大的替换模块但不实际 因为对每个64bit的模块 将需要264个实体的替换表因此使用一些小的模块代替使用成绩密码的思想这种概念由ShannonandFeistel提出 5 Shannons保密系统理论 ClaudeShannon对现代密码的重要工作CEShannon CommunicationTheoryofSecrecySystems BellSystemTechnicalJournal Vol28 Oct1949 pp656 715CEShannon PredictionandEntropyofprintedEnglish BellSystemTechnicalJournal Vol30 Jan1951 pp50 64在上述文章中 提出了下列概念 熵 的概念语言冗余度破译密码需要多少信息量定义了 计算安全 与 无条件安全 6 Shannons保密系统理论cont 指出Bookcipher是不安全的即如果通过填加一些英语字母加密英文内容 是不安全的因为英语有80 的冗余度英语密文如果有60 的冗余度 就可以破解7 7 替换 置换密码 在Shannon1949的文章中 介绍了替换 置换网络的思想 S P networks这种思想形成了现代密码的基础S Pnetwork替换 置换乘积密码的现代形式S Pnetworks是基于下列两种最基本的密码运算 前面介绍过 替换 Substitution 置换 Permutation 8 替换运算 一个二进制字用其它二进制字替换这种替换函数就构成密钥可以看作是一个大的查表运算叫做S boxes 替换运算 续 9 置换运算 变换 二进制字次序被打乱重新排序的方法构成密钥叫这种变换为P boxes 9 Cont 10 Substitution PermutationNetwork Shannon把这两种运算组合在一起一些S boxes由P box连接这种变换叫做混合变换 mixingtransformations 10 替换 置换网络 cunt 11 实际使用的替换 置换网络 实际中 我们需要加密 也需要解密因此 有两种方法 1 定义每个替换 置换的逆 这样增加了复杂度or2 定义一种结构 容易求逆 这样可以使用基本的相同编码或硬件用于加密和解密 12 Feistel密码 HorstFeistel workingatIBMThomasJWatsonResearchLabs 70 s初 设计了这样的结构 我们现在叫做feistelcipher思想是把输入块分成左右两部分L i 1 和R i 1 变换是在密码的第I轮只使用R i 1 函数gincorporatesonestageoftheS Pnetwork的每个阶段有g工作 由第I个密钥控制 叫子密钥 13 Feistel密码 变换可以用下列函数表示 L i R i 1 R i L i 1 XORg K i R i 1 求逆很容易实际中 一些这样的连续变换形成完整密码变换 典型 16轮 14 基本设计原理 Shannons混合变换形成一种特殊的成绩密码组成部分一起工作 S Boxes S 盒 提供输入bits混合作用 confusion P Boxes提供扩散作用 diffusionacrossS boxinputs 这种效果进一步解释为 雪崩 与 完全性 AvalancheandCompleteness byWebster Tavares OntheDesignofS boxes inAdvancesinCryptology Crypto85 LectureNotesinComputerScience No218 Springer Verlag 1985 pp523 534 15 雪崩效应 Avalancheeffect 输入改变1bit 导致近一般的比特发生变化 16 完备性效应 Completenesseffect 每个输出比特是所有输入比特的复杂函数的输出 17 分组密码设计 BlockCipherDesign 这些设计原理是设计好的分组密码的准则 雪崩 保证小的输入变化导致大的输出变化完全性保证每个输出比特依赖于所有的输出比特我们可以看到 古典密码没有这些性质 18 FeistelCipher设计 设计密码时 下列参数需要考虑 分组大小 blocksize 增加分组长度会提高安全性 但降低了密码运算速度密钥大小 keysize 增加密钥长度 可以提高安全性 使得穷搜索困难 同样 降低了密码速度 FeistelCipher设计 续 轮数增加轮数可以提高安全性 但降低速度子密钥生成子密钥生成越复杂 就越安全 但降低速度 所有问题就是平衡问题 轮函数复杂的轮函数能够使的密码分析困难 但降低速度设计 安全 的密码算法并不难 只要使用足够多的轮数就可以 但降低速度得到一个快速 安全的算法是困难的 19 密码设计评价 好的 密码设计具有 雪崩特性 完备性 不可预料性 avalanche completeness unpredictability 差的密码设计缺乏随机性 具有太大的可预料性许多密码都被攻破 mercialproductslikeWordperfect pkzip allcurrentmobilephoneciphers 即使密码学专家也会犯这样的错误最好的办法是测试 通过实际检验证明它的安全性 20 Lucifer 第一个可用的替换 置换密码 byHorstFeistelatIBMlabs HorstFeistel CryptographyandComputerPrivacy ScientificAmerican Vol228 5 May1973 pp15 23 提供了这项工作的框架 但没有Lucifer的细节详细的介绍 ArthurSorkin Lucifer ACryptographicAlgorithm Cryptologia Vol8 1 Jan1984 pp22 41 withaddendainVol8 3 pp260 261包括算法的详细描述 实现 21 Lucifer浏览 原始描述没有给出细节以下列形式描述 Lucifer 22 Lucifer密钥编排 LuciferISFeistelcipher 分组长度是128 bit 密钥长度是128 bit每轮使用的子密钥是密钥的左半部分密钥每次要向左旋转56 bits 所以 密钥的每部分都参加运算 23 Lucifer数据计算 16轮数据计算 使用子密钥 输出的右半部分作为下轮的输入RHsideasinputstotheroundfunction交换位置前 与左半异或S PfunctionforLucifer有下列结构 substitution使用8个4 bitS boxes S0 S1 对 每个对的交替使用方法依赖与密钥 order S0 S1 or S1 S0 dependingonthekey subkey替换输出相加 modulo2 在通