密码学概论 第1讲引论

密码学概论朱晓玲（ZXL408@）合肥工业大学计算机与信息学院2024/6/21课程学时

48

课程学分

3

周一周二周三周四周五上午1、2密码学概论（1-13周）主楼116下午7、8密码学概论（1-13周）主楼116考核形式：卷面≤70%，平时≥30%

平时：出勤，作业，报告课程安排与考核2024/6/22相关课程配置结构图(2011教学计划)本课程地位：重要的理论和技术基础！2024/6/23教材及参考书目《现代密码学》第二版，杨波，清华大学出版社，2007《密码编码学与网络安全》，WilliamStallings，电子工业出版社，2001；《信息安全数学基础》，覃中平、张焕国等，清华大学出版社，2006《密码学原理与实践》第二版，电子工业出版社，DouglasRSlinson著，2003欧密会、美密会、亚密会的高水平会议论文等2024/6/24课程内容流密码分组密码消息认证和杂凑算法公钥密码密钥分配与密钥管理数字签名和密码协议网络加密与认证2024/6/25第一章引言1.1信息安全面临的威胁1.2信息安全保障1.3密码学的发展1.4密码学的基本概念1.5几种古典密码2024/6/262024/6/27保密性？可用性？完整性？真实性？信息安全含义：信息的保密性、完整性、可用性、真实性、不可抵赖性1.1信息安全面临的威胁2024/6/28自然威胁自然威胁可能来自于各种自然灾害、恶劣的场地环境、电磁辐射和电磁干扰、网络设备自然老化等。人为威胁人为攻击可分为被动攻击和主动攻击安全威胁分类2024/6/29保密性完整性真实性可控性不可抵赖性不可否认业务访问控制认证业务保密业务完整性业务消息保密（所有消息、单个消息、一个消息中某个特定域）；对业务流实施保密用于保证通信的真实性；保证通信双方的通信连接不能被第三方介入保证所接收的消息未经复制、插入、篡改、重排或重放；对已毁坏的数据进行恢复用于防止通信双方中的某一方对所传输消息的否认（发出和接收）防止对网络资源的非授权访问，控制的实现方式是认证(如口令)。密码学是信息安全的核心1.2信息安全保障2024/6/2102024/6/2111.3密码学的发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学2024/6/212第1阶段－古典密码

密码学还不是科学,而是艺术出现一些密码算法和加密设备主要特点：数据的安全基于算法的保密20世纪早期密码机2024/6/213

计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“TheCommunicationTheoryofSecretSystems”，标志着密码学成为科学（60页）1967年DavidKahn的《TheCodebreakers》1971-1973年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密Kerchoffs提出这一编码原则,成为传统密码和现代密码的分界线第2阶段1949-19752024/6/2141976年：Diffie&Hellman的

“NewDirectionsinCryptography”提出了不对称密钥；（12页）1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能1977年DES正式成为标准对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者第3阶段1976-2024/6/215

明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。1.3密码学的基本概念密码学(Cryptology)：研究信息系统安全保密的科学。2024/6/216

加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。接收者(Receiver)：传送消息的预定对象。截收者(Eavesdropper)：在信息传输和处理系统中的非授权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。2024/6/217

密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。2024/6/218无条件安全和计算安全

无条件安全Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密）

计算安全

破译密文的代价超过被加密信息的价值破译密文所花时间超过信息的有效期2024/6/219

密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问

密码分析学(Cryptanalytics)，研究分析破译密码的学问。密码学研究分支2024/6/220密码分析截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。2024/6/221密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别

密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。2024/6/2221.3.1保密系统模型信源Mm加密器解密器接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道明文消息空间M，密文消息空间C，密钥空间K1和K2，在单钥体制下K1=K2=K；总体(M,C,K1,K2,EK1,DK2)为保密通信系统2024/6/223

保密系统应当满足的要求系统即使达不到理论上是不可破的，即pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。(计算安全)系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。2024/6/2241.3.2密码体制分类密码体制有2大类：单钥体制(One-keysystem)：加密密钥和解密密钥相同。双钥体制(Two-keysystem)：加密密钥和解密密钥不同。2024/6/225密码体制分类单钥体制加密器EK解密器DK密文明文明文K密钥产生器K2024/6/226分类：流密码(Streamcipher)明文逐位加密分组密码(Blockcipher)明文逐组加密单钥体制不仅可用于数据加密，也可用于消息的认证。单钥体制研究热点密钥管理(Keymanagement)。密钥产生、分配、存储、销毁等2024/6/227密码体制分类

双钥体制双钥体制或公钥体制(Publickeysystem)(Diffie和Hellman,1976)

每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。2024/6/228公钥体制的主要特点加密和解密能力分开可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。2024/6/229对称密码加解密速度快适合文件加密密钥管理困难非对称密码短消息加密解决密钥分配和管理问题，适合签名和认证安全基础基于一个数学困难问题综合运用对称密码技术和非对称密码技术。比较2024/6/230

1.3.3密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击加密算法截获的部分密文已知明文攻击加密算法，截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文2024/6/231上述攻击的目的是确定所使用的密钥。这四种攻击类型的强度按序递增，惟密文攻击是最弱的攻击。选择密文攻击是最强的一种攻击。如果一个密码系统能抵抗选择密文攻击，那么它能抵抗其余三种攻击。2024/6/232密码分析方法

-穷举破译法

对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。

2024/6/233常见的三字母组合：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH等。

常见的双字母组合：TH、HE、IN、ER、RE、AN、ON、EN、AT；-统计分析法2024/6/234其他分析方法线性分析差分分析插值攻击生日攻击等等2024/6/2351.4几种古典密码代换（Substitution）密码。明文中的字母由其他字母、数字或符号所取代的一种方法。单表代换多表代换置换（Permutation）密码。换位就是重新排列消息中的字母。2024/6/236著名的Caesar密码设明文为：China

加密:C：对应着字母F；

h：对应着字母K；

i：对应着字母L；

n：对应着字母Q；

a：对应着字母D。密文为“FKLQD”。Caesar密码：据说恺撒率先使用，因此这种加密方法被称为恺撒密码。基本思想是：通过把字母移动一定的位数来实现加密和解密。例如，如果密匙是把明文字母的位数向后移动三位。2024/6/237解密：

F：对应着C；

K：对应着H；

L：对应着I；

Q：对应着N；

D：对应着A。即“FKLQD”经Caesar密码解密恢复为“CHINA”(不区分大小写)2024/6/238Caesar数学表示加密与解密算法：c≡E3(m)≡m+3mod26m≡D3(c)≡c-3mod26属于单字母简单替换密码-单表代换密码结构过于简单建立字母和数字间对应关系2024/6/239移位密码c≡Ek(m)≡m+kmod26m≡Dk(c)≡c-kmod26仿射密码c≡Ea,b(m)≡am+bmod26m≡Da,b(c)≡a-1(c-b)mod26(a,26)≡1考虑上述密码的安全性所有单表代换密码都难以经受语言特性的统计攻击，单表代换保持明文的统计特性不变。加密明文hot。hot转化为数字7，14和19。c≡Ea,b(m)≡7m+3mod26密文串数字是为0，23和6，即AXG。其他的单表代换密码2024/6/240加密Ci≡AMi+B(modN)解密Mi≡A-1(Ci-B)(modN)A是modN的n*n的可逆阵B一般取0向量Mi=（m1,m2,…mn）T明文分组Ci=（c1,c2,…cn）T密文分组i=1,2,…多表代换密码-Hill密码2024/6/241假定密钥是A=加密明文july？两个明文组ju

(9，20)和ly(11，24)。july的加密是delw。对Hill密码的已知明文攻击？对Hill密码的惟密文攻击？完全隐藏了单字母的频率2024/6/242Hill密码的破译(已知明文攻击)输入明文、密文各2个分组，设（m[0],m[1]），（m[2],m[3]）和对应的（c[0],c[1]），（c[2],c[3]）满足A=mod26。2024/6/243模m下逆矩阵的存在性判断和求解在对于2×2矩阵A=，如果逆矩阵存在，由线性代数A-1=。在模26下，A-1=()-1mod26。矩阵A的逆存在的充分条件是在模26下存在逆元。2024/6/244算法描述及实现选择一个二阶可逆方阵a，即Hill密码的密钥矩阵。将明文字符串转化为数字。分组，每两个数字作为一组m（2维列向量），假设明文为偶数个字符。方阵a乘以m，得新2维列向量c=ammod26。重复步骤④，直到所有分组被加密。将数字转化为密文字符串。加密算法描述2024/6/245运行结果2024/6/246单表代换与多表代换密码比较单表代换密码对单个字母密码加密密码分析许多统计信息未变换唯密文攻击可行的多表代换密码对多个字母同时密码加密密码分析统计信息隐藏已知明文攻击可行多表代换密码的破译要比单表代换密码难2024/6/247置换密码单表或多表密码都是代换密码置换密码是重新排列消息中的字母，以便打破密文的结构特性的密码最简单的置换密码是把明文中字母顺序倒过来

如：cryptography

加密为：yhpargotpyrc2024/6/248举例明文：cryptographyisanappliedscience密钥：encry把明文按某一顺序排成一个矩阵，然后按另一顺序选出矩阵中字母形成密文密文：yripdn

cohnii

rgyaee

paspsc

tpalce

2024/6/249 M1M2M3M4M5M6M7M8

M9M10M11M12M13M14M15M16 M17M18M19M20M21M22M23M24

M25M26M27M28M29M30M31M32

M33M34M35M36M37M38M39M40

M41M42M43M44M45M46M47M48

M49M50M51M52M53M54M55M56

M57M58M59M60M61M62M63M64 M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30