现代密码学基础课件

《现代密码学基础课件》由会员分享，可在线阅读，更多相关《现代密码学基础课件（370页珍藏版）》请在金锄头文库上搜索。

1、现代密码学基础,丁彦蕊 江南大学信息工程学院,参考资料,现代密码学基础 章照止著，北京邮电大学出版社，2004 密码学宋震等编著，中国水利水电出版社，2002 密码编码学与网络安全原理与实践William Stallings著，刘玉珍等译，电子工业出版社，2004 密码学基础英文版，Oded Goldreich著，电子工业出版社，2002,第一章 引论,密码学的基本概念 密码体制的分类 密码学的发展历史 密码学研究的基本问题,密码学的基本概念,Bob,明文：信息的原始形式（记为P）。 密文：明文经过变换加密后的形式（记为C）。 加密：由明文变成密文的过程（记为E）。 加密算法:加密明文时采用的

2、一组规则。 解密：由密文还原成明文的过程（记为D）。 解密算法：对密文解密时采用的一组规则。 密钥：为了有效地控制加密和解密算法的实现，在其处理过程中要有通信双方掌握的专门信息参与，这种专门信息称为密钥（key，记为K）。,Oscar的攻击方式,被动攻击：采用电磁侦听、声音窃听、搭线窃听等方法直接得到未加密的明文或者加密后的密文。损害了明文信息的机密性。 主动攻击：采用删除、更改、增添、重放、伪造等手段主动地向系统注入假消息。损害了明文信息的完整性。,密码系统的破译性,可破译性：如果密码分析者可以由密文推出明文或密钥，或者由明文和密文可以寻求密钥，则该密码系统是可破译的。 不可破译性： 无条件

3、安全性：对于一个密码系统，如果攻击者无论得到多少密文也求不出确定明文的足够信息，也就是理论上不可破译。 实际安全性（计算安全性）：如果一个密码系统原则上可破译，但为了由密文得到明文或密钥需付出巨大的计算，不能在希望的时间内或者可能的经济条件下破译。,密码体制的分类,1、根据加密算法与解密算法使用密钥是否相同： 对称密钥（单钥密码、秘密密钥密码、对称密码） 非对称密钥（双密钥、公开密钥、非对称密钥）,2、根据密码算法对明文信息的加密方式： 流密码（逐位的加密明文信息） 分组密码（将明文消息分组，逐组进行加密）,3、按照是否能进行可逆的加密变换： 单向函数密码体制 双向变换密码体制,密码学的发展历

4、史,古代加密方法 古希腊墓碑的名文志 隐写术 黑帮行话 古典密码 一般是文字置换，使用手工或机械变化的方式实现 包括单表代替密码、多表代替密码等 近代密码 1949年Shannon发表保密系统的信息理论，1976年Diffie和Hellman发表密码学的新方向，1977年美国实施数据加密标准（DES），标志着近代密码学的开始。 公开密钥密码，椭圆曲线密码，混沌密码以及量子密码。,密码学研究的基本问题,密码体制 单向函数与伪随机序列生成器 数字签名与杂凑函数 消息认证和身份识别 抗欺骗协议和零知识证明,第二章 古典密码学,从数学的角度来讲，一个密码系统是一族映射，它在密钥的控制下将明文空间中的每

5、个元素映射到密文空间上的某个元素。这族映射由密码方案确定，具体使用哪一个映射由密钥决定。,古典密码系统分类,代换密码 单字母代换密码 单表代换密码 多表代换密码 多字母代换密码 置换密码,代换密码（Substitution Cipher),单表代换密码,移位密码,例2.1 凯撒密码是k=3的情况，即通过简单的向右移动源字母表3个字母(见P12)。 a b c d e f g h i j k l m n o p q r s t u v w 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 x y z 23 24 25 若明文为：

6、 please confirm receipt 则密文为： SOHDVH FRQILUP UHFHLSW,替换密码,例2.2 密钥句子为：the message was transmitted an hour ago 源字母表为：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 代换字母表：THEMSAGWRNIDOUBCFJKLPQVXYZ 明文：please confirm receipt 密文：CDSTKS EBUARJO JSESRCL (密钥句子中的字母被依次填入密文字母表（重复的字母只用一次），未用的字母按自然顺序排列）,仿射密

7、码,多表代换密码（ 密码）,优点： 克服了单表代换从密文中可以提取语言的特征的缺点。 密钥量为 ，对于一个相当小的值m，穷举法也需要很长时间。,(见P16),多字母代换密码（Hill 密码）,优点： 容易将字母的自然频度隐蔽或者均一化而有利于抗统计分析。,置换密码（Permutation Cipher),古典密码体制的分析,分类（P4）： 唯密文攻击 已知明文攻击 选择明文攻击 选择密文攻击 Kerckhoff假设：攻击方知道所用的密码系统。,密码分析方法,单表代换密码分析 统计语言特征 多表代换密码分析 Kasiski测试法 重合指数法（Coincidence index) Chi测试法,第

8、三章 密码学的信息论基础,保密系统的数学模型 信息量和熵 完善保密性 理论安全性和实际安全性,通信系统和保密系统,Shannon的保密系统模型,保密系统的数学模型,概率分布的关系,信息量和熵,熵的实质,反映了集中事件出现的平均不确定性，或为确定集中出现一个事件平均所需的信息量（观测之前），或集中每出现一个事件平均给出的信息量（观测之后）。如果从编码的角度来考虑，熵也可以理解成用最优的二进制编码形式表示所需的比特数。,联合熵和条件熵,各种熵,各类熵的关系（维拉图）,完善保密性,完善保密系统,理论安全性和实际安全性,理论安全性：假定密码分析者有无限的时间、设备和资金的条件下，研究唯密文攻击时密码系

9、统的安全性。 实际安全性：在资金、设备和时间有限的条件下破译一个具体的密码系统所需要的计算量。,密文长度与明文、密钥含糊度及密钥显现含糊度的关系,密钥显现含糊度用来测量密码抗击已知明文攻击的能力。 密钥含糊度和消息含糊度是测量密钥和明文抗击唯密文攻击的能力。,（P37）,很显然，密文文本越长，分析者找到密钥或者明文的可能性越大。 理论上密文长S至少为：,理论上，当截获的密报量大于唯一解距离时，原则上就可破译。 实际上可能不能破译： 由于自然语言的复杂性，没有任何一种分析方法能够假定分析者能利用明文语言的全部统计知识 ，所以，一般破译所需的密文量都远大于理论值。 没有涉及为了得到唯一解需完成多少

10、计算量。从实际破译来看，有时虽然截获的密文量远大于唯一解距离，但由于所需的工作量还太大而难以实现破译。,设计密码的基本观点(P39),通过合并简单密码系统而形成它们的“积” 挫败统计分析的观点： 在加密之前将语言的一些多余度除去。 采用所谓的“扩散（Diffusion）”和“混淆（Confusion）”这两种加密技术扩散或混淆多余度。,第四章 密码学的计算复杂性 理论基础,问题与算法的复杂性 问题的计算复杂性分类,学习本章的目的：计算复杂性理论是密码系统安全性定义的理论基础，也是安全的现代密码系统构造方法的理论依据。,问题与算法的复杂性,问题与语言(p42) 例4.1 . 整数的因子分解问题。

11、 例4.2 . 背包问题。 实际应用中的绝大多数问题都可直接或间接地转化为判定问题。,语言的概念,a b c d e f g h w x y z,B字符集,字符,we start second use high light,字,单词表 x,B*,语言,L,I,I+,c,D,算法,算法是指用来求解某一问题的、一步一步执行的计算过程。 一个算法可解某个问题是指这个算法可应用于这个问题的任何例子并求得答案。,算法的计算复杂性,一个算法的复杂性可以用执行该算法所需的运行时间和内存空间来度量。 密码学中只研究算法的时间复杂性。 一个算法的运行时间随着选用的计算语言、用这一语言编写程序的方法以及计算所用的

12、计算机等因素的影响。 因此在计算复杂性理论研究中采用理想的模型图灵机。,图灵机（turing）,组成部分： 一个无限长的纸带 一个读写头（中间的大盒子） 内部状态（盒子上的方块，如A，B，E，H）,工作过程： 从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。,蚂蚁,图灵机的数学定义,确定型图灵机和不确定型图灵机,确定型图灵机：在算法中，下一时刻的形(s,t,i)是由现在时刻的形唯一确定。 非确定型图灵机：在算法中，下一时刻的形(s,t,i) 并

13、不是由现在时刻的形唯一确定，而是有多种选择。,计算复杂性,问题的计算复杂性分类,一个问题的计算复杂性是由可解这个问题的算法的计算复杂性决定的。 解一个问题的算法有很多个，他们的计算复杂性是不同的，在理论上定义一个问题的计算复杂性为可解该问题的最有效算法的计算复杂性。 最有效算法很难确定，因此只能把解该问题的已知最有效算法的计算复杂性进行分类。,问题的计算复杂性分类,分类： P类（确定性多项式时间可解类） NP类（不确定性多项式时间可解类） NP完全类（不确定性多项式时间可解完全类）,P类问题,NP类问题,NPC类问题,概率算法与BPP类问题,第五章 单向函数,单向函数 单向函数族 单向函数的性

14、质 单向函数的硬核,单向函数的重要性,单向函数可用于构造随机序列生成器（密钥流生成器） 单向陷门函数可用于构造公钥密码体制 单向杂凑函数可用于数字签名和消息完整性检测,一般单向函数,x,f(x),容易,困难,从表面上看，弱单向函数的条件要比强单向函数的条件弱得多，但从理论上可以证明，有一个标准的方法可以将一个弱单向函数变换为一个强单向函数。因此，在某种意义上这两个概念是等价的。,候选单向函数,定义 单向函数的存在性在理论上还没有给出证明，但是有一些函数至今未找到多项式时间求逆算法，这些函数被称为候选单向函数。,例子(p55),整数因子分解 背包函数 线性编码函数,单向函数族,强单向函数族,候选

15、单向函数族,RSA函数族 Rabin函数族 Rabin-Blum函数族 离散对数函数族,单向陷门(trapdoor)置换族,单向无爪（Claw-Free)函数族,单向函数的硬核,单向函数的硬核谓词,谓词：个体的性质或个体之间的关系。,第六章 伪随机序列生成器,计算不可区分性 伪随机序列生成器的定义和性质 伪随机序列生成器的构造,前言,一次一密体制中，所需要的随机密钥数不能少于所传送的明文消息数。 在实用的密码体制中，要求所用的随机密钥序列比所传送的明文消息序列短得多。 伪随机序列生成器是一个确定性算法，它把短的随机比特序列延伸伪长得多的貌似随机的比特序列。 主要思想是输出序列虽然不是真正的随机

16、序列，但在计算资源受到一定限制的条件下，要区别这个输出序列与等长的真随机序列的不同是困难的。,计算不可区分性,伪随机序列生成器,伪随机序列生成器的性质 统计性质 多项式延伸性 不可预测性 单向函数性,统计性质,多项式延伸性,不可预测性,伪随机序列是多项式时间不可预测的。原因是：真随机序列是不可预测的。如果伪随机序列是多项式时间可预测的，则它与真随机序列是多项式时间可区分的，这与伪随机序列的定义相矛盾。,定理6.3 一个随机变量序列是伪随机的当且仅当它是多项式时间不可预测的。,单向函数性,伪随机序列生成器的构造,用一般单向置换构造伪随机序列生成器 用单向置换族构造伪随机序列生成器,用一般单向置换构造伪随机序列生成器,用单向置换族构造伪随机序列生成器,第七章 序列密码