第2章-密码学基础要点课件.ppt

1、版权所有，盗版必纠版权所有，盗版必纠 “天王盖地虎，宝塔镇河妖”大家一定在电影里看过对暗号的场面。其实，这种暗号是一种最朴素的密码。只不过这种密码过于简单，经不起密码学家的分析，非常容易破译。将密码当成一种科学来研究，就产生了密码学。 密码学源于希腊语krypts，意为隐藏的和 grphein意为 书写，传统意义上来说，是研究如何把信息转换成一种隐蔽的方式并阻止其他人得到它。密码学是信息安全的基础和核心，是防范各种安全威胁的最重要的手段。 版权所有，盗版必纠 明文：需要秘密传送的消息。 密文：明文经过密码变换后的消息。 加密：由明文到密文的变换。 解密：从密文恢复出明文的过程。 破译：非法接收

2、者试图从密文分析出明文的过程。 加密算法：对明文进行加密时采用的一组规则。 解密算法：对密文进行解密时采用的一组规则。 密钥：加密和解密时使用的一组秘密信息。版权所有，盗版必纠 密码学有悠久且多姿多彩的历史。最早的秘密书写只需纸笔，现在称为经典密码学(Classical Cryptography)。其两大类别分别为： (1). 置换加密法，将字母的顺序重新排列。 (2). 替换加密法，将一组字母换成其他字母或符号。版权所有，盗版必纠 Enigma 密码机 经典密码学现在仍未消失，常被用于考古学上，还经常出现在智力游戏之中。在20世纪早期,包括转轮机的一些机械设备被发明出来用于加密,其中最著名的

3、是用于第二次世界大战的密码机“迷”(Enigma) 版权所有，盗版必纠 Enigma 密码机 经典密码学现在仍未消失，常被用于考古学上，还经常出现在智力游戏之中。在20世纪早期,包括转轮机的一些机械设备被发明出来用于加密,其中最著名的是用于第二次世界大战的密码机“迷”(Enigma) 版权所有，盗版必纠 密码学的发展划分为3个阶段： 1. 第一阶段为古代到第一阶段为古代到1949年。年。 这一时期可以看作是科学密码学的前夜时期，这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明。 这个时期发明的密码算法在现代计算机技术条件下都是

4、不安全的。但是，其中的一些算法思想，比如代换、置换，是分组密码算法的基本运算模式。版权所有，盗版必纠 2. 第二阶段为1949年到1975年。 1949年香农发表的为私钥密码系统建立了理论基础，从此密码学成为一门科学，但密码学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研究工作进展不大，公开的密码学文献很少。 版权所有，盗版必纠 3. 第3阶段为1976年至今。 1976年Diffie 和 Hellman发表的文章“密码学的新动向”一文导致了密码学上的一场革命。他们首先证明了在发送端和接收端无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元。从此，密码开始充分发挥

5、它的商用价值和社会价值，普通人才能够接触到前沿的密码学。版权所有，盗版必纠版权所有，盗版必纠 密码员：对明文进行加密操作的人员称作密码员或加密员 （Cryptographer）。 加密算法：密码员对明文进行加密时采用的一组规则称为加密算法(Encryption Algorithm)。 接收者：传送消息的预定对象称为接收者(Receiver)。 解密算法：接收者对密文进行解密时采用的一组规则称作解密算法(dncryption algorithm)。 加密密钥和解密密钥：加密算法和解密算法的操作通常是在一组密钥（Key）的控制下进行的，分别称为加密密钥(Encryption Key)和解密密钥(D

6、ecryption key)。版权所有，盗版必纠 截收者：在消息传输和处理系统中，除了预定的接收者外，还有非授权者，他们通过各种办法，如搭线窃听、电磁窃听、声音窃听等来窃取机密信息，称其为截收者(Eavesdropper)。 密码分析：虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的明文，这一过程称为密码分析(Cryptanalysis)。 密码分析者: 从事密码分析工作的人称作密码分析员或密码分析者(Cryptanalyst)。 Kerckholf假设：通常假定密码分析者或敌手（Opponent）知道所使用的密码系统，这个假设称为Kerckholf假设。版权所有，盗版必纠 根

7、据密钥的特点将密码体制分为对称密码体制(Symmetric Cryptosystem) 和非对称密码体制 (Asymmetric Cryptosystem）两种。 对称密码体制又称单钥(One-key) 或私钥（Private Key）或传统(Classical)密码体制。非对称密码体制又称双钥(Two-Key) 或公钥(Public Key)密码体制。 版权所有，盗版必纠 那么，什么样的密码体制是安全的呢？有一种理想的加密方案，叫做一次一密密码（One-Time Pad），它是由Major Joseph Mauborgne和AT&T公司的Gilbert Vernam在1917年发明的。一次一

8、密的密码本是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并一起粘成一个密码本。 版权所有，盗版必纠 根据密码分析者破译时已具备的前提条件，通常人们将攻击类型分为4种。 1. 唯密文攻击(Ciphertext-only Attack)：密码分析者有一个或更多的用同一密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥。 2. 已知明文攻击(Known Plaintext Attack)：除待解的密文外，密码分析者有一些明文和用同一个密钥加密这些明文所对应的密文。 3. 选择明文攻击(Chosen Plaintext Attack)：密码分析者可以得到所需要的任何明文所对

9、应的密文，这些明文与待解的密文是用同一密钥加密得来的。 4. 选择密文攻击(Chosen Ciphertext Attack)：密码分析者可得到所需要的任何密文所对应的明文（这些明文可能是不大明了的），解密这些密文所使用的密钥与解密待解的密文的密钥是一样的。 版权所有，盗版必纠 密码技术是保护信息安全的主要手段之一。密码学通常用来保证安全的通信。希望通过安全通信来获得以下4个特性: (1) 保密性：只有应该收到的接收者能够解密码，其他人拿到文件也无法获得里面的信息。 (2) 完整性: 接收者可以确定信息在传送的过程中有无更改。 (3) 认证性: 接收者可以认出发送者，也可以证明声称的发送者确实

10、是真正的发送者。 (4) 不可抵赖性：发送者无法抵赖曾经送出这个信息。 版权所有，盗版必纠 w 版权所有，盗版必纠 代替密码（Substitution Cipher)又叫替换密码，就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。典型的代替密码是凯撒密码。 凯撒密码是一个古老的加密方法，当年凯撒大帝行军打仗时用这种方法进行通信，因此得名。它的原理很简单，其实就是单字母的替换。让看一个简单的例子：“This is Caesar Code”。用凯撒密码加密后字符串变为“vjku ku Ecguct Eqfg”。看起来似乎加密得很“安全”。可是只要把这段很难懂

11、的东西每一个字母换为字母表中前移2位的字母，结果就出来了。版权所有，盗版必纠 图3.5 字母的频度表版权所有，盗版必纠 置换密码(Permutation Cipher)又称换位密码（Transposition Cipher)即明文的字母保持相同，但顺序被打乱了。 在这种密码中最简单的是栅栏技术，在该密码中以对角线顺序写下明文，并以行的顺序读出。例如，为了用深度2的栅栏密码加密明文消息“meet me after the toga party”，写出如下形式： M e m a t r h t g p r y E t e f e t e o a a t 被加密后的消息是：MEMATRHTGPRYE

12、TEFETEOAAT。版权所有，盗版必纠 所谓对称算法就是指加密和解密过程均采用同一把密钥。如DES、3DES、AES等算法都属于对称算法。图3.6所示为对称密码算法的原理图。 对称算法所采用的基本技术大都是替换、置换和移位。比较典型的是DES、3DES、AES等算法。下面对有代表性的算法DES和3DES加以介绍。版权所有，盗版必纠 对称密码算法版权所有，盗版必纠 DES加密算法（Data Encryption Standard，数据加密标准）是美国经长时间征集和筛选后，于1977年由美国国家标准局颁布的一种加密算法。它主要用于民用敏感信息的加密，后来被国际标准化组织接收作为国际标准。 DES

13、主要采用替换和移位的方法加密。它用56位密钥对64位二进制数据块进行加密，每次加密可对64位的输入数据进行16轮编码，经一系列替换和移位后，输入的64位原始数据转换成完全不同的64位输出数据。版权所有，盗版必纠 DES算法仅使用最大为64位的标准算术和逻辑运算，运算速度快，密钥生产容易，适合于在当前大多数计算机上用软件方法实现，也适合于在专用芯片上实现。图3.7所示为DES算法的流程图。版权所有，盗版必纠 DES加密算法版权所有，盗版必纠 DES算法的弱点是不能提供足够的安全性，因为其密钥容量只有56位。由于这个原因，后来又提出了三重DES即3DES算法，使用3个不同的密钥对数据块进行（2次或

14、）3次加密，该方法比进行3次普通加密快。其强度大约和112比特的密钥强度相当。 这种方法用两个密钥对明文进行3次运算。设两个密钥是K1和K2，其算法的步骤如图3.8所示。版权所有，盗版必纠 3DES算法版权所有，盗版必纠 所谓非对称算法就是指加密和解密用的不是同一个密钥。非对称算法的密钥分为二部分，通常称为“公钥”和“私钥”（或者称为“公开密钥”和“秘密密钥”）。公钥和私钥存在数学上的关系，使得用公钥加密的数据只能用对应的私钥解密，用私钥加密的数据只能用对应的公钥解密。但是从公钥中推导出私钥是很难的（理论上是可以推导出来的，但是实际上找不到这么强的计算能力）。RSA、DSA、ECC(椭圆曲线加

15、密算法)等算法属于非对称算法。图3.9为对称加密算法示意图。版权所有，盗版必纠 所谓非对称算法版权所有，盗版必纠 下面以RSA算法为例，介绍非对称加密算法。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从1978年提出到现在已近30年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。通常认为破译RSA的难度与大数分解难度相当。RSA特别适用于通过因特网传送的数据。这种算法以它的3位发明者的名字命名：RonRivest、AdiShamir和LeonardAdleman。 RSA算法的安全性基于分解大数字时的困难（就

16、计算机处理能力和处理时间而言）。在常用的公钥算法中，RSA与众不同，它能够进行数字签名和密钥交换运算。 版权所有，盗版必纠 RSA算法既能用于数据加密，也能用于数字签名，RSA的理论依据为：寻找两个大素数比较简单，而将它们的乘积分解开则异常困难。在RSA算法中，包含加密密钥和解密密钥两个密钥，加密密钥是公开的。 RSA算法的优点是密钥空间大，缺点是加密速度慢，如果RSA和DES结合使用，则可弥补这个缺点。即将DES用于明文加密，RSA用于DES密钥的加密。由于DES加密速度快，适合加密较长的报文，而RSA可解决DES密钥分配的问题。RSA算法的原理如下。版权所有，盗版必纠1、密钥对的产生、密钥

17、对的产生选择两个大素数p 和q ，计算： n = pq。然后随机选择加密密钥e，要求 e 和 ( p - 1 )( q - 1 ) 互质。最后，利用Euclid 算法计算解密密钥d，使其满足:ed = 1 ( mod ( p - 1 )( q - 1 ) )其中n和d要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。 2、加密、加密加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,., mi ，块长s，其中 2s = n, s 尽可能大。加密的公式是：ci = mie ( mod n ) 3、解密、解密解密时作如下计算：mi = cid (

18、 mod n )版权所有，盗版必纠 1、选择两个素数p=7,q=17 2、计算机n=pXq=7X17=119 3、计算(n)=(p-1)(q-1)=96 4、选择一个e,它小于(n)且与(n)=96互素。这里 e=5 5、求出d,使得de=1 mod 96, 既5d=1 mod 96,且 d96 此处的取值是d=77,因为77*5=385=4*96+1 6、得到的密钥为：公钥KU=5，119，密钥KR=77，119 二 对明文的加密与解密 1、发送方输入明文M=19 2、在使用公钥KU=15，119加密时，求19的5次方得 2476099版权所有，盗版必纠 3、将19的5次方除以119后，计算

19、得到的余数为66， 既195 66 mod 119,密文为66 4、发送密文66 5、接收方使用密钥KR=77，119解密时，明文由 6677 19 mod 119 所确定。接收方解密后得到发送方明文M=19。版权所有，盗版必纠 Hash算法，也称为单向散列函数、杂凑函数、哈希算法、散列算法或消息摘要算法。它通过把一个单向数学函数应用于数据，将任意长度的一块数据转换为一个定长的、不可逆转的数据。这段数据通常叫做消息摘要（比如，对一个几兆字节的文件应用散列算法，得到一个128位的消息摘要）。消息摘要代表了原始数据的特征，当原始数据发生改变时，重新生成的消息摘要也会随之变化，即使原始数据的变化非常

20、小，也可以引起消息摘要的很大变化。因此，消息摘要算法可以敏感地检测到数据是否被篡改。消息摘要算法再结合其他的算法就可以用来保护数据的完整性。Hash算法处理流程如图3.10所示。 版权所有，盗版必纠 Hash算法版权所有，盗版必纠好的单向散列函数必须具有以下特性。 1. 1. 计算的单向性计算的单向性 给定M和H，求hH(M)容易，但反过来给定h和H，求MH-1(h)在计算上是不可行的。 2. 2. 弱碰撞自由弱碰撞自由 给定M，要寻找另一信息 M，满足 H(M)H(M)在计算上不可行。 3. 3. 强碰撞自由强碰撞自由 要寻找不同的信息M 和M，满足 H(M)H(M)在计算上不可行。版权所有

21、，盗版必纠 单向散列函数的使用方法为：用散列函数对数据生成散列值并保存，以后每次使用时都对数据使用相同的散列函数进行散列，如果得到的值与保存的散列值相等，则认为数据未被修改(数据完整性验证)或两次所散列的原始数据相同(口令验证)。 典型的散列函数有：MD4、MD5、SHA-1、HMAC、GOST等。单向散列函数主要用在一些只需加密不需解密的场合：如验证数据的完整性、口令表的加密、数字签名、身份认证等。表3.1列出了MD4、MD5、SHA算法在一些属性上的比较。 版权所有，盗版必纠 1. MD5算法简介算法简介 MD5即Message-Digest Algorithm 5（信息-摘要算法5），是

22、一种用于产生数字签名的单项散列算法，在1991年由MIT计算机科学实验室（MIT Laboratory for Computer Science）和RSA数据安全公司（RSA Data Security Inc）的Ronald L. Rivest教授开发出来，经由MD2、MD3和MD4发展而来。 版权所有，盗版必纠 2004年，山东大学王小云教授攻破了MD5算法，引起密码学界的轩然大波。MD5在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来，经MD2、MD3和MD4发展而来

23、。 2004年8月17日的美国加州圣巴巴拉召开的国际密码学会议（Crypto2004）安排了3场关于杂凑函数的特别报告。在国际著名密码学家Eli Biham和Antoine Joux相继做了对SHA-1的分析与给出SHA-0的一个碰撞之后，来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。王小云教授的报告轰动了全场，得到了与会专家的赞叹。 不久，密码学家Lenstra利用王小云提供的MD5碰撞，伪造了符合X.509标准的数字证书，这就说明了MD5的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击，MD5的撤出迫在眉睫。版权所有，盗版必纠 密码技术

24、是信息安全的核心技术，无处不在，目前已经渗透到大部分安全产品之中，正向芯片化方向发展。在芯片设计制造方面，目前微电子水平已经发展到0.1um工艺以下，芯片设计的水平很高。 我国在密码专用芯片领域的研究起步落后于国外，近年来我国集成电路产业技术的创新和自我开发能力得到了提高，微电子工业得到了发展，从而推动了密码专用芯片的发展。加快密码专用芯片的研制将会推动我国信息安全系统的完善。版权所有，盗版必纠 量子技术在密码学上的应用分为两类：一是利用量子计算机对传统密码体制的分析；二是利用单光子的测不准原理在光纤级实现密钥管理和信息加密，即量子密码学。量子计算机是一种传统意义上的超大规模并行计算系统，利用

25、量子计算机可以在几秒钟内分解RSA129的公钥。版权所有，盗版必纠 近年来，人们在研究生物遗传的同时，也发现DNA可以用于遗传学以外的其他领域，如信息科学领域。1994年，Adleman等科学家进行了世界上首次DNA计算，解决了一个7节点有向汉密尔顿回路问题。此后，有关DNA计算的研究不断深入，获得的计算能力也不断增强。2002年，Adleman用DNA计算机解决了一个有20个变量、24个子句、100万种可能的3-STA问题，这是一个NP完全问题。研究DNA计算的科学家发现，DNA具有超大规模并行性、超高容量的存储密度以及超低的能量消耗，非常适用于信息领域。利用DNA，人们有可能生产出新型的超

26、级计算机，它们具有前所未有的超大规模并行计算能力，其并行性远超过现有的电子计算机。这将会给人们带来惊人的计算能力，引发一场新的信息革命。DNA计算的先驱Adleman这样评价DNA计算，“几千年来，人们一直使用各种设备提高自己的计算能力。但是只有在电子计算机出现以后，人们的计算能力才有了质的飞跃。现在，分子设备的使用使得人类的计算能力能够获得第二次飞跃”。 版权所有，盗版必纠 在现在密码系统中，密钥是随机独立选取的，而超大规模并行计算机非常适用于对密钥穷举搜索。Dan Boneh等人用DNA计算机破译了DES，并且声称任何小于64位的密钥都可以用这种方法破译。Salomaa也宣称现有的很多数学困难问题可以通过DNA计算机进行穷举搜索得到结果，而期中很多困难问题都是现代密码系统的安全依据。人们不禁要问，密码学的大厦将会因为DNA计算的出现而倾覆吗？随着DNA计算的发展，有科学家开始把DNA用于密码学领域。Reif等人提出用DNA实现一次一密的密码系统，Celland等人提出用DNA隐藏消息。 版权所有，盗版必纠 这里主要给大家讲述了密码学基础。 欢迎大家提问？版权所有，盗版必纠返回