1、1计算机安全与保密信息安全原理与应用信息安全原理与应用袁静波袁静波东北大学秦皇岛分校东北大学秦皇岛分校2第第2章章 密码学基础密码学基础l密码学的发展历史密码学的发展历史l密码学的基本概念密码学的基本概念l密码系统的分类密码系统的分类l密码分析密码分析l经典密码学经典密码学 3加密技术概述加密技术概述l以以密码学密码学为理论基础,基本思想是伪装信息,使非为理论基础,基本思想是伪装信息,使非法接入者无法理解信息的真正含义法接入者无法理解信息的真正含义l一般应用于政治、经济、军事、外交、情报等重要一般应用于政治、经济、军事、外交、情报等重要部门,部门,2020世纪世纪8080年代后,得到广泛重视和
2、普及年代后,得到广泛重视和普及l信息安全中的数据安全主要采用现代加密技术对数信息安全中的数据安全主要采用现代加密技术对数据进行主动的安全保护据进行主动的安全保护l是保护大型网络传输信息安全的重要实现手段是保护大型网络传输信息安全的重要实现手段l是信息安全保障的基础工具,是信息安全保障的基础工具,解决信息安全问题的解决信息安全问题的根本基础是密码学;根本基础是密码学;l密码学实质密码学实质属于数学范畴,利用数学代数知识探讨属于数学范畴,利用数学代数知识探讨信息的隐藏与恢复机制,是研究如何保护信息安全信息的隐藏与恢复机制,是研究如何保护信息安全的一门学科;的一门学科;4密码学的作用和地位密码学的作
3、用和地位已成为一门综合性的尖端技术科学已成为一门综合性的尖端技术科学 u维持机密性维持机密性u用于鉴别用于鉴别u保证完整性保证完整性u用于抗抵赖用于抗抵赖52.1 密码学的发展历史密码学的发展历史l 自人类社会出现战争便产生了密码自人类社会出现战争便产生了密码l 公元前公元前19001900年,古埃及石碑记载年,古埃及石碑记载PhaistosPhaistos圆盘,一种直径约为圆盘,一种直径约为160mm160mm的的Cretan-MnoanCretan-Mnoan粘土圆盘,始于公元前粘土圆盘,始于公元前1717世纪。表面有明显字间空格的字母,世纪。表面有明显字间空格的字母,至今还没有破解。至今
4、还没有破解。l 公元前公元前1 1世纪,世纪,Julius Caesar Julius Caesar发明了凯撒密码发明了凯撒密码6密码学的发展历史密码学的发展历史l 1834年,伦敦大学的实验物理学教授惠斯顿发明了年,伦敦大学的实验物理学教授惠斯顿发明了电机,这是通信向机械化、电气化跃进的开始,也电机,这是通信向机械化、电气化跃进的开始,也为密码通信采用在线加密技术提供了前提条件。为密码通信采用在线加密技术提供了前提条件。l 1920年,美国电报电话公司的弗纳姆发明了弗纳姆年,美国电报电话公司的弗纳姆发明了弗纳姆密码。其原理是利用电传打字机的五单位码与密钥密码。其原理是利用电传打字机的五单位码
5、与密钥字母进行模字母进行模2相加。相加。7密码学的发展历史密码学的发展历史l 两次世界大战大大促进了密码学的发展。两次世界大战大大促进了密码学的发展。二战中美国陆军和海军使用的条形密二战中美国陆军和海军使用的条形密码设备码设备M-138-T4。根据。根据1914年年Parker Hitt的提议而设计。的提议而设计。25个可选取的纸条个可选取的纸条按照预先编排的顺序编号和使用,主按照预先编排的顺序编号和使用,主要用于低级的军事通信。要用于低级的军事通信。Kryha密码机大约在密码机大约在1926年由年由Alexander vo Kryha发明。这发明。这是一个多表加密设备,密钥长是一个多表加密设
6、备,密钥长度为度为442,周期固定。一个由数,周期固定。一个由数量不等的齿的轮子引导密文轮量不等的齿的轮子引导密文轮不规则运动。不规则运动。8密码学的发展历史密码学的发展历史l 两次世界大战大大促进了密码学的发展。两次世界大战大大促进了密码学的发展。转轮密码机转轮密码机ENIGMA,由,由Arthur Scherbius于于1919年发明,面板年发明,面板前有灯泡和插接板;前有灯泡和插接板;4轮轮ENIGMA在在1942年装备德国海军,年装备德国海军,英国从英国从1942年年2月到月到12月都没能月都没能解读德国潜艇的信号。解读德国潜艇的信号。英国的英国的TYPEX打字密码机,是德国打字密码机
7、,是德国3轮轮ENIGMA的改进型密码机。它在英的改进型密码机。它在英国通信中使用广泛,且在破译密钥后国通信中使用广泛,且在破译密钥后帮助破解德国信号。帮助破解德国信号。9密码学的发展历史密码学的发展历史l 1949年香农发表了一篇题为保密系统的通信理论年香农发表了一篇题为保密系统的通信理论的著名论文,该文首先将信息论引入了密码,从而的著名论文,该文首先将信息论引入了密码,从而把已有数千年历史的密码学推向了科学的轨道,奠把已有数千年历史的密码学推向了科学的轨道,奠定了密码学的理论基础。定了密码学的理论基础。l 1976年,美国密码学家年,美国密码学家W.Diffie和和M.Hellman在一在
8、一篇题为密码学的新方向一文中提出了一个崭新篇题为密码学的新方向一文中提出了一个崭新的思想,不仅加密算法本身可以公开,甚至加密用的思想,不仅加密算法本身可以公开,甚至加密用的密钥也可以公开。的密钥也可以公开。l 1977年美国国家标准局颁布了数据加密标准年美国国家标准局颁布了数据加密标准DES l 2019年年11月月26日,正式颁布日,正式颁布AES为美国国家标准。为美国国家标准。10密码学的发展密码学的发展手工密码手工密码机械密码机械密码电子电路密码电子电路密码计算机密码计算机密码物理、生物密码物理、生物密码112.2 密码学的基本概念密码学的基本概念l 密码学密码学(Cryptology)
9、(Cryptology):研究信息系统安全保密的研究信息系统安全保密的科学。它包含两个分支:科学。它包含两个分支:密码编码学密码编码学(Cryptography)(Cryptography),对信息进行编码,对信息进行编码实现隐蔽信息的一门学问实现隐蔽信息的一门学问密码分析学密码分析学(Cryptanalytics)(Cryptanalytics),研究分析破译,研究分析破译密码的学问。密码的学问。l二者相互独立,又相互依存,在矛盾与斗争中发二者相互独立,又相互依存,在矛盾与斗争中发展,对立统一。展,对立统一。12明文明文(消息消息)(Plaintext)(Plaintext):被隐蔽消息。被
10、隐蔽消息。密文密文(CiphertextCiphertext)或密报或密报(Cryptogram)(Cryptogram):明文经密明文经密码变换成的一种隐蔽形式。码变换成的一种隐蔽形式。加密加密(Encryption)(Encryption):将明文变换为密文的过程。将明文变换为密文的过程。解密解密(Decryption)(Decryption):加密的逆过程,即由密文恢复加密的逆过程,即由密文恢复出原明文的过程。出原明文的过程。加密算法加密算法(Encryption algorithm)(Encryption algorithm):密码员对明文:密码员对明文进行加密时所采用的一组规则。进行
11、加密时所采用的一组规则。解密算法解密算法(Decryption algorithm)(Decryption algorithm):接收者对密文:接收者对密文进行解密时所采用的一组规则。进行解密时所采用的一组规则。密钥密钥(Key)(Key):控制加密和解密算法操作的数据处理,控制加密和解密算法操作的数据处理,分别称作加密密钥和解密密钥。分别称作加密密钥和解密密钥。密码学的基本概念密码学的基本概念13密码学的基本概念密码学的基本概念l 加密员或密码员加密员或密码员(Cryptographer):对明文进行加:对明文进行加密操作的人员。密操作的人员。l 接收者接收者(Receiver):传送消息的
12、预定对象。:传送消息的预定对象。l 截收者截收者(Eavesdropper):在信息传输和处理系统中:在信息传输和处理系统中的非受权者,通过搭线窃听、电磁窃听、声音窃听的非受权者,通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。等来窃取机密信息。l 密码分析密码分析(Cryptanalysis):截收者试图通过分析从:截收者试图通过分析从截获的密文推断出原来的明文或密钥。截获的密文推断出原来的明文或密钥。l 密码分析员密码分析员(Cryptanalyst):从事密码分析的人员。:从事密码分析的人员。14Key Key 密钥密钥l在计算机上实现的数据加密算法,其加密或解密变在计算机上实现的数据
13、加密算法,其加密或解密变换是由一个换是由一个密钥密钥来控制的。来控制的。l密钥密钥keykey是由使用密码体制的用户随机选取的,密钥是由使用密码体制的用户随机选取的,密钥成为唯一能控制明文与密文之间变换的关键,它通常成为唯一能控制明文与密文之间变换的关键,它通常是由一串随机字符串组成。是由一串随机字符串组成。lKerckhoffss law柯克霍夫定律:柯克霍夫定律:只要加密算法使只要加密算法使用的密钥保持安全的,数据就是安全的、绝不能寄希用的密钥保持安全的,数据就是安全的、绝不能寄希望于敌人不知道怎样解密你的数据。望于敌人不知道怎样解密你的数据。l数据安全基于密钥而不是算法的保密。数据安全基
14、于密钥而不是算法的保密。也就是说,也就是说,对于一个密码体制,其对于一个密码体制,其算法是可以公开的算法是可以公开的,让所有人,让所有人来使用、研究。但具体对于某次加密过程中所使用的来使用、研究。但具体对于某次加密过程中所使用的密钥,则是保密的。密钥,则是保密的。15加密手段加密手段硬件加密硬件加密速度快速度快安全性高安全性高自带加密模块、通信链路专用加密盒、计自带加密模块、通信链路专用加密盒、计算机板卡算机板卡成本高成本高软件加密软件加密灵活性灵活性可移植性可移植性成本低成本低速度慢速度慢16l 密码体制基本组成密码体制基本组成:密码系统密码系统指为实现信息隐藏所采用的基本工作指为实现信息隐
15、藏所采用的基本工作方式。方式。一个密码系统,通常简称为密码体制一个密码系统,通常简称为密码体制 它是一个五元组(它是一个五元组(M,C,K,E,D):M,C,K,E,D):明文空间明文空间M M全体明文的集合全体明文的集合密文空间密文空间C C密钥空间密钥空间K K加密算法加密算法E E解密算法解密算法D D2.3 密码系统的分类密码系统的分类17CMKdDw 解密解密:M=D(C,Kd)设:设:M-M-明文;明文;C-C-密文;密文;Ke-Ke-加密密钥;加密密钥;Kd-Kd-解密密钥解密密钥 E-E-加密算法;加密算法;D-D-解密算法解密算法w 加密加密:C=E(M,Ke)MCEKe密码
16、系统的数学模型密码系统的数学模型18信息加密传输的过程信息加密传输的过程用户用户A用户用户B窃听者或窃听者或攻击者攻击者C19密码系统的分类密码系统的分类l 根据密钥的使用方式分类根据密钥的使用方式分类 对称密码体制(秘密钥密码体制)对称密码体制(秘密钥密码体制)u用于加密数据的密钥和用于解密数据的密钥相用于加密数据的密钥和用于解密数据的密钥相同,或者二者之间存在着某种明确的数学关系。同,或者二者之间存在着某种明确的数学关系。u加密:加密:E EK K(M)=C(M)=Cu解密:解密:D DK K(C)=M(C)=M 非对称密码体制(公钥密码体制)非对称密码体制(公钥密码体制)u用于加密的密钥
17、与用于解密的密钥是不同的,用于加密的密钥与用于解密的密钥是不同的,而且从加密的密钥无法推导出解密的密钥。而且从加密的密钥无法推导出解密的密钥。u用公钥用公钥KPKP对明文加密可表示为:对明文加密可表示为:E EKPKP(M)=C(M)=Cu用相应的私钥用相应的私钥KSKS对密文解密可表示为:对密文解密可表示为:D DKSKS(C)=M(C)=M20密码系统的分类密码系统的分类l 根据明文和密文的处理方式分类根据明文和密文的处理方式分类 分组密码体制(分组密码体制(Block CipherBlock Cipher)u设设M M为明文,分组密码将为明文,分组密码将M M划分为一系列明文块划分为一系
18、列明文块M Mi i,通,通常每块包含若干字符,并且对每一块常每块包含若干字符,并且对每一块M Mi i都用同一个密都用同一个密钥钥K Ke e进行加密。进行加密。uM=(MM=(M1 1,M,M2 2,M,Mn n),C=(CC=(C1 1,C,C2 2,C,Cn n,),),其中,其中C Ci i=E(M=E(Mi i,K,Ke e),i=1,2,ni=1,2,n。序列密码体制(序列密码体制(Stream CipherStream Cipher)u将明文和密钥都划分为位将明文和密钥都划分为位(bit)(bit)或字符的序列,并且对或字符的序列,并且对明文序列中的每一位或字符都用密钥序列中对
19、应的分明文序列中的每一位或字符都用密钥序列中对应的分量来加密。量来加密。uM=(MM=(M1 1,M,M2 2,M,Mn n),K Ke e=(k=(ke1e1,k,ke2e2,k,kenen),C=(CC=(C1 1,C C2 2,C,Cn n),其中,其中C Ci i=E(m=E(mi i,k,keiei),i=1,2,ni=1,2,n。21密码系统的分类密码系统的分类l 根据加密算法是否变化分类根据加密算法是否变化分类 设设E E为加密算法,为加密算法,K K0 0,K,K1 1,K,Kn n,为密钥,为密钥,M M0 0,M,M1 1,M,Mn n为明文,为明文,C C为密文为密文 固
20、定算法密码体制固定算法密码体制 uC C0 0=E(M=E(M0 0,K,K0 0),C),C1 1=E(M=E(M1 1,K,K1 1),.,C),.,Cn n=E(M=E(Mn n,K,Kn n)变化算法密码体制变化算法密码体制 uC C0 0=E=E1 1(M(M0 0,K,K0 0),C),C1 1=E=E2 2(M(M1 1,K,K1 1),.,C),.,Cn n=E=En n (M(Mn n,K,Kn n)22密码系统的评价密码系统的评价l保密强度保密强度u保密强度大的系统,开销往往较大保密强度大的系统,开销往往较大l密钥的长度密钥的长度u密钥的长度要适中,要经常变化密钥的长度要适
21、中,要经常变化l算法的复杂度算法的复杂度u复杂度要有限度复杂度要有限度l加密后信息长度的增加程度加密后信息长度的增加程度u信息长度的增加将导致通信效率的降低信息长度的增加将导致通信效率的降低23密码体制的安全性密码体制的安全性l 如果不论截取者获得了多少密文,但在密文中都没如果不论截取者获得了多少密文,但在密文中都没有足够的信息来唯一地确定出对应的明文,则这一有足够的信息来唯一地确定出对应的明文,则这一密码体制称为密码体制称为无条件安全的无条件安全的,或称为,或称为理论上是不可理论上是不可破的。破的。l 如果密码体制中的密码如果密码体制中的密码不能被可使用的计算资源破不能被可使用的计算资源破译
22、译,则这一密码体制称为在,则这一密码体制称为在计算上是安全的计算上是安全的,即加,即加密算法应该满足下列条件之一密算法应该满足下列条件之一:破译密码的代价超出密文信息的价值破译密码的代价超出密文信息的价值 破译密码的时间超出密文信息的有效生命期破译密码的时间超出密文信息的有效生命期242.4 密码分析密码分析l 截收者在不知道解密密钥及通信者所采用的加密体制截收者在不知道解密密钥及通信者所采用的加密体制细节条件下,对密文进行分析,试图获取机密信息细节条件下,对密文进行分析,试图获取机密信息l 密码分析在外交、军事、公安、商业等方面都具有重密码分析在外交、军事、公安、商业等方面都具有重要作用,也
23、是研究历史、考古、古语言学和古乐理论要作用,也是研究历史、考古、古语言学和古乐理论的重要手段之一。的重要手段之一。l 密码设计和密码分析是共生的、又是互逆的,两者密密码设计和密码分析是共生的、又是互逆的,两者密切有关但追求的目标相反。两者解决问题的途径有很切有关但追求的目标相反。两者解决问题的途径有很大差别:大差别:密码设计是利用数学来构造密码密码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学等知识密码分析除了依靠数学、工程背景、语言学等知识外,还要靠经验、统计、测试、眼力、直觉判断能外,还要靠经验、统计、测试、眼力、直觉判断能力力,有时还靠点运气。,有时还靠点运气。25密码
24、分析员的要求密码分析员的要求除密钥外,掌握加解密算法除密钥外,掌握加解密算法能够搜索到密文信息能够搜索到密文信息可搜集到某些密文和明文的对应关系可搜集到某些密文和明文的对应关系像合法用户一样发送加密信息像合法用户一样发送加密信息可以截取、改变或重新发送信息可以截取、改变或重新发送信息26密码分析方法密码分析方法分析法分析法 确定性分析法确定性分析法 利用一个或几个已知量利用一个或几个已知量(比如,已知密文或明文比如,已知密文或明文-密文对密文对)用数学关系式表示出所求未知量用数学关系式表示出所求未知量(如密钥如密钥等等)。已知量和未知量的关系视加密和解密算法而。已知量和未知量的关系视加密和解密
25、算法而定,寻求这种关系是确定性分析法的关键步骤。定,寻求这种关系是确定性分析法的关键步骤。统计分析法统计分析法 利用明文的已知统计规律进行破译的方法。密利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析,总结出其间码破译者对截收的密文进行统计分析,总结出其间的统计规律,并与明文的统计规律进行对照比较,的统计规律,并与明文的统计规律进行对照比较,从中提取出明文和密文之间的对应或变换信息。从中提取出明文和密文之间的对应或变换信息。27 2.4.1 密码分析学密码分析学攻击类型攻击类型攻击者拥有的资源攻击者拥有的资源惟密文攻击惟密文攻击加密算法加密算法截获的部分密文截获的部分密
26、文已知明文攻已知明文攻击击加密算法,加密算法,截获的部分密文和相应的明文截获的部分密文和相应的明文选择明文攻选择明文攻击击加密算法加密算法加密黑盒子,可加密任意明文得到相应的密加密黑盒子,可加密任意明文得到相应的密文文选择密文攻选择密文攻击击加密算法加密算法解密黑盒子,可解密任意密文得到相应的明解密黑盒子,可解密任意密文得到相应的明文文密码可能经受的攻击密码可能经受的攻击282.4.2 密码分析方法穷举破译法密码分析方法穷举破译法 对截收的密报依次用各种可解的密钥试译,直对截收的密报依次用各种可解的密钥试译,直到得到有意义的明文;一般来说,要获取成功必须到得到有意义的明文;一般来说,要获取成功
27、必须尝试所有可能密钥的一半。尝试所有可能密钥的一半。或在不变密钥下,对所有可能的明文加密直到或在不变密钥下,对所有可能的明文加密直到得到与截获密报一致为止,此法又称为完全试凑法得到与截获密报一致为止,此法又称为完全试凑法(Complete trial-and-error Method)(Complete trial-and-error Method)。只要有足够多的计算时间和存储容量,原则上只要有足够多的计算时间和存储容量,原则上穷举法总是可以成功的。但实际中,任何一种能保穷举法总是可以成功的。但实际中,任何一种能保障安全要求的实用密码都会设计得使这一方法在实障安全要求的实用密码都会设计得使这
28、一方法在实际上是不可行的。际上是不可行的。29穷举举例穷举举例DES算法算法30注意注意 l InternetInternet的广泛应用,可以把全世界的计算机资源的广泛应用,可以把全世界的计算机资源连成一体,形成巨大的计算能力,从而拥有巨大的连成一体,形成巨大的计算能力,从而拥有巨大的密码破译能力,使原来认为安全的密码被破译。密码破译能力,使原来认为安全的密码被破译。l 19941994年,年,4040多个国家的多个国家的600600多位科学家通过多位科学家通过InternetInternet,历时,历时9 9个月破译了个月破译了RSA-129RSA-129密码,密码,20192019年年又破
29、译了又破译了RSA-140RSA-140密码,密码,20192019年,年,RSA-200RSA-200也被成也被成功破译。功破译。l 20192019年年6 6月月1818日美国科罗拉多州以日美国科罗拉多州以Rocke VerserRocke Verser为为首的工作小组宣布,通过利用首的工作小组宣布,通过利用InternetInternet上的数万台上的数万台微机,历时微机,历时4 4个多月,通过穷举破译了个多月,通过穷举破译了DESDES。因此,。因此,在在2121世纪,只有经得起通过世纪,只有经得起通过InternetInternet进行全球攻击进行全球攻击的密码,才是安全的密码。的密
30、码,才是安全的密码。312.5 经典密码学经典密码学 l 经典密码(古典密码)对于今天来说,是极不安经典密码(古典密码)对于今天来说,是极不安全的,是极易破解的,但其基本方法仍然是近、全的,是极易破解的,但其基本方法仍然是近、现代密码学的基础。现代密码学的基础。l 经典密码运用的两种基本技术:经典密码运用的两种基本技术:代换法:将明文字母替换成其他字母、数字代换法:将明文字母替换成其他字母、数字或符号或符号 置换法:明文的字母保持相同,但顺序被打置换法:明文的字母保持相同,但顺序被打乱乱 322.5.1 2.5.1 代换代换密码密码l 代换代换密码密码(替代密码)就是明文中的每一个字符被替代密
31、码)就是明文中的每一个字符被替换为密文中的另外一个字符。替换为密文中的另外一个字符。l 接收者对密文进行逆替换即可恢复出明文。接收者对密文进行逆替换即可恢复出明文。l 在古典密码学中有三种类型的替代密码:在古典密码学中有三种类型的替代密码:单表替代密码单表替代密码 多表替代密码多表替代密码 多字母替代密码多字母替代密码331.Caesar密码密码l 如果让每个字母等价于一个数值:如果让每个字母等价于一个数值:a=0,b=1,z=25a=0,b=1,z=25l 凯撒密码的密钥凯撒密码的密钥k=3k=3,则:,则:加密公式:加密公式:C=E(P)=(P+3)mod 26C=E(P)=(P+3)mo
32、d 26 解密公式:解密公式:P=D(C)=(C-3)mod 26P=D(C)=(C-3)mod 26l 更一般地:更一般地:加密:加密:C=E(p)=(p+k)mod 26C=E(p)=(p+k)mod 26 解密:解密:P=D(C)=(C-k)mod 26P=D(C)=(C-k)mod 26l每个字母用其右边的第每个字母用其右边的第k k个字母代替,个字母代替,k k是密钥是密钥l例如:例如:明晨五点发动反攻明晨五点发动反攻 明文:明文:MING CHEN WU DIAN FA DONG FAN GONGMING CHEN WU DIAN FA DONG FAN GONG 密文:密文:PL
33、QJ FKHQ ZX GLDQ ID GRQJ IDQ JRQJPLQJ FKHQ ZX GLDQ ID GRQJ IDQ JRQJ34用穷举分析可轻松破解用穷举分析可轻松破解Caesar密码密码l 通常,加密和解密算法是已知的。通常,加密和解密算法是已知的。l 需测试的密钥只有需测试的密钥只有2525个。个。l 明文所用的语言是已知的,其意义易于识别。明文所用的语言是已知的,其意义易于识别。l 简单,脆弱简单,脆弱l 不能抵抗明文统计特性的攻击不能抵抗明文统计特性的攻击35密钥穷举攻击密钥穷举攻击(蛮力攻击蛮力攻击)举例举例例:在例:在Caesar系统中,若收集到的密文系统中,若收集到的密文
34、c为为IYBABZ,进行进行26次穷举搜索,即可找到明文次穷举搜索,即可找到明文m及密钥及密钥k0 IYBABZ 1 JZCBCA 2 KADCDB .19 BRUTUS 20 CSVUVT.25 HXAZAY最后得到明文为最后得到明文为BRUTUS(布鲁图(布鲁图),密钥),密钥k19。即:即:加密:加密:E(m)=(m+19)mod 26 解密:解密:D(c)=(c19)mod 26362.单表代换密码单表代换密码l 单表替代密码单表替代密码:使用一个密文字母表,使用一个密文字母表,明文的每一个字符用明文的每一个字符用相应的密文字符代替。而且相应的密文字符代替。而且密文所用的字符与一般的明
35、文所密文所用的字符与一般的明文所用字符属同一语言系统。用字符属同一语言系统。字母表(密码本)(字母表(密码本)(k=5k=5)明文:明文:a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p q r s t u v w x y z 密文:密文:F G H I J K L M N O P Q R S T U V W X Y Z A B C D EF G H I J K L M N O P Q R S T U V W X Y Z A B C D E i i:0 1 2 3 4 5 6
36、7 8 9 .250 1 2 3 4 5 6 7 8 9 .25例如,明文为:例如,明文为:network securitynetwork security 则密文为:则密文为:SJYBTWP XJHZWNYDSJYBTWP XJHZWNYDl一般化的替代密码变换为:一般化的替代密码变换为:加密:加密:E(m)=(m+k)mod q 解密:解密:D(c)=(ck)mod q q明文字母个数,明文空间记为明文字母个数,明文空间记为0,1,q-1 密钥空间为密钥空间为1,q-137单表代换密码单表代换密码l 增加密钥空间:例如,明文增加密钥空间:例如,明文a用用c来代换,来代换,b用剩下用剩下的的
37、25个字母中随机的一个来代换,个字母中随机的一个来代换,c用剩下的用剩下的24个个字母中随机的一个来代换,字母中随机的一个来代换,以此类推。这样,以此类推。这样,密钥空间为密钥空间为26!,约!,约4*1026种可能的密钥。种可能的密钥。例如,如下密码表:例如,如下密码表:字母表(密码本)(字母表(密码本)(k=5k=5)明文:明文:a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p q r s t u v w x y z 密文:密文:C X D W I H J S K A L
38、Y U E M N Q O F P R T V Z B GC X D W I H J S K A L Y U E M N Q O F P R T V Z B G例如,明文为:例如,明文为:network securitynetwork security 则密文为:则密文为:EIPVMOL FIDROKPBEIPVMOL FIDROKPB38破解单表代换密码破解单表代换密码l 根据频率统计进行分析根据频率统计进行分析l 确定每个字母被映射到什么字母确定每个字母被映射到什么字母l 单个字母出现的可能是单个字母出现的可能是A A或或I Il 一般来说一般来说3 3个字母出现的可能是个字母出现的可能是
39、THETHE或或ANDANDl 还可以用其他通常出现的双字母或三字母组合还可以用其他通常出现的双字母或三字母组合l 还可以应用其它很少应用的字母还可以应用其它很少应用的字母39英文字母及其组合的使用频率英文字母及其组合的使用频率l 最常见的两字母组合,依照出现次数递减的顺序排最常见的两字母组合,依照出现次数递减的顺序排列:列:THTH、HEHE、ININ、ERER、ANAN、RERE、DEDE、ONON、ESES、STST、ENEN、ATAT、TOTO、NTNT、HAHA、NDND、OUOU、EAEA、NGNG、ASAS、OROR、TITI、ISIS、ETET、ITIT、ARAR、TETE、S
40、ESE、HIHI、OFOFl 最常见的三字母组合,依照出现次数递减的顺序排最常见的三字母组合,依照出现次数递减的顺序排列:列:THETHE、INGING、ANDAND、HERHER、EREERE、ENTENT、THATHA、NTHNTH、WASWAS、ETHETH、FORFOR、DTHDTHl单个英文字母使用频率单个英文字母使用频率40改变明文的语法模式和结构改变明文的语法模式和结构-抵抗频度分析抵抗频度分析l 可采用多表可采用多表/多字母代换密码多字母代换密码 VigenreVigenre密码密码 PlayfairPlayfair密码密码 HillHill密码密码l 采用相关的单表代换规则采
41、用相关的单表代换规则l 由密钥来决定给定变换的具体规则由密钥来决定给定变换的具体规则413.最简单的多表代换密码最简单的多表代换密码-Vigenre l 多表代换密码多表代换密码是以两个以上代换表依次对明文消息是以两个以上代换表依次对明文消息的字母进行代换的加密方法。的字母进行代换的加密方法。l 维吉尼亚密码维吉尼亚密码选择一个词组作为密钥,密钥中每个选择一个词组作为密钥,密钥中每个字母用来确定一个代换表,每个密钥字母用来加密字母用来确定一个代换表,每个密钥字母用来加密一个明文字母。一个明文字母。l 例如密钥字母为例如密钥字母为a,明文字母为,明文字母为c,则密文字母为,则密文字母为(0+2)
42、(mod 26)=2,也就是,也就是c。l 直到所有的密钥字母用完,后再从头开始,使用第直到所有的密钥字母用完,后再从头开始,使用第一个密钥字母加密。也就是说,密钥循环使用。一个密钥字母加密。也就是说,密钥循环使用。42一个例子一个例子l 明文为明文为attack begins at five,密钥为密钥为cipher,attack begins at five 明文明文 cipher cipher ci pher 密钥密钥 -cbihgb dmvprj cb upzv 密文密文去除空格后密文为去除空格后密文为cbihgbdmvprjcbupzv加密:加密:E(mi)=(mi+ki)mod 2
43、6解密:解密:D(ci)=(ciki)mod 2643Vigenere方阵方阵Vigenere 代换表代换表a b c d e f g h i j k l m n o p q r s t u v w x y zaA B C D E F G H IJ K L M N O P Q R S T U V W X Y ZbB C D E F G H IJ K L M N O P Q R S T U V W X Y Z AeE F G H IJ K L M N O P Q R S T U V W X Y Z A B C DsS T U V W X Y Z A B C D E F G HIJ K L M N
44、 O P Q RtT U V W X Y Z A B C D E F G H IJ K L M N O P Q R SzZ A B C D E F G H IJ K L M N O P Q R S T U V W X Y0 1 2 3 4 5 6 7 8 9 10 15 20 24 25例如,明文为例如,明文为I am a teacherI am a teacher,密钥为,密钥为“best”“best”,则密文为:则密文为:MEETUISVIIKMEETUISVIIK44破解维吉尼亚密码的一个途径破解维吉尼亚密码的一个途径l 特点特点:算法公开,有相对复杂密钥算法公开,有相对复杂密钥 相同的
45、字母,将被加密成不同的密文,单字母频相同的字母,将被加密成不同的密文,单字母频率被掩盖了率被掩盖了l 如果密文足够长,其间会有大量重复的密文序列出如果密文足够长,其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子,分析者现。通过计算重复密文序列间距的公因子,分析者可能猜出密钥词的长度(可能猜出密钥词的长度(因为密钥词是重复使用因为密钥词是重复使用的的)。454.多字母代换密码多字母代换密码l 多字母密码(多字母密码(ployalphabetic cipher)ployalphabetic cipher):明文中的:明文中的字符映射到密文空间的字符还依赖于它在上下文中字符映射到密文
46、空间的字符还依赖于它在上下文中的位置。的位置。l PlayfairPlayfair加密体制加密体制:将明文中的双字母组合作为一将明文中的双字母组合作为一个单元对待,并将这些单元转换为密文的双字母组个单元对待,并将这些单元转换为密文的双字母组合。合。l 由英国科学家由英国科学家Charles WheatstoneCharles Wheatstone于于18541854年发明,年发明,以其好友以其好友Baron PlayfairBaron Playfair的名字命名。的名字命名。l 在第一次世界大战中,英军使用在第一次世界大战中,英军使用PlayfairPlayfair密码作为密码作为陆军的标准加
47、密体制。陆军的标准加密体制。l 在第二次世界大战中,盟军使用它作为通信加密工在第二次世界大战中,盟军使用它作为通信加密工具。具。46Lord Peter Wimsey给出的例子给出的例子l PlayfairPlayfair算法基于使用一个算法基于使用一个5 55 5字母矩阵,该矩阵使用字母矩阵,该矩阵使用一个关键词构造。从左至右、一个关键词构造。从左至右、从上至下填入该关键词的字从上至下填入该关键词的字母(去除重复字母),然后母(去除重复字母),然后再以字母表顺序将余下的字再以字母表顺序将余下的字母填入矩阵剩余空间。字母母填入矩阵剩余空间。字母I I和和J J 被算作一个字母。被算作一个字母。
48、MONARCHYBDEFGI/J KLPQSTUVWXZ47l 属于相同对中的属于相同对中的重复的明文字母重复的明文字母将用一个填充字母进行分隔,将用一个填充字母进行分隔,因此,词因此,词balloonballoon将被加密为将被加密为ba lx lo onba lx lo on。l 属于该矩阵属于该矩阵相同行相同行的明文字母将由其右边的字母替代,而行的明文字母将由其右边的字母替代,而行的最后一个字母由行的第一个字母代替。例如,的最后一个字母由行的第一个字母代替。例如,arar被加密为被加密为RMRM。l 属于属于相同列相同列的明文字母将由它下面的字母代替,而列的最后的明文字母将由它下面的字母
49、代替,而列的最后一个字母由列的第一个字母代替。例如,一个字母由列的第一个字母代替。例如,mumu被加密为被加密为CMCMl 否则否则,明文的其他字母将由与其同行,且与下一个同列的字,明文的其他字母将由与其同行,且与下一个同列的字母代替。因此,母代替。因此,hshs成为成为BPBP,eaea成为成为IMIM(或(或JMJM,这可根据加密,这可根据加密者的意愿而定)。者的意愿而定)。l 若明文奇数长度,若明文奇数长度,在明文末尾附加无效字母在明文末尾附加无效字母 代换规则代换规则48Playfair密码举例密码举例例:用给的的密钥例:用给的的密钥“HARPSICHORD“HARPSICHORD加密
50、加密 “speciallity”“speciallity”(1)明文明文speciallity sp ec ia lq li ty(用(用q进行分隔)进行分隔)(2)加密加密sp ec ia lq li ty hs fi ch gu eb yp所以,所以,speciallity hsfichguebypHARPICODEFGKMNQTVWXY49Playfair密码的优点密码的优点l PlayfairPlayfair密码与简单的单一字母替代法密码相比有密码与简单的单一字母替代法密码相比有了很大的进步了很大的进步 虽然仅有虽然仅有2626个字母,但有个字母,但有26262626676676种字母