[互联网]计算机安全保密2008-04密码学基础

2018/2/4,1,2018/2/4,2,2018/2/4,3,第四章密码学基础,4.1 密码学概述4.2 传统密码学4.3 分组密码4.4 公钥密码4.5 密钥管理,2018/2/4,4,4.1 密码学概述1. 加密和解密,密码学是一门古老而又年轻的科学。4000年前的埃及遗迹上发现密写文字。两千多年前恺撒就开始使用目前称为“恺撒密码”的密码系统。现代密码学涉及数论、有限域、复杂性理论、组合数学、概率论、量子力学、现代光学、混沌理论、信息论、计算机科学等学科。,2018/2/4,5,蝴蝶效应,气象学家洛伦兹在1963年讲述了一种“蝴蝶效应”：南美洲亚马逊河流域热带雨林中一只蝴蝶偶尔扇动了几次翅膀，所引起的微弱气流对地球大气的影响可能随时间增长而不是减弱，甚至可能在两周后在美国得克萨斯州引起一场龙卷风。,2018/2/4,6,蝴蝶效应,“蝴蝶效应” 由气象研究引出，但是社会、经济生活的方方面面都表现出很强的“蝴蝶效应”，特别是在世界经济一体化加速、互相依赖性加强、虚拟特征日益明显的情况下，一点很小的初始扰动，都有可能被放大后变成一场巨大的经济危机。,2018/2/4,7,蝴蝶效应,蝴蝶效应产生一般要有三个基本条件：1、初始条件的误差。2、事物间存在相互依赖性。3、非线性因素的介入。,2018/2/4,8,蝴蝶效应,“蝴蝶效应”表述了一种混沌状态的不确定性，面对这种现象人类也不是无所作为的。(1)引起“蝴蝶效应”的主要原因不是蝴蝶，蝴蝶只是一个触发因素。这样的系统，即使没有蝴蝶引起的扰动，也会有其他因素来触发。要避免“蝴蝶效应”，重要的在于系统设计中在保持系统流畅性、关联性的同时，要给各个部分之间设置适当的“控制阀”，使得微小扰动产生的扩展不至于在没有控制的情况下无限制的传递下去，从而带来灾难性的后果。,2018/2/4,9,蝴蝶效应,(2)偏差捕获的时机。在扰动产生的初期，扰动带来的偏差解决容易，但越是往扰动的源头寻找，发现偏差要求的能力就越高，投入就越大。(3)蝴蝶效应带来的不一定都是负面的。,2018/2/4,10,1. 加密和解密,一战前重要的密码学进展很少出现在公开文献中，但该领域却和其它专业学科一样向前发展。1918年，二十世纪最有影响的密码分析文章之一William F. Friedman的专题论文重合指数及其在密码学中的应用作为私立的“河岸(Riverbank)实验室”的一份研究报告问世了，这篇著作涉及的工作是在战时完成的。,2018/2/4,11,加密和解密(Encrypt & Decrypt),同年，加州奥克兰的Edward H.Hebern申请了第一个转轮机专利，这种装置在差不多50年里被指定为美军的主要密码设备。一战后，密码完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根本性的进展。,2018/2/4,12,1. 加密和解密,30年代和40年代，有几篇基础性的文章出现在公开的文献中，有关该领域的几篇论文也发表了，只不过这些论文的内容离当时真正的技术水平相去甚远，战争结束时，公开的文献几乎殆尽。,2018/2/4,13,1. 加密和解密,只有一个突出的例外，那就是仙农(Claude Shannon)的文章保密系统的通信理论出现在1949年贝尔系统技术杂志上，文章也是战时工作的产物。这篇文章在第二次世界大战结束后即被解密，可能是由于失误。1949年到1967年，密码学文献近乎空白。,2018/2/4,14,1. 加密和解密,1967年，David Kahn的破译者出现了，它没有任何新的技术思想，但却对以往的密码学历史作了相当完整的记述，包括提及政府仍然认为是秘密的一些事情。破译者的意义在于它涉及到的相当广泛的领域，使成千上万原本不知道密码学的人了解密码学。新的密码学文章慢慢地开始源源不断地被编写出来了。,2018/2/4,15,1. 加密和解密,约1967年，早期为空军研制敌我识别装置的Horst Feistel在位于纽约约克镇高地的IBM Watson实验室里花费了毕生精力致力于密码学的研究。在那里他开始着手美国数据加密标准(DES)的研究，到70年代初期，IBM发表了Feistel和他的同事在这个课题方面的几篇技术报告。,2018/2/4,16,1. 加密和解密,需要密码学和密码分析学紧密结合互为促进。分析密码设计中的漏洞远比原先设计它们更难。,2018/2/4,17,1. 加密和解密,1949年，Claude Elwood Shannon香农信息论之父。1949年仙农的文章保密系统的通信理论出现在贝尔系统技术杂志上，引起了密码学的一场革命。他提出了保密系统的Shannon模型。,2018/2/4,18,2018/2/4,19,1. 加密和解密,香农1916年生于美国，1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。2001年2月24日，84岁的香农博士去世。,2018/2/4,20,1. 加密和解密,1948年6月和10月，由贝尔实验室出版的贝尔系统技术杂志连载了香农博士的文章通讯的数学原理，该文奠定了香农信息基本理论的基础。文中用非常简洁的数学公式定义了信息时代的基本概念：熵。在此基础上，他又定义了信道容量的概念，指出了用降低传输速率来换取高保真通讯的可能性。这些贡献对今天的通信工业具有革命性的影响。,2018/2/4,21,1. 加密和解密,“熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农利用概率分布的理论给出“熵”的严格定义。由于熵表达了事物所含的信息量，我们不可能用少于熵的比特数来确切表达这一事物。这一概念是所有无损压缩的标准和极限。熵也是导出无损压缩算法做达到或接近“熵”的编码的源泉。,2018/2/4,22,1. 加密和解密,狭义信息论是关于通讯技术的理论，它是以数学方法研究通讯技术中关于信息的传输和变换规律的一门科学。广义信息论，则超出了通讯技术的范围来研究信息问题，它以各种系统、各门科学中的信息为对象，广泛地研究信息的本质和特点，以及信息的取得、计量、传输、储存、处理、控制和利用的一般规律。,2018/2/4,23,1. 加密和解密,广义信息论包括了狭义信息论的内容，但其研究范围却比通讯领域广泛得多，是狭义信息论在各个领域的应用和推广，它的规律也更一般化，适用于各个领域，所以它是一门横断学科。广义信息论也称为信息科学。,2018/2/4,24,1. 加密和解密,信息理论可分为三个方面：(1)以编码为中心的信息论，是引发信息论的核心问题。(2)以信息作为主要研究对象，包括信号噪声的统计分析。(3)以计算机为中心的信息处理的基本理论。,2018/2/4,25,1. 加密和解密,编码技术密码技术信息压缩技术人类对信息的认识,2018/2/4,26,1. 加密和解密,近年来还产生了一些全新的密码技术： 量子密码(Quantum Cryptography) 热流密码（Heat Flow Cryptography） 混沌密码（Chaos Cryptography） 图视密码(Visual Cryptography)这些都还处于预研阶段，特别是其安全性和可靠性需要研究，离实用尚有距离。,2018/2/4,27,1. 加密和解密,量子密码装置一般采用单个光子实现，根据海森堡的测不准原理，测量这一量子系统会对该系统产生干扰并且会产生出关于该系统测量前状态的不完整信息。窃听一量子通信信道就会产生不可避免的干扰，合法的通信双方则可由此而察觉到有人在窃听。,2018/2/4,28,1. 加密和解密,量子密码术利用这一效应，使从未见过面且事先没有共享秘密信息的通信双方建立通信密钥，然后再采用shannon已证明的是完善保密的一次一密钥密码通信，即可确保双方的秘密不泄漏。,2018/2/4,29,1. 加密和解密,量子密码学达到了经典密码学所无法达到的两个最终目的:(1)合法的通信双方可察觉潜在的窃听者并采取相应的措施；(2)使窃听者无法破解量子密码，无论企图破译者有多么强大的计算能力。量子密码术已被引入了计算机科学和物理学的最新前沿，量子密码学正在以很快的速度走向实际应用。,2018/2/4,30,1. 加密和解密,量子密码学主要应用在下述几方面：公共决定。量子密码除了可用于保密通信外，还可在保护专用信息的同时将这些信息用于作出公共决定。在约会问题中，如果并且仅仅两个人互相喜欢时，他们才寻找一种决定约会时间的方式，而用不着泄漏任何详细的信息；如果两个人中的a喜欢b而b不喜欢a，则b就用不着去弄清楚a是否喜欢自己而放弃约会，另一方面，a则不可避免地会了解到b不喜欢自己。,2018/2/4,31,1. 加密和解密,量子密码学主要应用在下述几方面：量子密钥的分配和存储。消息认证。量子密码术也可用于证明一条消息确是出自某人且在传送过程中未被改动过。比特承诺(bit commitment)。量子密码术还可用于比特承诺，可用来得到零知识证明。,2018/2/4,32,1. 加密和解密,阿兰图灵图灵1912年6月23日在伦敦出生，父亲是英国殖民地印度南部的行政官员。图灵出生后不久他父亲重新回到印度，十五个月后他的母亲也离开英国返回印度，把图灵一个人留在伦敦，由保姆和朋友抚养长大，一直到了图灵上寄宿学校的年纪。,2018/2/4,33,1. 加密和解密,14岁的图灵进入了雪伯恩(Sherborne)学校就读。在学校里他给人的印象是个爱害羞，做事笨手笨脚的男孩，但是在自然科学方面充满才华。1931年图灵进入剑桥大学国王学院。当时在剑桥的贝特朗罗素等著名的逻辑学家。在这种环境下，图灵作出了他一生中最重要的科学贡献，在他著名的论文论可计算数中，他提出了日后以他名字命名的虚拟计算机器图灵机。,2018/2/4,34,1. 加密和解密,1933年他受代码及加密学校的邀请成为一个密码分析专家。在分析了以前大量德国电文后，图灵发现许多电报有相当固定的格式，他可以根据电文中无关的内容信息来推断出一部分电文的内容。比方说，德国人每天的天气预报总在早上六点左右发出，要是在六点零五分截获了一份德国电报，它里面八成有Wetter这个词，也就是德文中的“天气”。,2018/2/4,35,1. 加密和解密,图灵甚至能相当准确地知道这个词具体在密文的哪个位置。这就使得图灵想到了用“候选单词”这一方法来破译ENIGMA电文。,2018/2/4,36,阿兰图灵,2018/2/4,37,2018/2/4,38,2018/2/4,39,2018/2/4,40,2018/2/4,41,Phaistos圆盘，直径约为160mm的Cretan -Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。,2018/2/4,42,二战中美国陆军和海军使用的条形密码设备M-138-T4。根据1914年Parker Hitt的提议而设计。25个可选取的纸条按照预先编排的顺序编号和使用，主要用于低级的军事通信。,2018/2/4,43,Kryha密码机 大约在1926年由Alexander vo Kryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。,2018/2/4,44,哈格林(Hagelin)密码机C-36由Aktiebolaget Cryptoeknid Stockholm于1936年制造，密钥周期长度为3,900,255。,2018/2/4,45,M-209是哈格林对C-36改进后的产品，由Smith Corna负责为美国陆军生产。它的密码周期达到了101,105,950。,2018/2/4,46,转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1944年装备德国海军，据说英国从1942年2月到12月都没能解读德国潜艇的信号。,2018/2/4,47,英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,2018/2/4,48,在线密码电传机Lorenz SZ 42，大约在1943年由Lorenz A.G制造。英国人称其为“tunny”，用于德国战略级陆军司令部。SZ 40/SZ 42加密因为德国人的加密错误而被英国人破解，此后英国人一直使用电子COLOSSUS机器解读德国信号。,2018/2/4,49,2018/2/4,50,日本制造的转动式密码机。,2018/2/4,51,1. 加密和解密,与加密有关的法规中华人民共和国保守国家秘密法计算机信息系统国际联网保密管理规定（国家保密局发布） 商用密码管理条例中华人民共和国国务院令第273号,自1999年10月7日起实行。,2018/2/4,52,1. 加密和解密,我国商用密码管理的原则 :密码机进、出口要报经国家密码管理委员会审批。 中共中央办公厅在1996年27号文中，明确了我国发展和管理商用密码实行“统一领导、集中管理、定点研制、专控经营、满足使用”的20字方针。,2018/2/4,53,1. 加密和解密,密码学(Cryptography)一词来源于古希腊的Crypto和Graphein，意思是“密写”。密码学是以认识密码变换的本质、研究密码保密与破译的基本规律为对象的学科。现代密码学的学科体系主要包括：密码编码学和密码分析学。,2018/2/4,54,1. 加密和解密,密码编码学：研究密码变化的规律并用于编制密码以保护秘密信息的科学。密码分析学：研究密码变化的规律并用于密码以获取信息情报的科学也叫密码破译学。,2018/2/4,55,1. 加密和解密,现代密码学除了包括以上两个主要学科外，还包括近几年才形成的新分支密码密钥学。密钥管理是一种规程，它包括密钥的产生、分配、存贮、保护、销毁等环 节，在保密系统中至关重要。,2018/2/4,56,加密器E,解密器D,接收者,发送者,明文m,明文m,密文c,c = E(m)m = D(c) m = D(c) = D(E(m) )m = m,1. 加密和解密,2018/2/4,57,1. 加密和解密,加密器和解密器的特点：(1)可以采用硬件或软件构成。(2)加密器和解密器有一组数学算法构成。(3)在一个加密、解密过程中，加密器和解密器的构成可以相同，也可不同。(4)加密器和解密器需要保密。(不利!）,2018/2/4,58,1. 加密和解密,加密器和解密器的特点：(4)加密器和解密器数学算法复杂，无法经常变更。(5)每次加密产生的密码相同。 (不利!）(6)长期使用，加密器和解密器的数学算法可能被猜破。 (不利!）,2018/2/4,59,1. 加密和解密,1.如何使用相同的加密系统生成不同的密码？2.加密器和解密器的结构和算法是否可以公开？,请考虑一下问题：,2018/2/4,60,c = Ek1(m)m = Dk2(c) m = Dk2(c) = Dk2(Ek1(m) )m = m,加密器E k1,解密器D k2,接收者,发送者,明文m,明文m,密文c,k1,k2,引入密钥,1. 加密和解密,2018/2/4,61,1. 加密和解密,引入密钥：密钥是一个控制参数；密钥k1、k2可相同或不同；每次加密可使用不同的密钥；密钥空间很大，难以猜中；,2018/2/4,62,1. 加密和解密,密码分析者：正常解密的必要条件：掌握解密器和密钥；密码可能被猜中；,2018/2/4,63,1. 加密和解密,1.加密方如何得到密钥？2.解密方如何得到密钥？,2018/2/4,64,1. 加密和解密,2018/2/4,65,1. 加密和解密,密码体系的评价：保密强度密钥的长度算法的复杂度差错的传播性加密后信息长度的增加程度,2018/2/4,66,1. 加密和解密,在不同的层次上对网络数据加密对网络数据加密不但可以防止非授权用户的搭线窃听和入网，而且也是对付恶意软件的有效方法之一。一般的数据加密可以在通信的三个层次来实现: 链路加密节点加密端到端加密,2018/2/4,67,1. 加密和解密,链路加密,节点加密,端到端加密,2018/2/4,68,1. 加密和解密,1.链路加密(又称在线加密)对于在两个网络节点间的某一通信链路, 链路加密能为网上传输的数据提供安全保证。链路加密是使所有消息在被传输之前进行加密, 在每一个节点对接收到的消息进行解密。然后先使用下一个链路的密钥对消息进行加密, 再进行传输。,2018/2/4,69,1. 加密和解密,由于在每一个中间传输节点消息均被解密后重新进行加密，因此包括路由信息在内的链路上的所有数据均以密文形式出现。这样，链路加密就掩盖了被传输消息的源点与终点。链路加密通常用在点对点的同步或异步线路上，它要求先对在链路两端的加密设备进行同步，然后使用一种链模式对链路上传输的数据进行加密。这就给网络的性能和可管理性带来了副作用。,2018/2/4,70,1. 加密和解密,在一个网络节点, 链路加密仅在通信链路上提供安全性, 消息以明文形式存在, 因此所有节点在物理上必须是安全的, 否则就会泄漏明文内容。保证每一个节点的安全性需要较高的费用。,2018/2/4,71,1. 加密和解密,2.节点加密节点加密能给网络数据提供较高的安全性。通信链路上为传输的消息在中间节点先对消息进行解密,然后进行加密。因为要对所有传输的数据进行加密, 所以加密过程对用户是透明的。,2018/2/4,72,1. 加密和解密,节点加密不允许消息在网络节点以明文形式存在,这一过程是在节点上的一个安全模块中进行。节点加密要求报头和路由信息以明文形式传输, 以便中间节点能得到如何处理消息的信息。因此这种方法对于防止攻击者分析通信业务是脆弱的。,2018/2/4,73,1. 加密和解密,3.端到端加密数据在从源点到终点的传输过程中始终以密文形式存在。采用端到端加密时消息在被传输时到达终点之前不进行解密，因为消息在整个传输过程中均受到保护，所以即使有节点被损坏也不会使消息泄露。,2018/2/4,74,1. 加密和解密,端到端加密系统的价格便宜些, 可靠性高,更容易设计、实现和维护。端到端加密避免了加密系统所固有的同步问题, 因为每个报文包均是独立被加密的, 所以一个报文包所发生的传输错误不会影响后续的报文包。从用户对安全需求的直觉上讲,端到端加密更自然些。,2018/2/4,75,1. 加密和解密,单个用户可能会选用这种加密方法,以便不影响网络上的其他用户,此方法只需要源和目的节点是保密的即可。这种加密方法不能掩盖被传输消息的源点与终点, 因此它对于防止攻击者分析通信业务是脆弱的。,2018/2/4,76,1. 加密和解密,2018/2/4,77,2. 对称算法和公开密钥算法,1 对称算法加密密钥可以从解密密钥中推算出来，或加密密钥与解密密钥相同。加密、解密双方在使用加密通信之前商定密钥。称为秘密密钥算法或单密钥算法。两类：序列密码(流密码)，分组密码。,2018/2/4,78,2. 对称算法和公开密钥算法,序列密码（简单异或） m=01010110 (明文） k=10101011 (密钥） c=11111101 (密文) k=10101011 (密钥） m=01010110 (明文）,2018/2/4,79,2. 对称算法和公开密钥算法,密钥流发生器：周期应足够长，250 。基于反馈移位寄存器。运算速度快，适合干线信息加密。,2018/2/4,80,2. 对称算法和公开密钥算法,分组密码体制：分组密码是将明文分成固定长度的组(块)，用同一密钥对每一块加密，输出也是固定长度的密文。易于解决密码同步问题，适合数据库加密和分组交换网的数据包加密。DES,IDEA,AES,2018/2/4,81,2. 对称算法和公开密钥算法,公钥密码算法(非对称算法)如将一个加密系统的加密密钥和解密密钥分开，加密和解密分别由两个密钥来实现，并且由加密密钥推导出解密密钥(或由解密密钥推导出加密密钥)在计算上是不可行的，一般系统是采用公钥密码体制。公钥密码体制的每一个用户都有一对选定的密钥，一个可以公开，一个由用户秘密保存。公钥密码体制的出现是对现代密码学的一个重大突破，它给计算机网络的安全带来了新的活力。,2018/2/4,82,2. 对称算法和公开密钥算法,20世纪70年代，斯坦福大学提出通过交换公开信息建立一个共享的秘密的方案，即Diffie-Hellmem方案。DH解决了一个密钥共享问题。RSA密码系统是较早提出的一种公开钥密码系统。1978年，美国麻省理工学院 的Rivest,Shamir和Adleman在题为获得数字签名和公开钥密码系统的方法的论文中提出了基于数论的非对称密码体制，称为RSA密码体制。,2018/2/4,83,2018/2/4,84,2018/2/4,85,2018/2/4,86,2. 对称算法和公开密钥算法,1978年RSA算法发表，RSA是三位发明者的名字的首字母。RSA是建立在“大整数的素因子分解是困难问题”基础上的，是一种分组密码体制。1985年，Washington大学和IBM Watson研究中心提出“椭圆曲线”算法。,2018/2/4,87,2. 对称算法和公开密钥算法,数字签名技术与数字化签名技术是两种截然不同的安全技术。数字签名使用了信息发送者的私有密钥变换所需传输的信息。对于不同的文档信息，发送者的数字签名并不相同。没有私有密钥,任何人都无法完成非法复制。数字签名是通过一个单向函数对要传送的报文进行处理得到的，用以认证报文来源并核实报文是否发生变化的一个字母数字串。,2018/2/4,88,2. 对称算法和公开密钥算法,数字签名可以解决否认、伪造、篡改及冒充等问题。发送者事后不能否认发送的报文签名,接收者能够核实发送者发送的报文签名,接收者不能伪造发送者的报文签名,接收者不能对发送者的报文进行部分篡改,网络中的某一用户不能冒充另一用户作为发送者或接收者。数字签名的应用范围十分广泛，凡是需要对用户的身份进行判断的情况都可以使用数字签名。,2018/2/4,89,2. 对称算法和公开密钥算法,解密者,密钥源,加密者1,一对密钥,但彼此不同,不能相互代替.,加密者2,加密者3,加密过程,一把钥匙公开,称为“公钥”.,另一把钥匙保密,称为“私钥”.,PK,SK,2018/2/4,90,2. 对称算法和公开密钥算法,加密者,密钥源,解密者1,一对密钥,但彼此不同,不能相互代替.,解密者2,解密者3,数字签名,一把钥匙公开,称为“公钥”.,另一把钥匙保密,称为“私钥”.,PK,SK,2018/2/4,91,3. 随机序列与随机数,密码学者定义“随机”的含义是：随机值仅是通过了随机性统计检查的数集，并且是不可重复的。随机数的重要性真随机数序列和伪随机数序列随机数发生器,2018/2/4,92,3. 随机序列与随机数,伪随机数发生器：可以使用算法生成伪随机。可以使用种子(seed)的输入来改变输出。可以用时间、移动鼠标等来产生种子。,2018/2/4,93,3. 随机序列与随机数,伪随机数序列要满足以下特征：不可预测性随机性,2018/2/4,94,4. 密码分析,攻击密文的方法：(1)惟密文分析：只有一些密文(2)已知明文攻击：有一些密文和对应的明文(3)选择明文攻击：可选择被加密的明文，便于发现规律。(4)选择密文攻击：有机会接触密码机(5)蛮力攻击，穷举密钥。,2018/2/4,95,4. 密码分析,攻击密钥强力攻击：测试每一个密钥，直到找到正确的密钥。重构种子重构密钥。密钥长度：密钥长度每增加一位，密钥数量增加一倍。,2018/2/4,96,4. 密码分析,2018/2/4,97,4. 密码分析,攻击算法(1)找到算法的弱点(2)重构算法度量攻破消息所花费的时间(1)选择一个不弱的算法；(2)加长密钥。(3)增加攻破消息所花费的时间。,2018/2/4,98,4. 密码分析,度量攻击的复杂性： (1) 数据复杂性；(2) 处理复杂性；(3) 存储需求。攻击的复杂性取这三个因数的最小化，有些攻击包括这三种复杂性的折中,存储需求越大，攻击可能越快。,2018/2/4,99,4. 密码分析,密码体系性质(1)从密文恢复明文应是难事(2)从密文计算出部分信息应是难事(3)从密文探测出简单却有用的事实应是难事,2018/2/4,100,4. 密码分析,攻击效果完全攻破部分攻破密文识别实例推导信息推导,2018/2/4,101,4. 密码分析,评价密码体系安全性(1)无条件安全，具有完善保密性。如不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的，一次一密密码本是无条件安全的，所有其它的密码系统在唯密文攻击中都是可破的(蛮力攻击)。,2018/2/4,102,4. 密码分析,(2)计算安全性。密码学更关心在计算上不可破译的密码系统。(3)可证明安全性。把密码体制安全性归约为某个数学难题，如大素数分解。,2018/2/4,103,4. 密码分析,(4)算法的安全性密码算法具有不同的安全等级：破译算法的代价大于加密数据的价值；破译算法所需的时间大于加密数据保密的时间；用单密钥加密的数据量小于破译算法需要的数据量。,2018/2/4,104,4. 密码分析,仅当密钥至少和明文一样长时才无条件安全(Shannon理论)。密码学更关心在计算上不可破译的密码系统。如果一个算法用现在或将来使用可得到的资源都不能破译，这个算法则被认为在计算上是安全的。,2018/2/4,105,5. 密码协议,密码协议，又称安全协议。特点：密码协议是一个有序的过程；密码协议至少有两个参与者；密码协议需要某项任务。用于消息认证，数字签名等。,2018/2/4,106,5. 密码协议,(1)密钥建立协议：建立密码协议的目的在两个或多个实体之间建立会话密钥，可通过一个可信服务器向用户分发密钥(密钥分发协议)，也可由两用户协商产生密钥。(2)认证协议认证协议防止假冒攻击可以对密码算法、协议中的密码技术、协议本身进行攻击。Kerberos协议,SSL协议，SET协议。,2018/2/4,107,4.2 传统密码学1. 置换密码,置换密码，换位密码换位密码是采用移位法进行加密。它把明文重新排列，本身不变，但位置变了。(1)列换位法(2)矩阵换位法,2018/2/4,108,1. 置换密码,(1)列换位法例：P=WHAT YOU CAN LEARN FROM THIS BOOK分组 W H A T Y O U C A N L E A R N F R O M T H I S B O O K * * * EK(P)=WOLFHOHUERIKACAOS*TARMB*YNNTO* K = 5,2018/2/4,109,1. 置换密码,2)矩阵换位法例 P = ENGINGEERING3*4矩阵: 1 2 3 4 E N G I N G E E R I N G,2018/2/4,110,1. 置换密码,(2)矩阵换位法例 P = ENGINGEERING给定置换矩阵: f = 1 2 3 4 2 4 1 3,2018/2/4,111,1. 置换密码,(2)矩阵换位法结果： 1 2 3 4 N I E G E R N E N I G P=NIEGERNEN IG,2018/2/4,112,2. 代换密码,代换密码，替代密码：将明文中的每一个字符用密文中的另一个字符代换，代换后各字符位置不变。(1)简单代替密码(2)多字母替代密码(3)多表替代密码(4)多名码替代密码(5)多字母组代替密码,2018/2/4,113,2. 置换密码,(1)简表代替密码(恺撒密码)明文中的一个字母用相应的一个密文字母代替。是一种典型的凯萨密码，也叫循环移位密码。 F(a)=(a+k) mod n A表示明文字母， n为字符集中字母的个数， K为密钥。,2018/2/4,114,2. 置换密码,例:字母表,2018/2/4,115,2. 置换密码,设:K=3 明文P=computer system 则F( c ) = ( 3+3 ) mod 26 = 6 = fF( o ) = ( 15+3 ) mod 26 = 18 = rF( m ) = ( 13+3 ) mod 26 = 16 = p密文:C = Ek(P) = frpsxr.特点:简单,安全性差。,2018/2/4,116,2. 置换密码,(2)多表替代密码又叫维吉尼亚密码。这种替代是循环的使用有限个字母来实现替代的一种方法。例： P=HOWAREYOU K=YOURYOURY C=FCQRPSSFS,2018/2/4,117,2. 置换密码,维吉尼亚体制是最古老而且最著名的多表密码体制之一，它以法国密码学家Blaise deVigenere(1523-1596)命名。与CAESAR密码体制相似，其密钥是逐步变化的。一般是用维吉尼亚方阵来进行加密和解密的。每列都可以看成是一个CAESAR体制。加密方阵作为多表体制的基础，它具有多样性，即可选择其它容易记忆的方阵。这里值得一提的就是Beaufort方阵，它的行是维吉尼亚方阵行的逆序。,2018/2/4,118,2. 置换密码,最著名的转轮密码机是德国人舍尔比乌斯设计的恩尼格马机和瑞典人哈格林设计的哈格林密码机(美国军方称为M-209)。德国人使用的恩尼格马机共有5个转轮，可选择3个使用。波兰的密码研究人员最早破译了德国的恩尼格马，并将方法提供给了英国人。M-209是二战中美军的主要加密设备，它是一种齿数可变的齿轮装置。该设备的各个部件互相作用，产生一串互不相关的长周期密钥。,2018/2/4,119,2. 置换密码,1854年查尔斯.惠斯通(CharlesWheatstone)发明了一种特殊的双叶双码代替密码，他的朋友莱昂.普莱弗尔(Lyon Playfair)将其推荐给政府和军界的高层人士。这种体制的首次使用是在克里米亚战争期间，正式报道的使用是在Boer战争中，其名称也就以Playfair命名。军队很看重它的一点就是此方法既不需要表也不需要器械，易作为战地密码。英国军队差不多用了一个世纪，而且保证它一直是保密的。然而在一次世界大战中的1915年，德国人将其破译了。,2018/2/4,120,2. 置换密码,Hill密码体制中明文空间和密文空间是相同的。首先对字母集中的字母进行编号，后面所有的运算都要模26。然后选择一个可逆的d维方阵M，其元素是介于0和25之间的整数。加密过程为MP=C，当然这里的P和C都是d维列向量。更确切地说，每个d元明文字符定义了列向量P，分量是d元明文字符的编号。计算得到的列向量C再被译为d元密文字符。,2018/2/4,121,2. 置换密码,Vigenere是典型的多表密码。,2018/2/4,122,3. 一次一密密码,一次密码本(1917年)，AT&T发明。一次密码本是一个大的不重复的真随机密钥字母集，它写在几张纸上，被粘成一个密码本。每个密钥仅对一个信息使用一次。解密者使用完全一样的密码本解密。,2018/2/4,123,3. 一次一密密码,例 明文P=ONE TIME PAD 密码本中选择一页作为密钥： k=TBF RGFA RFM则：O+T mod(26) = I N+B mod(26) = P E+F mod(26) = K密文: IPKLPSFHGQ,2018/2/4,124,4.3 分组密码1. 代替-置换网络,现代与古典密码学采用的基本思想相同：替换与变位。古典：算法简单，长密钥。现代：算法复杂。 Shannon提出通过“乘积”来组合密码体制的思想。采用m个函数f1,f2,fm的复合，每个fi可能是一个代换或置换，破坏对密码的各种统计分析。对DES、AES有深刻影响。,2018/2/4,125,1. 代替-置换网络,混乱和扩散扩散：将明文的统计特征扩散到密文中去，使明文的每一位影响密文中多位的值。混乱：使明文、密文之间的统计关系变得尽可能复杂。混乱和扩散是分组密码的本质特征和设计基础。,2018/2/4,126,1. 代替-置换网络,其它原则：分组长度应足够大，防止穷举搜索。但分组越大，加密速度越慢。密钥应足够长。常见的乘积密码是迭代密码，典型的迭代密码定义了一个论函数和一个密钥编排方案，对明文进行多次迭代。,2018/2/4,127,1. 代替-置换网络,设K是定长主密钥，可生成Nr轮个轮密钥(子密钥)Ki。轮函数g以轮密钥Ki和当前状态wi-1为输入。初始状态w0被定义为明文x，密文y定义为经过Nr轮后的状态wNr。加密过程： w0 = x wi = g(wi-1 ,Ki ) ，i = 1,2, Nr,2018/2/4,128,1. 代替-置换网络,加密过程： w0 = x wi = g(wi-1 ,Ki ) ，i = 1,2, Nr解密过程： wNr = y wi-1 = g-1(wi ,Ki )，i= Nr, Nr-1 , ,1,2018/2/4,129,1. 代替-置换网络,代替-置换网络(SPN)的轮函数包括三个变换：置换(换位)代换(代替)密钥混合S盒(代替)，基本性质是一个非线性映射。为使解密网络与加密网络相同，最后一轮没有置换操作。,2018/2/4,130,1. 代替-置换网络,2018/2/4,131,1. 代替-置换网络,P盒 用P盒构成的S盒P盒：实质上是置换(换位)。S盒：实质上是若干比特的替换(代替)。,2018/2/4,132,2018/2/4,133,2. 数据加密标准DES,IBM公司W.Tuchman和C.Meyer 1971-72年研制LUCIFER方案。美国商业部的国家标准局NBS1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中选定了IBM的LUCIFER方案。1976年11月美国政府采用DES，随后美国国家标准局和美国国家标准协会ANSI承认。,2018/2/4,134,2. 数据加密标准DES,1977年1月以数据加密标准DES(Data Encryption Standard)的名称正式向社会公布，1977年7月15日生效。DES衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等。,2018/2/4,135,2. 数据加密标准DES,1977年人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密，而且需要12个小时的破解才能得到结果。1997年起RSA公司发起了一个称作“向DES挑战”的竞技赛。1997年1月，用了96天时间成功地破解了用DES加密的一段信息；一年后，这一记录41天；1998年7月，DES挑战赛把破解DES的时间缩短到了只需56个小时；后又把破解DES的时间缩短到了只需22.5小时。,2018/2/4,136,2. 数据加密标准DES,DES使用56位密钥，对64位数据块进行16轮加密。加密后的密文是64位数据块。每轮编码时，一个48位的轮密钥由56位密钥完整密要得出。早期是硬件实现的。DES是分组密码，也基于Feistel网络结构。,2018/2/4,137,2. 数据加密标准DES,取长度为n(64位)的分组，分为长度为n/2的两部分：L和R (左右，各32位)。定义一个迭代的分组密码算法，其第i轮的输入取决于前一轮的输出： L(i) = R(i-1) R(i) = L(i-1) f(R(i-1),K(i) K(i)是第i轮子密钥，f是轮函数。,2018/2/4,138,2. 数据加密标准DES,加密：L(i) = R(i-1) R(i) = L(i-1) f(R(i-1),K(i)逆过程： R(i-1) = L(i) L(i-1) = R(i) f(R(i-1),K(i) = R(i) f(L(i),K(i),2018/2/4,139,2. 数据加密标准DES,设：m表示信息块，k表示密钥： m = m1,m2,m64 i =1,2,64 k = k1,k2,k64 i =1,2,64其中k8, k16, k24, k32, k40, k48, k56, k64,是奇偶校验位。56位密钥+8位校验位=64位。,2018/2/4,140,2. 数据加密标准DES,加密算法 c = Ek(m) = IP-1T16T15T1IP(m)其中IP为初始置换，IP-1是IP的逆， i = 1,2,16是一系列的变换。解密算法 m = Ek-1(c) = Ek-1(Ek(m) = IP-1T1T2T16IP(c),2018/2/4,141,2. 数据加密标准DES,DES的每一密文比特是所有明文比特和所有密钥比特的复合函数。使明文与密文之间，密钥与密文之间不存在相关性，提高了抗攻击能力。,2018/2/4,142,2. 数据加密标准DES,2018/2/4,143,2. 数据加密标准DES,Feistel Network,2018/2/4,144,2. 数据加密标准DES,(1)初始变换这是移位操作，用IP表示。移位时不用密钥，仅对64位明文操作。输入64个二进制位明码文数据区组： 输入64位明文分组：m= m1m2m64 按初始换位表IP进行换位，得到区组 B（0）：B（0）=b1(0)b2(0)b64(0)= m58m50m7记成L0、R0左右两部分。,2018/2/4,145,2. 数据加密标准DES,输入（64位）,58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7,输出（64位）,L0（32位）,R0（32位）,初始变换IP,2018/2/4,146,2. 数据加密标准DES,(2)选择运算(扩展置换)E选择运算E，输入32位数据，产生48位输出。设：B(i) = b1(i) b2(i) b64(i)是第i+1次迭代的64位输入区组，将其分为左右两部分，每部分32位： L(i) = l1(i) l2(i) l32(i) = b1(i) b2(i) b32(i) R(i) = r1(i) r2(i) r32(i) = b33(i) b34(i) b64(i),2018/2/4,147,2. 数据加密标准DES,把32位数R（i）视为由8个4位二进制的块组成:,r1(i)r2(i)r3(i)r4(i) r5(i)r6(i)r7(i)r8(i)r29(i)r30(i)r31(i)r32(i),2018/2/4,148,2. 数据加密标准DES,把它们再扩充为8个6位二进制的块(左右各增加一列);用E(R（i）)表示这个变换，称为选择函数E。,r32(i)r1(i)r2(i)r3(i)r4(i) r5(i)r4(i)r5(i)r6(i)r7(i)r8(i) r9(i)r28(i)r29(i)r30(i)r31(i)r32(i) r1(i),2018/2/4,149,2. 数据加密标准DES,L/R,32位,32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1,选择运算E,选择运算E的结果,48位,2018/2/4,150,2. 数据加密标准DES,(3)使用密钥在第i+1次迭代中，由56位密钥生成的48位密钥: K（i+1）=k1(i+1)k2(i+1)k48(i+1) 与E(R（i）)按位异或； 输出仍是48位，共8行、每行6位。,2018/2/4,151,2. 数据加密标准DES,Z 1 ：r32(i)k1(i+1) r1(i)k2(i+1) r5(i)k6(i+1)Z 2 ：r4(i)k7(i+1) r5(i)k8(i+1) r9(i)k12(i+1)Z 3 ：Z 4 ：Z 5 ：Z 6 ：Z 7 ：Z 8 ：r28(i)k43(i+1) r29(i)k44(i+1) r1(i)k48(i+1),2018/2/4,152,2. 数据加密标准DES,(4)选择函数(S-盒)(代替) S1,S2.S8选择函数，其功能是把6bit数据变为4bit数据。Si(i=1,2.8)的功能表:,2018/2/4,153,2. 数据加密标准DES,2018/2/4,154,2. 数据加密标准DES,S1: 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,S2: 15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,0,14,7,