第二讲 密码学的基础知识主讲人：谷利泽Email：glz_bupt263.netTel: 010-62283134上讲的主要内容l信息安全的重要性(理解)l信息安全的目标（机密性、完整性、认证性、不可否认性）l信息安全的内容(了解)l密码学与信息安全（核心的技术手段）l密码学的含义（密码编码学和密码分析学）l现代密码学的主要内容2本讲的主要内容l密码学的发展史l密码系统的构成l密码分析学l密码系统的安全性3密码学发展简史密码学的应用历史可以追溯到几千年前，可以说，自从人类社会有了战争，就有了保密通信，也有了密码的应用。不过在1949年之前，密码的研究与应用一直没有形成一门科学，仅是一门文字变换技术，因而只能称为密码技术，简称密码术。1949年，Shannon发表了“保密系统的通信理论（Communication Theory of Secrecy Systems）”一文，为密码学的发展奠定了坚实的数学基础，于是，密码技术的研究迈上了科学的轨道，因而从严格的意义上讲，此后的密码技术才真正称得上密码学。4密码学的发展阶段l古典密码时期l近代密码时期l现代密码时期密码学发展大致分为三个阶段：密码学发展大致分为三个阶段：5古典密码时期l起始时间：从古代到19世纪末，长达几千年。l密码体制：纸、笔或者简单器械实现的替代及换位，是一种艺术（富有创造性的方式、方法）。l技术工具：手工。l通信手段：信使。6近代密码时期l起始时间：从20世纪初到20世纪50年代，即一战及二战时期。l密码体制：手工或电动机械实现的复杂的替代及换位，仍是一门艺术。l技术工具：机械。l通信手段：电报通信。7现代密码时期l起始时间：从20世纪50年代至今。l密码体制：分组密码、序列密码以及公开密钥密码，有坚实的数学理论基础。成为一门科学。l技术工具：计算机。l通信手段：无线通信、有线通信、计算网络等8现代密码学的重要事件l1949年Shannon发表题为保密系统的通信理论，为 密码系统建立了理论基础，从此密码学成了一门科学。（ 第一次飞跃）l1976年后，美国数据加密标准（DES）的公布使密码学的 研究公开，密码学得到了迅速发展。l1976年，Diffe和Hellman发表了密码学的新方向，提 出了一种新的密码设计思想，从而开创了公钥密码学的新 纪元。 （第二次飞跃）l1978年由Rivest、Shamire和Adleman 首先提出第一个 实用的公钥密码体制RSA，使公钥密码的研究进入了快速 发展阶段。9安全通信的实现过程 l通信的参加者 ；l通信的信道；l密码系统；10通信的参加者l实体或参与方：指接受、发送或操作信息的某人或某物。l发方：指在双方通信中作为信息的合法传送者的实体。l收方：指在双方通信中作为信息的预定接受者的实体。l敌手：指在双方通信中既非发方又非收方的实体，它试图攻击保证发方和收方信息安全的服务。与它同义的称呼有敌人、攻击者、对手、搭线者、窃听者、入侵者、闯入者等，敌手常常企图扮演合法发方或者收方的角色。11信道l信道：指将信息从一个实体传送到另一个实体的一种方式。l信道分为不安全信道和安全信道。l不安全信道：指除了信息的预定接受方外，它方也能进行重组、删除、插入和读取操作。l安全信道：指敌手对其没有重组、删除、插入和读取信息能力的信道。安全信道可以通过物理方式达到，也可通过密码技术达到（逻辑方式）。 12密码系统（体制）一个密码系统（体制）至少由明文、密文、加密算法和解密算法、密钥五部分组成。l信息的原始形式成为明文（Plaintext）。l经过变换加密的明文称为密文（Ciphertext)。l对明文进行编码生成密文的过程称为加密（Encryption） ， 编码的规则称为加密算法。l将密文恢复出明文的过程称为解密（Decryption），解密 的规则称为解密算法。l密钥（Key）是唯一能控制明文与密文之间变换的关键， 分为加密密钥和解密密钥。13密码体制的分类l对称密码体制（Symmetric Syetem）加密密钥和解密密钥相同，或者虽然不相同，但由其中的任意一个可以很容易地推出另一个，又称传统密码体 制、秘密密钥体制或单密钥体制。 l 非对称密码体制（Asymmetric System） 加密密钥和解密密钥不相同，并且从一个很难推出另一个，又称公开密钥体制。公开密钥体制用一个密钥进 行加密，而用另一个进行解密。其中一个密钥可以公开 ，成为公开密钥(pulic key)，简称公钥；另一个密钥 成为私人密钥（private key）,简称私钥。14密码分析学l密码分析学：研究如何分析或破解各种密码编码 体制的一门科学。l密码分析俗称为密码破译，是指在密码通信过程中，非授权者在不知道解密密钥和通信者所采用 的密码体制细节的条件下对密文进行分析，试图 得到明文或密钥的过程。l解密和密码破译都是设法将密文还原成明文的过 程，但具备的条件是不同的。15密码破译方式l唯密文攻击 （ciphertextonly attack）l已知明文攻击（knownplaintext attack）l选择明文攻击（chosenplaintext attack）l选择密文攻击（chosenciphertext attack）16唯密文攻击密码破译者除了拥有截获的密文，以及对密码体制和密文信息的一般了解外，没有什么其它可以利用的信息用于破译密码。密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其它被加密的信息。在这种情况下进行密码破译是最困难的，经不起这种攻击的密码体制被认为是完全不保密的。17已知明文攻击密码破译者不仅掌握了相当数量的密文，还有一些已知的明-密文对（通过各种手段得到的）可供利用。密码分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的信息进行解密。现代的密码体制（基本要求）不仅要经受得住唯密文攻击，而且要经受得住已知明文攻击。18选择明文攻击密码破译者不仅能够获得一定数量的明-密文对，还可以用它选择的任何明文，在同一未知密钥的情况下能加密相应的密文。这比已知明文攻击更有效，因为密码分析者能选择特定的明文去加密并可能产生更多关于密钥的信息。密码分析者的任务是推出用来加密信息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的信息进行解密。密码破译者暂时控制加密机。19选择密文攻击密码破译者能选择不同的被加密的密文，并还可得到对应的解密的明文，密码分析者的任务是推出密钥及其它密文。密码破译者暂时控制解密机。这种攻击主要用于公开密钥算法。20密码分析者攻击密码体制的方法l穷举攻击：密码分析者通过试遍所有的密钥来进行破译，显然，可以通过增大密钥量来对抗穷举攻击。l统计分析攻击：密码分析者通过分析密文和明文的统计规律来破译密码。对抗统计分析攻击的方法是设法使明文的统计特征与密文的统计特征不一样。l解密变换攻击：密码分析者针对加密变换的数学基础，通过数学求解的方法来设法找到相应的解密变化。为对抗这种攻击，应该选用具有坚实的数学基础和足够复杂的加密方法。21柯克霍夫（Kerckhoffs）原则密码学领域存在一个很重要的事实：“如果许多聪明人都不能解决的问题，那么它可能不会很快得到解决。”这暗示很多加密算法的安全性并没有在理论上得到严格的证明，只是这种算法思想出来以后，经过许多人许多年的攻击并没有发现其弱点，没有找到攻击它的有效方法，从而认为它是安全的。密码系统中的算法即使为密码分析者所知，也无助于用来推到出明文或密钥。也就是说，密码系统的安全性不应取决于不易改变的算法，而应取决于可随时改变的密钥。22破译算法的分类（递减）l全部破译密码分析者找到密钥Key。l全盘推导密码分析者找到一个代替算法A，在不知道密钥Key的情况下，等价于Dkey(C)=P。l实例（或局部）推导密码分析者从获的密文中找出明文。l信息推导密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个位、有关明文格式的信息等。23密码体制的安全性（无条件）l不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；l具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统；24“一次一密”密码系统不失一般性，假设明文、密文、密钥都是二元数字序列，即明文m=(m1,m2, ,mL)密钥k=(k1,k2, ,kR)密文c=(c1,c2, ,cS)令L=R=S，并假定明文空间与密钥空间统计独立，且密钥k为一随机数字序列。定义加密变换为：定义解密变换为：因此，解密变换确实可以还原加密过的密文。可以证明，上面的密码体制是无条件安全的。25密码体制的安全性（有条件）l计算上的安全计算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。l有条件上的安全破译算法的代价大于加密数据的价值破译算法所需的时间比加密数据保密的时间更长用单密钥加密的数据量比破译算法需要的数据量少的多l可证明的安全从理论上证明破译它的计算量不低于解已知难题的计算量。 26复杂性理论l计算复杂性是密码分析技术中分析计算需求和研究破译密码的固有难度的基础。密码的强度是破译该密码所用的算法的计算复杂性决定的。l算法的计算复杂性由它所需的时间和空间量级来度量，其优点是独立于所用的系统并且使人们看到时间和空间的需求随输入的规模n而增长。l通常按时间T（或空间）复杂性对算法进行分类。27算法的计算复杂性l若对某个常数t，算法的运行时间T=O(nt)，则称该算法是多项式时间的。（可解的）l若对某个常数t(1)和多项式h(n)，算法的运行时间T=O(th(n)，则称该算法是指数时间的。（难解的）28不同时间复杂度算法的时间需求量级当n增大时，算法的时间复杂性显示了算法是否实际可行方面的巨大差别。假设有一台计算机，它可以在1秒内执行106个基本操作，在输入规模n=106的条件下，下表列出了在这台机器上执行不同时间复杂性类型的算法的运行时间。算法类 型复杂度操作次 数时间需求常数的O(1)11微秒 线性的O(n)1061秒 二次方的O(n2)101211.6天 三次方的O(n3)10183200年 指数的O(2n)103010303*10301016 年 注：注：1 1年年=31536000=31536000秒秒 3*103*107 7秒，宇宙的年龄秒，宇宙的年龄10101010（2 23434）年）年 29计算机速度提高对算法处理能力的影响下表列出在计算设备处理速度提高时对不同时间复杂性算法处理能力（即在1小时内可解的问题实例的最大规模）的影响。30密码体制的基本原则l密码体制是不可破的（理论上不可破，实际上不可破）；l密码体制的安全性是依赖密钥的保密，而不是依赖于对加密体制的保密；l加密和解密算法适用于密钥空间中的所有元素；l密码体制既易于实现又便于使用。l密钥空间应足够大，使得试图通过穷举密钥空间进行搜索的方式在计算上不可行。31本讲的小结l密码学的发展史（古典密码、近代密码、现代密码）l密码系统的构成（明文、密文、密钥、加密算法、解密算法）l密码分析学（唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击）l密码系统的安全性（无条件安全、计算上的安全、有条件上的安全、可证明的安全）32谢 谢 ！33