密码学概论精选教学课件

1、信息安全概论电子科技大学出版社2007年8月2022/8/201第2章 密码学概述 2.1 密码学简介 2.2 密码学基本概念 2.3 古典密码 2.4 基础数论 2022/8/2022.1 密码学概述2.1.1 密码学与数学的联系2.1.2 密码学的发展历史返回本章目录2022/8/2032.1.1 密码学与数学的联系基础数论在密码学中的作用基础数论作为一门古老的数学学科，在整个数学学科中占有非常重要的地位。古典密码机制，如加法、乘法密码，实质上就用到了数论中同余的概念。数论理论在近代密码学的研究中发挥了前所未有的生命力。最典型的是影响广泛的RSA公钥密码体制，它的基础是数论的欧拉定理，其安

2、全性依赖于大数的因素分解的困难性。数论中的许多基本内容，如同余理论、中国剩余定理、高次剩余理论等，在新型密码体制、密钥分配与管理、数字签名、身份认证等方面有直接的应用。 2022/8/2042.1.1 密码学与数学的联系近代数学对现代密码学的影响近代数学在现代密码研究中的应用比比皆是 ，如群论在分组密码中的应用，利用置换概念实现轮函数的扩散性等。（对称密码体制）有限域上椭圆曲线理论，多项式理论和陷门单向函数等使密码学与数学的关系越来越紧密。 （非对称密码体制）在生成密钥序列的对象中，布尔函数的一些特殊结构起到了很大的作用。就数理逻辑来说，BAN逻辑已延伸到网络协议的逻辑认证等方面，如网络安全协

3、议以及电子交易的防抵赖协议的形式化分析。返回本节目录2022/8/2052.1.2 密码学的发展历史朴素密码时代密码学的渊源可追溯到古代社会中的行帮暗语、黑帮行话和隐写术等。古典密码时代随着战争的出现，通信的保密性成为必然的需求。古典密码采用手工或机械变换的方式实现。古典密码体制可分为单表替代密码和多表替代密码。单表替代密码： Caesar密码（据传为凯撒使用）。多表替代密码： Engima密码（二战时德国使用）。2022/8/2062.1.2 密码学的发展历史电子计算时代1949年Shannon发表保密系统的通信理论，为密码学奠定了理论基础。1976年Diffe和Hellman发表了密码学的

4、新方向，提出了一种崭新的密码设计思想公钥加密体制。1977年美国国家标准局正式公布了数据加密标准 (DES)。网络计算时代随着网络技术的迅速发展和高性能计算机的问世，密码学重新引起了人们的极大关注。1997年美国开始征集新一代数据加密标准AES。2022/8/2072.2 密码学的基本概念 2.2.1 基本术语 2.2.2 密码系统模型 2.2.3 密码分析攻击 2.2.5 密码系统的安全性 返回本章目录2022/8/2082.2.1 基本术语明文与明文空间需要加密的信息称为明文。明文的取值范围称为明文空间。密文与密文空间明文经过隐藏（加密）形成密文。密文的取值范围称为密文空间。密钥与密钥空间

5、在明文转换为密文或将密文转换为明文的算法中输入的参数。密钥的取值范围称为密钥空间。2022/8/2092.2.1 基本术语加密和解密（算法）为了隐藏明文，对明文实施的一系列变换过程，称为加密（算法），所使用的密钥称为加密密钥。反之，为还原明文对密文施加的一系列逆变换，称为解密（算法），所使用的密称钥为解密密钥。密码算法加密算法和解密算法统称为密码算法。密码系统密码算法、明文空间、密文空间以及密钥空间。2022/8/20102.2.2 密码系统模型加密：C=E(K1,M)解密：M=D(K2,C)密码等式：M=D(K2, E(K1,M)加密密钥K1和解密密钥K2是否相同是密码算法的分类依据之一。2

6、022/8/20112.2.2 密码系统模型加密算法通常采用的两个基本方法替换法(Substitution)：将明文消息的每个字母（单词）替换为其它字母（单词）。变换法(Transposition)：将明文消息的字母重新排列组合而得到密文。密码算法的保密性必须是基于保持密钥的秘密，而不是基于加解密算法的秘密。（现代密码vs古典密码）。若是基于加解密算法的秘密，则成为受限制的算法，如换位密码。2022/8/20122.2.3 密码分析密码学是研究编制密码和破译密码的技术科学密码编码学:研究如何对消息进行变换，防止明文被窃取，进而被解读和利用。密码分析学:研究在不知道密钥的情况下，如何尽快恢复出明

7、文或密钥。密码分析也可以发现密码体制的弱点。密码学中亘古不变的真理只有密码分析家才能评判密码体制的安全性！2022/8/20132.2.3 密码分析的攻击方法穷举攻击法（强力攻击）对截获到的密文尝试遍历所有可能的密钥，直到获得了一种从密文到明文的可理解的转换；使用不变的密钥对所有可能的明文加密，直到得到与截获到的密文一致为止。统计分析法指密码分析者根据明文、密文和密钥的统计规律来破译密码的方法。数学分析法指密码分析者针对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码。2022/8/20142.2.3 密码分析的攻击类型惟密文攻击(Cipher text-only attac

8、k)在惟密文攻击中，密码分析者知道密码算法，但仅能根据截获的密文进行分析，以得出明文或密钥。由于密码分析者所能利用的数据资源仅为密文，这是对密码分析者最不利的情况。已知明文攻击 (Known-plain text attack)已知明文攻击是指密码分析者除了有截获的密文外，还有一些已知的“明文密文对”来破译密码。密码分析者的任务目标是推出用来加密的密钥或某种算法，这种算法可以对用该密钥加密的任何新的消息进行解密。2022/8/20152.2.3 密码分析的攻击类型选择明文攻击(Chosen-plain text attack)指密码分析者不仅可得到一些“明文密文对”，还可以选择被加密的明文，并

9、获得相应的密文。密码分析者能够选择特定的明文数据块去加密，并比较明文和对应的密文，已分析和发现更多的与密钥相关的信息。选择密文攻击(Chosen-cipher text attack)指密码分析者可以选择一些密文，并得到相应的明文。密码分析者的任务目标是推出密钥。这种密码分析多用于攻击公钥密码体制。2022/8/20162.2.3 密码分析衡量密码攻击的复杂度数据复杂度：为了实施攻击所需输入的数据量。处理复杂度：完成攻击所需要花费的时间。存储量：进行攻击所需要的数据存储空间大小。攻击的复杂性取决于以上三个因素的最小复杂度。密码系统的密钥空间必须足够地大。如果密钥空间太小的话，攻击者可以采用已知

10、明文攻击，甚至唯密文攻击，来穷举整个密钥空间从而攻破密码系统。 2022/8/20172.2.4 密码系统的安全性无条件安全性假定攻击者拥有无限的计算资源，但仍然无法破译该密码系统。计算安全性指使用目前最好的方法攻破它所需要的计算远远超出攻击者的计算资源水平，则可以定义这个密码体制是安全的。可证明安全性将密码系统的安全性归结为某个经过深入研究的数学难题（如大整数素因子分解、计算离散对数等），数学难题被证明求解困难。2022/8/20182.2.4 密码系统的安全性密码系统要达到实际安全性，就要满足以下准则：破译该密码系统的实际计算量（包括计算时间或费用）十分巨大，以致于在实际上是无法实现的。

11、破译该密码系统所需要的计算时间超过被加密信息有用的生命周期。（作战命令、重要新闻消息）破译该密码系统的费用超过被加密信息本身的价值。2022/8/20192.2.4 密码系统的安全性一个提供机密性服务的密码系统是实际可用的，必须满足的基本要求：系统的保密性不依赖于对加密体制或算法的保密，而仅依赖于密钥的安全性。 “一切秘密寓于密钥之中”是密码系统设计的一个重要原则。满足实际安全性，使破译者取得密文后在有效时间和成本范围内，确定密钥或相应明文在计算上是不可行的。加密和解密算法应适用于明文空间、密钥空间中的所有元素。 加密和解密算法能有效地计算，密码系统易于实现和使用。 2022/8/2020影响

12、密码系统安全性的因素所使用密码算法本身的保密强度。密码算法的保密强度取决于密码设计的水平、破译技术水平等。（技术保证）密码算法之外的不安全因素。如：操作系统、网络协议和应用软件的漏洞、人为管理失误。密码算法的保密强度并不等价于密码系统整体的安全性。个密码系统必须同时完善技术与管理要求，才能保证整个密码系统的安全。2.2.4 密码系统的安全性2022/8/20212.3 古典密码 2.3.1 字符或字符串的多维变序 2.3.2 单表古典密码中的置换运算 2.3.3 多表代替 2.3.4 古典密码的统计分析 返回本章目录2022/8/20222.3.1 字符或字符串的多维变序一维倒置根据对明文是分

13、段或分组处理的不同，可分为报文倒置法和分组倒置法。报文倒置法：将一段明文整体倒置，并截成固定长度的字母组，形成密文。分组倒置法：首先将明文分成固定长度的字母串，然后对每组明文的字母分别进行倒置，形成密文。2022/8/20232.3.1 字符或字符串的多维变序二维易位在一个空表内，根据约定的书写顺序填入所要加密的明文。如横向从上向下填写明文，则需约定列数。空表填充后，再按照约定的抄写顺序写出规定长度的密码。2022/8/20242.3.2 单表古典密码中的置换运算基本思想明文字母所对应的密文字母在密文中保持不变，即同一明文字母唯一对应着一致的密文字母。加法密码（凯撒加密法）定义P=p0,p1,

14、pn-1为明文字母表,加密变换为：ci=Ek(pi)=(pi+k) mod n. 乘法密码加密变换：ci=Ek(pi)=(pi*k) mod n. (gcd(k, n)=1) 仿射密码加密变换：ci=Ek(pi)=(pi*k1+k2) mod n. (gcd(k1, n)=1) 加法密码和乘法密码都是仿射密码的特殊情况。2022/8/20252.3.3 多表代替 多表代替密码是一个由多个代替表依次对明文字母进行替换。与单表密码不同的是，明文字母与密文字母之间不再存在一一对应的关系，明文中的字母统计特征不会在多表密码中体现出来。例子：Vigenere密码设密钥K=k0k1kd-1，加密变换： c

15、i=EK(pi)=(pi+kj) mod n. 其中，j=i mod d.2022/8/20262.3.3 多表代替 谢尔比乌斯发明的加密电子机械名叫ENIGMA，在当时，它被认为是有史以来最为可靠的加密系统之一。德军对ENIGMA加密机的过分信赖，也是德国战败的重要因素之一。2022/8/20272.3.4 古典密码的统计分析 单表密码体制中，由于明文字母与密文字母呈现出一一对应的关系，则明文字母的统计特性在密文中能够体现出来。当截获的密文足够多时，可以通过统计密文字母的出现频率，来确定明文字母与密文字母之间的对应关系。多表密码体制中，明文中的字母统计特征不会在密文中体现出来。但知道多字母的

16、统计特性对于密文的破译非常有用。2022/8/20282.4 基础数论 2.4.1 数的整除性 2.4.2 欧拉(Euler)函数 2.4.3 欧几里德(Euclid)算法 2.4.4 模运算 返回本章目录2022/8/20292.4.1 数的整除性 素数（质数）在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。公约（因）数、互素公约数是几个整数同时均能整除的整数，公约数中最大的称为最大公约数，简写为gcd(greatest common divisor)。如果两个整数a和b的最大公约数为1，即gcd(a, b)=1，则称a和b互素。2022/8/20302.4.2 欧拉

17、(Euler)函数 欧拉函数的定义欧拉函数(n) ：与n互素、且小于n的整数的个数。欧拉函数的性质若n为素数，则(n) = n-1；若p为素数，k0，则(pk) = pk-1(p-1)；若gcd(p, q)=1，则(pq) = (p) (q)。若p和q均为素数，则(pq) = (p-1) (q-1)；2022/8/20312.4.3 欧几里德(Euclid)算法 带余除法设 ，若存在唯一确定的整数q和r，使得a =bq+r, 。则称q为a除以b所得的商，称r为a除以b所得的余数，记为r = a mod b。欧几里德算法利用带余除法计算两个整数的最大公约数。设有正整数a, b，且ab，则gcd(a, b)=gcd(a, a mod b)。算法应用该算法可以快速求得给定整数a和b的最大公因数 gcd(a, b)，因此可用来计算