第2章密码技术介绍课件

《第2章密码技术介绍课件》由会员分享，可在线阅读，更多相关《第2章密码技术介绍课件（85页珍藏版）》请在金锄头文库上搜索。

1、密 码 技 术介绍,1.1 引 言,经典密码：古埃及人用以保密传递的消息； 单表置换密码，凯撒密码， 多表置换密码，Vigenere密码等等 近代密码：DES数据加密标准，70年代Diffie,Hellman 的开创性工作公钥体制的提出 密码应用：电子数据，军事目的，经济目的。 应用形式：数据的保密性、真实性、完整性。 主要内容：数据加密，密码分析，数字签名，信息 鉴别，零泄密认证，秘密共享等等。 信息攻击：主动攻击对数据的恶意删除、篡改等 被动攻击从信道上截取、偷窃、拷贝 信息。 无意攻击错误操作、机器故障等。,1.2 密 码 体 制,基本术语：信源消息的发送处 信宿消息的目的地 明文没有加

2、密的消息 密文加密后的消息 信道传递消息的通道 通信模型：经典的通信模型如图所示：,密码体制：可能的明文集合P称为明文空间 可能的密文集合C称为密文空间 可能的密钥集合K称为密钥空间 一组加密变换： 一组解密变换： 满足： 则五元组（P，C，K，Ek，Dk）称为一个密码体制。 基本要求：(1)对所有密钥，加、解密算法迅速有效, (2)体制的安全性不依赖于算法的保密， 只依赖于密钥的保密Kerchohoff原则。,经典的密码体制中，加密密钥与解密密钥是相同的，或者可以简单相互推导，也就是说：知道了加密密钥，也就知道了解密密钥；知道了解密密钥，也就知道了加密密钥。所以，加、解密密钥必须同时保密。这

3、种密码体制称为对称（也称单钥）密码体制。最典型的是DES数据加密标准，应该说数据加密标准DES是单钥体制的最成功的例子。,现代密码学修正了密钥的对称性，1976年，Diffie，Hellmann提出了公开密钥密码体制（简称公钥体制），它的加密、解密密钥是不同的，也是不能（在有效的时间内）相互推导。所以，它可称为双钥密码体制。它的产生，是密码学革命性的发展，它一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈密钥的分配问题。,第一个公钥体制是1977年由Rivest，Shamir，Adleman提出的，称为RSA公钥体制，其安全性是基于整数的因子分解

4、的困难性。RSA公钥体制已得到了广泛的应用。其后，诸如基于背包问题的Merkle-Hellman背包公钥体制，基于有限域上离散对数问题的EIGamal公钥体制，基于椭圆曲线的密码体制等等公钥体制不断出现，使密码学得到了蓬勃的发展，,公钥体制用于数据加密时： 用户将自己的公开（加密）密钥登记在一个公开密钥库或实时公开，秘密密钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥解密密文，从而，读取信息。可见，这里省去了从秘密信道传递密钥的过程。这是公钥体

5、制的一大优点。,E(m),Kb1,A,Ka1,B,D(E(m),Kb2,m,m,RSA的加解密过程,公开信道,公钥体制用于数字签名时： 信源为了他人能够验证自己发送的消息确实来自本人，他将自己的秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密称为签名，将原消息与签名后的消息一起发送. 对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息称为（签名）验证，如果解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。,1.3 密 码 分 析,方法分类：穷举法、统计法、系统分析法 穷举法对可能的密钥或明文的穷举； 统计法根据

6、明文、密文、密钥的统计 特性达到破译密码的方法； 系统分析法根据掌握的明文、密文的 有关信息，应用加、解密算法求解密钥、明文的方法。,计算安全性： 理论上，除一文一密外，没有绝对安全的密码体制，通常，称一个密码体制是安全的是指计算上安全的， 即：密码分析者为了破译密码，穷尽其时间、存储资源仍不可得，或破译所耗资材已超出因破译而获得的获益。,1、唯密文攻击：仅根据密文进行的密码攻击； 2、已知明文攻击：根据一些相应的明、密文对进行的密码攻击。 3、选择明文攻击：可以选择一些明文，并获取相应的密文，这是密码分析者最理想的情形。例如，在公钥体制中。,根据密码分析者掌握明、 密文的程度密码分析可分类为

7、：,1.4 数 字 签 名,数字签名最早被建议用来对禁止核试验条律的验证。禁止核试验条律的缔约国为了检测对方的核试验，需要把地震测试仪放在对方的地下，而把测试的数据送回，自然这里有一个矛盾：东道主需要检查发送的数据是否仅为所需测试的数据；检测方需要送回的数据是真实的检测数据，东道主没有篡改。,基本要求： 1、签名不能伪造：签名是签名者对文件内容合法性的认同、证明、和标记，其他人的签名无效； 2、签名不可抵赖：这是对签名者的约束，签名者的认同、证明、标记是不可否认的； 3、签名不可改变：文件签名后是不可改变的，这保证了签名的真实性、可靠性； 4、签名不可重复使用：签名需要时间标记，这样可以保证签

8、名不可重复使用。 5、签名容易验证：对于签名的文件，一旦发生纠纷，任何第三方都可以准确、有效地进行验证。,数字签名的基本原理：应用一对不可互相推导的密钥， 一个用于签名（加密），一个用于验证（解密），颠倒使用加解密过程。 公钥签名原理：这种签名就是加密过程的简单颠倒使用，签名者用加密密钥（保密）签名（加密）文件，验证者用（公开的）解密密钥解密文件，确定文件的真伪。,散列函数：散列函数是数字签名的一个重要辅助工具， 应用散列函数可以生成一个文件的，具有固定长度的 文件摘要，从而使数字签名可以迅速有效地签名一个 任意长度的文件。一般地，对文件的任意小改动，都 会改变文件的散列值，从而，秘密的散列函

9、数可以用 来检测病毒等对文件的破坏。 对签名的攻击：对数字签名有各种各样的欺骗存在， 重复使用是一个典型欺骗，如电子支票，重复的使用 具有可怕后果，阻止这种欺骗的有效方法是签名中包 含时间日期标志。,计算复杂性理论,加密算法，解密算法所需的计算量是密码算法运行效率的一个重要指标，而密码分析所需的计算量则是密码体制安全性的生命指标。理论上来说，除一次一密的密码体制外，没有绝对安全的密码体制，所谓一个密码体制是安全的都是指计算上是安全的。,如果用n表示问题的大小，则计算复杂性可用两个参数来表示，即：运算所需的时间和存储空间，它们都是n的函数，记为：T(n), S(n)。 如果T(n)=O(nc)，

10、则称该算法是多项式阶的，如果T(n)=O(cp(n) ，则称算法是指数阶的，其中P(n)是n的一个多项式（非常数）。对于指数阶的算法，适当增大n，算法都是计算上不可能的。从而，如果破译一个密码体制所需的时间是指数阶的，则它是计算上安全的。,空间复杂性与时间复杂性是可以相互转换的。例如，如果密钥空间的大小为n=2l，l为密钥的长度，则时间为：T=O(n)=O(2l)。 算法可分为确定性算法和非确定性算法，确定性算法的每一步的操作结果都是确定的，其计算时间就是完成这些确定步骤所需的时间。不确定性算法的某些操作结果是不确定的，使算法成功的操作序列中，所需时间最少的序列所需时间就是该不确定性算法的计算

11、时间。,用确定性算法可以在多项式时间内求解的问题称为P问题。在多项式时间内可以用非确定性算法求解的问题称为NP问题。显然NP问题包含P问题，但是，P问题是否包含NP问题，不得而知。PNP仍然是一个开问题。,如果问题G可以在多项式时间内用确定性算法转化为问题L，而L的解可在多项式时间内用确定性算法转化为G的解，则称问题G可归约为问题L。 如果某类NP问题中的任何一个问题都可归约为问题L，且L本身也是NP问题，则称L是一个NP完全问题。,对于一个NP问题，我们知道，不存在任何已知的确定性算法在多项式时间内求解该问题，所以，如果我们找到一个计算序列，作为解密算法，那么，密码分析者在不知道计算序列的情

12、形下求解问题称为客观求解成为计算上不可能的了。可见，NP问题可以用来构造密码体制。Diffie，Hellman指出，NP完全问题更适合于构造密码体制。,现已证明，正整数的因数分解问题是一个NP问题。对于一个正整数N，已知的最快的客观算法的算术次数是： elnnlnlnn。 同样，背包问题也是NP问题。,数据加密标准DES及IDEA,1973.5.15： 美国国家标准局（NSA）公开征求密码体制的联邦注册； 1975.3.17：DES首次在联邦记事公开，它由IBM开发，它是LUCIFER的改进； 1977.2.15：DES被采用作为非国家机关使用的数据加密标准，此后，大约每五年对DES进行依次审

13、查，1992年是最后一次审查，美国政府已声明，1998年后对DES不再审查了； 1977.2.15：联邦信息处理标准版46（FIPS PUB46）给出了DES的完整描述。,2.2 DES加密标准,DES密码体制：它是应用56位密钥，加密64比特明文分组的分组秘钥密码体制 DES加密算法：（一）初始置换：x0=L0R0=IP(x)；（二）16次迭代：xi-1=Li-1Ri-1， Li=Ri，Ri=Li f(Ri-1,ki) i=1,2,16；（三）逆置换：x16=L16R16，y=IP-1(x16)。 密钥生成器：密钥ki是由56位系统密钥k生成的32位子密钥。 函数f及S盒：f(Ri-1,ki

14、)=P(S(E(Ri-1)ki),其中E，P是两个置换， 表示比特的“异或”，S是一组八个变换S1，S2，S3， ，S8 ，称为S盒，每个盒以6位输入，4位输出，S盒构成了DES 安全的核心。 DES算法流程图,函数f及S盒的示意图,DES解密：DES的解密过程与加密过程相同，只不过子密钥的使用相反，即，首先使用k16，再使用k15， ，最后使用k1。,2.3 关于DES的讨论,S盒是唯一非线性组件：有人认为其中可能含有某种“陷门”，国家安全机关可以解密。 DES的密钥量太小：密钥量为256 1977年：Diffie.Hellman提出制造一个每秒测试106的VLSI芯片，则一天就可以搜索完整

15、个密钥空间，当时造价2千万美圆。 CRYPTO93：R.Session，M.Wiener提出并行密钥搜索芯片，每秒测试5x107个密钥，5760片这种芯片，造价10万美圆，平均一天即可找到密钥。,Internet的超级计算能力：1997年1月28日，美国RSA数据安全公司在Internet上开展了一项“秘密密钥挑战”的竞赛，悬赏一万美圆，破解一段DES密文。计划公布后，得到了许多网络用户的强力相应。科罗拉州的程序员R.Verser设计了一个可以通过互联网分段运行的密钥搜索程序，组织了一个称为DESCHALL的搜索行动，成千上万的的志愿者加入到计划中。,第96天，即竞赛公布后的第140天，199

16、7年6月17日晚上10点39分，美国盐湖城Inetz公司职员M.Sanders成功地找到了密钥，解密出明文：The unknown Message is：“Stronge cryptography makes the word a safer place”(高强度密码技术使世界更安全)。 Internet仅仅利用闲散资源，毫无代价就破译了DES密码，这是对密码方法的挑战，是Internet超级计算能力的显示.,差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著名的有Biham，Shamir的差分分析法。这是一个选择明文攻击方法。虽然对16轮DES没有攻破，但是，如果迭代的轮数降低，则它可成功地被攻破。例如，8轮DES在一个个人计算机上只需要2分钟即可被攻破。,2.4 IDEA,IDEA(Interna