现代密码学第02讲

1、2022-5-131第二章：第二章：密码学基础一、密码学的基本概念一、密码学的基本概念二、密码体制分类二、密码体制分类三、密码分析三、密码分析2022-5-132一、密码学的基本概念一、密码学的基本概念密码学密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，密码编码学密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学密码分析学(Cryptanalytics)，研究分析破译密码的学问。2022-5-133 几个概念（一）几个概念（一）。 = 明文明文(消息)(Plaintext) ：被隐蔽消息。= 密文密文(Ciphertext)或密

2、报密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。=加密加密(Encryption)：将明文变换为密文的过程。=解密解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员加密员或密码员密码员(Cryptographer)：对明文进行加密操作的人员。2022-5-134 几个概念（二）几个概念（二）。 =加密算法加密算法(Encryption algorithm)：密码员对明文进行加密时所采用的一组规则。=接收者接收者(Receiver)：传送消息的预定对象。=解密算法：解密算法：接收者对密文进行解密时所采用的一组规则。=密钥密钥(Key)：控制加密和解密算

3、法操作的数据处理，分别称作加密密钥加密密钥和解密密钥解密密钥。截收者截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。2022-5-135几个概念（三）几个概念（三） = 密码分析密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。 密码分析员密码分析员(Cryptanalyst)：从事密码分析的人。 被动攻击被动攻击(Passive attack)：对一个保密系统采取截获密文进行分析的攻击。 主动攻击主动攻击(Active attack)：非法入侵者入侵者(Tamper)、攻击者攻

4、击者(Attcker)或黑客黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。2022-5-136保密系统模型保密系统模型信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭线信道（主动攻击）C 搭线信道（被动攻击）密码分析员m密钥源K1k1密钥源K2k2密钥信道2022-5-137 保密系统应当满足的要求保密系统应当满足的要求l系统即使达不到理论上是不可破的，即prmm=m m=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。l系统的保密性不依赖于对加密体

5、制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。l加密和解密算法适用于所有密钥空间中的元素。l系统便于实现和使用。2022-5-138认证与认证系统认证与认证系统n认证系统认证系统(Authentication system) 防止消息被窜改、删除、重放和伪造的一种有效方法,使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统n保密性保密性 保密性是使截获者在不知密钥条件下不能解读密文的内容。n认证性认证性 使任何不知密钥的人不能构造一个密报，使意定的接收者解密成一个可理解的消息(合法的合法的消息)。2022-5-139安全

6、认证系统应满足下述条件安全认证系统应满足下述条件l意定的接收者能够检验和证实消息的合法性和真实性。l消息的发送者对所发送的消息不能抵赖。l除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c c和相应消息m m下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。l必要时可由第三者作出仲裁。2022-5-1310 完整性完整性(integrity) 在有自然和人为干扰条件下，系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和杂凑技术来保证消息的完整性。2022-5-1311二、密码体制分类二、密码体制分类n密码体制有密码体制有2大类：大类：

7、n单钥体制单钥体制(One-key system)： 加密密钥和解密密钥相同。n双钥体制双钥体制(Two key system)： 加密密钥和解密密钥不同。2022-5-1312密码体制分类密码体制分类 单钥体制单钥体制加密器EK解密器DK密文明文明文K密钥产生器K2022-5-1313密码体制分类密码体制分类 单钥体制单钥体制n单钥体制主要研究问题：单钥体制主要研究问题：n密钥产生(Key generation)，n密钥管理(Key management)。n分类：分类：n流密码(Stream cipher)n分组密码(Block cipher)n单钥体制不仅可用于数据加密，也可用单钥体制不

8、仅可用于数据加密，也可用于消息的认证于消息的认证。2022-5-1314密码体制分类密码体制分类 双钥体制双钥体制双钥体制双钥体制或公钥体制公钥体制(Public key system) (Diffie和Hellman,1976) 每个用户都有一对选定的密钥(公钥k k1；私钥k k2)，公开的密钥k k1可以像电话号码一样进行注册公布。2022-5-1315公钥体制的主要特点公钥体制的主要特点n加密和解密能力分开n可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）n只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。n无需事先分配密钥。2

9、022-5-1316三、密码分析三、密码分析 截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。2022-5-1317密码分析密码分析 密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。2022-5-1318密码分析方法密

10、码分析方法-穷举破译法穷举破译法 对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文； 或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法完全试凑法(Complete trial-and-error Method)。 只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。 2022-5-1319密码分析方法密码分析方法分析法分析法 确定性分析法确定性分析法 利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量

11、的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。 统计分析法统计分析法 利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。2022-5-1320 密码可能经受的攻击密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击n加密算法n截获的部分密文已知明文攻击n加密算法，n截获的部分密文和相应的明文选择明文攻击n加密算法n加密黑盒子，可加密任意明文得到相应的密文选择密文攻击n加密算法n解密黑盒子，可解密任意密文得到相应的明文2022-5-1321无条件安全和计算安

12、全无条件安全和计算安全 无条件安全无条件安全 如果算法产生的密文不能给出唯一决定相应明文的足够信息，无论截获多少密文，花费所少时间都不能解密密文。 Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密） 计算安全计算安全 破译密文的代价超过被加密信息的价值 破译密文所花时间超过信息的有效期2022-5-1322第三章第三章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列三三、B-M综合算法综合算法四、非线性序列四、非线性序列2022-5-1323一、流密码的基本概念一、流密码的基本概念2022-5-1324 流密码的

13、基本概念流密码的基本概念n流密码是将明文划分成字符流密码是将明文划分成字符( (如单个字母如单个字母) )，或其编码，或其编码的基本单元的基本单元( (如如0, 10, 1数字数字) )，字符分别与密钥流作用进，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。行加密，解密时以同步产生的同样的密钥流实现。n流密码强度完全依赖于密钥序列的随机性流密码强度完全依赖于密钥序列的随机性( (Randomness)Randomness)和不可预测性和不可预测性( (Unpredictability)Unpredictability)。n核心问题是密钥流生成器的设计核心问题是密钥流生成器的

14、设计。n保持收发两端密钥流的精确同步是实现可靠解密的关保持收发两端密钥流的精确同步是实现可靠解密的关键技术键技术。2022-5-1325流密码的框图流密码的框图kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)2022-5-1326 流密码的框图流密码的框图n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流：c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密钥流：密钥流：ki，i 0。 一个完全随机的非周期序列，可以实现一次一密体制。但一个完全随机的非周期序列，可以实现一次一密体制。但需要

15、无限存储单元和复杂的输出逻辑函数需要无限存储单元和复杂的输出逻辑函数f f。 i i是第是第i i时刻时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。密钥流生成器的内部状态，以存储单元的存数矢量描述。n加法流密码：加法流密码： ci=Eki(mi)=mi ki2022-5-1327有限状态自动机有限状态自动机FA(Finite state Automation)n具有离散输入和输出（输入集和输出集均具有离散输入和输出（输入集和输出集均有限）的一种数学模型有限）的一种数学模型n有限状态集有限状态集S=si|i=1,2,ln有限输入字符集有限输入字符集X= Xi|i=1,2,mn有限输出字符

16、集有限输出字符集Y= Yk|k=1,2,nn转移函数转移函数nYjf 1(sj ,Xj)nSj+1 f 2(sj ,Xj)第第j时刻输入时刻输入Xj X ，输出输出YjY 2022-5-1328例2-1nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n转移函数转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s22022-5-1329FA的状态图表示 若输入为若输入为x1x2x1x3x3x1初始状态初始状态s1输出为输出为y1y1y2y1y3y12022-5-1330作为作为FAFA的密钥流产生器的密钥流产生器n同步流密码的密钥流产生器可同步流密码的密钥流产生器可看为一个参数为看为一个参数为k的的FAFAn输出集输出集Z Z，状态集，状态集，状态转移，状态转移函数函数和输出函数和输出函数，初态，初态 0 0n设计的关键是设计的