Ch02分组密码体制.ppt

信息系统安全原理 Ch02分组密码体制 2 本章学习目的 掌握密码学的基本概念分组密码 流密码 对称密码 非对称密码理解经典密码体制的原理理解分组密码原理了解数据加密标准 高级加密标准了解分组密码的工作模式了解流密码 一密码学的基本概念 3 1基本概念 加密技术的基本思想就是伪装信息 使非法接入者无法理解信息的真正含义 伪装就是对信息进行一组可逆的数学变换 我们称伪装前的原始信息为明文 经伪装的信息为密文 伪装的过程为加密 用于解除伪装还原出原始信息的过程为解密 加密Encrypt解密Decrypt密文ciphertext明文plaintext 一般m表示密钥Key 一密码学的基本概念 4 1基本概念 用于对信息进行加密的一组数学变换称为加密算法 用于对信息进行解决的数学变换就是解密算法 为了有效控制加密 解密算法的实现 在这些算法的实现过程中 需要有某些只被通信双方所掌握的专门的 关键的信息参与 这些信息就称为密钥 用作加密的称加密密钥 用作解密的称作解密密钥 一密码学的基本概念 5 2密码学与密码体制 密码学两个分支 密码编码学与密码分析学 密码编码学主要研究对信息进行编码实现信息保密性的科学 即加密算法密码分析学是研究 分析 破译密码的科学 即如何从密文推出明文 密钥或解密算法的学问这两种技术相互依存 相互支持 共同发展 一密码学的基本概念 6 2密码学与密码体制 加密算法的三个发展阶段 经典密码体制对称密钥密码 即 单钥密码体制 公开密钥密码 即 双钥密码体制 这些算法按密钥管理的方式可以分为对称算法与非对称算法两大类 即我们通常所说的对称密钥密码体制和非对称密钥密码体制 一密码学的基本概念 7 3对称密码体制 加密密钥和解密密钥相同 或实质上等同 即从一个可以推出另外一个 我们称其为对称密钥或单钥密码体制 加密方式有两种 对明文按字符逐位加密 称为流密码或序列密码序列密码是手工和机械密码时代的主流方式 先对明文消息分组 再逐组加密 称为分组密码分组密码将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出也是固定长度的密文 最典型的就是1977年美国国家标准局颁布DES算法 一密码学的基本概念 8 单密钥密码的加 解密过程 3对称密码体制 一密码学的基本概念 9 3对称密码体制 加密密钥和解密密钥相同 或实质上等同 即从一个可以推出另外一个 我们称其为对称密钥或单钥密码体制 单钥密码体制的优点 安全性高 加解密速度快其缺点是 进行保密通信之前 双方必须通过安全信道传送所用的密钥 相距较远的用户 较大的代价 甚至难以实现 例如 在拥有众多用户的网络环境中使n个用户之间相互进行保密通信 若使用同一个对称密钥 一旦密钥被破解 整个系统就会崩溃 使用不同的对称密钥 则密钥的个数几乎与通信人数成正比 需要n n 1 个密钥 由此可见 若采用对称密钥 大系统的密钥管理几乎不可能实现 一密码学的基本概念 10 保密通信系统模型 4保密通信系统模型 一密码学的基本概念 11 5非对称密码体制 若加密密钥和解密密钥不相同 从其中一个难以推出另一个 则称为非对称密钥或双钥密码体制 采用双钥密码体制的主要特点是将加密和解密功能分开 因而可以实现多个用户加密的消息只能由一个用户解读 或只能由一个用户加密消息而使多个用户可以解读 在使用双钥体制时 每个用户都有一对预先选定的密钥 一个是可以公开的 公钥 以k1表示 另一个则是秘密的 私钥 以k2表示 公钥k1可以像电话号码一样进行注册公布 私钥是其拥有者自己保存 因此双钥体制又称作公钥体制 PublicKeySystem 最有名的双钥密码体制是1977年由Rivest Shamir和Adleman等三人提出的RSA密码算法 一密码学的基本概念 12 双钥密码体制的通信模型 5非对称密码体制 一密码学的基本概念 13 双钥密码体制既可用于实现公共通信网的保密通信 也可用于认证系统中对消息进行数字签名 同时实现信息保密性和对消息的认证 在明文消息空间和密文消息空间等价 且加密 解密运算次序可换 即Ekl Dk2 m Dk2 Ek1 m m 双钥保密和认证体制 6双密钥 认证系统 一密码学的基本概念 14 实际网络多采用双钥和单钥密码相结合的混合加密体制 即使用单钥密码进行加解密明文或密文 采用双钥密码实现密钥传送 这样既解决了密钥管理的困难 又解决了加 解密速度的问题 7混合加密系统 一密码学的基本概念 15 8密码学的作用 密码学主要的应用形式有数字签名 身份认证 消息认证 也称数字指纹 数字水印等几种 这几种应用的关键是密钥的传送 网络中一般采用混合加密体制来实现 密码学的应用主要体现了以下几个方面的功能 1 维持机密性传输中的公共信道和存储的计算机系统容易受到被动攻击 如截取 偷窃 拷贝信息 和主动攻击 如删除 更改 插入等操作 加密关键信息 让人看不懂而无从攻击 2 可用性由于网上的通信双方互不见面 必须在相互通信时 交换敏感信息时 确认对方的真实身份 即消息的接收者应该能够确认消息的来源 入侵者不可能伪装成他人 一密码学的基本概念 16 8密码学的作用 3 保证完整性接收者能够验证在传送过程中是否被篡改 入侵者不可能用假消息代替合法消息 4 抗抵赖 不可否认性 在网上开展业务的各方在进行数据传输时 必须带有自身特有的 无法被别人复制的信息 以保证发生纠纷时有所对证 发送者事后不可能否认他发送的消息 一密码学的基本概念 17 9密码分析学 一密码学的基本概念 密码编码学 对信息进行编码实现隐蔽信息的一门学问 密码分析学 分析破译密码的学问 两者相互对立 促进 1 常用的密码分析攻击有四类 前提 加密算法 公开 攻击目标 获得密钥K唯密文攻击 ciphertextonlyattacks 已知 截获部分密文已知明文攻击 knowplaintextattacks 已知 截获部分密文 若干明文 密文对 选择明文攻击 chosenplaintextattacks 已知 截获部分密文 自主选择的明文 密文对 选择密文攻击暂时接近密码机 可选择密文串 并构造出相应的明文 18 9密码分析学 一密码学的基本概念 2 算法的安全性密码算法具有不同的安全等级 以下情况可能是安全的破译算法的代价大于加密数据的价值破译算法所需的时间大于加密数据保密的时间用单密钥加密的数据量小于破译算法需要的数据量Shannon理论 仅当密钥至少和明文一样长时才无条件安全 如果不论密码分析者有多少密文 都没有足够的信息恢复出明文 那么这个算法就是无条件保密的 只有一次一密乱码本 才是无条件安全的 所有其它的密码系统在唯密文攻击中都是可破的 蛮力攻击 19 9密码分析学 一密码学的基本概念 3 密码学更关心在计算上不可破译的密码系统 如果一个算法用 现在或将来 可得到的资源 公开数据 都不能破译 这个算法则被认为在计算上是安全的 可以用不同方式衡量攻击方法的复杂性 数据复杂性 用作攻击输入所需的数据量 处理复杂性 完成攻击所需要的时间 这个经常叫做工作因素 存储需求 进行攻击所需要的存储量 作为一个法则 攻击的复杂性取这三个因数的最小化 有些攻击包括这三种复杂性的折中 存储需求越大 攻击可能越快 20 1经典密码体制 二经典密码体制的基本原理 单表代换密码密钥移位固定多表代换密码密钥移位周期固定多字母代换密码明文分组变换 21 1单表代换密码 二经典密码体制的基本原理 单表代换密码 对所有的明文字母都用一个固定的代换进行加密 因而称为单表代换密码 加密过程中是从明文字母表到密文字母表的一一映射 例 恺撒 Caesar 密码 明文abcdefghIjklmnopqrstuvwxyz密文XNYAHPOGZQWBTSFLRCVMUEKJDI解决函数是一个逆置换 即解密算法 ABCDEFGHIJKLMNOPQRSTUVWXYZdlryvohezxwptbgfjqnmuskacI例 MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA解 thisciphertextcannotbedecrypted含义 Thisciphertextcannotbedecrypted缺点 不能抗击字母频度分析 容易被破译 22 1单表代换密码 二经典密码体制的基本原理 英语26个字母中 各字母出现的频率不同而稳定 经过大量统计 可以给出了各字母出现的频率值 英文明文字母按出现概率大小分组表 1e 0 12taoinshr0 05 0 13dl0 03 0 054cumwfgypb0 01 0 035vkjxqz 0 01 23 1单表代换密码 二经典密码体制的基本原理 字母 三字母组合是分析单表密码的有力手段 英语单词以e s t d双结尾的超过一半 以t a s w为起始字母的约为一半 某些常用用法也会提供有价值的线索 如信的开头写Dear 源程序的某一位置是版权声明 电子资金传送报头格式 单表密码的弱点 明文和密文字母之间的一一代替关系 这使得明文中的一些固有特性和规律 比如语言的各种统计特性 必然反映到密文中去 24 2多表代换密码 二经典密码体制的基本原理 多表代换密码 由多个单字母密码构成 每个密钥加密对应位置的明文 例 维吉尼亚密码 维吉尼亚 Vigenere 密码 典型的多表密码 即一个明文字母可表示为多个密文字母 例如 明文为System 密钥为dog a b c x y z分别用0 1 2 23 24 25来表示 加密过程如下 明文 System密钥 dogdog密文 Vmgwrs在这个例子中 明文事每三个字母中的第一 第二 第三个字母分别移动 mod26 3个 14个和6个位置 明文与密钥字母频率分布相同 可统计分析 除非选择与明文长度相同并与之没有关系的密钥内容 25 3多表代换密码 二经典密码体制的基本原理 多表代替密码 明文字符串按固定长度被分组 然后成组加密 如 明文 wearediscoveredsaveyourselfabc首先将明文分成6个字母长的明文组 分组 wearediscoveredsaveyourselfabc将每6字母长的明文组按密钥k重新排列如下 AEWDRECVIEOSDARVSEORESUYFBECAL密文 AEWDRECVIEOSDARVSEORESUYFBECAL特点 隐藏字母频度 抗击统计分析 使用复杂 26 1分组密码基本含义 三分组密码原理 分组密码系统对不同的组采用同样的密钥K进行加 解密 设密文组为y y1y2 ym 则对明文组x x1x2 xm 用密钥k加密可得到 y ek x1 ek x2 ek xm 27 2分组密码设计原理 三分组密码原理 进一步分析 分组密码将明文消息编码表示后的明文数字序列x0 x1 x2 划分成长度为n的组 X x0 x1 x2 xn 1 可看到长度为n的矢量每组分别在密钥k k0 k1 k2 km 1 的控制下变换成等长的密文序列Y y0 y1 y2 yn 1 也可看到成n维矢量加密函数是E Vn K Vn 是n维矢量空间 K为密钥空间 过程如下图所示 28 2分组密码设计原理 三分组密码原理 分组密码模型 29 3分组密码设计的一般原则 三分组密码原理 分组长度应足够大 使得不同明文分组的个数2n足够大 以防止明文被穷举法攻击 密钥空间应足够大 尽可能消除弱密钥 从而使所有密钥同等概率 以防穷举密钥攻击 由密钥确定的算法要足够复杂 充分实现明文与密钥的扩散和混淆 软件实现的要求 尽量使用适合编程的子块和简单的算法 硬件实现的要求 加密和解密应具有相似性 即加密和解决过程的不同应仅仅在于密钥的使用方式上 以便采用同样的器件来实现加密和解密 以节省费用和体积 尽可能采用标准的组件结构 以便能在超大规模集成电路中实现 30 4分组密码的一般结构 三分组密码原理 一般有两种 Feistel网络结构由Feistel发明 被DES采用SP网络结构可逆函数S 置换作用P 是一种重要的结构AES标准采用此结构 31 1DES加密标准 四数据加密标准 发明人 IBM公司W Tuchman和C Meyer1971 72年研制 产生 美国商业部的国家标准局NBS1973年5月到1974年8月两次发布通告 公开征求用于电子计算机的加密算法 IBM的LUCIFER的改进方案被采纳 标准化 于1976年11月被美国政府采用 DES随后被美国国家标准局和美国国家标准协会 AmericanNationalStandardInstitute ANSI 承认 1977年1月以数据加密标准DES DataEncryptionStandard 的名称正式向社会公布 于1977年7月15日生效 DES的发展 如衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等 32 1DES加密标准 四数据加密标准 破解 发明人在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小时 标准已不适用 33 2DES算法框图 四数据加密标准 34 3DES的问题讨论 四数据加密标准 DES算法中 除S盒外 所有计算都是线性的 有人质疑S盒可能存在陷门 但至今没发现 担心实际56比特的密钥长度不足以抵抗穷举攻击 因为密钥量只有256 1017个 事实也如此 1997年即被破解 35 3DES的问题讨论 四数据加密标准 DES算法中 除S盒外 所有计算都是线性的 有人质疑S盒可能存在陷门 但至今没发现 担心实际56比特的密钥长度不足以抵抗穷举攻击 因为密钥量只有256 1017个 事实也如此 1997年即被破解 36 4DES的变形 四数据加密标准 双重DES已知明文P和两个密钥K1和K2 密文为C EK2 EK1 P 解决过程做逆运算 P DK1 DK2 C 问题 是否存在K3 使得EK2 EK1 P EK3 P 直到1992年 这个结论才被证明是不成立的 中途攻击已知明文 密文对 P C 是可能找到K1和K2的 三重DES为解决中途攻击而设计 密钥长度2112 37 1高级加密标准 五高级加密标准 NIST 国家标准技术研究所 1997年9月12日发出征集高级加密标准的通知 1998年8月首次选出15个候选者 1999年3月遴选出5个 包括 E2 MARS RC6 Rijndael Twofish 2000年10月2日 美国商务部部长宣布比利时的Rijndael算法成为新的AES 选择的基本条件 公开 分组单钥 分组长度128 密钥可为128 192 256 可软硬件实现 优劣标准 安全性 计算效率 内存要求 简便灵活 此外 适应性 减少专利纠纷 分散目标减少攻击 AES被开发用于替代DES 但NIST预测TripleDES仍将在近期作为一种实用的算法 38 1ECB模式 六分组密码的工作模式 ECB 电码本 模式 各明文组独立地以同一密钥加密 用于传送短数据 如加密密钥 39 2CBC模式 六分组密码的工作模式 CBC 密码分组链接 模式 每次加密使用同一密钥 加密算法的输入是当前明文组和前一次密文组的异或 Cn Ek Cn 1 Pn 初始向量V1 用途 传送数据分组 认证 40 3CFB模式 六分组密码的工作模式 CFB 密码反馈 模式 可将DES转换为流密码 流密码无需填充消息 实时运行 流密码中明文和密文长度相同 如对字符加密 只要密钥长度8bit Cn Pn Sj E Cn 1 41 4OFB模式 六分组密码的工作模式 OFB 输出反馈 模式 用分组密码产生一个随机密钥流 将此密钥流和明文流进行异或可得密文流 仍然需要一个初始向量 IV 42 1流