现代密码学第1章：现代密码学概论

1现代密码学概论《现代密码学》第1章2本章主要内容1、密码学基本概念2、密码体制的分类3、密码攻击（分析）4、密码学的起源、发展及实例5、密码学的现状和发展趋势3当今社会已经进入信息时代，密码是与信息相关的。信息：指语言、文字、数据、图象、符号等，它使人们了解社会上的各种现象、变化以及相互关系等。信息的传递或广播，往往需要除合法的授权者外，不让其他任何人知道，这就引发了所谓的秘密通信。秘密通信的手段基本上可分为两类：•信道保护（传递信息的载体称为信道）：如信使传递、密写、缩微摄影、专线电话、突发式通信等；•密码保护：如电报加密、传真加密、语音加密、图象加密，计算机数据加密等。信道保护纯属技术问题，它有较大的局限性。如派信使传送信息速度太慢，专线电话也难以防止窃听。密码保护属于理论与技术相结合，是当今最常用的、也最重要的秘密通信手段。1.密码学基本概念4密码学（cryptology）是一门研究密码保护通信手段的科学，属于应用数学的范畴，包括加密理论与解密理论。密码技术（Cryptography）—把可理解的消息变换成不可理解消息，同时又可恢复原消息的方法和原理的一门科学或艺术。密码学技术可以使消息的内容对(除发送者和接收者以外)的所有人保密.可以使接收者验证消息的正确性是解决计算机与通信安全问题重要技术之一.1.密码学基本概念5密码学的基本任务甲和乙两个人在不安全的信道上进行通信，而他们的敌人丙不能理解他们正在通信的内容。甲乙丙6一般的通信系统的模型7保密通信系统加密器解密器8通信双方采用保密通信系统可以隐蔽和保护需要发送的消息，使未授权者不能提取信息。发送方将要发送的消息称为明文(plaintext)明文被变换成看似无意义的随机消息，称为密文（ciphertext），这种变换过程称为加密（encipher/encode）；其逆过程，即由密文恢复出原明文的过程称为解密（decipher/decode)。1.密码学基本概念91.密码学基本概念对明文进行加密操作的人员称为加密员或密码员。密码员对明文进行加密时所采用的一组规则称为加密算法（Encryption）。传送消息的预定对象称为接收者，接收者对密文进行解密时所采用的一组规则称为解密算法（Decryption）。。10加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥（key）。传统密码体制所用的加密密钥和解密密钥相同，或实质上等同，即从一个易于得出另一个，称其为单钥或对称密码体制。若加密密钥和解密密钥不相同，从一个难于推出另一个，则称为双钥或非对称密码体制。密钥是密码体制安全保密的关键，它的产生和管理是密码学中的重要研究课题。1.密码学基本概念11在信息传输和处理系统中，除了预定的接收者外，还有非授权者，他们通过各种办法（如搭线窃听、电磁窃听、声音窃听等）来窃取机密信息，称其为截收者。截收者虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的明文或密钥，这一过程称为密码分析，从事这一工作的人称为密码分析员，研究如何从密文推演出明文、密钥或解密算法的学问称为密码分析学（cryptanalysis/codebreaking)。1.密码学基本概念12对一个保密通信系统采取截获密文进行分析的这类攻击称为被动攻击。现代信息系统还可能遭受的另一类攻击是主动攻击，非法入侵者、攻击者或黑客主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利己害人的目的。这是现代信息系统中更为棘手的问题。1.密码学基本概念13保密通信系统可用示意图表示，它由以下几部分组成：明文消息空间M，密文消息空间C，密钥空间K1和K2。在单钥体制下K1=K2=K，此时密钥K需经安全的密钥信道由发送方传给接收方；加密变换Ek1：M→C，其中k1∈K1，由加密器完成；解密变换Dk2：C→M，其中k2∈K2，由解密器实现。1.密码学基本概念14信源M加密器解密器信宿)(1mEck)(2cDmkcm密钥源K1密钥源K2k1k2密钥信道非法接入者密码分析员'mm'm密码学上保密通信系统的模型15称总体(M,C,K1,K2,EK1,DK2)为保密通信系统。对于给定明文消息m∈M，密钥k1∈K1，加密变换将明文m变换为密文c，即c=f(m,k1)=Ek1(m)m∈M,k1∈K1。接收方利用通过安全信道送来的密钥k（k∈K，单钥体制下）或用本地密钥发生器产生的解密密钥k2（k2∈K2，双钥体制下）控制解密操作D，对收到的密文进行变换得到恢复的明文消息，即：m=Dk2(c)m∈M,k2∈K21.密码学基本概念16而密码分析者，则用其选定的变换函数h，对截获的密文c进行变换，得到的明文是明文空间中的某个元素,即m′=h(c)。一般m′≠m。如果m′=m，则分析成功。1.密码学基本概念17为了保护信息的保密性，抗击密码分析，保密系统应当满足下述要求：①系统即使达不到理论上是不可破的，即pr{m′=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文在计算上是不可行的。1.密码学基本概念18②系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。③加密和解密算法适用于所有密钥空间中的元素。④系统便于实现和使用。1.密码学基本概念192.密码学与密码体制密码学的分类：•密码编码学.设计和研究密码通信系统，使其传递的信息具有很强的保密性和认证性的学科。•密码分析学.研究如何从密文推出明文、密钥或解密算法的学科。•密钥管理学.研究密钥的产生、分配、存贮、传递、装入、丢失、销毁以及保护等内容的学科。20密码体制的定义一个密码体制可以可以描述为一个五元组(P,C,K,E,D)，必须满足下面的条件：1P是可能明文的有限集。2C是可能密文的有限集。3k是可能的密钥的有限集。对于每一个kK，都有一个加密规则Eek和相应的解密规则Ddk每一个CPek:和PCdk:是一个函数，它满足：对于每一个明文Px都满足xxedkk))((21例如26ZCP（小写的26个英文字母）250k9726mod)()(kxxek9726mod)()(kyydk取k=10，明文：good密文：hppeg(103)o(111)d(100)22原理来分类单密钥双密钥流密码分组密码密码体制的分类密码体制从原理上可分为两大类，即单钥体制和双钥体制。23单钥体制的加密密钥和解密密钥相同。采用单钥体制的系统的保密性主要取决于密钥的保密性，与算法的保密性无关，即由密文和加解密算法不可能得到明文。换句话说，算法无需保密，需保密的仅是密钥。根据单钥密码体制的这种特性，单钥加解密算法可通过低费用的芯片来实现。单钥密码体制24单钥（私钥、对称）加密算法25密钥可由发送方产生然后再经一个安全可靠的途径（如信使递送）送至接收方，或由第三方产生后安全可靠地分配给通信双方。如何产生满足保密要求的密钥以及如何将密钥安全可靠地分配给通信双方是这类体制设计和实现的主要课题。密钥产生、分配、存储、销毁等问题，统称为密钥管理。这是影响系统安全的关键因素，即使密码算法再好，若密钥管理问题处理不好，就很难保证系统的安全保密。单钥密码体制26单钥体制对明文消息的加密有两种方式：一是明文消息按字符（如二元数字）逐位地加密，称之为流密码；另一种是将明文消息分组（含有多个字符），逐组地进行加密，称之为分组密码。单钥体制不仅可用于数据加密，也可用于消息的认证。单钥密码体制27双钥体制是由Diffie和Hellman于1976年首先引入的。采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，可以像电话号码一样进行注册公布；另一个则是秘密的。因此双钥体制又称为公钥体制。双钥密码体制的主要特点是将加密和解密能力分开，因而可以实现多个用户加密的消息只能由一个用户解读，或由一个用户加密的消息而使多个用户可以解读。前者可用于公共网络中实现保密通信，而后者可用于实现对用户的认证。双钥密码体制283.密码攻击（分析）密码分析学是指在没有加密密钥的情况下,攻击密文的过程目标：就是要从密文得到明文或者由已知的条件得到密钥。密码分析有一个假定：攻击者知道加密算法。291、唯密文攻击(ciphertextonly)--只知道算法与一些密文--利用统计方法--需要能够识别明文2、已知明文攻击（knownplaintext）----知道一些明文/密文对----利用已知的明文密文对进行攻击3.密码攻击（分析）303、选择明文攻击（chosenplaintext）----能够选择明文并得到响应的密文----利用算法的结构进行攻击4、选择密文攻击（chosenciphertext）----能够选择密文并得到对应的明文----利用对算法结构的知识进行攻击3.密码攻击（分析）31攻击者对密码系统的4种攻击类型中，类型的划分由攻击者可获取的信息量决定。其中，最困难的攻击类型是惟密文攻击，这种攻击的手段一般是穷搜索法，即对截获的密文依次用所有可能的密钥试译，直到得到有意义的明文。只要有足够多的计算时间和存储容量，原则上穷搜索法总是可以成功的。3.密码攻击概述32但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。敌手因此还需对密文进行统计测试分析，为此需要知道被加密的明文的类型，比如英文文本、法文文本、MD-DOS执行文件、Java源列表等。3.密码攻击概述33惟密文攻击时，敌手知道的信息量最少，因此最易抵抗。然而，很多情况下，敌手可能有更多的信息，也许能截获一个或多个明文及其对应的密文，也许知道消息中将出现的某种明文格式。例如ps格式文件开始位置的格式总是相同的，电子资金传送消息总有一个标准的报头或标题。这时的攻击称为已知明文攻击，敌手也许能够从已知的明文被变换成密文的方式得到密钥。3.密码攻击概述34与已知明文攻击密切相关的一种攻击法称为可能字攻击。例如对一篇散文加密，敌手可能对消息含义知之甚少。然而，如果对非常特别的信息加密，敌手也许能知道消息中的某一部分。例如，发送一个加密的账目文件，敌手可能知道某些关键字在文件报头的位置。又如，一个公司开发的程序的源代码中，可能在某个标准位置上有该公司的版权声明。3.密码攻击概述35如果攻击者能在加密系统中插入自己选择的明文消息，则通过该明文消息对应的密文，有可能确定出密钥的结构，这种攻击称为选择明文攻击。选择密文攻击是指攻击者利用解密算法，对自己所选的密文解密出相应的明文。3.密码攻击概述36还有两个概念值得注意。第一，一个加密算法是无条件安全的，如果算法产生的密文不能给出惟一决定相应明文的足够信息。此时无论敌手截获多少密文、花费多少时间，都不能解密密文。第二，Shannon指出，仅当密钥至少和明文一样长时，才能达到无条件安全。也就是说除了一次一密方案外，再无其他加密方案是无条件安全的。3.密码攻击概述37因此，加密算法只要满足以下两条准则之一就行：①破译密文的代价超过被加密信息的价值。②破译密文所花的时间超过信息的有用期。满足以上两个准则的加密算法称为计算上安全的。3.密码攻击概述383.密码攻击概述无条件安全（unconditionalsecurity）由于密文没有泄露足够多的明文信息，无论计算能力有多大，都无法由密文唯一确定明文。计算安全（computationalsecurity）----在有限的计算资源条件下，密文不能破解。（如破解的时间超过地球的年龄）393.穷密钥搜索理论上很简单，对每个密钥进行测试最基本的攻击方法，复杂度有密钥量的大小决定假设可以对正确的明文能够识别假设的时间表:40Keysize(bits)Time(1us/test)Time(1us/10^6test)3235.8mins2.15msec406.4days550msec561140yeas10.0hours64~500000yeas107days1285*10^24yea