计算机安全-密码学.ppt

计算机安全技术密码学,刘培顺,2019/7/14,Copyright Liu Peishun,2,计算机系统安全定义, 信息安全的五类服务,2019/7/14,Copyright Liu Peishun,3,需要掌握的知识,密码学基础知识 常见的密码算法 密码算法的应用模式,2019/7/14,Copyright Liu Peishun,4,内容提要,密码学的起源 密码学的发展和现状 基本的概念和术语,2019/7/14,Copyright Liu Peishun,5,1密码学的起源,信息的存储:在公开的地方 信息的交换:使用非隐秘介质 信息的传输:通过不安全信道,信息源,信息目的地,信息源,信息目的地,窃听,篡改,2019/7/14,Copyright Liu Peishun,6,1密码学的起源:密码技术的主要用途,数据保密数据加密/解密 数据加密（存储和传输） 认证技术 实体身份认证 数据源发认证 信息完整性保护 数据在传输过程中没有被插入、篡改、重发； 数字签名和抗抵赖（Non-repudiation ） 源发抗抵赖 交付抗抵赖,2019/7/14,Copyright Liu Peishun,7,2密码学发展阶段,1949年之前古典密码学 密码学是一门艺术 19491975年现代密码学 密码学成为科学 1976年以后 密码学的新方向公钥密码学,2019/7/14,Copyright Liu Peishun,8,密码的重要型,第一次世界大战进行到关键时刻，英国破译密码的专门机构“40号房间”利用缴获的德国密码本破译了著名的“齐默尔曼电报”，促使美国放弃中立参战，改变了战争进程。 第二次世界大战中，在破译德国著名的“恩格玛(Enigma)”密码机密码过程中，原本是以语言学家和人文学者为主的解码团队中加入了数学家和科学家。电脑之父亚伦图灵(Alan Mathison Turing)就是在这个时候加入了解码队伍，发明了一套更高明的解码方法。同时，这支优秀的队伍设计了人类的第一部电脑来协助破解工作。显然，越来越普及的计算机也是军工转民用产品。美国人破译了被称为“紫密”的日本“九七式”密码机密码。靠前者，德国的许多重大军事行动对盟军都不成为秘密；靠后者，美军炸死了偷袭珍珠港的元凶日本舰队总司令山本五十六。,2019/7/14,Copyright Liu Peishun,9,3 基本概念,密码学(Cryptology): 是研究信息系统安全保密的科学. 密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽. 密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.,2019/7/14,Copyright Liu Peishun,10,3 基本概念：基本术语,消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)，加密和解密要在密钥的控制下进行。 密码算法(Cryptography Algorithm):是用于加密和解密的数学函数。 密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm). 所传送消息的预定对象称为接收者(Receiver). 接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm).,2019/7/14,Copyright Liu Peishun,11,加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).,3 基本概念：加解密过程示意图,安全信道,2019/7/14,Copyright Liu Peishun,12,3 基本概念：加密通信的shannon模型,密码学的目的：实现消息源和消息宿在不安全的信道上进行通信，而系统分析者(破译者)不能理解他们通信的内容。,消息源,加密机,解密机,消息宿,安全信道,密钥源,系统分析者,x,y,x,k,不安全信道,2019/7/14,Copyright Liu Peishun,13,3 基本概念：密码体制,密码体制：它是一个五元组（M,C,K,E,D)满足条件： （1）M是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；(密钥空间) *（4）任意k K,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足dk(ek(x)=x, 这里 x P。,2019/7/14,Copyright Liu Peishun,14,3 基本概念：密码体制分类,古典密码算法和现代密码算法 按照算法是否公开 对称密钥密码和非对称密钥密码 加密和解密是否使用相同的密钥 分组密码和序列密码 每次操作的数据单元是否分块,2019/7/14,Copyright Liu Peishun,15,3 基本概念对称密码算法,对称密码算法（symmetric cipher)：又称传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。 优点 加密速度快，便于硬件实现和大规模生产 缺点 密钥分配：必须通过保密的信道 密钥个数：n(n-1)/2 无法用来签名和抗抵赖（没有第三方公证时）,2019/7/14,Copyright Liu Peishun,16,3 基本概念非对称密码算法,非对称密钥算法（asymmetric cipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-key cipher) 。 公开密钥算法用一个密钥进行加密, 而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥.解密密钥必须保密,又称私人密钥（private key)私钥.简称私钥。 优点： 密钥分配：不必保持信道的保密性 密钥个数：n pair 可以用来签名和抗抵赖 缺点 加密速度慢，不便于硬件实现和大规模生产,2019/7/14,Copyright Liu Peishun,17,3 基本概念分组密码和流密码,分组密码（block cipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码（stream cipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。 序列密码是手工和机械密码时代的主流,2019/7/14,Copyright Liu Peishun,18,3 基本概念密码算法分类,对称密钥密码又可分为： 分组密码 每次对一块数据加密，多数网络加密应用 DES,IDEA,RC6,Rijndael 流密码 每次对一位或一字节加密，A5(GSM移动通信)，RC-4,2019/7/14,Copyright Liu Peishun,19,3 基本概念密码算法分类,公开密钥密码: 大部分是分组密码 每次对一块数据加密,数字签名,身份认证 RSA,ECC,ElGamal,DSA 加密解密速度慢,2019/7/14,Copyright Liu Peishun,20,3 基本概念密码分析,在未知密钥的前提下，从密文恢复出明文、或者推导出密钥 对密码进行分析的尝试称为攻击 攻击方法分类（根据已知信息量的多少） 唯密文攻击 已知明文攻击 选择明文攻击 选择密文攻击 选择文本,2019/7/14,Copyright Liu Peishun,21,3 基本概念密码分析,1883年Kerchoffs第一次明确提出了编码的原则：算法的公开不影响明文和密钥的安全。 这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。,2019/7/14,Copyright Liu Peishun,22,3 基本概念密码算法的安全性,Lars Knudsen 把破译密码算法分为4种不同的类型 全部破译：密码分析者找出密钥K，从而可以解密密文 全盘推导：密码分析者找到一个代替算法A， 在不知道密钥K的情况下可以解密密文。 实例（局部）推导：密码分析者从截获的密文中找出明文。 信息推导：密码分析者获得一些有关密钥或明文的信息。 无条件保密：无论获得多少密文，都不能恢复明文 一次一密：密钥是一个随机序列，密钥只使用一次，密钥的长度等于明文序列的长度。 蛮力攻击：测试每一种可能的密钥,2019/7/14,Copyright Liu Peishun,23,3 基本概念密码算法的安全性,密码算法的安全性 如果破译算法的代价大于加密数据本身的价值，或者在信息的生命期内无法破解，那么你的算法可能是安全的。(实际保密性) 一个算法被称为是计算上安全的，如果一个算法用可得到的资源不能破解。 处理复杂性：计算量，CPU时间 数据复杂性：所需输入数据量 存储复杂性：计算所需的存储空间,2019/7/14,Copyright Liu Peishun,24,典型的算法复杂度分析,2019/7/14,Copyright Liu Peishun,25,4 古典密码,古典密码是密码学的渊泉，这些密码大都比较简单，可用手工或机械操作实现加解密。 古典密码的分类 换位 代替,Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。,2019/7/14,Copyright Liu Peishun,26,4 古典密码换位密码,根据一定的规则重新安排明文字母,使之成为密文. 列换位密码( Columnar transposition cipher),2019/7/14,Copyright Liu Peishun,27,4 古典密码换位密码,换位密码把明文按列写入,按行读出 密钥包含3方面信息: 行宽,列高,读出顺序 key: 4 3 1 2 5 6 7 plaintext: a t t a c k p o s t p o n e d u n t i l t w o a m x y z ciphertext: TTNA APTM TSUO AODW COIX PETZ 完全保留字符的统计信息 使用多轮加密可提高安全性,2019/7/14,Copyright Liu Peishun,28,4 古典密码换位密码,周期换位密码( Periodic permutation cipher),i=1,2,3,4 f(i)=3,4,2,1 M=c a n y o u n n d e r s t a n d C=NYAC UNUO RSED NDAT,2019/7/14,Copyright Liu Peishun,29,4古典密码替代密码,明文的字母由其它字母或数字或符号代替 若该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式 单表替换(Monalphabetic substitution) 同音替换(Homophonic substitution) 多表替换(Polyalphabetic substitution) 多字母组替换(Polygram substitution),2019/7/14,Copyright Liu Peishun,30,4 古典密码替代：单表代替,破译以下密文：,wuhdwb lpsrvvleoh,TREATY IMPOSSIBLE,Ci=E(Pi)=Pi+3,加密算法：,字母表：(密码本） ABCDEFGHIJKLMNOPQRSTUVWXYZ defghijklmnopqrstuvwxyzabc,凯撒密码,加解密算法已知 可能尝试的密钥只有6个 通过强力攻击得到明文： 很容易受到唯密文攻击。,2019/7/14,Copyright Liu Peishun,31,4 古典密码单表代替,使用密钥短语 “key” ABCDEFGHIJKLMNOPQRSTUVWXYZ keyabcdfghijlmnopqrstuvwxz “spectacular” ABCDEFGHIJKLMNOPQRSTUVWXYZ spectaulrbdfghijkmnoqvwxyz 泄露给破译者的信息更少,2019/7/14,Copyright Liu Peishun,32,4 古典密码单表代替,对字母进行无规则的重新排列 E(i)=3*i mod 26 ABCDEFGHIJKLMNOPQRSTUVWXYZ adgjmpsvybehknqtwzcfilorux,2019/7/14,Copyright Liu Peishun,33,4 古典密码单表代替,任意替换：26！4x1026 可能的key，大于56位DES的密钥空间。 基于语言统计规律仍可破译,2019/7/14,Copyright Liu Peishun,34,2019/7/14,Copyright Liu Peishun,35,例： UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ,2019/7/14,Copyright Liu Peishun,36,“完美”的替换密码,使用非重复的加密字母序列加密,会使至今能使用的任何密码分析工具失效。 一次性密钥（One Time Pad) 相同的PAD，发方与收方绝对同步； 打印、分发、保存与使用问题 长随机数序列（对OTP的近似实现） ri+1=ri*c+b mod w c和b为常数,w为计算机能表示的最大整数,2019/7/14,Copyright Liu Peishun,37,4 古典密码转轮密码机,转轮密码机是一种长周期的多表代替密码机,转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，4 轮ENIGMA在1944年装备德国海军. 被英国图灵破译。,英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,2019/7/14,Copyright Liu Peishun,38,古典密码总结,换位和代替是密码学中有效的加密方法。 破译威胁来自 频率分布 重合指数 考虑最可能的字母及可能出现的单词 重复结构分析及克思斯基方法 持久性、组织性、创造性和运气,2019/7/14,Copyright Liu Peishun,39,古典密码,古典密码 代替密码 (Substitution Cipher) 换位密码 (transposition Cipher) 代替密码与换位密码的组合 古典密码（受限密码）的缺陷 密码体制的安全性在于保持算法本身的保密性 受限算法的缺陷 不适合大规模生产 不适合较大的或者人员变动较大的组织 用户无法了解算法的安全性,2019/7/14,Copyright Liu Peishun,40,现代密码,现代密码算法 把算法和密钥分开 密码算法可以公开，密钥保密 密码系统的安全性在于保持密钥的保密性,发送方,接收方,m,m,加密 E,解密 D,c= Ek (m),m= Ek (c),密码分析者,密钥分配（秘密信道）,k,k,现代对称加密技术,DES算法,2019/7/14,Copyright Liu Peishun,42,5 现代对称加密技术,在实际应用中常用对称密钥密码算法 DES (Data Encryption Standard )及其各种变形 IDEA (International Data Encryption Algorithm) RC2, RC4, RC5,CAST-128,Blowfish AES(Advanced Encryption Standard),2019/7/14,Copyright Liu Peishun,43,5 现代对称加密技术:DES的产生,1973年5月15日, NBS开始公开征集标准加密算法,并公布了它的设计要求: (1)算法必须提供高度的安全性 (2)算法必须有详细的说明,并易于理解 (3)算法的安全性取决于密钥,不依赖于算法 (4)算法适用于所有用户 (5)算法适用于不同应用场合 (6)算法必须高效、经济 (7)算法必须能被证实有效 (8)算法必须是可出口的,2019/7/14,Copyright Liu Peishun,44,5 现代对称加密技术:DES的产生,发明人:IBM公司W. Tuchman 和 C. Meyer 1971-72年研制 产生：美国商业部的国家标准局NBS1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。 标准化：于1976年11月被美国政府采用，DES随后被美国国家标准局和美国国家标准协会(American National Standard Institute， ANSI) 承认。1977年1月以数据加密标准DES(Data Encryption Standard)的名称正式向社会公布。 于1977年7月15日生效。,2019/7/14,Copyright Liu Peishun,45,5 现代对称加密技术:DES的概述,DES是一种对称密钥算法，密钥长度为56bits (加上奇偶校验，通常写成64bits) 是一种分组加密算法，64 bits为一个分组 采用多次换位和代替相组合的处理方法，属于乘积密码。 基本思想： 混淆（Confusion） 和扩散（Diffusion ） 使用标准的算术和逻辑运算,2019/7/14,Copyright Liu Peishun,46,DES的描述,DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文,2019/7/14,Copyright Liu Peishun,47,2019/7/14,Copyright Liu Peishun,48,混淆(confusion)：使密文与明文的统计独立性关系复杂化。使得输出是输入的非线性函数；用于掩盖明文和密文间的关系。通过代替法实现，如S盒。 散布 (diffusion)：使每位明文尽可能影响多位密文。扩展输出对输入的相关性，尽量使密文的每一位受明文中多位影响。通过置换法实现，如P盒。 单独用一种方法，容易被攻破。 流密码只依赖于混淆；分组密码两者都用。,5 DES分析,2019/7/14,Copyright Liu Peishun,49,5 DES算法的脆弱性,DES的半公开性：S盒的原理至今保密，所以不能算作真正的公开加密算法。 1）函数构造与作用域： 加密强度取决于函数f的复杂度 (S、P)和f的执行次数。 64位固定分组，短组模式，易造成密文重复组块 有限的函数作用域 ASCII码 0127 子密钥只参与异或简单的运算，有可能损害变换精度。 2）迭代问题 无法证明迭代16次最好 迭代在有限的作用域中存在封闭性；迭代次数多不仅费时，还可能被一次简单的变换所代替。,2019/7/14,Copyright Liu Peishun,50,5 DES算法存在的问题与挑战,强力攻击：255次尝试 穷尽搜索 蛮力攻击 差分密码分析法：247次尝试 1991年提出，选择明文攻击。分析明文对的差值对密文对差值的影响。很有效。 线性密码分析法：243次尝试 1992年提出，已知明文攻击。寻找一个近似的线性表达式，通过选择充分多的明文密文对来破解密钥。对DES更有效。,2019/7/14,Copyright Liu Peishun,51,5 现代对称加密技术:DES的破译,数据加密标准,在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密，而且需要12个小时的破解才能得到结果。 1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。 1997年1月，用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天 ；1998年7月， “第2-2届DES挑战赛（DES Challenge II-2）” 把破解DES的时间缩短到了只需56个小时； “第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5小时 。,2019/7/14,Copyright Liu Peishun,52,5 现代对称加密技术:DES的破译,2019/7/14,Copyright Liu Peishun,53,5 现代对称加密技术:DES的破译,上表中攻击者配有如下计算机资源的攻击能力,2019/7/14,Copyright Liu Peishun,54,5 多重DES及IDEA,二重DES （二个密钥，长度112位） ： 加密：C=Ek2Ek1(P) 解密：P=Dk1Dk2(C) 要防止中途攻击 三重DES（二个密钥） 加密： C=Ek1Dk2 Ek1(P) 解密： P=Dk1Ek2 Dk1(C) IDEA加密算法 1992年，瑞士的Lai和Massey 128位密钥，8轮，快速，软硬件实现。,2019/7/14,Copyright Liu Peishun,55,5 高级加密标准(AES),NIST(国家标准技术研究所)1997年9月12日发出征集高级加密标准的通知 。1998年8月首次选出15