第2章数据加密算法NEW 信息安全.ppt

1 第2章数据加密算法 2 内容 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 3 2 1数据加密概念 明文 plaintext 作为加密输入的原始信息密文 ciphertext 明文变换结果加密算法 变换函数密钥 key 参与变换的参数 4 加密通信的模型 密码学的目的 Alice和Bob两个人在不安全的信道上进行通信 而破译者Oscar不能理解他们通信的内容 5 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 6 2 2密码体制 通常一个完整密码体制要包括如下五个要素M C K E DM是可能明文的有限集称为明文空间C是可能密文的有限集称为密文空间K是一切可能密钥构成的有限集称为密钥空间对于密钥空间的任一密钥 有一个加密算法和相应的解密算法使得ek M C和dk C M 分别为加密解密函数 满足 这里 7 一个密码体制要是实际可用的必须满足如下特性 每一个加密函数ek和每一个解密函数dk都能有效地计算破译者取得密文后 将不能在有效的时间内破解出密钥k或明文x一个密码系统是安全的必要条件穷举密钥搜索将是不可行的 即密钥空间非常大 8 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 9 2 3密码分类 按发展进程分 古典密码 基于字符替换的密码对称密钥密码公开密钥密码 10 按密钥管理的方式分为秘密密钥算法 对称算法的加密密钥和解密密钥相同 也叫作秘密密钥算法或单密钥算法 如DES算法 公开密钥算法 如果加密和解密的密钥不同 则称之为公开密钥算法 如RSA和DH算法 11 按加密模式分 序列密码 每次加密一位或一字节的明文 也可以称为流密码 分组密码 将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出也是固定长度的密文 12 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 13 2 4算法分类 经典密码代替密码 简单代替 多名或同音代替 多表代替 多字母或多码代替换位密码 对称加密算法DES AES非对称公钥算法RSA 背包密码 McEliece密码 Rabin 椭圆曲线 EIGamalD H 14 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 15 2 5加密算法 2 5 1简单代替密码或单字母密码简单代替密码就是将明文字母表M中的每个字母用密文字母表C中的相应字母来代替 这一类密码包括移位密码 替换密码 仿射密码 乘数密码 多项式代替密码 密钥短语密码等 16 移位密码 是最简单的一类代替密码 将字母表的字母右移k个位置并对字母表长度作模运算形式为ek m k m modq 解密变换为dk c m k modq 其中 q为字母表M的长度 m 既代表字母表M中的值 也代表其在M中的位置 c 既代表字母表C中的值 也代表其在C中的位置 13mod26 13 27mod26 1 凯撒Caesar密码是对英文26个字母进行移位代替的密码 其M C q 26 这种密码称为凯撒密码是因为凯撒使用过k 3的这种密码 使用凯撒密码将明文M meetmeafterthetogaparty加密为C phhwphdiwhowkhwrjdsduwb 17 替换密码 对明文字母表的所有字符进行所有可能置换得到密文字母表 移位密码是替换密码算法一个特例 设M C Z 26 K是由26个符号0 1 25的所有可能置换组成 任意 定义d y 1 y x 1是 的逆置换 有的是乘法逆元 密钥空间K很大 K 26 4 1026 破译者穷举搜索是不行的 然而 可由统计的方式破译它 移位密码体制是替换密码体制的一个特例 它仅含26个置换做为密钥空间 18 乘数密码 是一种替换密码 它将每个字母乘以一个密钥k 即ek m kmmodq 其中k和q为互素的 这样字母表中的字母会产生一个复杂的剩余集合 若k和q不互素 则会有一些明文字母被加密成相同的密文字母 而且 不是所有的字母都会出现在密文字母表中 加密函数取形式为ea x ax mod26 a Z 26 要求唯一解的充要条件是gcd a 26 1 该算法描述为 设M C Z 26 K a Z 26 gcd a 26 1 对k a K 定义ek x ax mod26 和dk y a 1 y mod26 x y Z 26 aa 1modq 1a 5 a 1 21a 7 a 1 15 19 例子 a 9 ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文密文cipher SUFLKX 20 对于乘数密码 当且仅当a与 互素时 加密变换才是一一映射的 因此a的选择有11种 a 3 5 7 9 11 15 17 19 21 23 25 可能尝试的密钥只有11个 21 仿射密码 是替换密码的另一个特例 加密的形式为ek m k1m k2 modq cmodq 其中k1和q是互素的 22 加密函数取形式为e x ax b mod26 a b Z 26 要求唯一解的充要条件是gcd a 26 1该算法描述为 设M C Z 26 K a b Z 26 Z 26 gcd a 26 1 k a b K 定义 ek x ax b mod26 和dk y a 1 y b mod26 x y Z 26 q 26时 可能的密钥是26 12 312个 23 例子 设k 7 3 注意到7 1 mod26 15 加密函数是ek x 7x 3 mod26 相应的解密函数是dk y 15 y 3 15y 19 mod26 易见dk ek x dk 7x 3 15 7x 3 19 x 45 19 x mod26 若加密明文 hot 首先转换字母hot成为数字7 14 19 加密 解密 24 2 5 2单表替换密码的破译 简单代替密码由于使用从明文到密文的单一映射 所以明文字母的单字母出现频率分布与密文中相同 可以很容易地通过使用字母频率分析法进行只有密文的攻击 25 2 5 2单表替换密码的破译 通过字母的使用频率破译 26 2 5 3多名或同音代替密码 与简单代替密码类似 只是映射是一对多的 每个明文字母可以加密成多个密文字母 同音代替密码比简单代替密码难破译得多 例A可能为3 7 15尤其是当对字母的赋值个数与字母出现频率成比例时 这是因为密文符号的相关分布会近似于平的 可以挫败频率分析 然而 若明文字母的其它统计信息在密文中仍很明显时 那么 同音代替密码仍然是可破译的 27 2 5 4多表代替密码 单字母出现频率分布与密文中相同 多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布 每个映射是简单代替密码中的一对一映射 维吉尼亚Vigenere密码和博福特Beaufort密码均是多表代替密码的例子 多表代替密码有多个单字母密钥 每一个密钥被用来加密一个明文字母 第一个密钥加密明文的第一个字母 第二个密钥加密明文的第二个字母 等所有密钥使用完后 密钥又再循环使用 维吉尼亚Vigenere密码算法如下 设密钥明文加密变换ek m c1c2 cn 其中 Ci mi ki mod26 密钥k可以通过周期性地延长 反复进行以至无穷 28 2 5 5多字母或多码代替密码 不同于前面介绍的 代替密码都是每次加密一个明文字母 多字母代替密码将明文字符划分为长度相同的消息单元 称为明文组 对字符块成组进行代替 这样一来使密码分析更加困难 多字母代替的优点是容易将字母的自然频度隐蔽或均匀化 从而 有利于抗击统计分析 Playfair密码Hill密码都是这一类型的密码 29 2 5 6换位密码 在换位密码中 明文的字母保持相同 但顺序被打乱了 由于密文字符与明文字符相同 密文中字母的出现频率与明文中字母的出现频率相同 密码分析者可以很容易地由此进行判别 虽然 许多现代密码也使用换位 但由于它对存储要求很大 有时 还要求消息为某个特定的长度 因而比较少用 30 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 31 2 6数据加密标准DES DataEncryptionStandard 2 6 1DES的产生1973年5月15日 NBS开始公开征集标准加密算法 并公布了它的设计要求 1 算法必须提供高度的安全性 2 算法必须有详细的说明 并易于理解 3 算法的安全性取决于密钥 不依赖于算法 4 算法适用于所有用户 5 算法适用于不同应用场合 6 算法必须高效 经济 7 算法必须能被证实有效 8 算法必须是可出口的 32 1974年8月27日 NBS开始第二次征集 IBM提交了算法LUCIFER 该算法由IBM的工程师在1971 1972年研制1975年3月17日 NBS公开了全部细节1976年 NBS指派了两个小组进行评价1976年11月23日 采纳为联邦标准 批准用于非军事场合的各种政府机构1977年1月15日 数据加密标准 FIPSPUB46发布 33 2 6 2DES的应用 1979年 美国银行协会批准使用 1980年 美国国家标准局 ANSI 赞同DES作为私人使用的标准 称之为DEA ANSI 392 1983年 国际化标准组织ISO赞同DES作为国际标准 称之为DEA 1 该标准规定每五年审查一次 计划十年后采用新标准 最近的一次评估是在1994年1月 已决定1998年12月以后 DES将不再作为联邦加密标准 34 2 6 3分组密码的一般设计原理 分组密码是将明文消息编码表示后的数字 简称明文数字 序列 划分成长度为n的组 可看成长度为n的矢量 每组分别在密钥的控制下变换成等长的输出数字 简称密文数字 序列 35 2 6 4两个基本设计方法 Shannon称之为理想密码系统中 密文的所有统计特性都与所使用的密钥独立 扩散 Diffusion 明文的统计结构被扩散消失到密文的长程统计特性 使得明文和密文之间的统计关系尽量复杂 混乱 confusion 使得密文的统计特性与密钥的取值之间的关系尽量复杂 36 2 6 5实现的设计原则 软件实现的要求 使用子块和简单的运算 密码运算在子块上进行 要求子块的长度能自然地适应软件编程 如8 16 32比特等 应尽量避免按比特置换 在子块上所进行的密码运算尽量采用易于软件实现的运算 最好是用处理器的基本运算 如加法 乘法 移位等 硬件实现的要求 加密和解密的相似性 即加密和解密过程的不同应仅仅在密钥使用方式上 以便采用同样的器件来实现加密和解密 以节省费用和体积 尽量采用标准的组件结构 以便能适应于在超大规模集成电路中实现 37 2 6 6简化的DES SimplifiedDES方案 简称S DES方案 加密算法涉及五个函数 1 初始置换IP initialpermutation 2 复合函数fk1 它是由密钥K确定的 具有置换和替代的运算 3 转换函数SW 4 复合函数fk2 5 初始置换IP的逆置换IP 1 6 置换函数P8 P10 38 算法如下 39 加密算法的数学表示 IP 1 fk2 SW fk1 IP 也可写为 密文 IP 1 fk2 SW fk1 IP 明文 其中K1 P8 移位 P10 密钥K K2 P8 移位 移位 P10 密钥K 解密算法的数学表示 明文 IP 1 fk1 SW fk2 IP 密文 40 2 6 7对S DES的深入描述 1 S DES的密钥生成 设10bit的密钥为 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 置换P10是这样定义的P10 k1 k10 k3 k5 k2 k7 k4 k10 k1 k9 k8 k6 相当于P10 35274101986 LS 1为循环左移一次 P8 637485109 41 算法如下图按照上述条件 若K选为 1010000010 产生的两个子密钥分别为K1 10100100 K2 01000011 42 2 S DES的加密运算 初始置换用IP函数 IP 末端算法的置换为IP的逆置换 IP 1 易见IP 1 IP X X 43 简化的得DES方案加密细节如右图 44 3 函数fk 是加密方案中的最重要部分 它可表示为 fk L R L F R SK R 其中L R为8位输入的左右各4位 F为从4位集到4位集的一个映射 并不要求是1 1的 SK为子密钥 对映射F来说 首先输入是一个4位数 n1 n2 n3 n4 第一步运算是扩张 置换 E P 运算 E P 41232341 45 E P 41232341 事实上 它的直观表现形式为 46 8 bit子密钥 K1 k11 k12 k13 k14 k15 k16 k17 k18 然后 与E P的结果作异或运算得 47 把它们重记为8位 48 上述第一行的4位输入进S盒S0 产生2 位的输出 第二行的4位输入进S盒S1 产生2位的输出 两个S盒按如下定义 49 S盒按下述规则运算 将第1和第4的输入比特做为2bit数 指示为S盒的一个行 将第2和第3的输入比特做为S盒的一个列 如此确定为S盒矩阵的 i j 数 例如 P0 0 P0 3 00 并且 P0 1 P0 2 10 确定了S0中的第0行2列 0 2 的系数为3 记为 11 输出 由S0 S1输出4bit经置换P4 2431 它的输出就是F函数的输出 50 2 6 8数据加密标准DES DataEncryptionStandard DES是一种对二元数据进行加密的算法 数据分组长度为64位 密文分组长度也是64位 使用的密钥为64位 有效密钥长度为56位 有8位用于奇偶校验 解密时的过程和加密时相似 但密钥的顺序正好相反 DES的整个体制是公开的 系统的安全性完全靠密钥的保密 51 DES算法的过程 是在一个初始置换IP initialpermutation 后 明文组被分成右半部分和左半部分 每部分32位以L0和R0表示 然后 是16轮迭代的乘积变换 称为函数f 将数据和密钥结合起来 16轮之后 左右两部分再连接起来 经过一个初始逆置换IP 1算法结束 52 53 54 初始置换与初始逆置换在密码意义上作用不大 他们的作用在于打乱原来输入x的ASCII码字划分关系 并将原来明文的校验位变成置换输出的一个字节 55 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 56 2 7密码分组操作模式 共四种操作模式电子编码本ECB密码分组链接CBC密码反馈CFB输出反馈OFB 57 2 7 1电子编码本ECB electroniccodebook 在ECB方式中 对于相同的密钥 相同的明文产生相同的密文 58 特点 简单和有效可以并行实现不能隐藏明文的模式信息相同明文相同密文同样信息多次出现造成泄漏对明文的主动攻击是可能的信息块可被替换 重排 删除 重放误差传递 密文块损坏 仅对应明文块损坏 适合于传输短信息 59 2 7 2密码分组链接CBC cipherblockchaining 60 特点 没有已知的并行实现算法能隐藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的信息块不容易被替换 重排 删除 重放误差传递 密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文 还可以进行用户鉴别 是大多系统的标准如SSL IPSec 61 2 7 3密码反馈CFB cipherfeedback 62 CFB特点 分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息 IV必须唯一误差传递 一个单元损坏影响两个单元 63 2 7 4输出反馈OFB outputfeedback 64 65 OFB特点 OFB 分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV误差传递 一个单元损坏只影响对应单元对明文的主动攻击是可能的 信息块可被替换 重排 删除 重放安全性较CFB差 66 2 1数据加密概念2 2密码体制2 3密码分类2 4算法分类2 5加密算法2 6数据加密标准DES2 7密码分组操作模式2 8其它分组加密算法2 9破译时间 67 2 8其它分组加密算法 下面主要考察较为流行的最重要的几个对称密钥的分组密码算法 这些算法都是自DES公布之后 人们了解DES的弱点越来越深入的情况下给出的 给出的方式有两种 一种是对DES进行复合强化它的抗攻击能力 另一种是开辟新的方法 即象DES那样加解密速度快 又具有抗差分攻击和其他方式攻击的能力 这些算法有三重DES IDEA RC5 RC6 Blowfish CAST RC2 68 2 8 1三重DES 这种方式里 使用三或两个不同的密钥对数据块进行三次或两次加密 加密一次要比进行普通加密的三次要快 三重DES的强度大约和112 bit的密钥强度相当 三重DES有四种模型 1DES EEE3使用三个不同密钥顺序进行三次加密变换 2DES EDE3使用三个不同密钥依次进行加密 解密 加密变换 3DES EEE2其中密钥K1 K3顺序进行三次加密变换 4DES EDE2其中密钥K1 K3依次进行加密 解密 加密变换 69 到目前为止 还没有人给出攻击三重DES的有效方法 对其密钥空间中密钥进行蛮干搜索 那么由于空间太大这实际上是不可行的 若用差分攻击的方法 相对于单一DES来说复杂性以指数形式增长要超过1052 70 2 8 2RC5 RC5是由RSA公司的首席科学家RonRivest于1994年设计 95年正式公开的一个很实用的加密算法 它是一种分组长 2倍字长w位 密钥长 按字节数计 和迭代轮数都可变的一种分组迭代密码 它以RC5 w r b表示 Rivest建议使用的标准RC5为RC5 32 12 16 71 该算法具有如下特性 a 形式简单易于软件或者硬件实现 运算速度快 b 能适应于不同字长的程序 不同字长派生出相异的算法 c 加密的轮数可变 这个参数用来调整加密速度和安全性的程度 d 密钥长度是可变的 加密强度可调节 e 对记忆度要求不高 使RC5可用于类似SmartCard这类对记忆度有限定的器件 f 具有高保密性 适当选择好参数 g 对数据实行bit循环移位 增强了抗攻击能力 72 RC5自1995年公布以来 尽管至今为止还没有发现实际攻击的有效手段 然而 一些理论攻击的文章先后也分析出RC5的一些弱点 73 2 8 3IDEA IDEA是InternationalDataEncryptionAlgorithm的缩写 是1990年由瑞士联邦技术学院来学嘉 X J Lai 和Massey提出的建议标准算法 称作PES ProposedEncryptionStandard Lai和Massey在1992年进行了改进 强化了抗差分分析的能力 改称为IDEA 它也是对64bit大小的数据块加密的分组加密算法 密钥长度为128位 它基于 相异代数群上的混合运算 设计思想 算法用硬件和软件实现都很容易 它比DES在实现上快得多 74 2 8 4AES算法 1997年4月15日美国国家标准和技术研究所NIST发起了征集AES算法的活动 并成立了专门的AES工作组 目的是为了确定一个非保密的公开披露的全球免费使用的分组密码算法 用于保护下一世纪政府的敏感信息 并希望成为秘密和公开部门的数据加密标准 75 1997年9月12日在联邦登记处公布了征集AES候选算法的通告 AES的基本要求是比三重DES快 而且 至少和三重DES一样安全 分组长度128比特 密钥长度为128 192 256比特 1998年8月20日NIST召开了第一次候选大会并公布了15个候选算法 1999年3月22日举行了第二次AES候选会议 从中选出5个 76 AES将成为新的公开的联邦信息处理标准 FIPS FederalInformationProcessingStandard 用于美国政府组织保护敏感信息的一种特殊的加密算法 美国国家标准技术研究所 NIST 预测 AES会被广泛地应用于组织学院及个人 入选AES的五种算法是MARS RC6 Serpent Twofish Rijndael 2000年10月2日美国商务部部长NormanY