《网络信息安全》第3-4讲.ppt

第2章密码技术 2 1密码学基本概念2 2古典密码2 3对称密码 2 1密码学基本概念 1 密码学密码学是研究如何实现数据加密的学科 密码学包括两方面内容 即密码编码学和密码分析学 将数据保密的技术和科学叫做密码编码学 与此对应的是破译密文的技术和科学叫做密码分析学 利用加密技术的通信过程如图2 1所示 图2 1加密和解密 2 1密码学基本概念 2 加密算法与解密算法在利用加密技术的通信过程中 消息m被称为明文 plaintext 对需要保密的消息进行编码的过程称为加密 编码的规则称为加密算法 被加密的消息称为密文 ciphertext 而把密文转变为明文的过程称为解密 解密的规则称为解密算法 图2 1加密和解密 2 1密码学基本概念 2 密码算法密码算法是用于加密和解密的数学函数 如果密码算法的保密性是基于算法的保密 这种算法称为受限制的算法 按照现在的安全标准 它们的保密性已远远不够 现代密码学采用密钥来解决这个问题 密钥用K来表示 如图2 2所示 加密算法和解密算法通常在一对密钥 K 的控制下进行 分别称为加密密钥和解密密钥 图2 2有密钥的加密和解密 2 1密码学基本概念 3 密码系统一个现代密码系统 体制 包括所有可能的明文 密文 密钥 加密算法和解密算法 所有这些算法的安全性都基于密钥的安全性 而不是基于算法的细节的安全性 这就意味着算法可以公开 即使窃听者知道你的算法也没有关系 如果他不知道你使用的具体密钥 就不可能阅读到你的消息 2 1密码学基本概念 3 密码系统密码系统根据密钥可以分为两类 即为对称密钥系统和公钥系统 对称密钥系统就是加密密钥能够从解密密钥中推算出来 反过来也成立 在大多数对称算法中 加 解密密钥是相同的 公钥系统又称公开密钥系统或非对称密钥系统 有两个密钥 一个是公开的 用K1表示 谁都可以使用 也叫加密密钥 另一个是私人密钥 用K2来表示 只能由采用此系统的人自己掌握 也叫解密密钥 从公开的密钥推不出私人密钥 2 2古典密码 1 代替密码 1 单表代替密码又可以称为单字母密码 就是明文的一个字符用相应的一个密文字符代替 著名的恺撒密码就是一种简单的代替密码 其加密原理就是每一个明文字符都由其右边第3个字符代替 那么3就是这个算法的密钥 即A由D代替 B由E代替 W由Z代替 X由A代替 Y由B代替 Z由C代替 若明文为student 则对应的密文为VWXGHQW 此时密钥为3 恺撒密码仅有26个可能的密钥 非常的不安全 2 2古典密码 1 代替密码 1 单表代替密码又可以称为单字母密码 由于英文字母中各字母出现的频率有明显的固有特征 而单表代替密码没有把明文中的不同字母的出现频率掩盖起来 因此根据字母频率表可以很容易对替换密码进行破译 代替密码是对所有的明文字母都用一个固定的代替密码进行加密 故也叫单表代替密码 为了防止字母频率分析攻击 随后产生了多表代替密码和多字母代替密码 2 2古典密码 1 代替密码 2 多表代替密码 由LeonBattista在1568年发明 在美国南北战争中由联军使用 比较著名的多表代替密码是1858年法国密码学家维吉尼亚设计的以移位替代为基础的一种周期替代密码 称为维吉尼亚密码 Vigen re 维吉尼亚密码有多个单字母密钥 每一个密钥被用来加密一个明文字母 第一个密钥加密明文的第一个字母 第二个密钥加密明文的第二个字母 等等 在所有密钥用完后 密钥又再循环使用 其中密钥的长度就是密码的周期 在古典密码学中 密码周期越长越难破译 2 2古典密码 1 代替密码 2 多表代替密码 例如 明文为system 密钥为dog 加密过程如下 其中 密钥字母a b c d x y z对应的数字为 0 1 2 3 24 25 密钥字母d对应数字3 所以明文字母s在d作用下右移3位 得到密文字母v 明文字母y在o作用下右移14位可以得到密文字母m 依次类推 解密时 密文字母在密钥字母的作用下向前移位即可得到对应的明文字符 明文 system密钥 dogdog密文 vmgwrs 多表代替密码结果将使得对单表代替用的字母简单频率分析方法失效 但使用计算机可以轻易破译具有很长周期的代替密码 2 2古典密码 1 代替密码 3 多字母代替密码 在前面介绍的两种算法中 明文中的每一个字符都是以单个字母作为代替的对象 如果用多于一个字母代替明文字符就是多字母代替密码 它的优点是容易将字母的频率隐藏 从而抗击字母统计分析 这种密码首先是由Playfair在1854年发明的 另外一个使用相对较多的多字母代替密码例子是Hill密码 但这类密码由于加密过于复杂而且不是非常安全 因此未能广泛应用 2 2古典密码 2 换位密码在换位密码中 明文的字母数保持相同 但相互之间的顺序被打乱了 在简单的纵行换位密码中 明文以固定的宽度水平写在一张图表纸上 密文按垂直方向读出 解密就是将密文按相同的宽度垂直地写在图表纸上 然后水平地读出明文 2 3对称密码 1 对称密码简介如果一个加密系统的加密密钥和解密密钥相同 或者虽然不相同 但是由其中的任意一个可以很容易地推导出另一个 则该系统所采用的就是对称密码体制 对称密码体制的优点是具有很高的保密强度 可以达到经受较高级破译力量的分析和攻击 但它的密钥必须通过安全可靠的途径传递 密钥管理成为影响系统安全的关键性因素 使它难以满足系统的开放性要求 2 3对称密码 1 对称密码简介对称密码体制根据对明文加密方式的不同而分为分组密码和流密码 又叫序列密码 序列密码一次只对明文中的单个位 有时也对字节 加 解密 对输入元素进行连续处理 同时产生连续单个输出元素 而分组密码是先按一定长度如64字节 128字节等对明文进行分组 然后以组为单位进行加 解密 一次处理一块输入明文 每个输入块生成一个输出块 各分组分别在密钥的控制下变换成等长度的密文分组 现代计算机加 解密典型分组长度为64位 这个分组不仅有防止分析破译的足够强度 又可以方便使用 2 3对称密码 2 DES加密数据加密标准 DES DataEncryptionStandard 是一种最通用的计算机加密算法 属于分组密码的一种 1973年5月美国国家标准局 NBS NationalBureauofStandyards 公布了一则公告 征求国家密码标准方案 1975年3月NBS公布了IBM公司提供的密码算法 以标准建议的形式在全国范围内征求意见 在经过大量公开讨论之后 该密码算法于1977年1月15日正式被批准为美国联邦信息处理标准 并授权在非密级的政府通信中使用 同年7月15日生效 发明人 IBM公司W Tuchman和C Meyer1971 72年研制 2 3对称密码 2 DES加密在1977年 人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密 而且需要12个小时的破解才能得到结果 1997年开始 RSA公司发起了一个称作 向DES挑战 的竞技赛 1997年1月 用了96天时间 成功地破解了用DES加密的一段信息 一年之后 在第二届赛事上 这一记录41天 1998年7月 第2 2届DES挑战赛 DESChallengeII 2 把破解DES的时间缩短到了只需56个小时 第三届DES挑战赛 DESChallengeIII 把破解DES的时间缩短到了只需22 5小时 2 3对称密码 2 DES加密DES是一个分组加密算法 以64位为分组对数据加密 64位一组的明文从算法的一端输入 64位的密文从另一端输出 DES是一个对称算法 加密和解密都用同一个算法 除密钥编排不同 密钥长度也是64位 其中每个第8位都用作奇偶校验 因此实际有效密钥长度为56位 是可以任意改变的56位数 DES算法是公开的 其安全性依赖于密钥的保密程度 2 3对称密码 2 DES加密先进行64位的明文分组操作 将该分组用初始置换IP进行置换 得到一个乱序的64位明文分组 然后将分组分成左 右等长的两边 各为32位长 记作L0和R0 在进行16轮完全类似的迭代运算后 其中F是在运算过程中将数据与密钥结合在一起的函数 把所得到的左 右长度相等的两半L16和R16交换 从而得到64位数据R16L16 最后再用初始逆置换 IP 1 进行置换 可以得到64位密文分组 加密算法过程如图2 3所示 图2 3加密算法过程 1 DES算法描述 2 3对称密码 2 DES加密初始置换是在第一轮迭代前执行 对输入64位分组实现如图所示变换 此图顺序为从上到下 从左到右 例如 初始置换把明文的第58位换到第一位 把50位换到第二位 以次类推 2 初始置换IP 2 3对称密码 2 DES加密产生子密钥Ki 如果不考虑每一个字节的第八位 即校验位 DES的密钥可以由64位减少到56位 在DES加密算法中 将用户提供的64位初始密钥经过一系列的处理得到K1 K2 K16 分别作为1 16轮运算的16个子密钥 先将64位密钥去掉8个校验位 用密钥置换 图2 5 剩下的56位密钥 图2 5密钥置换表 3 密钥处理 密钥置换 2 3对称密码 2 DES加密再将56位分成两个部分 各28位 然后根据轮数 图2 6 这两部分分别循环左移1位或2位 图2 6密钥每轮移动的位数 3 密钥处理 每轮移动 2 3对称密码 2 DES加密移动后 将两部分合并成56位再通过压缩置换 如图2 7所示 从而得到48位子密钥 这样经过16次运算就可以得到迭代运算所需的16个48位子密钥 图2 7压缩置换 3 密钥处理 合并与压缩置换 2 3对称密码 2 DES加密F函数是由数据扩展 与子密钥的异或运算 S盒代替 P盒置换组成 输入是由32位数据和48位的子密钥组成 下面分别介绍这几种运算 4 F函数简介 2 3对称密码 2 DES加密数据扩展也可以称为E盒扩展 如图2 8 此运算将数据的右半部分Ri从32位扩展到48位 可以产生与密钥同长度的数据进行异或运算 同时也可以使输入的一位影响两个替换 从而使输出对输入的依赖性传播得更快 图2 8扩展置换E 4 F函数简介 数据扩展 2 3对称密码 2 DES加密异或 就是将扩展后的48位输出数据E Ri 和压缩后的子密钥Ki作异或运算 4 F函数简介 扩展后的48位数据E Ri 压缩后的子密钥Ki 异或运算 2 3对称密码 2 DES加密S盒代替 就是将异或得到的48位结果分成八个6位的块 每一块作为每个S盒的输入 同时每个S盒产生一个4位的输出 这样8个S盒就可以产生32位的输出 如图2 9所示 对于每一个Si 由6位输入中的第1和第6位组成的二进制数确定Si的行 中间其余的4位二进制数用来确定Si的列 Si中相应的行 列位置的十进制数的4位二进制数用来作为输出 4 F函数简介 S盒代替 2 3对称密码 2 DES加密例如 右图中S2的输入为101001 则行数和列数的二进制数分别表示11和0100 即十进制数下的第3行和第4列 而在S盒2中第3行第4列的十进制数为11 用4位二进制数表示为1011 所以S2的输出为1011 从而可以用值1011代替101001 4 F函数简介 S盒代替 2 3对称密码 2 DES加密P置换 即将S盒代替运算后的32位输出按照P盒表 如图2 10 进行置换 该置换把每输入位对应到输出位上 任何一位不能被置换二次 也不能被忽略 例如 将第29位移动到第5位处 而把第5位移动到第13位处 以次类推 图2 10P盒置换 4 F函数简介 P盒置换 2 3对称密码 2 DES加密初始逆置换是初始置换的逆过程 就是将最后一轮迭代所得64位数据R16L16用初始逆置换IP 1 如图2 11 进行置换 产生64位密文分组 图2 11初始逆置换IP 1 5 初始逆置换IP 1 图2 4初始置换表IP 例如 第58位经过初始置换后 处于第1位 而通过逆置换 又将第1位换回到第58位 可见输入组m和IP IP 1 m 是一样的 2 3对称密码 2 DES加密6 DES解密 明文虽然经过许多轮的代替 置换 异或和循环移动之后 产生对应的密文 但由于经过精心选择各种操作 因此加密和解密可以使用相同的算法 惟一不同的是各轮密钥使用的次序相反 比如各轮加密密钥分别是K1 K2 K3 K16 那么 解密密钥就是K16 K15 K3 K2 K1 7 DES工作模式有四种 电子密本 ECB 密码分组链接 CBC 密文反馈 CFB 和输出反馈 OFB 这四种模式中ECB方式比较简单 也最容易受到攻击 但在流行的商业软件中 仍然是最常用的方式 2 3对称密码 3 DES算法中的关键函数设计1 函数F的设计函数F的基本功能就是 扰乱 confusion 输入 因此 对于F来说 其非线性越高越好 也就是说 要恢复F所做的 扰乱 操作越难越好 其他的设计准则还包括严格雪崩准则 SAC 和比特独立准则 BIC 所谓SAC 就是要求算法具有良好的雪崩效应 输入当中的一个比特发生变化都应当使输出产生尽可能多的比特变化 严格地说 就是当任何单个输入比特位i发生变换时 一个S盒的第j比特输出位发生变换的概率应为1 2 且对任意的i j都应成立 BIC的意思是当单个输入比特位i发生变化时 输出比特位j k的变化应当互相独立 且对任意的i j k均应成立 SAC和BIC可以有效地增强F函数的 扰乱 功能 2 3对称密码 3 DES算法中的关键函数设计2 S盒设计S盒的设计在对称分组密码研究领域中起着举足轻重的作用 本质上 S盒的作用就是对输入向量进行处理 使得输出看起来更具随机性 输入和输出之间应当是非线性的 很难用线性函数来逼近 显然 S盒的尺寸是一个很重要的特性 S盒越大 越容易抵制差分和线性密码分析 在实践当中 通常选择n在8 10之间 2 3对称密码 3 DES算法中的关键函数设计2 S盒设计S盒是DES的最敏感部分 其原理至今未公开 人们担心S盒隐藏陷门 使得只有他们才可以破译算法 但研究中并没有找到弱点 美国国家安全局透露了S盒的几条设计准则 所有的S盒都不是它输入的线性仿射函数 就是没有一个线性方程能将四个输出比特表示成六个比特输入的函数 改变S盒的1位输入 输出至少改变2位 这意味着S盒是经过精心设计的 它最大程度上增大了扩散量 S盒的任意一位输出保持不变时 0和1个数之差极小 即如果保持一位不变而改变其它五位 那么其输出0和1的个数不应相差太多 2 3对称密码 3 DES算法中的关键函数设计2 S盒设计Mister和Adams提出了很多的S盒设计原则 其中包括要求S盒满足SAC和BIC的原则 以及S盒的所有列的全部线性组合应当满足一类称为Bent函数的高度非线性布尔函数的原则 Bent函数具有很多有趣的特性 其中 高度非线性和最高阶的严格雪崩准则对于S盒的设计尤为重要 Nyberg提出了以下几种S盒的设计和实践原则 1 随机性 采用某些伪随机数发生器或随机数表格来产生S盒的各个项 2 随机测试 随机选择S盒各个项 然后按照不同准则测试其结果 3 数学构造 根据某些数学原理来产生S盒 其好处就是可以根据数学上的严格证明来抵御差分和线性密码分析 并且可以获得很好的扩散特性 习题 2 1简述密钥加密的基本原理 2 2比较对称加密和公钥加密的异同 2 3将字符串 networkandinformationsecurity 用恺撒密码加密