《密码学基础》PPT课件.ppt

计算机安全与保密 信息安全原理与应用 袁静波 东北大学秦皇岛分校 第2章密码学基础 密码学的发展历史密码学的基本概念密码系统的分类密码分析经典密码学 加密技术概述 以密码学为理论基础 基本思想是伪装信息 使非法接入者无法理解信息的真正含义一般应用于政治 经济 军事 外交 情报等重要部门 20世纪80年代后 得到广泛重视和普及信息安全中的数据安全主要采用现代加密技术对数据进行主动的安全保护是保护大型网络传输信息安全的重要实现手段是信息安全保障的基础工具 解决信息安全问题的根本基础是密码学 密码学实质属于数学范畴 利用数学代数知识探讨信息的隐藏与恢复机制 是研究如何保护信息安全的一门学科 密码学的作用和地位 已成为一门综合性的尖端技术科学维持机密性用于鉴别保证完整性用于抗抵赖 2 1密码学的发展历史 自人类社会出现战争便产生了密码公元前1900年 古埃及石碑记载 Phaistos圆盘 一种直径约为160mm的Cretan Mnoan粘土圆盘 始于公元前17世纪 表面有明显字间空格的字母 至今还没有破解 公元前1世纪 JuliusCaesar发明了凯撒密码 密码学的发展历史 1834年 伦敦大学的实验物理学教授惠斯顿发明了电机 这是通信向机械化 电气化跃进的开始 也为密码通信采用在线加密技术提供了前提条件 1920年 美国电报电话公司的弗纳姆发明了弗纳姆密码 其原理是利用电传打字机的五单位码与密钥字母进行模2相加 密码学的发展历史 两次世界大战大大促进了密码学的发展 二战中美国陆军和海军使用的条形密码设备M 138 T4 根据1914年ParkerHitt的提议而设计 25个可选取的纸条按照预先编排的顺序编号和使用 主要用于低级的军事通信 Kryha密码机大约在1926年由AlexandervoKryha发明 这是一个多表加密设备 密钥长度为442 周期固定 一个由数量不等的齿的轮子引导密文轮不规则运动 密码学的发展历史 两次世界大战大大促进了密码学的发展 转轮密码机ENIGMA 由ArthurScherbius于1919年发明 面板前有灯泡和插接板 4轮ENIGMA在1942年装备德国海军 英国从1942年2月到12月都没能解读德国潜艇的信号 英国的TYPEX打字密码机 是德国3轮ENIGMA的改进型密码机 它在英国通信中使用广泛 且在破译密钥后帮助破解德国信号 密码学的发展历史 1949年香农发表了一篇题为 保密系统的通信理论 的著名论文 该文首先将信息论引入了密码 从而把已有数千年历史的密码学推向了科学的轨道 奠定了密码学的理论基础 1976年 美国密码学家W Diffie和M Hellman在一篇题为 密码学的新方向 一文中提出了一个崭新的思想 不仅加密算法本身可以公开 甚至加密用的密钥也可以公开 1977年美国国家标准局颁布了数据加密标准DES2001年11月26日 正式颁布AES为美国国家标准 密码学的发展 手工密码 机械密码 电子电路密码 计算机密码 物理 生物密码 2 2密码学的基本概念 密码学 Cryptology 研究信息系统安全保密的科学 它包含两个分支 密码编码学 Cryptography 对信息进行编码实现隐蔽信息的一门学问 密码分析学 Cryptanalytics 研究分析破译密码的学问 二者相互独立 又相互依存 在矛盾与斗争中发展 对立统一 明文 消息 Plaintext 被隐蔽消息 密文 Ciphertext 或密报 Cryptogram 明文经密码变换成的一种隐蔽形式 加密 Encryption 将明文变换为密文的过程 解密 Decryption 加密的逆过程 即由密文恢复出原明文的过程 加密算法 Encryptionalgorithm 密码员对明文进行加密时所采用的一组规则 解密算法 Decryptionalgorithm 接收者对密文进行解密时所采用的一组规则 密钥 Key 控制加密和解密算法操作的数据处理 分别称作加密密钥和解密密钥 密码学的基本概念 密码学的基本概念 加密员或密码员 Cryptographer 对明文进行加密操作的人员 接收者 Receiver 传送消息的预定对象 截收者 Eavesdropper 在信息传输和处理系统中的非受权者 通过搭线窃听 电磁窃听 声音窃听等来窃取机密信息 密码分析 Cryptanalysis 截收者试图通过分析从截获的密文推断出原来的明文或密钥 密码分析员 Cryptanalyst 从事密码分析的人员 Key密钥 在计算机上实现的数据加密算法 其加密或解密变换是由一个密钥来控制的 密钥key是由使用密码体制的用户随机选取的 密钥成为唯一能控制明文与密文之间变换的关键 它通常是由一串随机字符串组成 Kerckhoffs slaw柯克霍夫定律 只要加密算法使用的密钥保持安全的 数据就是安全的 绝不能寄希望于敌人不知道怎样解密你的数据 数据安全基于密钥而不是算法的保密 也就是说 对于一个密码体制 其算法是可以公开的 让所有人来使用 研究 但具体对于某次加密过程中所使用的密钥 则是保密的 加密手段 硬件加密速度快安全性高自带加密模块 通信链路专用加密盒 计算机板卡成本高软件加密灵活性可移植性成本低速度慢 密码体制基本组成 密码系统指为实现信息隐藏所采用的基本工作方式 一个密码系统 通常简称为密码体制它是一个五元组 M C K E D 2 3密码系统的分类 设 M 明文 C 密文 Ke 加密密钥 Kd 解密密钥E 加密算法 D 解密算法 密码系统的数学模型 信息加密传输的过程 用户A 用户B 窃听者或攻击者C 密码系统的分类 根据密钥的使用方式分类对称密码体制 秘密钥密码体制 用于加密数据的密钥和用于解密数据的密钥相同 或者二者之间存在着某种明确的数学关系 加密 EK M C解密 DK C M非对称密码体制 公钥密码体制 用于加密的密钥与用于解密的密钥是不同的 而且从加密的密钥无法推导出解密的密钥 用公钥KP对明文加密可表示为 EKP M C用相应的私钥KS对密文解密可表示为 DKS C M 密码系统的分类 根据明文和密文的处理方式分类分组密码体制 BlockCipher 设M为明文 分组密码将M划分为一系列明文块Mi 通常每块包含若干字符 并且对每一块Mi都用同一个密钥Ke进行加密 M M1 M2 Mn C C1 C2 Cn 其中Ci E Mi Ke i 1 2 n 序列密码体制 StreamCipher 将明文和密钥都划分为位 bit 或字符的序列 并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密 M M1 M2 Mn Ke ke1 ke2 ken C C1 C2 Cn 其中Ci E mi kei i 1 2 n 密码系统的分类 根据加密算法是否变化分类设E为加密算法 K0 K1 Kn 为密钥 M0 M1 Mn为明文 C为密文固定算法密码体制C0 E M0 K0 C1 E M1 K1 Cn E Mn Kn 变化算法密码体制C0 E1 M0 K0 C1 E2 M1 K1 Cn En Mn Kn 密码系统的评价 保密强度保密强度大的系统 开销往往较大密钥的长度密钥的长度要适中 要经常变化算法的复杂度复杂度要有限度加密后信息长度的增加程度信息长度的增加将导致通信效率的降低 密码体制的安全性 如果不论截取者获得了多少密文 但在密文中都没有足够的信息来唯一地确定出对应的明文 则这一密码体制称为无条件安全的 或称为理论上是不可破的 如果密码体制中的密码不能被可使用的计算资源破译 则这一密码体制称为在计算上是安全的 即加密算法应该满足下列条件之一 破译密码的代价超出密文信息的价值破译密码的时间超出密文信息的有效生命期 2 4密码分析 截收者在不知道解密密钥及通信者所采用的加密体制细节条件下 对密文进行分析 试图获取机密信息密码分析在外交 军事 公安 商业等方面都具有重要作用 也是研究历史 考古 古语言学和古乐理论的重要手段之一 密码设计和密码分析是共生的 又是互逆的 两者密切有关但追求的目标相反 两者解决问题的途径有很大差别 密码设计是利用数学来构造密码密码分析除了依靠数学 工程背景 语言学等知识外 还要靠经验 统计 测试 眼力 直觉判断能力 有时还靠点运气 密码分析员的要求 除密钥外 掌握加解密算法能够搜索到密文信息可搜集到某些密文和明文的对应关系像合法用户一样发送加密信息可以截取 改变或重新发送信息 密码分析方法 分析法 确定性分析法利用一个或几个已知量 比如 已知密文或明文 密文对 用数学关系式表示出所求未知量 如密钥等 已知量和未知量的关系视加密和解密算法而定 寻求这种关系是确定性分析法的关键步骤 统计分析法利用明文的已知统计规律进行破译的方法 密码破译者对截收的密文进行统计分析 总结出其间的统计规律 并与明文的统计规律进行对照比较 从中提取出明文和密文之间的对应或变换信息 2 4 1密码分析学 密码可能经受的攻击 2 4 2密码分析方法 穷举破译法 对截收的密报依次用各种可解的密钥试译 直到得到有意义的明文 一般来说 要获取成功必须尝试所有可能密钥的一半 或在不变密钥下 对所有可能的明文加密直到得到与截获密报一致为止 此法又称为完全试凑法 Completetrial and errorMethod 只要有足够多的计算时间和存储容量 原则上穷举法总是可以成功的 但实际中 任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的 穷举举例 DES算法 注意 Internet的广泛应用 可以把全世界的计算机资源连成一体 形成巨大的计算能力 从而拥有巨大的密码破译能力 使原来认为安全的密码被破译 1994年 40多个国家的600多位科学家通过Internet 历时9个月破译了RSA 129密码 1999年又破译了RSA 140密码 2005年 RSA 200也被成功破译 1997年6月18日美国科罗拉多州以RockeVerser为首的工作小组宣布 通过利用Internet上的数万台微机 历时4个多月 通过穷举破译了DES 因此 在21世纪 只有经得起通过Internet进行全球攻击的密码 才是安全的密码 2 5经典密码学 经典密码 古典密码 对于今天来说 是极不安全的 是极易破解的 但其基本方法仍然是近 现代密码学的基础 经典密码运用的两种基本技术 代换法 将明文字母替换成其他字母 数字或符号置换法 明文的字母保持相同 但顺序被打乱 2 5 1代换密码 代换密码 替代密码 就是明文中的每一个字符被替换为密文中的另外一个字符 接收者对密文进行逆替换即可恢复出明文 在古典密码学中有三种类型的替代密码 单表替代密码多表替代密码多字母替代密码 1 Caesar密码 如果让每个字母等价于一个数值 a 0 b 1 z 25凯撒密码的密钥k 3 则 加密公式 C E P P 3 mod26解密公式 P D C C 3 mod26更一般地 加密 C E p p k mod26解密 P D C C k mod26 每个字母用其右边的第k个字母代替 k是密钥例如 明晨五点发动反攻明文 MINGCHENWUDIANFADONGFANGONG密文 PLQJFKHQZXGLDQIDGRQJIDQJRQJ 用穷举分析可轻松破解Caesar密码 通常 加密和解密算法是已知的 需测试的密钥只有25个 明文所用的语言是已知的 其意义易于识别 简单 脆弱不能抵抗明文统计特性的攻击 密钥穷举攻击 蛮力攻击 举例 例 在Caesar系统中 若收集到的密文c为IYBABZ 进行26次穷举搜索 即可找到明文m及密钥k 0IYBABZ1JZCBCA2KADCDB 19BRUTUS20CSVUVT 25HXAZAY 最后得到明文为BRUTUS 布鲁图 密钥k 19 即 加密 E m m 19 mod26解密 D c c 19 mod26 2 单表代换密码 单表替代密码 使用一个密文字母表 明文的每一个字符用相应的密文字符代替 而且密文所用的字符与一般的明文所用字符属同一语言系统 字母表 密码本 k 5 明文 abcdefghijklmnopqrstuvwxyz密文 FGHIJKLMNOPQRSTUVWXYZABCDEi 0123456789 25 例如 明文为 networksecurity则密文为 SJYBTWPXJHZWNYD 一般化的替代密码变换为 加密 E m m k modq解密 D c c k modqq 明文字母个数 明文空间记为 0 1 q 1 密钥空间为 1 q 1 单表代换密码 增加密钥空间 例如 明文a用c来代换 b用剩下的25个字母中随机的一个来代换 c用剩下的24个字母中随机的一个来代换 以此类推 这样 密钥空间为26 约4 1026种可能的密钥 例如 如下密码表 字母表 密码本 k 5 明文 abcdefghijklmnopqrstuvwxyz密文 CXDWIHJSKALYUEMNQOFPRTVZBG 例如 明文为 networksecurity则密文为 EIPVMOLFIDROKPB 破解单表代换密码 根据频率统计进行分析确定每个字母被映射到什么字母单个字母出现的可能是A或I一般来说3个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合还可以应用其它很少应用的字母 英文字母及其组合的使用频率 最常见的两字母组合 依照出现次数递减的顺序排列 TH HE IN ER AN RE DE ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF最常见的三字母组合 依照出现次数递减的顺序排列 THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH 单个英文字母使用频率 改变明文的语法模式和结构 抵抗频度分析 可采用多表 多字母代换密码Vigen re密码Playfair密码Hill密码采用相关的单表代换规则由密钥来决定给定变换的具体规则 3 最简单的多表代换密码 Vigen re 多表代换密码是以两个以上代换表依次对明文消息的字母进行代换的加密方法 维吉尼亚密码选择一个词组作为密钥 密钥中每个字母用来确定一个代换表 每个密钥字母用来加密一个明文字母 例如密钥字母为a 明文字母为c 则密文字母为 0 2 mod26 2 也就是c 直到所有的密钥字母用完 后再从头开始 使用第一个密钥字母加密 也就是说 密钥循环使用 一个例子 明文为attackbeginsatfive 密钥为cipher attackbeginsatfive明文 cipherciphercipher密钥 cbihgbdmvprjcbupzv密文去除空格后密文为cbihgbdmvprjcbupzv 加密 E mi mi ki mod26解密 D ci ci ki mod26 Vigenere方阵 Vigenere代换表 01234567891015202425 例如 明文为Iamateacher 密钥为 best 则密文为 MEETUISVIIK 破解维吉尼亚密码的一个途径 特点 算法公开 有相对复杂密钥相同的字母 将被加密成不同的密文 单字母频率被掩盖了如果密文足够长 其间会有大量重复的密文序列出现 通过计算重复密文序列间距的公因子 分析者可能猜出密钥词的长度 因为密钥词是重复使用的 4 多字母代换密码 多字母密码 ployalphabeticcipher 明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置 Playfair加密体制 将明文中的双字母组合作为一个单元对待 并将这些单元转换为密文的双字母组合 由英国科学家CharlesWheatstone于1854年发明 以其好友BaronPlayfair的名字命名 在第一次世界大战中 英军使用Playfair密码作为陆军的标准加密体制 在第二次世界大战中 盟军使用它作为通信加密工具 LordPeterWimsey给出的例子 Playfair算法基于使用一个5 5字母矩阵 该矩阵使用一个关键词构造 从左至右 从上至下填入该关键词的字母 去除重复字母 然后再以字母表顺序将余下的字母填入矩阵剩余空间 字母I和J被算作一个字母 属于相同对中的重复的明文字母将用一个填充字母进行分隔 因此 词balloon将被加密为balxloon 属于该矩阵相同行的明文字母将由其右边的字母替代 而行的最后一个字母由行的第一个字母代替 例如 ar被加密为RM 属于相同列的明文字母将由它下面的字母代替 而列的最后一个字母由列的第一个字母代替 例如 mu被加密为CM否则 明文的其他字母将由与其同行 且与下一个同列的字母代替 因此 hs成为BP ea成为IM 或JM 这可根据加密者的意愿而定 若明文奇数长度 在明文末尾附加无效字母 代换规则 Playfair密码举例 例 用给的的密钥 HARPSICHORD 加密 speciallity 1 明文speciallity specialqlity 用q进行分隔 2 加密specialqlity hsfichguebyp所以 speciallity hsfichguebyp Playfair密码的优点 Playfair密码与简单的单一字母替代法密码相比有了很大的进步虽然仅有26个字母 但有26 26 676种字母对 因此 识别字母对要比单个字母要困难得多一个明文字母有多种可能的代换密文字母 使得频率分析困难的多 hs成为BP hq成为YP 字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难由于这些原因 Playfair密码过去长期被认为是不可破的 5 一次一密 无法攻破的加密体制 一次一密乱码本 one timepad 由MajorJosephMauborgne和AT T公司的GilbertVernam在1917发明 一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集 这个密钥字母集被写在几张纸上 并被粘成一个乱码本 发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法 每个密钥仅对一个消息使用一次 发送者对所发送的消息加密 然后销毁乱码本中用过的一页或磁带部分 接收者有一个同样的乱码本 并依次使用乱码本上的每个密钥去解密密文的每个字符 接收者在解密消息后销毁乱码本中用过的一页或磁带部分 新的消息则用乱码本中新的密钥加密 一次一密的优点 面对一条待破译的密文 攻击者能够找到很多个与密文等长的密钥 使得破译出的明文符合语法结构的要求 因为密钥本身是随机的 是没有规律的 就算在这些可能的密钥中存在真正的密钥 攻击者也无法在这些可能的密钥中确定真正的密钥 因为密钥只是用一次 攻击者无法用其它密文来验证这个密钥 因此是无法攻破的 一次一密的缺点 一个一次一密加密系统 需要在某个规则基础上建立百万个随机字符 提供这样规模的真正随机字符集市相当艰巨的任务 对每一条消息 需要提供给发送发和接收方等长度的密钥 因此存在庞大的密钥分配问题 基于这些原因 一次一密在实际中极少应用 2 5 2置换技术 重排明文字母的位置来隐藏消息 在置换密码中 明文的字母保持相同 但顺序被打乱了 列置换密码 在简单的纵行换位密码中 明文以固定的宽度水平地写在一张图表纸上 密文按垂直方向读出 解密就是将密文按相同的宽度垂直地写在图表纸上 然后水平地读出明文 列置换密码举例 已知 明文 COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE列数d 10则如下排列明文 COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE按次序读各列 得到密文 CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX 这种简单的技巧对于密码分析者来说是微不足道的 可在置换前 把列的次序打乱 列的次序就是算法的密钥如果k 1 3 5 7 9 2 4 6 8 10 则密文为 CAELPMHLANUCWTIEMUTEGYAEOPSEEPIOSSTSBIVRATSRBTX 列置换密码举例 带关键字的列置换密码 可由关键字keyword说明列数和列顺序关键字的长度就是列数关键字的字母序就是列序例如 明文为 Usingaciphertwicemayimprovestrengthofthecipheroritmaynot keyword为 what 密文 iceiapeehhpomosahwmmvrttirtnnircyrsnoehratugpteiotgfceiy keyword what