通信保密与信息安全教学课件.ppt

第二章加密技术基础 二O一O年秋季 本章目录 一 密码学与信息安全的关系二 密码学简史三 定义与基本概念四 古典加密技术 一 密码学与信息安全的关系 加密认证 网络安全模型 一 密码学与信息安全的关系 密码学是保证信息安全的一种必要手段密码技术是信息安全的一个核心技术没有密码学就没有信息安全此外 立法和管理政策手段等等 一 密码学与信息安全的关系 密码学所要解决的是信息安全的主要任务 即保证信息的机密性 confidentiality 数据完整性 integrity 认证性 authentication 抗否认性 non repudiation 访问控制 accesscontrol 一 密码学与信息安全的关系 密码学的目的使不知道如何解密的攻击者不可能由其截获的密文中得到任何有意义的明文信息 Byencodingmessagetomakethemnon readable 使攻击者不可能伪造任何密文性质的信息 一 密码学与信息安全的关系 什么是密码学 大的范畴分密码编码学 建立各种类型的密码系统设计一个密码算法构建一个密码方案密码分析学 对密码系统进行攻击破译由截获到的密文获得明文由用户公开的信息找到保密的秘密密钥密码编码学 密码分析学 密码学 一 密码学与信息安全的关系 什么是密码学 按保密的内容分受限制 restricted 的算法算法的安全性基于算法的保密性基于密钥 key based 的算法算法的安全性基于密钥的保密性 一 密码学与信息安全的关系 密码编码学Kerchhoff原则 1883年 Kerchoff第一次明确提出了编码的原则判定密码强度的衡量标准古典密码和现代密码的分界线 加密算法应建立在算法的公开不影响明文和密钥的安全的基础上 一 密码学与信息安全的关系 密码分析学穷举法 ExhaustiveAttack 暴力法 Brute forceAttack 对截获的密文尝试所有可能的密钥直至破译对抗措施 加大密钥量统计分析法 通过分析密文和明文的统计规律来破译对抗措施 使明文与密文的统计特性不一样解密变换法 针对加密变换的数学基础 通过数学求解的方法找到相应的解密变换对抗措施 设计具有坚实数学基础或结构复杂的加密算法 二 密码学简史 密码学是一门古老又年轻的学科三个阶段 1949 古典密码 艺术 art 1949 1975 近代密码 科学 science 1976 现代密码学 moderncryptography 2 1古典密码 1949年之前的手工阶段4000年以前 古埃及的一位擅长书写的祭司在贵族的墓碑上书写铭文时 有意用变形的象形文字而不是普通的象形文字来写铭文 这是有文字记载的最早的密码形式 2 1古典密码 1949年之前的手工阶段古巴比伦时代 Phaistos圆盘是一种直径约为160mm的粘土圆盘 始于公元前17世纪 表面有明显字间空格的字母 近年有研究学家认为它是古巴比伦人的加密工具 2 1古典密码 1949年之前的手工阶段密码学 Cryptology 源自希腊语 kryptos 及 logos 两字 直译即为 隐藏 及 单词 之意 2 1古典密码 1949年之前的手工阶段公元前440年 古希腊 隐写术 隐形药水字符标记图形图像 2 1古典密码 1949年之前的手工阶段公元前400年 古斯巴达人的Scytale 这是人类历史上最早使用的密码器械 公元前4世纪前后 希腊著名作家艾奈阿斯在其著作 城市防卫论 中曾提到一种被称为 艾奈阿斯绳结 的密码 2 1古典密码 1949年之前的手工阶段古罗马 公元前1世纪 著名的凯撒 Caesar 密码被用于高卢战争 2 1古典密码 1949年之前的手工阶段公元9世纪 阿拉伯的科学家阿尔 金迪提出解密的频度分析方法 通过分析密文字符出现的频率破译密码 公元16世纪晚期 英国的菲利普斯利用频度分析法成功破解苏格兰女王玛丽的密码信 信中策划暗杀英国女王伊丽莎白 这次解密将玛丽送上了断头台 2 1古典密码 1949年之前的手工阶段密码学不是科学 而是艺术纸 笔 简单加密设备 针对的是字符基本操作 substitution permutation简单的密码分析手段出现 2 1古典密码 1949年之前的机械阶段工业革命的兴起 密码学进入了机器时代一战是世界密码史上的第一个转折点二战的爆发促进了密码科学的飞速发展密码学逐渐成为科学密码算法逐步考虑复杂性要求密码分析理论开始形成 2 1古典密码 1949年之前的机械阶段二战期间 德国共生产了大约10多万部 ENIGMA 意为 谜 密码机英国 TYPEX密码机法国 Hagelin密码机 2 1古典密码 1949年之前 二战中 印第安纳瓦约土著语言被美军用作密码 当时纳瓦约族以外的美国人中 能听懂这种语言的也就一二十人 纳瓦约语密码成为历史上从未被破译的密码 2 2近代密码 1949年 1975年计算机的出现使基于复杂计算的密码成为可能现代数学方法为加密技术提供了新的工具信息论为密码学提供了理论基础1949年 Shannon 保密通信的信息理论 1971年 1973年 IBMWatson实验室的HorstFeistel等研发Lucifer密码体制 2 2近代密码 1949年 1975年数据的安全基于密钥而不是算法的保密高次迭代技术和非线性技术的使用算法设计需要抵抗各类已知的分析攻击方法算法分析理论逐步形成 2 3现代密码 1976年以后1977年 美国的数据加密标准 DES 公布公钥密码使无密钥传输的保密通信成为可能1976年 Diffie和Hellman在 NewDirectionsinCryptography 一文中提出了公钥密码思想1977年 MIT的Rivest Shamir和Adleman提出了RSA公钥密码算法90年代 逐步出现椭圆曲线等其它公钥密码算法 2 3现代密码 1976年以后密码算法设计既要考虑理论 又要考虑实现和使用 成为一项工程单一算法不能完全解决问题 需要一套综合的算法体系算法的安全性要融入系统的安全性考虑之中 2 4关于密码的教训 声称算法是 不可攻破的 没有使用最好的可用算法没有正确的实现算法在产品里放置了后门密码强度依赖于算法保密我们要使用自主产权的密码产品吗 三 定义与基本概念 Shannon保密通信模型 三 定义与基本概念 发送者与接收者Sender 信息传送过程中 主动提供信息的一方Recipient 得到信息的一方发送者要确保信息安全传送 窃听者不能盗取信息 明文与密文Plaintext 作为加密输入的原始消息Ciphertext 实施了加密的消息 三 定义与基本概念 加密 解密与破译Encryption 由明文到密文的变换过程Decryption 合法接收者从密文恢复出明文的过程Decoding 非法接收者试图从密文分析出明文的过程 三 定义与基本概念 加密算法与解密算法加密算法 对明文进行加密时采用的一组规则解密算法 对密文解密时采用的一组规则加密算法和解密算法是在一组仅有合法用户知道的秘密信息 称为密钥 Key 的控制下进行的 加密密钥和解密密钥分别指加密和解密过程中使用的密钥 三 定义与基本概念 密码系统明文消息空间M Plaintextspace 所有可能的明文的集合密文消息空间C Ciphertextspace 所有可能的密文的集合密钥空间K Ke和Kd Keyspace 所有可能的密钥的集合 三 定义与基本概念 密码系统加密变换E 由加密密钥控制的加密算法的集合任给k Ke Kd K 存在EKe E 使EKe M C解密变换D 由解密密钥控制的解密算法的集合任给k Ke Kd K 存在DKd D 使DKd C M六元组 M C Ke Kd EKe DKd 称为密码系统 密码体制 三 定义与基本概念 密码系统 给定 明文m M 密钥k Ke Kd K 加密变换EKe E 解密变换DKd D将明文m变换为密文c c EKe m 将密文c变换为明文m DKd EKe m m DKd EKe 1 三 定义与基本概念 密码算法的要求已知明文m M 加密密钥Ke 计算密文c EKe m 容易已知密文c C 解密密钥Kd 计算明文m DKd c 容易已知明文m M 但不知加密密钥Ke 就不能算出密文c EKe m 已知密文c C 但不知解密密钥Kd 就不能推出明文m DKd c 现代密码用密钥来保证安全性 三 定义与基本概念 密码系统分类按密钥管理方式对称密钥密码 symmetriccipher 单密钥密码公开密钥密码 public keycipher 非对称密钥密码按加密方式序列密码 流密码 streamcipher 分组密码 块密码 blockcipher 三 定义与基本概念 密码分析 密码破译无须取得密钥而能将密文信息恢复成明文的科学攻击者 恢复明文 窃取机密信息设计者 分析体制的弱点可破译的密码系统 仅根据密文可以推算出明文或密钥安全的密码系统 仅依赖于密钥的保密 满足Kerchhoffs原则 三 定义与基本概念 密码分析常用的攻击类型唯密文攻击 ciphertext onlyattack 已知明文攻击 known plaintextattack 选择明文攻击 chosen plaintextattack 选择密文攻击 chosen ciphertextattack 1 唯密文攻击 ciphertext onlyattack条件有一些消息的密文这些信息使用同一加密算法加密的目的恢复尽可能多的明文信息最好导出用于加密消息的密钥可以解密相同的密钥加密的任何新的消息的算法 1 唯密文攻击 ciphertext onlyattack已知c1 EK m1 c2 EK m2 ci EK mi 导出m1 m2 miK由ci 1 EK mi 1 推知mi 1的算法 2 已知明文攻击 known plaintextattack条件有一些消息的明 密文对这些信息使用同一加密算法加密的目的导出用于加密消息的密钥可以解密相同的密钥加密的任何新的消息的算法 2 已知明文攻击 known plaintextattack已知m1 c1 EK m1 m2 c2 EK m2 mi ci EK mi 导出K由ci 1 EK mi 1 推知mi 1的算法 3 选择明文攻击 chosen plaintextattack条件有一些消息的明 密文对这些信息使用同一加密算法加密的可选择加密的明文并获得相应的密文目的导出用于加密消息的密钥可以解密相同的密钥加密的任何新的消息的算法 3 选择明文攻击 chosen plaintextattack已知m1 c1 EK m1 m2 c2 EK m2 mi ci EK mi 其中密码分析者选择m1 m2 mi 导出K由ci 1 EK mi 1 推知mi 1的算法 4 选择密文攻击 chosen ciphertextattack条件可选择一些密文并得到相应的明文这些信息使用同一加密算法加密的目的导出用于加密消息的密钥密码破译员能选择不同的密文和已解的明文 将它们放入一个自动解密的分解判别的工具箱中 导出密钥 4 选择密文攻击 chosen ciphertextattack已知c1 m1 DK c1 c2 m2 DK c2 ci mi DK ci 其中密码分析者选择c1 c2 ci 导出K 密码破译方法小结 三 定义与基本概念 密码体制安全性无条件安全 Unconditionallysecure 破译者拥有无穷多计算资源和密文 也不能解出明文即使解出明文 无法验证结果的正确性计算安全 Computationallysecure 破译密码成本超过信息价值破译时间超过信息生命周期可证明安全 Provablesecure 归约安全破译难度归约为某个不可解的基础算法或数学难题 四 古典加密技术 隐写术 Steganography 替代 Substitution 置换 Permutation 4 1隐写术 Steganography 隐秘书写 将秘密消息隐藏在其它消息中字符标记隐形墨水图形图像扎小孔格孔密写卡 4 1隐写术 格孔密写卡 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天必需备伞一把方能上街 苦矣 大约本月中旬我才能返回 届时再见 弟李明敬上 4 1隐写术 4 1隐写术 优点不易发现缺点形式简单 但构造费时一旦发现 毫无价值稳健性不强 4 2替代 加密 明文字母由其它字母 数字或符号替换解密 接收者对密文进行逆替换四种替代密码简单替代 simplesubstitution 单表替代多名码替代 homophonicsubstitution 同音替代多元替代 polygramsubstitution 多表替代 polyalphabeticsubstitution 4 2替代 简单替代 单表替代明文每一字符被替代成密文相应字符 例如 tobeornottobe BDQHDXWDBBDQH 4 2替代 多名码替代 同音替代类似简单替代 一次把一个明文字符换成一个密文字符 密文字符可以是所选集合中任何一个字符 例 A 可能相应于5 13 25多元替代成块的字符加密成一组其它字符例 ABA 相应于 RTQ 例 ABB 相应于 SLL 4 2替代 多表替代对明文消息采用多个简单替代例 使用5张简单替代表的多表替代密码 明文第一个字母用第一张替代表 第二个字母用第二个替代表 第三个字母用第三个替代表 等等 以此类推 循环使用这5张替代表 1 简单替代 移位密码体制明文空间 密文空间 密钥空间M C A B Z K 1 25 或M C 0 1 25 K 1 25 加解密 对k KEk x x k mod26 yDk y y k mod26 密钥空间大小 K 25 1 简单替代 移位密码体制例 k 3C E M M 3 mod26M D C C 3 mod26明文 meetmeaftertheparty密文 PHHWPHDIWHOWKHSDUWB 1 简单替代 移位密码体制例 k 3算法描述 将字母表中的每个字母用其后的第三个字母代替 Caesar密码 1 简单替代 移位密码体制通用Caesar密码 k换为1 25间任意一个数例 k 5C E M M 5 mod26M D C C 5 mod26密文 NQTAJYMNXLFRJ明文 1 简单替代 仿射密码体制明文空间 密文空间 密钥空间M C 0 1 25 a b 0 1 25 K a b gcd a 26 1 互素 加解密 对k a b K 定义Ek x ax b mod26 yDk y a 1 y b mod26 a 1 称为a的逆 满足a 1a 1mod26 a 1存在的充要条件是gcd a 26 1 1 简单替代 仿射密码体制当a 1 即移位密码当a 1 b 3 即Caesar密码密钥空间大小 K 12 26 1 311 1 简单替代 仿射密码体制例 K a b 9 2 Ek x 9x 2 mod26 Dk y a 1 y 2 mod26 问 a 1 a 1amod26 Plaintext n Ciphertext 1 简单替代 仿射密码体制解 将字母n转换成为数字13 然后加密c 9 13 2 119mod26 15密文 p解密m 3 15 6 45 6 39mod26 13明文 n 1 简单替代 仿射密码体制例 K a b 7 3 Ek x 7x 3 mod26 Dk y a 1 y 3 mod26 问 a 1 Plaintext hotCiphertext 1 简单替代 仿射密码体制解 将字母h o t转换成为数字7 14 19 加密7 7 3 52mod26 0mod26 A7 14 3 101mod26 23mod26 X7 19 3 136mod26 6mod26 G解密15 0 19 19mod26 7mod26 H15 23 19 326mod26 14mod26 O15 6 19 71mod26 19mod26 T 1 简单替代 密码分析移位密码体制 仿射密码体制穷举攻击 可行任意26英文字符的简单替代密码体制穷举攻击 K 26 1 4 1026 不可行频率分析攻击 利用语言统计特性 明文单词构造有规律 可以根据字母出现频率破译 2 多元替代 基本思路将明文字符成块代替成密文字符块相同的明文字符被加密成不同的密文字符完全隐藏了单字母的频率 抗频率分析攻击 2 多元替代 Hill密码1929年 数学家LesterHill研制基本思想 将m个连续的明文字母通过线性变换转换为m个密文字母密钥 线性变换矩阵解密 逆变换 2 多元替代 Hill密码明文空间 密文空间 密钥空间M C 0 1 25 m m为正整数K 0 1 25 上的m阶可逆方阵 加解密 对k K 定义Ek x xK mod26 yDk y yK 1 mod26 K 1 K的逆矩阵 满足K K 1 I 存在的条件gcd det K 26 1 2 多元替代 Hill密码例 m 2 明文 july 加密密钥分组 明文分成2组元素 ju ly 分别对应于 920 1124 2 多元替代 Hill密码例 m 2 明文 july加密密文 DELW 2 多元替代 Hill密码例 m 2 密文 DELW 解密密钥分组 密文分成2组元素 DE LW 分别对应于 34 1122 2 多元替代 Hill密码例 m 2 密文 DELW解密明文 july 2 多元替代 Hill密码例 加密密钥明文 hill密文 2 多元替代 Hill密码例 加密密钥m 4加密 明文分成1组元素 hill 对应于 781111 2 多元替代 Hill密码例 m 4 明文 hill加密密文 JIIY 2 多元替代 密码分析Hill密码频率分析攻击 不可行完全隐藏了单字母的频率已知明文攻击 可行获得m个明 密文对 可计算出K 破译 3 多表替代 基本思路使用明文字母到密文字母的多个映射 每个映射都是简单替代相同的明文字符被加密成不同的密文字符将字母自然频度隐蔽或均匀化 抗频率分析攻击 3 多表替代 维吉尼亚密码 Vigenere 16世纪 法国外交家BlaisedeVigenere发明使用一个m长度的词组作密钥 密钥的每个字母确定了一个单表替代表密钥循环使用 3 多表替代 维吉尼亚密码 Vigenere 明文空间 密文空间 密钥空间M C 0 1 25 m K 0 1 25 d m d正整数加解密 对k k1 k2 kd K 定义Ek X x1 k1 x2 k2 xi ki mod26 yDk Y y1 k1 y2 k2 yi ki mod26 密钥空间大小 K 26d 1 3 多表替代 维吉尼亚密码例 k best 明文 datasecurity按密钥长度d 4将明文分组 datasecurity每一序列利用密钥k加密 data best mod26 eeltsecu best mod26 tiunrity best mod26 smlr密文 eelttiunsmlr 3 多表替代 维吉尼亚密码例 k best 密文 eelttiunsmlr按密钥长度d 4将密文分组 eelttiunsmlr每一序列利用密钥k解密 eelt best mod26 datatiun best mod26 secusmlr best mod26 rity明文 datasecurity 3 多表替代 维吉尼亚密码例 k cipher 明文 cryptography密文 例 k key 密文 fmeorcbi明文 3 多表替代 密码分析维吉尼亚密码穷举攻击 不可行频率分析攻击 4 3置换 原理加密时不改变明文字符 只将字符在明文中的排列顺序改变 从而实现明文信息的加密 常用方法倒置换位 1 倒置 倒置 将明文按字母顺序依次倒置形成密文示例一明文 internetinform